系统架构设计之数据库的核心数据结构

系统架构设计之数据库的核心数据结构

从最基本层面看，数据库只需做两件事：

向它插入数据肘，它就保存数据之后查询时，返回那些数据

本文讨论如何存储输入的数据，并在收到查询请求时，如何重新找到数据。

为何关注数据库内部的存储和检索呢？你不可能从头开始实现存储引擎，往往需要从众多现有的存储引擎中选择适合业务的存储引擎。为针对特定工作负载而对数据库调优时，就得对存储引擎底层机制有所了解。

针对事务型工作负载、分析型负载的存储引擎优化存在很大差异。

事务处理与分析处理”和“面向列的存储”部分，分析型优化的存储引擎。

先讨论存储引擎，用于大家比较熟悉的两种数据库，传统关系数据库和NoSQL数据库。研究两个存储引擎家族 ，即日志结构的存储引擎和面向页的存储引擎，比如B-tree。

数据库核心：数据结构

最简单的数据库，由两个Bash函数实现：

#!/bin/bashdb_set() { echo "$1,$2" >> database}db_get() { grep "^$1," database | sed -e "s／^$1,//" tail -n 1}

这两个函数实现一个K.V存储。当调用 db_set key value，它将在数据保存你所输入的key value key value几乎可以是任何内容。例如值可以是JSON文档。然后调用db_get key，它会查找与输入key相关联的最新值并返回。

例如：

$ db_set 123456 '{"name":"London", "attractions":["Big Ben","London Eye"]}'$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'$ db_get 42 {"name":"San Francisco", "attractions":["Golden Gate Bridge"]}

它底层的存储格式其实非常简单：一个纯文本文件。其中每行包含一个K.V，用逗号分隔（大致像一个csv文件，忽略转义问题）。每次调用db_set，即追加新内容到文件末尾，因此，若多次更新某K，旧版本值不会被覆盖，而需查看文件中最后一次出现的K来找到最新V（因此在db_get中使用tail -n 1）。

$ db_set 42 '{"name":"San Francisco", "attractions":["Exploratorium"]}'$ db_get 42 {"name":"San Francisco", "attractions":["Exploratorium"]}$ cat database123456,{"name":"London","attractions":["Big Ben","London Eye"]} 42, {"name":"San Francisco","attractions":["Golden Gate Bridge"]}42,{"name":"San Francisco","attractions":["Exploratorium"]}

简单情况，追加到文件尾部方式通常够高效了，因而db_set函数性能很好。类似db_set，许多数据库内部都使用日志（log），日志是个仅支持追加式更新的数据文件。虽然真正的数据库有很多更复杂问题要考虑（如并发控制、回收磁盘空间以控制日志文件大小、处理错误和部分完成写记录等），但基本原理相同 。

日志这个词通常指应用程序的运行输出日志，来记录发生了什么事情 。日志则是个更通用的含义，表示一个仅能追加的记录序列集合。它可能是人类不可读的，可能是二进制格式而只能被其他程序来读取。

另一方面，若日志文件保存大量记录，则db_get性能会很差。每次想查找一个K，db_get 必须从头到尾扫描整个数据库文件来查找K的出现位置。在算法术语中，查找开销是O（n） ，即若数据库记录条数加倍，则查找需要两倍时间。这一点并不好。

为高效查找数据库中特定K的V，需要数据结构：索引。它们背后基本想法都是保留一些额外元数据，这些元数据作为路标，帮助定位想要数据。若希望用几种不同方式搜索相同数据，在数据的不同部分，可能要定义多种不同的索引。

索引是基于原始数据派生而来的额外数据结构。很多数据库允许单独添加、删除索引，而不影响数据库内容，它只会影响查询性能。维护额外结构势必会引入开销，特别是在新数据写入时。对于写人，它很难超过简单追加文件方式的性能，因为那已经是最简单的写操作。由于每次写数据时，需更新索引，所以任何类型索引基本都会降低写速度。

存储系统中重要的trade off

合适的索引能加速查询，但每个索引都会降低写速度。默认情况下，数据库通常不会对所有内容索引 ，它需要SE或DBA基于对应用程序典型查询模式的了解，手动决定索引。就是为应用提供最有利加速同时，避免引入过多不必要的开销。

哈希索引

以KV数据的索引开始。KV类型并非唯一能索引的数据，但随处可见，而且是其他更复杂索引的基础。

