DBs replication

replication的定义：在不同的联网的机器上，保存相同的数据。

需要replication的理由

  • 使数据地理上离用户更近
  • 保障系统的可用性
  • 应付大量的读请求

replication的主要难点在于处理数据的变更。

在实现replication的时候，有许多可以权衡的点：同步或者异步，怎么处理失效的replicas。

主从模型

被好多数据库产品采用：mysql， PostgresSQL，MongoDB，RethinkDB。

同步异步

其中的一个重要的细节：备份是同步还是异步发生的，在关系数据库中，这个选项大多是可配置的，其他的数据库，一般会选择其中一种情况。所有的从节点的同步，无论是全同步，或是全异步都有问题：全同步的情况，如果一个节点断了，就会导致整个系统的写入变慢；全异步的情况，数据又容易丢失。一般采用混合的方式：一个从同步写，其他的采用异步，如果同步写的从节点断线了，可以立刻用其他的节点来补上，这样的方式，通常被叫做：semi-synchronous 。在持久性上的弱化，莫阿斯

新增从节点

不管是扩容还是替换掉废节点，都需要做这个操作。怎么保证新增的从节点和主节点的同步？

在不停服务的情况下，一般这样操作：

1 获取主节点某个时刻的snapshot。

2 复制这个snapshot到新增的从节点。

3 新从节点和主节点获取时间点之后的所有更新。这个需要一个准确的位置，在PostgresSQL中叫’log sequence number’，在mysql中叫‘binlog coordinates’。

4 当从snapshot开始的所有数据变更都被同步了之后，这个从节点可以像正常的从节点一样了。

处理节点掉线

为了保证整个系统长时间运行，需要有这样的能力，保证任何节点 （主从）挂掉都不会影响整个系统的可用性。

从节点挂掉：Catch-up recovery

被重新启动的从节点会向主节点请求这期间的所有数据改动。

主节点挂掉：Failover

失效转移可以人工或者自动执行。但都包含以下几步：

1 主节点的失效检测

2 选举出新的主节点

3 修改配置，使用新的主节点

但是也存在很多难以解决的问题：

1 在异步同步的情况下，如果保障选出的新leader有最新的更新。

2 丢弃的写操作很危险。

3 脑裂

4 主节点失效检测的timeout选取

复制日志(replication log)的实现

1 Statement-based replication

最简单的方式，主节点记录所有收到的请求，并转发给从节点。mysql 5.1 之前都在用这种方式。

2 Write-ahead log (WAL) shipping

几乎都在使用WAL日志，不管是log-structured 存储引擎（SSTable 和 LSM-tree）还是B-tree存储引擎。

但还是有他的坏处：太底层了。一条WAL日志记录了一个磁盘block上的某个byte的变更。这个坏处导致了relication和存储引擎的实现耦合太紧。

3Logical (row-based) log replication

也就是logical log，和底层的存储引擎解耦。 Mysql的binlog(when configured to use row-based replication) 就是这一类。

4 Trigger-based replication

这种方式，一般是依赖外部工具来实现，更容易带来bug，但是更灵活。

read-after-write consistency

写入后，由主从同步的延迟，可能读不到写入的变更。 read-after-write consistency可以防止这样的情况 .

怎么做到这种一致性：有这样几种思路， 1 任何可能被当前用户修改的数据的读取，都从主节点进行。举个例子：用户的profile，我们就可以永远从主库读取自己的profile， 从从库读取他人的profile。2 如果上面的方法不行，可以记录updatetime，然后在每次写入后的一段时间内都读取主库。3 客户端可以记录一个它最近一次写操作的“时间戳”，然后，每次读取的时候都带着这个“时间戳”。系统来保障，服务读请求的从节点，自身同步过的写操作的“时间戳”要大于读请求中带着的。4 如果涉及到多数据中心，会更加复杂。

Monotonic Read（单调读）

当一个客户端多次进行读时，他不会感觉到时间倒流，每次读到的结果一定是相同的或者更新的。

一个实现的方法是：保障每个客户端被绑定在一个replica上，

Consistent Prefix Reads

确保的是：无论任何一个客户端，他读到的写操作的顺序是和实际的写入顺序是一致的。

多主模型

之前说的都是单主模型：只有一个主节点接受写操作。但是如果因为什么原因无法连接上主节点，导致的结果就是，无法向数据库写入。自然的，产生了多主模型。

使用场景

1 多数据中心：每个中心一个leader。这样比单leader有不少好处，但是相应的坏处是：数据可能被并发的修改，在不同的数据中心之间，这个“冲突”必须被解决。

2 Clients with offline operation ：一部分datacenter离线一段时间，然后又回到集群。离开的那段时间，也可以正常运行。比方说 CouchDB

3 Collaborative editing ：一般我们不把协同编辑功能，当做一个数据库的replication的问题来看，但是他们有好多相似的地方。

