关于数据库:数据库存储与索引技术一存储模型与索引结构演变

随着 1970 年代关系模型被提出，数据库进入了一个飞速发展的期间。整个 80 年代和 90 年代，各类关系数据库层出不穷，这些产品到当初仍然占据着数据库市场的支流。然而到了 2000 年当前，互联网产业的崛起，使得传统的关系数据库在面对海量申请和数据的时候有些力不从心。在这一时期，解决可扩大问题的支流计划是拆分数据库 (分库分表)，诞生了泛滥的数据库中间层(中间件)；同时，业界也诞生了泛滥的 K - V 数据库，如 BigTable，MongoDB，Cassandra 等，解决了半结构化数据的计算和存储的可扩大问题，然而业界对于可扩大的关系数据库的诉求始终存在。2012 年 Google 的论文《Spanner: Google’s Globally-Distributed Database》为业界提供了一个分布式数据库的十分好的参考，尔后，各类参考 Spanner 架构的分布式数据库系统层出不穷。其中国内厂商在本身用户数，以及去 IOE 能源的驱使下，诞生了包含 OceanBase 和 TiDB 在内的几款十分优良的分布式数据库，在技术上的差距和国外巨头曾经拉平，然而市场开辟上还须要持续致力。同时，泛滥的云计算厂商基于本身的云基础设施为其客户提供的数据库解决方案也为数据库的扩展性提供了新的思路。代表性的产品是亚马逊的 Aurora，其下层 100% 兼容开源数据库(MySQL, PostgreSQL)，上层依靠本身云厂商存储技术设施，计算与存储拆散的架构，成为了泛滥云厂商参考的对象。数据库是一个宏大而简单的零碎，其各个子系统，如 SQL，事务，存储，日志等，每一个都是既有肯定的实践了解门槛，又有十分高的实现难度，分布式数据库还会波及更多艰涩的实践，如 CAP 实践，2/ 3 阶段提交协定，Paxos 协定，Raft 协定等。本系列通过三篇文章尝试从存储和索引的角度和大家独特学习和理解数据库在存储畛域的一些技术，心愿这样记忆犹新的文章能给大家留下些许印象，拓宽一些思路，在当前的工作中能有所帮忙（注：本系列参考的材料均系自己搜集自互联网公开的论文和博客文章，以及开源的代码和文档等，并经自己了解和整顿。文章中的一些技术观点仅代表个人观点，如有形容偏差烦请斧正）。2. 传统单机数据库存储与索引技术 2.1. 存储模型介绍为了保障在零碎产生故障时的数据长久化，数据库应用非易失的磁盘作为主存储介质。传统数据库的在磁盘上的数据组织形式为页面行存，即数据库将磁盘空间划分为多个页面，每个页面的大小个别是 4K 的整数倍，数据在页面内以行为单位存储在一起。数据库读写 IO 的根本单位都是页面。因为零碎不能间接操作磁盘上的数据，因而还需应用内存作为缓存。通常数据库在内存中会保护一个 Buffer Pool 的数据结构，用于缓存从磁盘中读取的页面。数据库下层子系统对于数据的读写，都通过 Buffer Pool 进行。数据库在进行事务操作时，先将 redo log 程序写入日志文件，而后再将批改利用到 Buffer Pool 中的指标页面。通常这一过程只有一次日志文件的程序 IO 操作，没有磁盘的随机 IO。Buffer Pool 会在零碎闲暇或者内存达到肯定阈值的时候异步将某些页面回刷到磁盘并回收内存。Buffer Pool 页面回刷会产生随机 IO，页面的替换策略也会影响零碎整体的缓存命中率，因而页面回刷策略也是很多钻研的热点。数据库的数据存储在页面上，通常以行为单位存储。页面个别会有一个固定大小的页头(Page Header)，用于存储页面的一些 meta 信息，如页面类型，记录条数，同一张表下一个页面的地址等。如果页面存储的行记录是定长的，那么从 Page Header 开始顺次存储记录就行了。如果是变长记录，即每一行数据的大小都可能不一样，个别的做法是从 Page Header 后开始存储数据，再从页面的开端开始反向调配也目录(Row Offset) 空间，Row Offset 记录行在页面内的偏移。这样能够在不确定一个页面能够存储多少行数据的状况下，尽量进步页面空间的利用率。

