·  List 结构 data_key 和 data_value 的落盘方式

data_key 由三个部分组成：编码 Key 、 4 Bytes 的版本号 Version 和 8 Bytes 的该节点的底层索引。 data_value 就是该列表元素对应的 Value 。

4. Set 结构的存储

Set 结构的元数据中储存了 集合 的大小、版本号和过期时间，每个集合的 member 储存为普通数据。

· Set 结构 meta_key 和 meta_value 的落盘方式

• 

• meta_key 就是 Set 结构的 Key 本身，meta_value则包含 3 个部分： 4 Bytes 的 Set Size （当前集合的 member 数量）、 4 Bytes 的版本号 Version 、 4 Bytes 的有效时间戳 timestamp 。
  
  
  · Set 结构 data_key 和 data_value 的落盘方式

data_key 由三个部分组成：编码 Key 、 4 Bytes 的版本号 Version 和该条记录中 Member 的内容。集合只需要记录 member ，data_value 目前为 空串 。

5. ZSet 结构的存储

data_key 由三个部分组成：编码 Key 、 4 Bytes 的版本号 Version 和该条记录中 Member 的内容。 与Set 不同， 可以在 data_value 中储存该 Member 对应的 Value 。

由于 RocksDB 默认按照 字节序 排序，因此这样排布后，同一 Key 下的所有记录的开头部分均相同，必定是按照 Member 排序的。

·  Zset 结构中描述 ZsetScoreKey 的 data_key 和 data_value 的落盘方式

data_key 由四个部分组成：编码 Key 、 4 Bytes 的版本号 Version 、该条记录的 Score 以及 Member 。由于 data_key 中储存了所有的信息，因此这里的 data_value 依然为空。

针对 ZsetScoreKey ， Blackwidow 实现了它对应的 comparator ，同一个 Key 的 ZsetScoreKey 会先按照 Score 的大小排序，再按照 Member 排序。

为什么采取新的编码方案

Todis 编码方案的主要目的是使同一结构的 data_key 对应的 meta_key 也有序。
• RocksDB 默认按照字节序排序。在原版的 Blackwidow 编码方案中， meta_key 就是原始 key ，而 data_key 总是以 key_size + key 的方式开头，因此 meta_key 是按 key 排序的， data_key 是以 key_size 为第一关键字， key 为第二关键字排序的。 data_key 和 meta_key 的对应关系是混乱的：



采用了新的编码方案后，由于编码 Key 和原始 Key 有一致的字节序，因此 data_key 对应的 meta_key 是有序的。





• · 原版编码方案对于 Todis 的缺陷


在编码方案介绍中，我们提到过，过期的数据（ timestamp 非 0 且小于当前时间）和无效的数据（ data_key 中的 version 低于 meta_key 中的 version ）是在 compact 的过程中被清理的。这可以通过自定义的 rocksdb::CompactionFilter 接口来实现。而在原版的 Pika 中，相关的 代码逻辑如下。


// 仅保留了主要逻辑， BaseData 可以用于构建 Hash 、 Set 、 ZsetMemberKey 的 data_keyBaseDataFilter::Filter(data_key, data_value) {
    [meta_key, data_version] = parse_data_key(data_key);
    [meta_version, meta_timestamp] = parse_meta_value(get_from_meta_cf(meta_key));
    if (meta_timestamp && meta_timestamp < curr_time)
      return true;
    if (meta_version > data_version)
      return true;
    return false;
}


可以看到，作为筛选条件的 meta_timestamp 和 meta_version 都储存在元数据中，必须先在 RocksDB 中查询 meta_value （get_from_meta_cf） 。对于原版 Pika 而言，data_key 对应的 meta_key 无序并不是什么大问题，最多也就是慢一点，但是对于 Todis就无法接受了：

Todis 的设计目标之一是 存储计算分离 ， 储存数据  和  执行分布式 compact  的不是同一个节点， 没法直接拿到 meta_value 


直接走 远程调用 ？每次 get_from_meta_cf 走一个网络来回，得慢到什么程度？费力不讨好......

把所有的  meta_data  直接发给分布式 compact 节点？理论上可以，但实际数据量大到无法负担......
把 CompactionJob 中需要用到的 meta_data 提前找出来，一起发给 compact 节点？不是不可以，但有这个时间，在本地跑 compact 都结束了......
• 以上因素促使我们设计了新的编码方式。在 meta_key 和 data_key 拥有一致的有序性后，对于每一个 CompactionJob ，我们可以快速找到所有需要用到的 meta_data ，发送给执行 compact 的
远端节点
• 。（具体可以看
compaction_job.cc
• 中的 RunRemote ）与此同时，由于 compact 扫描的 key 与所要用到 meta_key 均有序，执行 compact 的节点不需要在发送的 meta_data 中进行二次搜索，直接进行两路
归并
• 即可。我们为它实现了对应的
WorkerBaseDataFilter
• 接口。


• comact dataCF 时，输入数据的 key 范围对应的 metaCF 中的数据，要提前捞出来放到
共享存储
• 上给 compact 结点使用，这样就要求我们只能从 metaCF 中拿
有用的数据
• ，不碰无用的数据，这种编码方式，就可以做到这一点。pika/blackwidow 自身的编码方式，做不到这一点。我们的架构跟你的这个猜测不同，我们是这样的：


丨 对data_key采用的新编码。这个会和meta_key顺序保持一致，依据是什么？
依据是，顺序保持一致只需要满足 谓词逻辑 ：对任意的  k1,k2 ，如果  k1 < k2 ，则  encode(k1) < encode(k2)。 （其中  <  的含义是 BytewiseCompare）
这很容推导出来，因为 encode 仅对 0 进行了转移（变成 00），如果 0 之前的部分不同，就提前得出比较结果了，0 本身，两者都一样，那就继续比较后续部分……
丨  把原先的key中的0变成两个，是为了识别到最后一个0处于 奇数 为并且相邻的为1，即认为是data_key结束吗？
是的，我们没有保存 key_size，所以就必须有某种方式来判断 key 结束，因为 0 变成了 00，所以 对 encode(key) 内容，如果我们看到当前字节是 0，下一个字节也必然是 0，如果不是 0，就意味着结束。我们用 01 做 结束标记，其实也可以用 02,03 ……