分布式数据存储

于各种各样的原因,将数据库分布到多台机器上:

共享架构:通过共享数据存储的方式来进行扩展

无共享架构:通过水平扩展来提升性能

分区与复制同时使用

复制

几乎所有的存储系统和数据库,都是用复制状态机这一套方法来解决备份恢复和数据复制问题

202251611343

分片元数据的存储:

  1. 静态分片:分片过程中,元数据不会发生变化的情况下,将元数据复制多份放在对应的工作节点上的分片方式
  2. 动态分片:在寻址过程中会不断地更新分片元数据,促成各节点元数据达成一致

如无必要,勿增副本:避免人为引入不一致性

主从复制

主从复制

同步复制或是异步复制

同步复制的问题在于主库需要确认从库写入成功,才会响应客户写入成功

新从库加入:通过读取快照 + 追赶快照后的变更方式来达到可用性与一致性的折中

如果想追求强一致性,其必须使用"顺序投票"的方式来保证日志的一致性和正确性,每个节点必须按照一定的顺序将日志追加到本地的日志中,然后将其发送给其他节点进行复制。在这个过程中,如果有一个节点的复制过程出现了问题,比如网络故障或者节点故障,那么后续的节点都必须等待它完成复制,否则就会产生日志的空洞,所以不同的事务无法并行

tidb通过以下几点优化了raft:

  1. 批操作(Batch):Leader 缓存多个客户端请求,然后将这一批日志批量发送给 Follower
  2. 流水线(Pipeline):Leader 本地增加一个变量(NextIndex),每次发送一个 Batch 后,更新 NextIndex 记录下一个 Batch 的位置,然后不等待 Follower 返回,马上发送下一个 Batch
  3. 并行追加日志(Append Log Parallelly):Leader 将 Batch 发送给 Follower 的同时,并发执行本地的 Append 操作
  4. 异步应用日志(Asynchronous Apply):异步更新数据

节点宕机恢复

  1. 从库挂了:重连主库后追赶恢复
  2. 主库挂了:故障切换

故障切换带来的问题:

复制日志实现

复制延迟

如果停止写入数据库并等待一段时间,从库最终会赶上并与主库保持一致。出于这个原因,这种效应被称为 最终一致性(eventually consistency)

读己之写一致性防止的:写入主库 从库还没同步就被用户读取到了

为了保证读己之写一致性(read-your-writes consistency),使用这么样几个方法:

读写一致性

自己写入成功的任何数据,下一刻一定能读取到,其内容保证与自己最后一次写入完全一致

单调读一致性

一个比强一致性(strong consistency)更弱,但比最终一致性(eventually consistency)更强的保证,保证每次读取的数据不会比上一次读取的老。

单调读防止的:第一次看到最新内容 第二次却看到了老的内容

实现的一种方式是确保每个用户总是从固定的副本读取数据

前缀读一致性(consistent prefix reads)

如果一系列写入按某个顺序发生,那么任何人读取这些写入时,也会看见它们以同样的顺序出现

复制的延迟导致后写的数据反而比先写的更早被看到

线性一致性

建立在事件的先后顺序之上的。在线性一致性下,整个系统表现得好像只有一个副本,所有操作被记录在一条时间线上,并且被原子化,这样任意两个事件都可以比较先后顺序

因果一致性

这种一致性模型确保了系统的状态演变符合事件的因果顺序,即,如果一个操作A因果上影响了另一个操作B,那么系统中的所有节点必须在执行B之前看到A的结果

多主复制

应用场景:

写入冲突

202139103032

为了解决这个问题,写入时使用一个主库来避免冲突

如果无法避免冲突,则使用冲突合并:

  1. 丢弃比较老的写入 也就是最后写入者获胜
  2. 参考git,记录冲突并在应用层处理

冲突解决逻辑:

  1. 写时执行:测到复制更改日志中存在冲突,就会调用冲突处理程序
  2. 读时执行:当检测到冲突时,所有冲突写入被存储。下一次读取数据时,会将这些多个版本的数据返回给应用程序。应用程序可能会提示用户或自动解决冲突

多主复制拓扑结构

202139143850

前两种拓扑结构会出现单点故障,而最后一种虽然不会单点故障,但是如果不特别处理,很容易就会出现写入顺序不一致的问题