2.2 数据文件组织形式后面咱们讲到数据表的存储形式是以页面为单位进行存储的，然而页面与页面之间如何组织，也由不同的形式。常见的形式有两种。一种叫做堆文件(Heap File)，另外一种叫做索引组织表(IOT，Index Organized Table)。2.2.1 堆文件堆文件是数据库中最简略，最根本的文件构造，新数据插入优先应用文件开端的闲暇页面，每行数据都会被调配一个 rowid 作为行的惟一标识。rowid 通常蕴含其所在的文件 ID，页面 ID，以及页面内的行序号 ID。堆文件有以下一些应用场景：数据量很小的表，如数据只有几个页面，此时通过索引拜访和间接进行全表扫描相比没太大差异。数据表有一次性的大量数据插入的场景，如数据迁徙。此时，应用对文件进行数据插入，效率会比通过索引组织表的形式插入会高十分多。在堆文件上建设索引后，也能够用于数据量大的场景。

堆文件的各种操作如下如下。插入：插入优先应用文件开端的闲暇页面空间，只有当闲暇空间有余时，才思考复用被删除的记录的空间。删除：删除数据须要将页面上的物理记录标记为删除，并删除索引中对 rowid 的援用。查问：依据索引 (B+Tree) 进行点查问或者范畴查问，查问索引失去 rowid 之后，再通过 rowid 失去对应的数据。如果没有建设索引的话，无论点查问或者范畴查问，都须要全表扫描。2.2.2 索引组织表咱们能够看到，堆文件的索引只能索引到对应的 rowid，如果须要获取数据的话，还须要一次间接援用 (如果页面不在内存中，则是一次额定的 IO) 能力获取到数据。如果一张表次要的查问场景都是通过主键进行查问的话，咱们能够抉择另外一种索引文件的组织形式，即索引组织表。索引组织表最大的特点就是，通过在主键上建设索引(B+Tree)，并在索引叶子页面上间接存储数据，而非 rowid，融主键索引和表数据为一体。索引组织表反对其余二级索引(Secondary Index)，只不过与堆文件不同的是，二级索引中存储的不是 rowid，而是行的主键。二级索引通过查问到记录的主键之后再拜访主索引获取行记录。索引组织表的各项操作均通过主索引进行，查问或者插入数据均须要从 B + 树的根节点开始，始终到叶节点的数据页面上，而后再进行对应的操作。

2.2. 索引咱们常见的内存索引有很多种，如 HashTable, SkipList, BinaryTree, B+Tree 等，然而在传统数据库畛域，基本上只有 B + 树一种，B+ 树能够说是页面为单位组织数据的数据库架构的基石。究其原因，次要还是因为 B + 树各项操作的均衡性，无论是点查问，范畴查问，还是插入，删除等，B+ 树均能在可承受的 IO 代价内实现。与之相比，以 HashTable 为例，HashTable 反对很高效的点查问，然而对范畴查问则只能全表扫描；对插入操作来说，HashTable 最大的问题是，Hash 桶难以动静扩张。当插入数据量大的时候，如果对 Hash 桶的设置不适合，则将导致读取操作 IO 数急剧减少；如果进行 rehash，则代价微小，难以承受。2.2.1 B+ 树根本性质 B + 树由叶结点和非叶节点组成。数据库中应用到的 B + 树，叶结点和非叶节点个别都是以一页为单位，二者构造相似，只不过寄存的信息稍微有所不同。对于非叶节点，一个页面大小的空间中，会寄存一些管制信息，通常放在 Page Header 中，剩下则是 Payload 信息。Payload 信息中寄存着 K 个 KEY 和 K + 1 个子节点的指针(PID, page_id)。有些实现为了不便，会额定减少一个 INVALID_KEY，这样非叶节点的 KEY 和指针个数能够一一对应。对于叶结点，其 Page Header 中除了一些管制信息之外，还会寄存其左右兄弟的指针，这样整个 B + 树的叶结点能够通过左右兄弟指针进行遍历。如果该 B + 树是咱们前文讲的索引组织表的话，那么叶结点中寄存的是实在的行数据。如果是 Secondary Index 的话，寄存的是索引的 KEY 和表的主键值(如果是 Heap File 的索引的话，是 rowid)。B+ 树的 KEY 能够是一行的某一列，也能够是多个列。B+ 树要求所有节点中寄存的 KEY 都必须是有序的。对于非叶节点中的某个，其左子树的任一 KEY 为，右子树的任一 KEY 为，那么满足：

2.2.2 B+ 树基本操作 2.2.2.1 查找 B + 树的查找从根节点开始，逐层往下查找直到叶结点。依据每一层的 KEY 都是有序的特点，能够抉择进行二分查找(KEY 较少的状况下也能够间接遍历)。找到第一个大于查找元素的 KEY，其左子树即是下一层要搜寻的节点。

