什么是 MVCC

常见并发控制机制

1. 悲观锁：通过锁机制确保同一时刻只有一个事务可以对数据进行修改操作。常见的实现包括读写锁、互斥锁、两阶段锁等。悲观锁假设并发事务间很可能发生冲突，因此要求事务必须先获得锁才能执行修改。

   • 缺点：锁粒度较大，在高并发场景下可能导致大量事务阻塞，降低服务性能。

2. 乐观锁：与悲观锁相反，乐观锁假设数据冲突不常发生，允许所有事务同时尝试修改数据，并在提交时检查是否有冲突。

MVCC 机制的优点

• 基于多版本技术：MVCC 实现了一种乐观锁机制，它不会直接覆盖原有数据，而是为每次更新生成一个新的数据版本。

• 提高并发性：由于不需要等待锁释放，MVCC 支持更高的并发处理能力。

• 数据快照：读取数据时访问的是特定版本号的数据快照，避免了读写之间的相互干扰。

MVCC 工作机制

• 版本管理：每个数据项都有一个版本号，这是一个逻辑时间标记。每当数据被修改时，系统会创建一条新记录而不是覆盖原记录，新记录包含更新后的数据及递增的版本号。

• 读取操作：当你指定某个版本号读取数据时，实际上是在访问该版本号对应时间点的数据快照。

• 删除操作：删除数据时，实际上是添加一条带有删除标识的新记录，而非立即物理删除数据。

MVCC 整体架构

MVCC 架构概述

数据处理流程

1. 请求处理：

   • 当执行如 put 命令时，请求会经过 gRPC KV Server 和 Raft 模块进行流转，并在日志条目被提交后，由 Apply 模块执行该日志内容。

2. 事务类型：

   • MVCC 模块将请求划分为读事务 （ReadTxn） 和写事务 （WriteTxn），分别负责处理 range 查询和执行 put / delete 操作。

核心组件详解

• treeIndex：

  • 基于内存中的 B-tree 实现，用于管理 key 索引。它保存了用户 key 与版本号 （revision） 之间的映射关系，支持快速查找特定版本的数据。

• Backend / boltdb：

  • 负责 etcd 的持久化存储，主要包含 ReadTx、BatchTx 和 Buffer 三个部分。

    • ReadTx 定义了抽象的读事务接口。

    • BatchTx 在 ReadTx 之上定义了抽象的写事务接口。

    • Buffer 是数据缓存区。

  • 目前使用的 Backend 实现是 boltdb，它是一个基于 B+ tree 实现的支持事务的嵌入式数据库，其 value 值包含了用户 key-value、各种版本号以及 lease 信息的结构体。

工作机制

• Get 操作示例：

  • 当发起一个 get hello 命令时，系统首先从 treeIndex 获取 key 对应的版本号，然后使用这个版本号从 boltdb 中检索出相应的 value 信息。

treeIndex 模块

• 核心数据结构：重点在于其基于内存的 B-tree 实现，能够高效地管理和查找 key 与版本号的映射关系，对于实现 MVCC 功能至关重要。

treeIndex 原理

etcd v2 与 v3 对比

• etcd v2：直接更新内存树，导致历史版本被覆盖，无法支持保存 key 的历史版本。

• etcd v3：引入了 treeIndex 模块，支持保存 key 的历史版本，提供稳定的 Watch 机制和事务隔离等能力。

treeIndex 实现原理

1. 全局递增的版本号（revision）：

   • 每次修改 key 时生成一个全局递增的版本号（revision），通过 B-tree 数据结构保存用户 key 与版本号之间的关系。

   • 使用版本号作为 boltdb 的 key，用户的 key-value 等信息作为 boltdb 的 value，保存到 boltdb。

2. B-tree 数据结构的选择：

   • 范围查询需求：由于 etcd 支持范围查询，因此需要使用支持范围查询的数据结构，哈希表不适合，而 B-tree 支持范围查询。

   • 性能分析：平衡二叉树每个节点只能容纳一个数据，导致树的高度较高；B-tree 每个节点可以容纳多个数据，树的高度更低，查找次数更少，具有优越的增、删、改、查性能。

   • 具体实现：etcd 基于 Google 开源项目 btree 实现了一个内存版的 B-tree，并命名为 treeIndex 模块。

