TiDB内部(I)-数据存储

2017-07-11 李慎 工程

来自李慎:shenli@www.schmieso.com

表的内容

前言:

数据库,操作系统和编译器称为三个大系统,并视为整个计算机软件的脚石。其中,数据库支持业务并更靠近应用程序层。经过几十年的发展,进展在这一领域不断涌现。

许多人肯定使用过不同类型的数据库,但很少有人有开发数据库的经验,尤其是分布式数据库。了解数据库实现的原理和细节有助于提高一个人的技能水平,这有利于构建其他系统,也有助于更好地利用数据库。

我认为研究一项技术的最好方法是深入研究该领域的开源项目。数据库也不例外。在独立数据库领域有很多好的开源项目。其中,MySQL和PostgreSQL是最著名的,很多人一定读过他们的源代码。然而,在分布式数据库方面,好的开源项目并不多,TiDB就是其中之一。很多人,尤其是技术爱好者,希望参与这个项目。然而,由于分布式数据库的复杂性,很多人很难理解整个项目。因此,我计划写几篇文章来说明TiDB的技术原理,包括用户可以看到的技术以及SQL接口背后无数不可见的技术。

这是我们系列文章的第一篇。

存储数据

存储数据

我想从数据库存储数据的最基本函数开始。

存储数据的方法有很多,最简单的一种是在内存中构建一个数据结构来存储用户发送的数据。例如,使用数组来存储数据,并在接收到数据片段时向数组添加一个新条目。该解决方案简单,满足基本需求,具有良好的性能。但它的缺点大于优点。最大的问题是,由于所有数据都存储在内存中,如果服务器停止或重启,数据将丢失。

为了实现数据持久性,我们可以将数据存储在非易失性存储介质,磁盘中。我们在磁盘上创建文件,并在接收数据时将新记录附加到文件。这是一个耐用的存储解决方案。

但这还不够。如果磁盘坏了怎么办?为了避免磁盘的坏道,我们可以使用RAID (Redundant Array of Independent Disks)来进行独立的冗余存储。但是,如果整个机器都宕机了怎么办?如果发生火灾怎么办?RAID不是安全屋。

另一种解决方案是将数据存储在网络中或使用硬件或软件进行存储和复制。但问题是如何保证副本之间的一致性。确保数据的完整性和正确性是基本要求,以下问题更苛刻:

  • 数据库是否支持多数据中心的灾难恢复?
  • 写速度够快吗?
  • 存储数据时读取数据方便吗?
  • 如何更新存储的数据?它如何处理并发修订?
  • 如何原子地修改多个记录?

所有这些问题都很难解决。但是一个优秀的数据库存储系统必须能够处理其中的每一个问题。

为此,我们开发了TiKV。现在,我想和大家分享TiKV的设计理念和基本概念。

当我们谈论TiKV时,我希望您可以忘记任何关于SQL的概念,而将注意力放在如何实现TiKV上,这是一个具有高性能和可靠性的巨大的分布式有序映射。

关键字值

数据存储系统首先应该确定数据的存储模型。换句话说,数据应该以哪种格式存储。TiKV选择了关键值模型,并提供了一种有序遍历的解决方案。简单地说:您可以将TiKV看作一个巨大的映射,其中键和值是原始字节数组。在这个映射中,密钥是根据字节数组的原始二进制位按比较顺序排列的。

需要牢记以下几点:

  1. 这是一个巨大的键值对地图。
  2. 在这个Map中,Key- value对根据Key的二进制序列进行排序。我们可以查找Key的位置,然后使用Next方法查找其他的Key- value对,这些Key- value对都比这个大。

您可能想知道我所讨论的存储模型和SQL中的表之间的关系。在这里,我想强调:它们是无关的。

RocksDB公司

任何持久的存储引擎都将数据存储在磁盘上,TiKV也不例外。但TiKV不直接将数据写入磁盘。相反,它将数据存储在RocksDB中,然后RocksDB负责数据存储。原因是开发一个独立的存储引擎,特别是一个高性能的独立引擎需要花费大量的成本。你需要做各种详细的优化。幸运的是,我们发现RocksDB是一个优秀的开源独立存储引擎,满足了我们的所有需求。此外,随着Facebook团队不断优化,我们可以享受一个强大而先进的独立引擎,而无需投入太多精力。当然,我们为RocksDB贡献了几行代码,我们希望这个项目会变得更好。总之,您可以将RocksDB视为一个独立的键值映射。

找到一个有效、可靠的本地存储解决方案是这个复杂项目的重要第一步。现在我们面临着一个更困难的问题:当一台机器发生故障时,如何保证数据的完整性和正确性?

一种好方法是将数据复制到多个机器。然后,当一台机器崩溃时,我们在其他机器上有复制品。但有人指出,复制解决方案应该是可靠的,有效的,可以处理无效副本的情况。这听起来很困难,但筏子使它成为可能。

RAFT是一种共识算法,而筏子更容易理解,则相当于PAXOS。那些对筏感兴趣的人可以参考本文为更多的细节。我想指出的是,Raft论文只给出了一个基本的解决方案,如果严格按照论文的要求执行,性能会很差。我们已经做了很多优化来实现Raft,更多的细节请参考这个博客由我们的首席建筑师唐刘撰写。

RAFT是一种共识算法,提供了三种重要功能:

  1. 领导人选举
  2. 会员改变
  3. 日志复制

