数据模型

etcd 设计用于可靠存储不频繁更新的数据,并提供可靠的观察查询。etcd 暴露键值对的先前版本来支持不昂贵的快速和观察历史事件(“time travel queries”)。对于这些使用场景,持久化,多版本,并发控制的数据模型是非常适合的。

ectd 使用多版本持久化键值存储来存储数据。当键值对的值被新的数据替代时,持久化键值存储保存先前版本的键值对。键值存储事实上是不可变的;它的操作不会就地更新结构,替代的是总是生成一个新的更新后的结构。在修改之后,key的所有先前版本还是可以访问和观察的。为了防止随着时间的过去为了维护老版本导致数据存储无限增长,存储应该压缩来脱离被替代的数据的最旧的版本。

逻辑视图

存储的逻辑视图是一个扁平的二进制键空间。键空间有一个在 byte string 键上的语义排序的索引,因此范围查询不是太昂贵。

键空间维护多个版本。每个原子变化操作(类如,一个事务操作可能包含多个操作)在键空间上创建一个新的修订版本。先前版本持有的所有数据保持不变。key 的旧有版本还可以通过先前修订版本访问。同样的,修订版本也是被索引的;在修订版本上搜索(带观察者)是高效的。一旦存储被压缩来恢复空间,在压缩修订版本之前的修订版本被移除。

key的生命周期跨越一代(spans a generation)。每个 key 可以有一代或者多代。创建 key 增加了 key 的代,如果 key 从未存在则从 1 开始。删除一个 key 产生一个 key 的墓碑,结束 key 的当前时代。key 的每次改动创建 key 的一个新的版本。一旦压缩发生,任何在给定修订版本之前结束的时代将被删除,而在压缩修订版本之前设置的值,除最后一个外,都将被移除。

物理视图

etcd 以持久性 b+tree 键值对的方式存储物理数据。存储的状态的每个修订版本仅仅包含和它的前一个修订版本的增量以求高效。单个修订版本可能对应到 tree 上的多个 key。

键值对的 key 是三元数组(major, sub, type)。Major 是持有 key 的存储修订版本。Sub 区分同一个修订版本的不同key。Type是用于特别值(例如,t,如果值包含一个墓碑)的可选后缀。键值对的值包含对前一个修订版本的改动,例如对前一个修订版本的增量。b+tree 以 key 的词典字节顺序排序。在修订版本增量上的延伸查找(Ranged lookups)很快。这样可以快速发送从一个特定修订版本到另一个的改变。压缩删除过期的键值对。

etcd 也保持内存中的第二 btree 索引来加速 key 的范围查询。在 btree 索引中的 key 是存储暴露给用户的 key。值是到持久化 b+tree 修改的指针。压缩删除死指针。