3. B-tree 度数设置：

   • 在 etcd treeIndex 模块中，创建的是最大度为 32 的 B-tree，意味着一个叶子节点最多可以保存 63 个 key。

   • 在一个度为 d 的 B-tree 中，节点保存的最大 key 数为 2d - 1，否则需要进行平衡、分裂操作。

     

     
     

4. keyIndex 结构：

   • ​keyIndex​ 结构用于保存用户的 key 与版本号的映射关系，包含以下字段：

     type keyIndex struct {
        key         []byte // 用户的 key 名称
        modified    revision // 最后一次修改 key 时的 etcd 版本号
        generations []generation // key 的若干代版本号信息
     }
     
     

5. generation 结构：

   • ​generation​ 表示一个 key 从创建到删除的过程，每代对应 key 的一个生命周期的开始与结束。

     type generation struct {
        ver     int64    // 此 key 的修改次数
        created revision // generation 结构创建时的版本号
        revs    []revision // 每次修改 key 时的 revision 记录列表
     }
     
     

6. revision 结构：

   • ​revision​ 包含 main 和 sub 两个字段，分别表示全局递增的主版本号和事务内的子版本号。

     type revision struct {
        main int64    // 全局递增的主版本号
        sub int64    // 一个事务内的子版本号
     }
     
     

示例操作

• 启动一个空集群，执行如下事务：

  $ etcdctl txn -i
  compares:
  
  success requests (get, put, del):
  put hello 1
  get hello
  put world 2
  
  

  • 全局版本号随读写事务自增，因此是 main 为 2。

  • 子版本号从 0 开始随事务内的 put/delete 操作递增，因此 key "hello" 的 revision 为 {2,0}，key "world" 的 revision 为 {2,1}。

MVCC 更新 key 原理

Put 操作流程

1. 查询 KeyIndex 索引信息：

   • 当执行 put hello​ 操作时，首先从 treeIndex 模块中查询 key 的 keyIndex​ 索引信息。keyIndex​ 包含了 key 的创建版本号、修改次数等信息，这些信息在事务处理过程中至关重要。

   • 在首次创建 key hello​ 的情况下，keyIndex​ 索引为空。

2. 生成版本号（revision）：

   • 根据当前全局版本号自增生成新的版本号 revision。对于空集群启动后首次操作，版本号为 {2,0}​。

   • ​boltdb​ 的 key 使用这个版本号 {2,0}​，而 boltdb​ 的 value 则是一个 mvccpb.KeyValue​ 结构体，包含用户提供的 key、value 及其相关的版本信息（如 create_revision、mod_revision、version 和 lease）。

3. 填充 KeyValue 结构体并保存：

   • 在首次创建 key hello​ 的例子中，create_revision​ 为 2，表示此 key 创建时的版本号；mod_revision​ 也为 2，代表最后一次修改时的版本号；version​ 为 1，表示该 key 已被修改的次数。

   • 填充好 KeyValue​ 结构体后，通过 Backend 的写事务接口 batchTx​ 将数据保存到 boltdb 的缓存中，并同步更新 buffer。

4. 更新 treeIndex 模块：

   • 更新本次修改的版本号与用户 key 的映射关系到 treeIndex 模块中。

   • 对于首次创建的 key hello​，treeIndex 会生成对应的 keyIndex​ 对象，并填充相关数据结构。例如，keyIndex​ 的 generations​ 数组中会添加一个新元素来跟踪 key 的生命周期和修改记录。

5. 数据持久化：

   • 数据并非立即持久化到磁盘，而是由 Backend 的异步 goroutine 定时将 boltdb 缓存中的脏数据提交到持久化存储中，以提高写吞吐量和性能。默认情况下，当堆积的写事务数超过 1 万时才会触发同步持久化。

示例数据

keyIndex​ 结果示例

key hello的keyIndex:
key:     "hello"
modified: <2,0>
generations:
[{ver:1, created:<2,0>, revisions:[<2,0>]}]

• ​key​: "hello"​

• ​modified​: <2,0>​ 表示最后一次修改的版本号

• ​generations​: 跟踪 key 生命周期和修改记录，首次创建时 ver 为 1，created 为 <2,0>​，revisions 数组保存每次修改的版本号列表。

MVCC 查询 key 原理

Get 操作流程

