《数据密集型应用系统设计》阅读笔记(1)

最近在阅读《数据密集型应用系统设计》(Designing Data-Intensive Applications),做些笔记。这是一本讲述存储和分布式系统的书,非常精炼,强烈推荐。

3 数据存储与检索

数据库的核心:数据结构。

3.1 经典索引

3.1.1 哈希索引

哈希索引在内存中储存了key到相应的value在段文件上的offset的映射。段文件中储存了实际的key-value键值对,采用append-only的写方式,新来一个k-v对,就在段文件末尾追加记录。查找指定key对应的value时,只需要在内存中找到指定key的最新offset,然后到对应的段文件中读取value即可。

随着数据量的增加,段文件过大怎么办?

可以当段文件过大时关闭段文件,并新建新的段文件。对段文件可以做压缩,只记录包含的key的最新对应值即可。压缩后,多个段文件可以做多路merge。这些段文件的压缩和merge过程可以在后台进行。

哈希索引要考虑的几个问题:

  1. 文件格式

    采用二进制显然是最好的方案。

  2. 删除记录

    如果要删除一个key-value,需要在段文件中增加一个“墓碑”记录。merge时如果遇到墓碑记录,则丢弃之前这个key的值。

  3. 崩溃恢复

    如果数据库重启,那么内存中的hashmap将丢失。理论上需要扫描所有段文件,恢复出hashmap,会很缓慢。可以考虑储存snapshot。

  4. 并发控制

    写入要求有严格的顺序,通常只有一个写线程,多个读线程。

追加写append-only的考虑:

  1. 顺序写速度>>随机写速度。
  2. 并发和崩溃恢复会简单得多。

局限性:

  1. hashmap必须全量load到内存中;处理冲突。
  2. 区间查询效率不高。

3.1.2 SSTables和LSM-Tree

如果我们将上述段文件内容按照key进行排序,则得到了SSTable。

优点:

  1. 合并段文件更加高效。可以使用k路排序merge算法。
  2. 在文件中查找特定键时,不必保存全量key映射,只需保存部分值即可,然后找最邻近的key,然后从指定offset遍历段文件即可。
  3. 更好的支持区间查询。

内存中的hashmap可以使用树状数据结构,如红黑树或AVL树。我们同意将这种结构称作内存表

存储引擎基本工作流程:

  1. 写入时,将其添加至内存表中。
  2. 内存表到达阈值时,将其作为SSTable写入磁盘。由于树已经是有序的,写磁盘会比较高效。
  3. 读取时,首先查找内存表,然后是最新的段文件,然后是次新的,以此类推直到找到。
  4. 后台周期性合并与压缩段文件。

3.1.3 B-trees

B树的定义略,可以自行网上搜索。

B树的数据单元存储了指定的一个块或页。更新值时,需要查找到对应的页地址,就地修改页内容。如果页内容溢出,则需要分裂页,指定新页,覆盖父页并更新对两个子页的引用。

优化版本:B+tree。只有叶子节点存储数据,且叶子节点间有指针,方便范围查询。

为了做好崩溃恢复,常见B-tree需要支持WAL(write-ahead log, WAL)。想要更新B-tree,首先要更新WAL,再修改真实的页。在崩溃时,WAL将会被用于恢复到最近一致的状态。

3.1.4 比较

B-tree写入时要写2次,一次写WAL,一次写真实页。如果改动很小,也必须写整页。

LSM-Tree写入时一般只需写入到内存表即可,能够承受比B-tree更高的吞吐量。

但是LSM-Tree后台的压缩过程会干扰正在进行的读写操作。压缩时,读写都要挂起。所以LSM-Tree的响应速度不稳定,B-tree则相对稳定得多。

如果写入吞吐量高,压缩所需的磁盘带宽就会越来越高,读写速度会降低。

B-tree的优点还在于可以较为方便地提供事务语义。(通过键上的锁实现)

3.2 数据仓库

OLTP和OLAP。

3.2.1 列式存储

在经典关系型数据库存储中,一行的数据是作为一个整体被储存。在列式存储中,每一列的数据都被单独地存储。通常,列中的不同值的数量远小于行数。可以使用n个不同值的bitmap,一个bitmap对应一个不同的值。如果行具有该值,则为1;反之则为0。通常bitmap会很稀疏。还可以对bitmap进行游程编码。


5 数据复制

5.1 主节点与从节点

主从模式:一个主节点,多个从节点。主节点可以写入和读取;从节点只支持读取。

大部分关系型数据库内置支持主从复制,如MySQL, PostGreSQL等。一些分布式消息队列也支持主从复制,如Kafka, RabbitMQ等。

5.1.1 同步复制和异步复制

同步复制:主节点收到写入请求时,首先写入自己的硬盘中,然后将写入信息传递给从节点。当收到从节点的完毕信号时,返回完毕信号。优点:保持数据一致性。缺点:阻塞读写。

异步复制:写入主节点后就返回完毕信号。

一般不会将所有节点都配置成为同步复制。