错误的写请求到达数据

无主复制

客户端可以自由选择节点进行写入,这个被选择的节点充当协调者,将数据写入到自身或者其他节点

为了解决旧节点重新上线造成的新老节点数据不一致问题,不仅写需要写入到所有节点,同时读也要读多个节点,以此来判定数据的最新值

读写quorum

写操作只有法定票数节点成功才会认为最终写入成功,而读操作也通过读取所有,取法定票数的值作为最终结果

这个值一般为过半 也就是如果有3个节点 则法定票数为2 当然为了性能可以降低法定票数 但可以容忍的故障节点就会降低

这种方式的一些问题:

检测并发写

为每个写入附加一个时间戳,挑选最“最近”的最大时间戳,并丢弃具有较早时间戳的任何写入。这种冲突解决算法被称为最后写入胜利(LWW, last write wins)

客户端写需要带上上次的版本号,当发现不是最新的,服务端返回最新版本的值由客户端进行合并

需要注意的是如果新版的数据增加值,那还好办,但是如果新版的数据是删除了数据,则需要引入墓碑机制,标志哪些数据被删掉了

版本号用来比较数据 版本矢量用来比较状态

分区

202131015533

键值数据分区

如果分区不公平,则会产生偏斜(skew),进而出现高负载的热点(hot spot)。避免这个问题的最简单方式是随机分配数据的节点,但这样的话必须并行查询所有节点以获取数据。

2021310151228

如果单纯使用散列值进行分区会无法进行范围查询,所以一种折中的方式是使用多个列,主键进行散列,次键用来进行范围查找

哈希能有效帮助减少热点,但还不够,为了消除某些极端情况诸如单个键的数据热点,可以对散列键加上随机数,让其继续分布存储在不同的分区中。

普通哈希可以均衡数据分布,缺点就是扩展性不好,一致性哈希扩展性好,但是仍无法处理业务热点。

范围分区也只支持静态分片,虽然可以预估业务热点,但无法根据业务灵活调整

动态分区可以自动完成分裂与合并,也可以根据访问压力调度分片,只有动态了,才能自适应各种业务场景下的数据变化,平衡存储、访问压力、分布式事务和访问链路延时等多方面的诉求

对于 NewSQL 来说,分片是高可靠的最小单元;而对于 PGXC,分片的高可靠要依附于节点的高可靠,NewSQL 架构下,分片采用 Paxos 或 Raft 算法可以构成复制组,这种复制机制相比 PGXC 的主备节点复制,提供了更高的可靠性

二级索引

基于分区的二级索引

基于分区的二级索引需要查询所有分区,再进行合并

基于词条的二级索引

基于词条则特定的索引都会在特定的分区,可避免查询所有分区

分区再平衡

将负载从集群中的一个节点向另一个节点移动的过程称为再平衡(reblancing)

几个最低要求:

策略

最差的方案

hash mod N

这种方案一旦节点数量发生变化,所有数据都得全部移动

固定数量分区

2021310154640

当新增节点时,每个节点分出一定的分区给新节点

当减少节点时:减少节点上的分区由剩下的节点分担

动态分区

按键的范围进行分区的数据库会动态创建分区。当分区增长到超过配置的大小时,会被分成两个分区,每个分区约占一半的数据。与之相反,如果大量数据被删除并且分区缩小到某个阈值以下,则可以将其与相邻分区合并

按节点比列分区

当一个新节点加入集群时,它随机选择固定数量的现有分区进行拆分,然后占有这些拆分分区中每个分区的一半,同时将每个分区的另一半留在原地

自动化再平衡的问题

完全自动化的再平衡可能会出现问题,如某些节点过载被认为宕机,此时将其的负载分摊到其他节点上面,这可能会导致节点和网络造成额外的负载,从而使情况变得更糟。再平衡的过程中有人参与是一件好事。这比完全自动的过程慢,但可以帮助防止运维意外

请求路由

2021310155412

为了获取整个集群的元数据情况,有两种方式:

  1. 通过如zk这样的元数据管理服务
  2. 使用如gossip这种协议

透明性

数据对于用户来说如果是透明的:

实现上述透明性的方式是引入命名服务器,或者称之为元数据库