1. 创建读事务对象：

   • 当执行 get hello​ 操作时，MVCC 模块首先会创建一个读事务对象（TxnRead）。在 etcd 3.4 中，Backend 实现了 ConcurrentReadTx，支持并发读特性。

   • 并发读的核心原理是在创建读事务对象时全量拷贝当前写事务未提交的 buffer 数据，从而避免并发读写事务之间的阻塞，实现了全并发读。

2. 从 treeIndex 获取版本号：

   • 在读事务中，首先根据 key 从 treeIndex 模块获取版本号。如果未指定版本号，则默认读取最新的数据。

   • treeIndex 模块从 B-tree 中查找 key 对应的 keyIndex​ 对象，并匹配有效的 generation，返回 generation 的 revisions 数组中的最后一个版本号（如 {2,0}​）给读事务对象。

3. 查询 value 信息：

   • 读事务对象根据获取到的版本号作为 key，通过 Backend 的并发读事务接口优先从 buffer 中查询。如果命中则直接返回，否则从 boltdb 中查询此 key 的 value 信息。

指定版本号读取历史记录

1. 更新 keyIndex：

   • 当再次执行 put hello world2​ 修改操作时，key hello​ 对应的 keyIndex​ 结构更新如下：

     key hello的keyIndex:
     key:     "hello"
     modified: <3,0>
     generations:
     [{ver:2, created:<2,0>, revisions:[<2,0>, <3,0>]}]
     
     

   • ​keyIndex.modified​ 字段更新为 <3,0>​，generation 的 revisions 数组追加最新的版本号 <3,0>​，ver 字段修改为 2。

2. boltdb 更新：

   • boltdb 插入一个新的 key {3,0}​，存储的 key-value 数据如下：

     Command	BoltDB Key	BoltDB Value / mvccpb.KeyValue
     ​etcdctl put hello world1​	​{2,0}​	​{"Key":"aGVsbG8=","create_revision":2, "mod_revision":2, "version":1, "value":"d29ybGQx"}​
     ​etcdctl put hello world2​	​{3,0}​	​{"Key":"aGVsbG8=","create_revision":2, "mod_revision":3, "version":2, "value":"d29ybGQy"}​

3. 读取指定版本的历史记录：

   • 当发起一个指定历史版本号为 2 的读请求时，实际上是在读取版本号为 2 的时间点的快照数据。

   • treeIndex 模块遍历 generation 内的历史版本号，返回小于等于 2 的最大历史版本号（在本案例中为 {2,0}​），并以此作为 boltdb 的 key，从 boltdb 中查询出相应的 value 信息。

MVCC 删除 key 原理

删除操作流程

1. 延期删除模式：

   • 当执行 etcdctl del hello​ 命令时，etcd 并不会立即从 treeIndex 和 boltdb 中物理删除该数据，而是采用一种延期删除的方式。

   • 这种方式类似于更新 key 的过程，但有特定的不同之处。

2. 生成带有删除标识的版本号：

   • 生成的 boltdb key 版本号会追加一个删除标识（tombstone, 简写 t），例如 {4,0,t}​。

   • boltdb value 变为只包含用户 key 的 KeyValue 结构体，不再包含实际的 value 数据。

3. 更新 treeIndex：

   • 在 treeIndex 模块中，给被删除的 key 对应的 keyIndex​ 对象追加一个空的 generation 对象，表示此索引对应的 key 已被删除。

   • 示例中的 keyIndex​ 更新如下：

     key hello的keyIndex:
     key:     "hello"
     modified: <4,0>
     generations:
     [
     {ver:3, created:<2,0>, revisions:[<2,0>,<3,0>,<4,0>(t)]},
     {empty}
     ]
     
     

4. boltdb 插入新条目：

   • boltdb 会插入一个新的 key {4,0,t}​，存储的 key-value 数据示例如下：

     Command	BoltDB Key	BoltDB Value / mvccpb.KeyValue
     ​etcdctl put hello world1​	​{2,0}​	​{"Key":"aGVsbG8=","create_revision":2, "mod_revision":2, "version":1, "value":"d29ybGQx"}​
     ​etcdctl put hello world2​	​{3,0}​	​{"Key":"aGVsbG8=","create_revision":2, "mod_revision":3, "version":2, "value":"d29ybGQy"}​
     ​etcdctl del hello​	​{4,0,t}​	​{"Key":"aGVsbG8="}​

