TiDB内部(I) -数据存储
目录
前言：
数据库、操作系统和编译器被称为三大系统，是整个计算机软件的基石。其中，数据库支持业务，更接近应用层。经过几十年的发展，这一领域不断取得进步。
许多人必须使用过不同类型的数据库，但很少有人有开发数据库的经验，尤其是分布式数据库。了解实现数据库的原理和细节有助于提高一个人的技能水平，这有助于构建其他系统，也有助于更好地利用数据库。
我相信研究一项技术的最好方法是深入研究该领域的开源项目。数据库也不例外。在独立数据库领域有许多优秀的开源项目。其中，MySQL和PostgreSQL最为著名，很多人一定读过他们的源代码。然而，就分布式数据库而言，好的开源项目并不多，TiDB就是其中之一。许多人，特别是技术爱好者，希望参与这个项目。然而，由于分布式数据库的复杂性，很多人发现很难理解整个项目。因此，我计划写几篇文章来说明TiDB的技术原理，包括用户可以看到的技术以及SQL界面背后的许多不可见技术。
这是我们系列文章的第一篇。
存储数据
我想从数据库最基本的功能开始——存储数据。
存储数据的方法有很多，最简单的方法是在内存中构建数据结构来存储用户发送的数据。例如，使用数组存储数据，并在接收数据时向数组添加新条目。该解决方案简单，满足基本需求，性能良好。但其弊大于利。最大的问题是，由于所有数据都存储在内存中，如果服务器停止或重新启动，数据就会丢失。
为了实现数据持久性，我们可以将数据存储在非易失性存储介质中，例如磁盘。我们在磁盘上创建一个文件，并在接收数据时向该文件追加一条新记录。这是一种持久的存储解决方案。
但这还不够。如果磁盘坏了怎么办？为了避免磁盘的坏磁道，我们可以使用RAID（独立磁盘冗余阵列）进行独立冗余存储。但是，如果整个机器都坏了怎么办？万一发生火灾怎么办？空袭不是安全之家。
另一种解决方案是将数据存储在网络中，或者使用硬件或软件进行存储和复制。但问题是如何保证副本之间的一致性。确保数据的完整性和正确性是最基本的要求，下面的问题要求更高:
- 数据库是否支持多数据中心容灾?
- 写速度够快吗？
- 存储数据时读取数据方便吗?
- 如何更新存储的数据？它如何处理并发修订？
- 如何原子地修改多个记录?
所有这些问题都很难解决。但是一个优秀的数据库存储系统必须能够处理它们中的每一个。
为此，我们开发了TiKV。现在，我想和大家分享一下TiKV的设计理念和基本概念。
当我们谈论TiKV时，我希望你可以忘记任何关于SQL的概念，而专注于如何实现TiKV，这是一个巨大的分布式有序映射，具有高性能和可靠性。
键-值
数据存储系统首先应该确定数据的存储模型。换句话说，应该以哪种格式存储数据。TiKV选择了Key-Value模型，并提供了有序遍历的解决方案。简单地说:您可以看到TiKV作为一个巨大的Map，其中Key和Value是原始的字节数组。在这个Map中，Key按照字节数组的原始二进制位的比较顺序排列。
需要记住以下几点：
- 这是一个巨大的键值对映射。
- 在此映射中，键-值对根据键的二进制序列排序。我们可以找到一个键的位置，然后使用下一种方法找到其他键值对，这些键值对都比这个大。
您可能想知道我所说的存储模型与SQL中的表之间的关系。在这里，我想强调一点：它们无关紧要。
RocksDB
任何耐用的存储引擎都将数据存储在磁盘上，TiKV也不例外。但是TiKV并不直接将数据写入磁盘。相反，它将数据存储在RocksDB中，然后RocksDB负责数据存储。原因是开发独立存储引擎的成本很高，尤其是高性能的独立引擎。你需要做各种详细的优化。幸运的是，我们发现RocksDB是一个优秀的开源独立存储引擎，能够满足我们所有的需求。此外，随着Facebook团队不断优化，我们无需投入太多精力就能享受到强大而先进的独立引擎。当然，我们也为RocksDB贡献了几行代码，我们希望这个项目能变得更好。总之，你可以把RocksDB看作是一个独立的键值映射。
筏
找到一个有效、可靠的本地存储解决方案是这个复杂项目的重要第一步。现在我们面临着一个更困难的问题:当一台机器发生故障时，如何保证数据的完整性和正确性?
一个好的方法是将数据复制到多台机器。然后，当一台机器崩溃时，我们在其他机器上有副本。但是需要注意的是，复制解决方案应该是可靠的、有效的，并且能够处理无效副本的情况。这听起来很难，但Raft做到了。
Raft是一种共识算法，相当于Paxos，而Raft更容易理解。对Raft感兴趣的可以参考这篇论文更多细节。我想指出，Raft文件只提供了一个基本的解决方案，如果严格遵循该文件，性能将很差。为了实现Raft，我们已经进行了许多优化，有关更多详细信息，请参阅这个博客由我们的总建筑师唐柳撰写。
Raft是一个共识算法，提供三个重要功能:
- 领导人选举
- 会员改变
- 日志复制
TiKV使用Raft复制数据，每次数据更改都将记录为Raft日志。通过Raft的日志复制功能，数据安全可靠地同步到Raft组的多个节点。
总之，通过独立的RocksDB，我们可以在磁盘上快速存储数据;通过Raft，我们可以复制数据到多台机器，在机器故障的情况下。数据通过Raft接口写入，而不是通过RocksDB。多亏了Raft的实现，我们有了一个分布式的键值，不再需要担心机器故障。
区域
在本节中，我想介绍一个非常重要的概念：区域。它是理解一系列机制的基础。
在开始之前，让我们先忘掉Raft，试着想象一下所有数据只有一个副本。
正如我前面提到的，TiKV被视为一个巨大但有序的键值映射。为了实现存储的水平可伸缩性，我们需要将数据分布到多台机器中。
对于Key-Value系统，有两种典型的解决方案可以在多台机器中分发数据。一是创建Hash，并根据Hash值选择对应的存储节点;二是使用Range，在存储节点中存储一段串行Key。TiKV选择了第二种方案，将整个Key-Value空间划分为许多段。每个区段由一系列相邻的Key组成，我们称之为“区域”。每个Region存储数据的大小都有限制(默认值是64MB，大小可以配置)。每个Region可以用一个左-右-右-开区间来描述，从StartKey到EndKey。
请注意，我所说的区域与SQL中的表没有关系！请忘记SQL，现在把重点放在键值上。
将数据划分为Region后，我们将执行两个更重要的任务:
- 将数据分发到集群中的所有节点，并使用Region作为数据移动的基本单元。我们还需要确保每个节点的Region数量大致相同。
- 在区域内进行Raft复制和成员管理。
这两项任务非常重要，我将逐一介绍。
在第一个任务中，根据Key将数据划分为多个Region，每个Region中的所有数据存储在一个节点中。我们系统中的一个组件负责将区域平均分配到集群的所有节点。这一方面实现了存储容量的横向可扩展性(当增加一个新节点时，系统会自动在其他节点上调度region);另一方面，实现了负载均衡(不会出现一个节点拥有很多数据而其他节点拥有很少数据的情况)。同时，为了保证上层客户端能够访问到所需的数据，另一个组件将记录region在节点之间的分布。换句话说，您可以通过任何Key查询Key的确切Region和该Region的节点。稍后我将分享关于这两个组件的更多信息。
现在让我们开始第二个任务。TiKV复制Region中的数据，这意味着一个Region中的数据将有多个名为“Replica”的副本。利用Raft实现了replica之间的数据一致性。一个Region的多个Replicas保存在不同的节点上，构成一个Raft Group。一个副本作为小组的领导者，其他的作为追随者。所有的读取和写入都通过Leader进行，然后Leader复制到Follower。
下图展示了Region和Raft组的整体情况。
当我们在Regions中分发和复制数据时，我们就有了一个分布式的Key-Value系统，在某种程度上，它具有灾难恢复的能力。您不再需要担心容量问题或硬盘故障导致的数据丢失问题。这很酷，但并不完美。我们需要更多的功能。
MVCC
许多数据库都实现了多版本并发控制(MVCC)， TiKV也不例外。假设两个客户端同时更新一个Key的Value，如果没有MVCC，数据将被锁定。在分布式场景中，这将导致性能和死锁问题。
TiKV通过将Version附加到Key来实现MVCC。在没有MVCC的情况下，TiKV的数据布局可以看到:
~~ Key1 ->值~~ Key2 ->值~~ ......~~ KeyN ->值使用MVCC, TiKV中的键数组看起来像这样:
~~ Key1-Version3 ->值~~ Key1-Version2 ->值~~ Key1-Version1 ->值~~ ...... .~~ Key2-Version4 -> Value ~~ Key2-Version3 -> Value ~~ Key2-Version2 -> Value ~~ Key2-Version1 -> Value ~~ ...... .~~ KeyN-Version2 ->值~~ KeyN-Version1 ->值~~ ...... .值得注意的是，对于一个Key的多个版本，我们把较大的数字放在前面(您可以查看Key- value部分，在那里我提到Key是一个有序数组)。这样，当用户通过Key +获取Value时<版本>，他可以用Key和Version构造MVCC的Key，即Key-<版本>．然后他可以直接Seek(Key-Version)并找到大于或等于该Key-Version的第一个位置。有关更多细节，请参见在TiKV MVCC．
交易
TiKV交易采用Percolator模型，进行了大量的优化。我不想深入探讨，因为你可以阅读报纸和我们的文章(目前是中文)。我想说的是，TiKV的交易使用了乐观锁。在执行过程中，它不会检测写冲突。只有在提交阶段，它才会检测到冲突。较早完成提交的事务将被成功写入，而另一个事务将重试。如果业务的写冲突不严重，则该模型的性能非常好。例如，它可以很好地在一个大表中随机更新一些数据行。但是，如果写冲突很严重，性能就会很差。举个极端的例子。 The situation that many clients update a few rows at the same time leads to serious conflicts and numerous invalid retry.
杂项
到目前为止，我已经介绍了TiKV的基本概念和一些细节，这个分布式和事务性Key-Value引擎的分层结构，以及如何实现多数据中心灾难恢复。在下一篇文章中，我将介绍如何在Key-Value存储模型之上构造SQL层。