KV存储与大多数编程语言所内置的字典结构类似，一般采用hash map或hash table实现。既然已有内存数据结构的hash map ，为何不用它们在磁盘上直接索引数据？

假设数据存储全部采用追加式文件组成，最简单的索引策略：保存内存中的hash map，将每个K一一映射到数据文件中特定的字节偏移量，这就能找到每个值的位置：

图1

每当在文件中追加新的KV对时，还要更新hashma来反映刚写入的数据的偏移量（包括插入新K与更新已有K）。当查找一个值时，使用hashmap找到文件中的偏移量，即存储位置，然后读取其内容。

听着简单，但的确可行。Bitcask（Riak默认的存储引擎）就是这么做的。Bitcask提供高性能读写，但所有K必须能放入内存。而V则可以使用比可用内存更多的空间，只需一次磁盘寻址，就能将V从磁盘加载到内存，若那部分数据文件已在文件系统的缓存中，则读取根本不需要任何磁盘I/O。

Bitcask这种存储引擎适合每个K的V经常更新场景。如：

在这种工作负载下，有大量写操作，但没有太多不同的K，即每个K都有大量写操作，但将所有K保存在内存中还是可行的。

至此，只追加写到一个文件，那如何避免最终用完磁盘空间？可将日志分为特定大小的段，当日志文件达到一定大小时就关闭，并开始写到一个新的段文件中。然后，就能压缩这些段：

图2：压缩KV 更新日志文件，仅保留每个K的最新值

压缩意味着在日志中丢弃重复K，只保留每个K的最近更新。

由于压缩经常会使段更小（假设K在一个段内被平均重写多次），也能在执行压缩时将个段合并：

由于段在写入后不会再被修改，所以合并的段会被写入一个新文件。对这些冻结段的合并和压缩过程可在后台线程完成，而在运行时，仍能继续使用旧的段文件继续正常的读写请求。合并过程完成后，将读请求切换到新的合并段上，旧的段文件就能安全删除了。

每个段现在都有自己的内存哈希表，将K映射到文件的偏移量。为找到键的值，先检查最新的段的 hashmap；若K不存在，则检查第二最新的段，依此类推。因为合并过程可维持较少的段数量，因此查找一般无需检查太多hashmap。

实现难点

(1) 文件格式

CSV不是日志最佳格式，二进制格式更快，更简单。首先以字节为单位，记录字符串的长度，然后跟上原始的字符串（无需转义）。

(2) 删除记录

若要删除一个K及其V，则必须在数据文件中中追加一个特殊的删除记录（有时称为逻辑删除）。合并日志段时，一旦发现逻辑删除标记，就会丢弃这个已删除键的所有值。

(3) 崩溃恢复

若数据库重启，则内存的hashmap将丢失。原则上，可通过从头到尾读取整个段文件，记录每个键的最新值的偏移量，来恢复每个段的hashmap。但若段文件很大，这可能耗时久，这将使服务器重启很慢。Bitcask通过存储加速恢复磁盘上每个段的哈希映射的快照，可以更快地加载到内存中。

(4) 部分写入记录

数据库可能随时崩溃，包括将记录追加到日志的过程中。Bitcask文件包含校验值，这样就能发现损坏部分并丢弃。

(5) 并发控制

由于写是以严格的先后顺序追加到日志，所以常见实现是只有一个写线程。数据文件段是追加的且不可变，所以它们能被多线程同时读取。

追加的日志看起来很浪费：为何不更新文件，用新值覆盖旧值？

追加写设计的优势

追加和分段合并是顺序写，一般比随机写快得多，尤其是在旋转式磁盘。某种程度上，顺序写在基于闪存的 固态硬盘（***） 也很合适若段文件是追加的或不可变的，则并发和崩溃恢复就简单得多。如不必担心在重写值时发生崩溃的情况，导致留下一个包含部分旧值和部分新值混杂的文件合并旧段能避免数据文件随时间推移，数据文件出现碎片化问题

哈希索引的劣势

散列表必须能放进内存若你有很多键，那真是倒霉。原则上，可在磁盘上维护一个hashmap，但磁盘上的hashmap很难表现优秀，需大量随机访问I/O，当hash变满时，继续增长代价昂贵，并且哈希冲突需要复杂处理逻辑范围查询效率不高如无法轻松扫描kitty00000到kitty99999之间的所有K，只能采用逐个查找的方式查询每个K

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。