删除标记的作用和实际删除时机

• 事件生成：删除 key 时会生成 events，Watch 模块根据 key 的删除标识生成相应的 Delete 事件。

• 重启重建内存树：当重启 etcd 时，遍历 boltdb 中的 key 构建 treeIndex 内存树，需要识别哪些 key 被标记为已删除，并为其生成 tombstone 标识。

• 异步压缩：真正删除 treeIndex 中的索引对象及 boltdb 中的 key 是由压缩（compactor）组件异步完成的。这使得在压缩组件未回收历史版本之前，可以找回误删的数据。

主要优点

• 数据恢复能力：由于采用了延期删除机制，只要压缩组件未进行数据回收，就可以从 etcd 中恢复误删的数据。

• 高效管理：通过延迟删除减少了即时删除带来的性能开销，同时支持基于事件的监控和通知功能。

小结

MVCC 特性概述

• MVCC 架构：由 treeIndex 和 boltdb 组成。

  • treeIndex：基于 Google 开源的 btree 库实现，核心数据结构为 keyIndex​，用于保存用户 key 与版本号的关系。

  • boltdb：作为持久化存储，其 key 是版本号，value 是包含用户 key-value、各种版本号以及 lease 信息的 mvccpb.KeyValue 结构体。

更新、查询、删除操作详解

1. 更新 Key：

   • 每次修改 key 都会生成一个新的版本号，并创建新的 boltdb key-value 对。

   • 这些版本号帮助 etcd 实现多版本控制，支持历史数据的保存和查询。

2. 查询 Key：

   • 当未指定版本号查询时，etcd 返回的是该 key 的最新版本数据。

   • 如果指定了特定版本号，则返回该版本号对应时间点的数据快照。

3. 删除 Key：

   • 删除操作并未立即从 treeIndex 和 boltdb 中物理删除数据，而是采用了延期删除（lazy delete）机制。

   • 删除操作会在 boltdb 的 key 上打上删除标记（如 {4,0,t}​），并在 keyIndex 索引中追加一个空的 generation 对象表示该 key 已被删除。

   • 真正的删除是通过 etcd 的压缩组件异步完成的，这允许在压缩前恢复误删的数据。

关键特性和优点

• 保存历史版本：基于上述机制，etcd 能够保存 key 的所有历史版本，这是实现高可靠 Watch 机制的基础。

• 事务隔离：利用 key-value 中的各种版本号信息，etcd 提供了不同级别的简易事务隔离能力。

• 读写不冲突：通过 Backend/boltdb 提供的 MVCC 机制，实现了读写操作之间不会相互阻塞，提高了系统的并发处理能力。

思考

为什么 etcd 使用 lazy delete 方式？

Lazy Delete 的优点：

1. 减少写放大：直接删除 key 可能导致频繁的磁盘 I/O 操作，尤其是在高并发场景下，这会影响系统性能。Lazy delete 通过异步清理机制减少了对存储系统的即时压力。

2. 提高并发性：由于删除操作不会立即从 treeIndex 和 boltdb 中移除数据，读写操作可以继续进行而不被阻塞，从而提高了系统的并发处理能力。

3. 支持历史版本查询：lazy delete 允许在删除后的一段时间内仍然能够访问被删除的数据版本，这对于需要追踪或恢复误删数据的应用非常重要。

4. 事件通知机制：删除操作生成的 tombstone 标记可以用于 Watch 机制，提供关于 key 删除的通知，这对于监听变化的应用非常有用。

Lazy Delete 的缺点：

1. 延迟空间回收：由于删除操作是异步执行的，物理空间的回收会有延迟，可能导致短期内数据库大小增加或不减少。

2. 复杂性增加：实现和维护一个有效的压缩机制以清除过期数据增加了系统的复杂性。

同步 Delete 的优缺点：

• 优点：

  • 即时空间回收：删除操作完成后，相关的资源立即被释放，数据库大小会立刻减小。

  • 简化设计：无需复杂的后台任务来管理数据的生命周期，降低了系统设计的复杂度。

• 缺点：

  • 影响性能：尤其是在大量删除操作发生时，可能会导致显著的性能下降，因为每次删除都需要同步更新索引和持久化存储。

  • 降低并发性：同步删除可能需要锁定相关资源，限制了其他读写操作的并发执行。

当突然删除大量 key 后，db 大小的变化