#kvrocks
# redis数据结构编码
## String
- 存储在 metadata cf。
### Key
| ns size | ns | slot | user key |
| ------- | ------- | ------ | -------- |
| 1 byte | N bytes | 2 byte | N bytes |
- **ns size**: namespace 长度
- **ns**: namespace 数据
- **slot** 仅在 cluster 特性启用后编码
- 示例：`SET foo bar`
- key编码后为 `\v__namespacefoo
- `\v`：11 的 ASCII 码，表示 ns 长度为 11
- `__namespace`：默认 ns
- `foo`：user key
### Value
| flag | expire | user value |
| ------ | ------ | ---------- |
| 1 byte | 8 byte | N bytes |
- **flag**：
- 包含了 encoding version 和 redis type
- encoding version：为 1 时表示新版本，expire 使用 8 字节（旧版本 4 字节）
- redis type：数据结构的类型枚举，如 string/hash 等
| encoding version | reserved | redis type |
| ---------------- | -------- | ---------- |
| 1 bit | 3 bit | 4 bit |
- **expire**：
- 过期的绝对时间，单位 ms
- 大端编码，固定 64 字节
- flag + expire 对应 MetaData
## Hash
- hash 的编码分为两部分：
- metadata：包含 field 数量、过期时间等元数据，一个 kv 存储在 metadata cf
- fields：每个 field 对应一个 kv，存储在 default cf
### Metadata
- **key**：hash key，编码方式同 String
- **value**：hash metadata
| flag | expire | version | size |
| ------ | ------ | ------- | ------ |
| 1 byte | 8 byte | 8 byte | 8 byte |
- flag 和 expire 编码同 String 类型
- **version**：每次创建 hash 结构时生成新的版本
- 高 53 bits 取当前时间的毫秒数
- 低 11 bits 取自增 couter
- counter 启动时设为一个随机值，减少时钟回退时可能引发的版本冲突
- **size**：fields 的数量
### Field
- field key：
- 前半部分跟 metadata key 编码接近（除了加了 key size，因为后面还有其他数据）
- version 用于关联所属的 metadata
| ns size | ns data | slot | key size | key data | version | field key |
| ------- | ------- | ------ | -------- | -------- | ------- | --------- |
| 1 byte | N bytes | 2 byte | 4 byte | N bytes | 8 byte | N bytes |
- field value：无编码，直接存入
> [!summary] version
> 使用 version 表示不同生命期的 hash，用于关联同一个生命期 hash 的 metadata 和 fields。
> 用于实现快速删除：
> - 删除 hash 时只删除 metadata key，fields 通过 compaction filter 删除；
> - compaction filter 中发现跟 field 相同 version 的 metadata 过期或者不存在时则可以回收；
>
## Set
- 整体与 hash 相同，除了 field value 为空。
## List
- 类似 hash，区分 metadata 和 elements（存放在 default cf）。
- 使用数组模拟 list，每个 node 分配一个整型 index 编号，相邻 node 之间 index 连续。
### metadata
- metadata key 跟其他结构相同。
- metadata value：增加了 list 专属的 head 和 tail 元数据
- head 和 tail 为整型，元素节点的编号（index），链表数据不包含 tail。
- 节点编号的分配：
- list 上的节点编码代表了前后关系，且是连续的
- head 和 tail 初始值为 UINT64_MAX / 2
- lpush 时新节点编号为 head - 1，同时更新 head
- rpush 时新节点编号为 tail，同时 tail 自增
| flag | expire | version | size | head | tail |
| ------ | ------ | ------- | ------ | ------ | ------ |
| 1 byte | 8 byte | 8 byte | 8 byte | 8 byte | 8 byte |
### nodes
- 与 hash field 相同，使用节点编号作为 field key
- node key：
| ns size | ns data | slot | key size | key data | version | index |
| ------- | ------- | ------ | -------- | -------- | ------- | ------ |
| 1 byte | N bytes | 2 byte | 4 byte | N bytes | 8 byte | 8 byte |
> [!summary] node index
> node index 的大小代表了在链表上的前后位置，且连续
> - 优势：
> - 遍历如 LRANGE 性能较好，顺序扫描
> - 按 index 读写单节点性能最优
> - LINDEX 可实现为 Get 操作，Get(head + index)
> - LSET 可实现为一个 Put 操作
> - 每个 node 上不用额外存储前驱和后驱，空间较优
> - 劣势：
> - 修改如增删中间节点时需要维护连续性，可能重写前后所有节点，
> - 例如 LREM/LINSERT 操作可能涉及移动、重写大量节点
> [!question]
> 三者性能的均衡：LRANGE，LINDEX，LREM 以及空间
> 是否可以牺牲 index 的连续性（会牺牲 LINDEX 性能），只保证顺序性，来减少修改时的维护代价
## Zset
- 分为三部分：
1. metadata： 编码与 hash 相同，存放在 metadata cf。
2. member：每元素一个 kv，存放在 default cf
3. score：每元素一个 kv，存放在 zset_score cf
### member
- member key ：同 hash field 的编码相同
- member value：存放 score
- double 先转 uint64 再存储
### score
- score key：类似 hash field，相当于把 field key 换成 score + member_key
| ns size | ns data | slot | key size | key data | version | score | member |
| ------- | ------- | ------ | -------- | -------- | ------- | ------ | ------- |
| 1 byte | N bytes | 2 byte | 4 byte | N bytes | 8 byte | 8 byte | N bytes |
- score value：空
---
# 总结
> [!summary] Metadata
> 每种数据结构都有一条 metadata KV entry：
> - 所有数据结构 metadata key 编码都一样；
> - metadata value 统一编码了 flags 和 expire 信息；
> - String 类型直接将 value 编码在 metadata value 中；
> - 集合类的 metadata value 中还编码了 version、size；
> - list 额外编码了 head 和 tail；
>
> metadata 和集合数据分离到不同 cf：
> - 访问 metadata 的效率变高（数据量小），许多命令只需要访问 metadata
>
---
# TODO
- [ ] hyperloglog
- [ ] bitmap