5.1.2 配置一个新的从节点

  1. 在某个时间点产生一个主节点的snapshot
  2. 将snapshot拷贝到从节点
  3. 从节点连接到主节点,并请求快照点之后所发生的的数据更改日志。(MySQL将其成为binlog coordinates)
  4. 获得日志后,从节点开始apply这些变更,这个过程称为catch up。

5.1.3 处理节点失效

5.1.3.1 从节点失效

从节点重启后,确定自己处理的最后一笔事务号,从主节点拉取该事务后的所有更改。

5.1.3.2 主节点失效

  1. 通过心跳、超时等机制确认主节点失效。
  2. 选举新的主节点,这是一个共识问题。
  3. 客户端将请求发送给新的主节点。如果原失效主节点重新上线,则需要一种机制来自动降级为从节点。

一些问题:

  1. 如果开启了异步复制,主节点崩溃,就无法确保更新持久化的承诺。
  2. 达成共识的过程中有可能出现脑裂问题。

5.1.4 复制日志的实现

5.1.4.1 基于语句的复制

直接复制该条sql语句,作为一条log进行同步。存在一些问题:

  1. 如果语句是非确定性的,如包含NOW()/RAND()函数,那么在从节点上将产生不同的结果。
  2. 如果语句依赖现有的数据,那么日志的顺序必须被严格保证。

MySQL 5.1之前采用该方法。

5.1.4.2 基于WAL的复制

将一条WAL作为一条log进行同步。由于WAL是一种相当底层的描述,包含了哪些磁盘块的哪些字节发生改变,使得复制方案和存储系统耦合。

5.1.4.3 基于行的逻辑复制

哪些行更新了,就产生这些行的逻辑log,进行同步。如一条update语句更新了10条记录,则产生10条log进行同步。

MySQL的binlog采用该方式。

5.1.4.4 基于触发器的复制

触发器支持以hook的方式注册自定义方法进行同步。

5.2 复制滞后问题

复制滞后导致数据不一致。

3个问题如下。

5.2.1 读自己的写

读自己的写,结果没读到。因为写到了主节点,却只读了从节点。

一种解决方法:强制指定读主库。

5.2.2 单调读

单调读一致性,弱于强一致性,强于最终一致性。单调读保证,多次读的时候不会发生回滚现象。

一种实现方式:读的时候总是从固定的统一副本读。

5.2.3 前缀一致性

这是分片(分区)数据库发生的一个特殊问题。写入A、B两条消息。A被写到了分区1的主节点,B被写到了分区2的主节点,虽然分区各自有序,但是全局不一定有序。写入时,先A后B,读取时,可能就变成了先B后A。

5.2.4 复制滞后的解决方案

  1. 在应用层解决。缺点:复杂且容易出错。
  2. 使用事务。缺点:在分布式数据库上性能极差。

5.3 多主节点复制

适用场景:

  1. 多数据中心
  2. 离线客户端操作
  3. 协作编辑

5.3.1 处理写冲突

处理方法如下:

5.3.1.1 同步与异步冲突检测

无法采用异步冲突检测。因为只能在稍后的时间点上才能检测到,为时已晚。

同步冲突检测将丧失多主节点的优势。

5.3.1.2 避免冲突

避免发生冲突。写的时候路由到相同的数据中心主节点,这等价于主从复制模型。

5.3.1.3 收敛于一致状态

一些解决方法:

  1. 根据规则决定哪个写入是最终的答案,如时间戳最晚的写入有效。容易造成数据丢失。
  2. 保留多个写入结果,然后依靠应用层的逻辑来事后解决冲突。可自定义冲突解决逻辑。
    1. 在写入时执行
    2. 在读取时执行

5.3.2 拓扑结构

  1. 环形拓扑
  2. 星形拓扑
  3. All-to-all拓扑(每个主节点连接了其他所有的主节点)

环形和星形拓扑的问题是,如果单点故障,那么会影响其他节点的复制。

全链路拓扑的一个问题是,每条链路的速度不同,可能造成到达某节点的多个写入乱序的问题。

5.4 无主节点复制

5.4.1 节点失效时的读写

节点失效时,如果要写,并发写入多个节点,只要其中一部分节点写入成功即可返回。如果要读,并发读取多个节点,采用版本号确定使用哪个值。

5.4.1.1 读修复和反熵

当一个失效节点重新上线,它如何赶上中间错过的哪些写请求呢?

  1. 读修复

    当client并行读取多个副本时,如果发现过期数据,则将新值更新到该副本上。适合被频繁读取的场景。

  2. 反熵过程

    后台进程不断寻找副本之间数据的差异,并复制新值到旧副本上。此过程并不保证以特定顺序赋值写入,并且会引入明显的同步滞后。

5.4.1.2 读写quorum

如果有n个副本,写入需要w个副本确认,读取需要r个副本确认,只要w+r>n,则读取的节点中一定包含最新值。在Dynamo风格的数据库中,n/w/r通常可配置。一个常见的选择是n是某奇数,w=r=(n+1)/2(向上取整)。也可以灵活配置,例如对于读多写少的负载,设置w=n和r=1比较合适。