解决写冲突

  • 冲突检测：多主的情况下，每个写入都是成功的，冲突只能在后续的一个时间点被检测出来，那个时候，已经无法让用户去解决冲突。 如果要同步的冲突检测，就只能等待所有的replica都同步完，这个和单leader没什么区别。
  • 避免冲突：最简单的解决冲突的办法就是避免冲突。举个🌰：用户可以修改自己的信息，可以让这个用户一直路由到同一个dc。但是当用户旅游到了其他地方，就近接入了另外一个dc， 这个方法就失效了， 冲突就会出现。
  • Converging toward a consistent state： 如果是单个leader，我们可以知道更新操作的顺序，如果有对同一个field的更新操作，最后一个更新决定了这个field的值。如果是多个leader，这个顺序很难知道。

收敛的方法：

1 每一个写操作都带一个唯一Id。冲突的几个版本中，id大的胜利。

2 在一个额外的地方记录冲突，后续解决。可能通知用户来选择。

  • 自定义解决冲突的逻辑：让应用去解决冲突是大部分数据库的一般做法，大部分多主的数据库工具可以自定义冲突解决逻辑。一般有2个时机可以执行冲突解决逻辑：当冲突被检测到或者当读请求到来的时候。

自动冲突解决：

1
2
3
• Conflict-free replicated datatypes (CRDTs) [32, 38] are a family of data structures for sets, maps, ordered lists, counters, etc. that can be concurrently edited by multiple users, and which automatically resolve conflicts in sensible ways. Some CRDTs have been implemented in Riak 2.0 [39, 40].
• Mergeable persistent data structures [41] track history explicitly, similarly to the Git version control system, and use a three-way merge function (whereas CRDTs use two-way merges).
• Operational transformation [42] is the conflict resolution algorithm behind col‐ laborative editing applications such as Etherpad [30] and Google Docs [31]. It was designed particularly for concurrent editing of an ordered list of items, such as the list of characters that constitute a text document.

无主

废除主节点，任何节点都可以接受写操作。比较有代表性的此类数据库：Dynamo，Riak，Cassandra。

有节点挂掉时的写入

假设有个3个节点，其中一个挂掉。 写入的时候，是能更新其余2个节点。当挂掉的节点又启动起来，不能立刻与另外2个同步。这个时候如果读数据，可能会得到未更新的结果（读请求落到刚刚恢复的节点）。过一会，数据都同步了，读也会全部为新的了。

怎么解决这个问题？读请求也并行的发到多个节点，如果得到了多个结果，选择“版本号”最大的结果。

Read repair and anti-entropy

副本集群应该保证最终集群中的数据是一致的。一个离开的节点，又回到了集群，怎么保证他的同步？和Dynamo类似的数据库，一般会采用两种方法，来实现：

  • Read repair

    读取的时候，会读多个节点，把其中落后的节点，通知他们补上。

  • Anti-entropy process

​ 有一个后台的任务不断的去发现节点中的不同，进行修复。

Quorums for reading and writing （读写的法定人数）

假设有n个replicas，写入的时候，必须有至少w个节点写入成功，读的时候，至少从r个节点中读取。只要 w + r > n ，就可以保证读的时候，总可以读到最新的结果，因为读写至少有一个节点是重合的。在类Dynamo数据库中，w，r，n都是可配置的。

Sloppy Quorums and Hinted Handoff

无主的集群，可以忍受任意一个节点的挂掉， 因为不需要fallover， 也可以忍受个别节点变慢，因为因为只需要w或r个节点返回就可以。所以这个导致了，它十分适合需要 高可用，低延迟，但是可以容忍偶发的 stale reads。

如果因为网络原因，导致一个clinet只能看到一部分的节点，这样会导致他的读写无法达到法定人数。

这个时候，如果选择？

1 失败。

2

Hinted Handoff：当需要向一个已知宕机的节点写入数据的时候，Cassandra会将数据作为提示数据写入另一个正常的复本节点。稍后会对恢复的宕机节点进行数据重放。如果所有的复本节点都不能访问，则将提示数据写入到协调者本地。（能够理解提示的含义么） 当一个节点，通过Gossip发现它所存储的提示数据的所属节点恢复正常，他就会将提示数据发送到其所属目标节点。

缩短了暂时失败的节点恢复一致的时间。尤其是在一些奇怪的网络问题下，更加有用。（网络短时间不可用之类）

Hinted Handoff并不是修复机制的代替品。

上面的方式也叫做 Sloppy quorums，它可以有效的增加写入的可用性，但是它不是真正的法定人数，不能保证读到最新的数据。

Limitations of Quorum Consistency （Quorum Consistency 的限制）

就算 w + r > n， 也是有一些边界case，会返回不是最新的结果。

1 sloppy quorum