简单的来说，对于原版 Pika ， Blackwidow 的储存编码方案已经很优秀了；但可惜的是，对于 Todis 来说，原版储存编码方案存在一个致命的缺陷。我们不得不重新设计了现在的编码方式。
Todis 的储存编码方案
Todis 基本沿用了原版 Blackwidow 的编码方案：对于除 string 之外的数据类型，均拆解为元数据 (meta_key , meta_value) 和普通数据 (data_key , data_value) 。
区别在于：对于储存数据的 data_key ，原版编码方式采用了KeySize + KeyData来描述原始 key ，而 Todis 改为了双写原 key 的0x00，并以 0x00 0x01 表示终止（以下称"编码 Key"）。除了 data_key 里描述原始 key 的方式之外，其余部分与原版 Blackwidow 方案完全相同。
这样做的目的是什么呢？
1.Bytewise Comparable, 只有这样，才能使用 Topling 的 MemTab 和 SST
2.支持分布式 Compact，Todis 结点和 Compact 结点是互相独立的机器，这样的编码方案可以最小化数据传输（后面详细说明）
设计细节
0. 编码 key
举一个简单栗子： 假设我们现在要存的 key 是 "0102507" 。（注意这里是字节意义上的，即每个 byte 的值）
在原版 Blackwidow 中，这个 key 会被编码为 "00070102507" ， 前 4 字节 "0007" 是 KeySize ， 后面的 7 个字节 "0102507" 是原始的 key 。（这里忽略了实际编码中后续的 version / index / member 等要素）
而在 Todis 中，我们会首先双写原 key 的每一个 0 ， 变为 "0010025007" ；再在末尾加上终止符"01" ， 最终的编码为 "001002500701" 。
容易看出，将排序后的原始 Key 均改写为编码 Key 后，所有的 Key 仍然是有序的。
另一个额外的好处是更节省空间，因为 0 字节在 Redis 的 Key 中是极少出现的，因为绝大部分场景下，其 Key 都是 C 语言 string 格式（以 0 字节结尾，但不包括结尾的 0）。
1. String 结构的存储
String 本身就是一个 Key ，无需额外的 meta_data ，所有记录以普通数据的形式储存。
String 结构 data_key 和 data_value 的落盘方式
data_value 包含原始 Value 和 4 Bytes 的有效时间戳 timestamp 。timestamp 主要用于支持 Redis 的 expire 功能，若未设置超时时间，则 timestamp 的值为 0 。
大部分情况下， timestamp 储存与对应结构的元数据中， String 比较简单因而记录在普通数据中。
· String 结构的查询方式
在查询时，会首先解析末尾的有效时间戳 timestamp 。若获取的 timestamp 已经过期，则不会返回数据。过期数据会在 compact 时被一并清理。
2. Hash 结构的存储
哈希表的元数据储存了哈希表 Filed - Value 对的数量，版本号（创建时间戳）以及过期时间，普通数据则是该哈希表的每一对 Filed 和 Value 。
Hash 结构 meta_key 和 meta_value 的落盘方式
meta_key 就是 Hash 结构的 Key 本身，meta_value则包含 3 个部分： 4 Bytes 的 Hash Size （当前 Hash 表的元素数量）、 4 Bytes 的版本号 Version （创建时间戳，用于秒删）、 4 Bytes 的有效时间戳 timestamp 。
·
Hash 结构 data_key 和 data_value 的落盘方式
data_key 由三个部分组成：编码 Key 、 4 Bytes 的版本号 Version 和该条记录中 Field 的内容。 data_value 就是该 Field 对应的 Value 。
· Hash 结构的查询方式
查找过程中，首先会获取到该 Key 的 meta_value ，解析出有效时间戳 timestamp 和版本号 version 。当数据没有过期时，将对应的编码 key 、 version 和 field 拼成 data_key ，再进行一次查询。
timestamp 超时或是 version 无效的数据（data_key 中的 version 与 meta_key 的 version 不一致）会在 compact 的过程中被清理。
3. List 结构的存储
Blackwidow 底层以数组的形式储存 List 的每一个节点。除了 Value 之外，还为每一个元素创建了索引。Blackwidow 保证同一列表的所有节点的索引是连续的。
列表的元数据储存了该列表的大小、版本号、过期时间以及索引范围，普通数据则储存该列表的每一个元素和它的索引。
· List 结构 meta_key 和 meta_value 的落盘方式
meta_key 就是 List 结构的 Key 本身，meta_value则包含 5 个部分： 8 Bytes 的 List Size （当前列表的元素数量）、 4 Bytes 的版本号 Version 、 4 Bytes 的有效时间戳 timestamp 、 8 Bytes 的列表数组左边界 Left Index 和 8 Bytes 的列表数组右边界 Right Index 。
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 结构的存储
Zset 结构比较特殊，既需要支持按照 Score 排序，也需要支持按照 Member 排序，故 Zset 中的每一个数据都会在普通数据中被写两遍，我们分别将其称为 ZsetScoreKey 和 ZsetMemberKey 。这两种 Key 都储存了某一条 Score - Member 的全部信息，但 ZsetScoreKey 落盘后按 Score 排序，而 ZsetMemberKey 按 Member 排序。
Zset 的元数据中储存 Zset 的大小、版本号和过期时间。
· Zset 结构 meta_key 和 meta_value 的落盘方式
meta_key 就是 Zset 结构的 Key 本身，meta_value则包含 3 个部分： 4 Bytes 的 Zset Size （当前有序集合的元素数量）、 4 Bytes 的版本号 Version 、 4 Bytes 的有效时间戳 timestamp 。
· Zset 结构中描述ZsetMemberKey的 data_key 和 data_value 的落盘方式
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 编码方案的优点
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)returntrue;if(meta_version>data_version)returntrue;returnfalse;}
可以看到，作为筛选条件的 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 ……
原文作者：雷鹏
原文链接：https://www.zhihu.com/question/504604561/answer/2262293780