2.2.2.2 插入 B + 树的插入也须要先通过查找找到元素须要被插入的叶结点。如下图，咱们插入 25，通过逐层二分查找之后，找到 31 这个值的为地位。如果叶结点有闲暇空间能够插入，那么只须要把插入元素放进适合插入地位就行了。如果叶节点曾经满了的话，须要对该节点进行决裂。决裂办法是将以后已满的叶结点一分为二，而后在适合的地位搁置待插入的元素。最初像父节点插入新决裂进去的叶结点的第一个 KEY。如果父节点也是满的，那么须要递归对父节点进行决裂，这一过程有可能继续到根节点也被决裂，此时 B + 树的高度被升高了一级。

2.2.2.3 删除 B + 树的删除操作一样也须要先通过查找找到待删除元素所在的叶结点，而后进行删除操作。如果待删除元素不是叶结点中惟一的元素，那么间接删除待删除元素即可。如果待删除元素是该叶结点中的惟一元素，则须要将该叶结点也删除掉，回收空间用于后续再次利用。此时咱们须要将该元素的父节点对应的 KEY 也删除掉。对父节点的删除也可能引发对父节点的删除操作，这一过程可能递归始终到根节点。如果根节点调整后只剩下一个子节点，那么咱们能够将根节点也摘除掉，并将根节点的惟一子节点晋升为根节点。此时 B + 树的高度被升高了一级。

2.2.3 B+ 树并发策略咱们后面讲 B + 树的基本操作都是在没有思考并发的状况下，在实在的数据库实现中，B+ 树往往是被并发读取的。一张表会被多个申请同时读写，对应数据库中多个线程同时在并发读取整棵 B + 树。无论读还是写操作，咱们都须要适当的加锁 (latch) 能力保障并发读写的平安。最间接的想法当然是对整棵树加读写锁，读加读锁 (RL)，写加写锁(WL)。这种做法读写尽管都平安了，然而并发都太低，性能不好，咱们须要更粗疏的桎梏计划以失去更好的并发。咱们来剖析 B + 树的写操作(插入和删除)：大多数状况下，写操作不引发决裂或者节点摘除的状况下，只须要操作指标元素所在的叶结点即可，此时咱们只须要对该叶结点加写锁就能够了。随机状况下，一个叶结点均匀插入或者删除 N 次，才会引发一次决裂或者摘除。此时咱们须要对以后叶结点的父节点也进行写操作，此时咱们须要对父节点也加写锁。即父节点被加写锁的概率是子节点的 1 /N。有了上述察看，咱们来看罕用的 B + 树并发策略(Crabbing 协定)。2.2.3.1 读操作(查找) 读操作从根节点开始，一一节点进行加读锁，进行元素查找，获取子节点读锁，而后开释读锁的过程。如一开始获取根节点读锁，查找到 KEY 呈现的子节点，而后获取子节点的读锁，再开释根节点的读锁。

2.2.3.2 写操作 (插入或删除) 对于写操作，也是从根节点开始，先获取根节点的写锁，进行元素查找，找到子节点后获取子节点写锁。获取到子节点写锁之后，须要查看父节点是否平安，如果平安则能够开释所有父节点的写锁。所谓平安，即子节点的操作是否会引起父节点的写入。如某个节点 X 能够包容的最大元素 (叶结点为 KEY 个数，非叶节点为子节点个数) 是 N，以后元素个数为 K，1 < K + 1 < N，那么咱们晓得，无论 X 的子节点如何决裂或者摘除，X 的父节点都不会受影响，因而咱们能够平安的开释 X 的所有父节点的写锁。

3.1. ShardingSharding 技术在 PC 互联网时代应用较多，常见的各类数据库中间件，如淘宝的 TDDL 等，就采纳的这种计划。这种计划实质是由应用层去感知底层数据库的分库分表信息，而后在应用层确定查问的路由，并合并查问的后果。写入数据时也由应用层本人来保障波及到多个分库时的事务的胜利。Sharding 计划肯定水平上解决了数据库存储的瓶颈，然而对于数据计算的瓶颈，依然未能解决。3.2. Share-Storage 目前这种计划简直是有自研数据库 (微软 /Google) 的云服务厂商之外的其余厂商的标配，典型代表有 Amazon Aurora，腾讯云 TDSQL-C，以及阿里云的 PolarDB-1.0。这种计划的特点是一写多读，多个计算层实例共享底层存储服务，且由底层存储服务来解决数据的一致性，从而简化计算层的逻辑。以已公开论文的 Aurora 为例，其实现有如下特点：充分利用云服务厂商的基础设施，共享存储层简直都是建设在云服务厂商提供的云存储之上。充分利用开源代码，云服务厂商能够将开源数据库 (MySQL，PostgreSQL) 代码与本人研发的存储层充沛联合。在一套存储层基础设施的根底上，通过替换 MySQL, PostgreSQL 的存储层，从而能够在一套存储上反对多种数据库，且能做到 100% 兼容。因为对 SQL 和事务层代码未做大调整，这种计划都只反对单节点写入。通过底层存储服务解决数据存储的可靠性和可扩大的问题，通过减少多个只读副原本解决读 QPS 可扩大的问题。写入节点与只读节点之间，写入节点与存储层之间，通过事务的原始 redo log 进行同步，效率比 MySQL 多正本之间通过 bin log 进行同步高了十分多。

