一、TiDB 存储
https://pingcap.com/zh/blog/tidb-internal-1
1.1 key-value
数据的存储模型(数据以何种形式保存):key-value模型,且提供有序遍历方法。
将 TiKV 看做一个巨大的 Map,其中 Key 和 Value 都是原始的 Byte 数组,在这个 Map 中,Key 按照 Byte 数组总的原始二进制比特位比较顺序排列。 对 TiKV 需记住两点:
- 这是一个巨大的 Map,也就是存储的是 Key-Value pair
- 这个 Map 中的 Key-Value pair 按照 Key 的二进制顺序有序,也就是我们可以 Seek 到某一个 Key 的位置,然后不断的调用 Next 方法以递增的顺序获取比这个 Key 大的 Key-Value
存储模型与SQL中Table无关
1.2 RocksDB
持久化的存储引擎都要将数据保存到磁盘。TiKV 没有选择直接向磁盘上写数据,而是把数据保存在 RocksDB 中,具体的数据落地由 RocksDB 负责。
这个选择的原因是开发一个单机存储引擎工作量很大,特别是要做一个高性能的单机引擎,需要做各种细致的优化,而 RocksDB 是一个非常优秀的开源的单机存储引擎,可以满足我们对单机引擎的各种要求,而且还有 Facebook 的团队在做持续的优化
这里可以简单的认为 RocksDB 是一个单机的 Key-Value Map。
1.3 Raft
我们已为数据找到一个高效可靠的本地存储方案。
如何保证单机失效的情况下,数据不丢失,不出错?简单来说,我们需要想办法把数据复制到多台机器上,这样一台机器挂了,我们还有其他的机器上的副本;复杂来说,我们还需要这个复制方案是可靠、高效并且能处理副本失效的情况。—— Raft 协议
Raft 是一个一致性算法,它和 Paxos 等价。提供几个重要的功能:
- Leader 选举
- 成员变更
- 日志复制
TiKV 利用 Raft 来做数据复制,每个数据变更都会落地为一条 Raft 日志,通过 Raft 的日志复制功能,将数据安全可靠地同步到 Group 的多数节点中。
总结:
通过单机的 RocksDB,我们可以将数据快速地存储在磁盘上;通过 Raft,我们可以将数据复制到多台机器上,以防单机失效。数据的写入是通过 Raft 这一层的接口写入,而不是直接写 RocksDB。通过实现 Raft,我们拥有了一个分布式的 KV,现在再也不用担心某台机器挂掉了。
1.4 Region
前面提到,我们将 TiKV 看做一个巨大的有序的 KV Map,那么为了实现存储的水平扩展,我们需要将数据分散在多台机器上。这里提到的数据分散在多台机器上和 Raft 的数据复制不是一个概念。
个人看法:
Raft 是为了将本地的完整数据复制到多台机器,以达到容灾的目的;
Region 是想将本地的完整数据分散到多台机器上。
对于一个 KV 系统,将数据分散在多台机器上有两种比较典型的方案:
- 按照 Key 做 Hash,根据 Hash 值选择对应的存储节点;
- 分 Range,某一段连续的 Key 都保存在一个存储节点上。
TiKV 选择了第二种方式,将整个 Key-Value 空间分成很多段,每一段是一系列连续的 Key,我们将每一段叫做一个 Region,并且我们会尽量保持每个 Region 中保存的数据不超过一定的大小(这个大小可以配置,目前默认是 96mb)。每一个 Region 都可以用 StartKey 到 EndKey 这样一个 左闭右开区间 来描述。
将数据划分成 Region 后,我们将会做 两件重要的事情:
- 以 Region 为单位,将数据分散在集群中所有的节点上,并且尽量保证每个节点上服务的 Region 数量差不多
- 以 Region 为单位做 Raft 的复制和成员管理
先看第一点,数据按照 Key 切分成很多 Region,每个 Region 的数据只会保存在一个节点上面。我们的系统会有一个组件来负责将 Region 尽可能均匀的散布在集群中所有的节点上,这样一方面实现了存储容量的水平扩展(增加新的结点后,会自动将其他节点上的 Region 调度过来),另一方面也实现了负载均衡(不会出现某个节点有很多数据,其他节点上没什么数据的情况)。同时为了保证上层客户端能够访问所需要的数据,我们的系统中也会有一个组件记录 Region 在节点上面的分布情况,也就是通过任意一个 Key 就能查询到这个 Key 在哪个 Region 中,以及这个 Region 目前在哪个节点上。至于是哪个组件负责这两项工作,会在后续介绍。
对于第二点,TiKV 是以 Region 为单位做数据的复制,也就是一个 Region 的数据会保存多个副本(默认3副本),我们将每一个副本叫做一个 Replica
。Replica 之间是通过 Raft 来保持数据的一致(终于提到了 Raft),一个 Region 的多个 Replica 会保存在不同的节点上,构成一个 Raft Group
。其中一个 Replica 会作为这个 Group 的 Leader,其他的 Replica 作为 Follower。所有的读和写都是通过 Leader 进行,再由 Leader 复制给 Follower(通过raft日志)。 大家理解了 Region 之后,应该可以理解下面这张图:
若Follower长期接收不到Leader的信息,则会将自己变为Candidate并发起投票。
以 Region 为单位做数据的分散和复制,就有了一个分布式的具备一定容灾能力的 KeyValue 系统,不用再担心数据存不下,或者是磁盘故障丢失数据的问题。
若region过多,则管理成本会很高,网络压力较大,因为每个region都要定期向PD汇报心跳
1.5 MVCC
很多数据库都会实现多版本并发控制
(MVCC),TiKV 也不例外。设想这样的场景,两个 Client 同时去修改一个 Key 的 Value,如果没有 MVCC,就需要对数据上锁,在分布式场景下,可能会带来性能以及死锁问题。 TiKV 的 MVCC 实现是通过在 Key 后面添加 Version 来实现,简单来说,没有 MVCC 之前,可以把 TiKV 看做这样的:
Key1 -> Value
Key2 -> Value
……
KeyN -> Value
有了 MVCC 之后,TiKV 的 Key 排列是这样的:
Key1-Version3 -> Value
Key1-Version2 -> Value
Key1-Version1 -> Value
……
Key2-Version4 -> Value
Key2-Version3 -> Value
Key2-Version2 -> Value
Key2-Version1 -> Value
……
KeyN-Version2 -> Value
KeyN-Version1 -> Value
……
注意,对于同一个 Key 的多个版本,我们把版本号较大的放在前面,版本号小的放在后面(回忆一下 Key-Value 一节我们介绍过的 Key 是有序的排列),这样当用户通过一个 Key + Version 来获取 Value 的时候,可以将 Key 和 Version 构造出 MVCC 的 Key,也就是 Key-Version。然后可以直接 Seek(Key-Version),定位到第一个大于等于这个 Key-Version 的位置。
1.6 事务
TiKV 的事务采用的是 Percolator 模型,并且做了大量的优化。
事务的细节这里不详述,大家可以参考论文以及我们的其他文章。这里只提一点,TiKV 的事务采用乐观锁
,事务的执行过程中,不会检测写写冲突,只有在提交过程中,才会做冲突检测,冲突的双方中比较早完成提交的会写入成功,另一方会尝试重新执行整个事务。
当业务的写入冲突不严重的情况下,这种模型性能会很好,比如随机更新表中某一行的数据,并且表很大。但是如果业务的写入冲突严重,性能就会很差,举一个极端的例子,就是计数器,多个客户端同时修改少量行,导致冲突严重的,造成大量的无效重试。
悲观锁
:是基于一种悲观的态度类来防止一切数据冲突,以一种预防的姿态在修改数据之前把数据锁住,然后再对数据进行读写,在它释放锁之前任何人都不能对其数据进行操作,直到前面一个人把锁释放后下一个人数据加锁才可对数据进行加锁,然后才可以对数据进行操作,一般数据库本身锁的机制都是基于悲观锁的机制实现的;
- 特点:可在事务运行时马上发现冲突。可以完全保证数据的独占性和正确性,因为每次请求都会先对数据进行加锁, 然后进行数据操作,最后再解锁,而加锁释放锁的过程会造成消耗,所以性能不高;
乐观锁
:对于数据冲突保持一种乐观态度,操作数据时不会对操作的数据进行加锁(这使得多个任务可以并行的对数据进行操作),只有到数据提交的时候才通过一种机制来验证数据是否存在冲突(一般实现方式是通过加版本号,然后进行版本号的对比方式实现);
- 特点:是一种并发类型的锁,其本身不对数据进行加锁通而是通过业务实现锁的功能,不对数据进行加锁就意味着允许多个请求同时访问数据,同时也省掉了对数据加锁和解锁的过程,这种方式因为节省了悲观锁加锁的操作,所以可以一定程度的的提高操作的性能,不过在并发非常高的情况下,会导致大量的请求冲突,冲突导致大部分操作无功而返而浪费资源,所以在高并发的场景下,乐观锁的性能却反而不如悲观锁。
1.7 小结
TiKV 集群是 TiDB 数据库的分布式 KV 存储引擎,把数据保存在 RocksDB 中,数据以 Region 为单位进行复制和管理,每个 Region 会有多个 Replica(副本),这些 Replica 会分布在不同的 TiKV 节点上,其中 Leader 负责读/写,Follower 负责同步 Leader 发来的 raft log。