条件w+r>n定义了系统可容忍的失效节点数。

5.4.2 Quorum一致性的局限性

其实也可以配置w+r<=n以换取更高的性能,但是一致性可能就不能得到保证。

在w+r>n的情况下,也可能出现返回旧值的情况:

  1. 如果两个写入同时发生,则无法明确先后顺序。如果用时间戳判定有效性,则由于时钟偏差问题,某些写入可能会被错误地抛弃。
  2. 读和写同时发生,写可能只在一部分副本上完成。读取时读的是新值还是旧值无法确定。
  3. ...

5.4.2.1 宽松的quorum和回传

在一个大规模集群中,client在网络中断期间还能连接到某些数据库节点,但这些节点又不是能满足数据仲裁的那些节点,此时如果我们接受该请求,只是将他们暂时写入到一些可访问的节点中(这些节点并不在这n个节点范围中),那么我们就称之为放松的仲裁(宽松的quorum)。

一旦网络问题得到解决,临时节点会将数据全部发送到原始主节点上。(回传)

Sloppy quorum对提高写入可用性非常有用,但读取时并不保证能读取到最新的值。

5.4.3 检测并发写

Dynamo风格的数据库允许多个client对相同主键发起写操作,即使采用严格的quorum机制也可能发生写冲突。严格来说,是在并发写入时缺乏顺序性保证。

5.4.3.1 最后写入者获胜

强制对并发写排序,在写入时附上一个时间戳。只采用最新的时间戳写入。Last Write Wins。但是牺牲了数据持久性,因为每个写都报告了成功。

要确保LWW无副作用的唯一方法是,只写入一次然后将写入的值视为不可变。如Cassandra将uuid作为主键,每个写操作都针对不同的、系统唯一的主键。

5.4.3.2 Happends-before关系和并发

两个操作A和B,如果B知道A,或者B依赖A,就称A在B之前发生。如果两个操作都不在对方之前发生,则称两个操作是并发的。

5.4.3.3 确定先后关系

购物车问题。

对于2个并发写的客户端,使用一个版本号即可解决问题。

对于多个并发写的客户端,使用vector clock。


6 数据分区

6.1 数据分区和数据复制

分区通常和复制结合使用。

6.2 key-value数据的分区

6.2.1 基于关键字区间分区

优点:轻松支持区间查询。缺点:导致热点数据的产生。

6.2.2 基于关键字哈希值分区

优点:均匀。缺点:丧失了区间查询特性。

6.2.3 负载倾斜与热点

哈希分区可以减轻热点,但不可完全避免。只能寄希望于应用层来处理热点。如在关键字开头或结尾添加随机数进一步分散。但读取也相应需要额外的工作。

6.3 分区与二级索引

key-value模型相对简单,即都是通过关键字来访问记录,自然可以根据关键字来确定分区,并路由到该分区上。

二级索引会变得复杂,它通常不能唯一确定一条记录,而是用来加速特定值的查询。是Solr和ElasticSearch等全文索引服务器存在的根本。

6.3.1 基于文档分区的二级索引

每个分区完全独立,各自维护自己的二级索引id列表。每当写入时,只更新所在分区的二级索引。所以每次查询时,需要将查询发送到所有分区,然后合并所有返回的结果。这个过程称为分散/聚集(scatter/gather)。可能会造成读延迟显著放大。

MongoDB/Riak/Cassandra/ElasticSearch/SolrCloud/VoltDB都采用这种方式。

6.3.2 基于词条的二级索引分区

按照索引的关键词进行分区。比如color:red和color:green就处于不同的分区。当查询时,只需要按照确定查询词所在的分区,然后只请求那个分区即可。问题在于更新文档时,需要跨分区更新很多索引,引入显著的写放大。所以现有的数据库都不支持同步更新二级索引。

6.4 分区再平衡

6.4.1 动态再平衡的策略

6.4.1.1 为什么不用mod?

因为在节点数变化时,取模会造成大量关键字的迁移。

6.4.1.2 固定数量的分区

创造远超实际节点数的分区,每个节点包含多个分区。这样在节点变动时,就可以迁移分区。关键字和分区的对应关系仍不变。

Riak/ElasticSearch支持这种方案。

6.4.1.3 动态分区

一开始只有一个分区,当分区数据增长超过一个阈值时,就分裂成两个分区。相反,如果大量数据被删除,分区小于某个阈值时,可以进行分区合并。有点像b树。

6.5 请求路由

有几种不同的处理策略:

  1. 允许client连接任意的节点,如果是正确分区,则返回对应数据;如果不是正确分区,则转发给正确分区,并作为proxy返回数据。
  2. 将所有请求都发到路由层,由其负责将请求转发到正确的分区节点。
  3. 由client感知分区和节点分配关系,client会直接连接到正确的分区节点。