Share Storage 的计划解决了存储和读的可扩大，但仍然存在单点写入瓶颈。云服务厂商采纳这种计划有着本人十分事实的思考：这种计划能够复用开源数据库大部分代码，且能做到 100% 兼容 (不仅 SQL 兼容，行为也兼容)，充沛升高了开发难度，属于一个十分适合的折中。100% 兼容多种开源数据库，对于以 MySQL, PostgreSQL 等为主的互联网中小企业而言，简直能够做到无感迁徙。对存储和读申请做了充沛的扩大，单点写入，也是思考到实现难度，兼容性，以及客户个性的折中。应用云服务的少数都是互联网中小客户，绝对写入扩大，对读和存储扩大的需要更大一些。3.3. Share-Nothing 目前支流的分布式数据库，即所谓 ”NewSQL” 数据库的实现，多采纳了 Share Nothing 的架构。这类架构数据库实例之间不共享存储，本人治理本人分区的数据。这是一种齐全不同于过来的全新的关系数据库架构，须要从 SQL，事务，存储等各个子系统都思考到扩展性。这类零碎的第一个实现是 Google 的 Spanner(Spanner2012)，但 Spanner 反对的存储模型并不是关系模型，因而 Google F1(F12013) 又在 Spanner 的根底上实现了对 SQL 的反对，成为了一个残缺的分布式关系数据库。受此启发，国内互联网企业受制于传统数据库 Oracle 的限度，也纷纷开始了本人的研发打算。目前国内曾经商用的分布式数据库次要有三个实现，即阿里系蚂蚁团体的 OceanBase 和阿里云的 PloarDB-X(即 PolarDB-2.0)，以及独立数据库开发商 PingCAP 的 TiDB。这类分布式数据库都采纳了 LSM 树用于构建底层的存储系统，下层通过 Paxos 或者 Raft 协定来保障多个正本之间的一致性，通过主动的数据分区 (可类比 MySQL 的分表) 来解决不同分区数据的并行写入，同时通过两阶段提交协定来反对跨分区的多机事务。这类实现对存储和读写申请的扩大都有了十分好的反对，能够说从根本上解决了数据库可扩大的问题。以 TPCC Benchmark 的后果看，排在榜单第一的 OceanBase 的的事务 (写操作) 解决能力，曾经是传统数据库 Oracle 的 20 倍。

OceanBase 能取的这样的 TPCC 榜单问题，正是得益于分布式数据库的可扩大能力。整个零碎的事务处理能力能够随着部署实例的减少线性扩大，而传统的数据库则做不到这一点。但这类数据库研发门槛高，同时，LSM 树本身的 Compaction 机制，会导致在 Compaction 时，会占用十分大的 CPU 和 IO，因而这类数据库须要对 Compaction 的机会和策略有十分粗疏的设计，否则会显著影响到零碎的稳定性。对于 LSM 树的原理及各类操作，会在本系列的第二篇文章《数据库存储与索引技术（二）分布式数据库基石——LSM 树》中进行具体介绍。参考文献 1. 传统数据库《数据库管理系统实现根底讲义》:https://github.com/oceanbase/oceanbase/blob/master/docs/docs/lectures/index.mdPostgreSQL 物理存储介绍：http://rachbelaid.com/introduction-to-postgres-physical-storage/《MySQL 技术底细》：https://book.douban.com/subject/24708143/《MySQL B+ 树并发管制机制前世今生》：http://mysql.taobao.org/monthly/2018/09/01/《Coarse-Gr Coarse-Grained, Fine-Gr ained, Fine-Grained, and Lock-F ained, and Lock-Free Concurr ee Concurrency Approaches for Self-Balancing B-Tree》: https://digitalscholarship.unlv.edu/cgi/viewcontent.cgi?artic… Share Disk 架构 Aurora 原始论文:https://www.allthingsdistributed.com/files/p1041-verbitski.pd… Aurora 解读：https://dbaplus.cn/news-160-1748-1.htmlAmazon Aurora 解读 2: https://blog.acolyer.org/2019/03/25/amazon-aurora-design-cons… 腾讯云 TDSQL- C 架构解析:https://www.modb.pro/db/536423. OceanBase TPCC 测试 OceanBase TPCC 后果：http://tpc.org/tpcc/results/tpcc_results5.asp?print=false&ord… TPCC 测试细节：https://developer.aliyun.com/article/761887