TiKV使用Raft复制数据,每次数据更改都将被记录为Raft日志。通过Raft的日志复制功能,将数据安全可靠地同步到Raft组的多个节点。

数据被复制到Raft组的多个节点

总之,通过独立的RockSDB,我们可以快速将数据存储在磁盘上;通过筏,我们可以在机器故障的情况下将数据复制到多个机器。数据通过筏的界面而不是RockSDB编写的。由于筏的实现,我们具有分布式键值,不再需要担心机器故障。

地区

在这一节中,我想介绍一个非常重要的概念:Region。它是理解一系列机制的基础。

在开始之前,让我们先忘掉Raft,想象一下所有数据只有一个副本。

正如我前面提到的,TiKV被视为一个巨大但有序的键值映射。为了实现存储的横向可扩展性,我们需要在多台机器之间分发数据。

对于键值系统,有两个典型的解决方案可以在多台机器之间分配数据。一个是创建哈希,并根据散列值选择相应的存储节点;另一个是在存储节点中使用范围并将一段串行键。TIKV选择了第二种解决方案,并将整个钥匙空间划分为多个段。每个段都包括一系列相邻键,我们称之为“区域”。每个区域都有一个尺寸限制来存储数据(默认值为64MB,并且可以配置大小)。每个区域可以通过左右右开放间隔来描述,该间隔来自启动到endkey。

地区TiKV

请注意,我所谈论的区域与SQL中的表没有关系!请暂时忘记SQL,专注于Key-Value。

将数据划分为区域后,我们将执行两个更重要的任务:

  • 将数据分发到集群中的所有节点,并以区域作为数据移动的基本单元。我们还需要确保每个节点中的区域数大致相同。
  • 负责区域内筏的复制和会员管理。

这两个任务非常重要,我将逐一说明。

对于第一个任务,根据密钥将数据划分为多个区域,每个区域中的所有数据都存储在一个节点中。我们系统中的一个组件负责将区域均匀地分布到集群的所有节点。这一方面实现了存储容量的横向可扩展性(当添加一个新节点时,系统将自动在其他节点上调度区域);另一方面,实现了负载平衡(不会出现一个节点有很多数据而其他节点只有很少数据的情况)。同时,为了保证上层客户端能够访问所需的数据,另一个组件将记录节点间区域的分布情况。换句话说,您可以查询某个键的确切区域以及通过任何键放置的该区域的节点。稍后我将分享有关这两个组件的更多信息。

现在让我们搬到第二任务。TIKV在区域中复制数据,这意味着一个区域中的数据将具有多个具有名称“副本”的副本。RAFT用于达到复制品之间的数据一致性。一个区域的多个副本保存在不同的节点中,该节点构成筏组。一张副本是团队的领导者和其他人作为追随者。所有读书和写作都是通过领导者进行的,然后是领导者复制到追随者。

下图显示了区域和筏群的全貌。

区域和筏群

当我们在区域中分发和复制数据时,我们有一个分布式键值系统,在某种程度上具有灾难恢复的能力。您不再需要担心磁盘故障引起的数据丢失的容量或问题。这很酷但不完美。我们需要更多的功能。

MVCC

许多数据库实现多版本并发控制(MVCC),TIKV也不例外。假设两个客户端同时更新键的值,没有MVCC,数据将被锁定。在分布式场景中,这将导致性能和死锁问题。

TIKV通过将版本附加到键来实现MVCC。没有MVCC,TIKV的数据布局可以看作:

~~ key1  - > value ~~ key2  - >值~~ ...... ~~ keyn  - >值

使用MVCC,TIKV中的关键数组如下所示:

~~ key1-Version3  - > value ~~ key1-version2  - > value ~~ key1-version1  - > value ~~ ...... ~~ key2-version4  - > value ~~ key2-version3  - > value ~~ key2-version2  -> value ~~ key2-version1  - >值~~ ...... ~~ keyn-version2  - > value ~~ keyn-version1  - > value ~~ ......

注意到,对于一个密钥的多个版本,我们首先放大更大的数字(您可以查看我提到的键值部分,其中键是一个有序的数组)。以这种方式,当用户通过键+获取值时<版本>,可以用Key和Version构造MVCC的Key,即Key-<版本>. 然后他可以直接寻找(密钥版本)并定位第一个大于或等于该密钥版本的位置。有关详细信息,请参见MVCC(单位:千伏).

事务

TiKV的事务采用Percolator模型,并进行了大量的优化。我不想深究,因为你可以阅读报纸和我们的文章(目前是中文)。我想说的是,TiKV中的事务使用乐观锁。在执行过程中,它不会检测到写冲突。只有在提交阶段,它才会检测到冲突。较早完成提交的事务将被成功写入,而另一个事务将重试。如果业务的写冲突不严重,则该模型的性能非常好。例如,随机更新一个大表中的一些数据行效果很好。但是,如果写冲突严重,则性能会很差。以counter为例。许多客户端同时更新几行的情况会导致严重的冲突和多次无效重试。

各种各样的

到目前为止,我介绍了TIKV的基本概念和一些细节,这是一个分布式和事务键值引擎的分层结构以及如何实现多数据中心灾难恢复。我将介绍如何在下一篇文章中的键值存储模型的顶部构建SQL图层。

TiKV MVCC

准备开始用TIDB开始吗?