数据密集型应用设计-分布式数据存储

多台机器参与数据的存储和查询，这种系统被称为分布式系统，分布式系统相对于单机系统有以下优点：

1. 可扩展性：可以通过增加机器来扩展系统的容量和吞吐量。
2. 高可用性：即使某台机器出现故障，系统仍然可以继续工作。
3. 延迟：可以在全球范围内部署机器，从而每个用户都可以就近访问数据，减少延迟。

数据分布在多个节点上，有两种常见的方式：

1. 复制(replication)：在不同的节点上保留相同的数据副本，提高可用性和读取性能。复制提供了冗余，即使某个节点出现故障，剩余的节点仍然可以继续工作。复制有三种方式：单主复制、多主复制、主从复制。
2. 分区(partitioning)：将数据分布在不同的节点上，每个节点只存储全部数据的一个子集。分区提供了扩展性，因为每个节点只需要存储全部数据的一部分，所以可以通过增加节点来扩展系统的容量和吞吐量。

上图的数据库被切分为两个分区，每个分区都有两个副本。这种复制和分区的组合方式被称为 **分片(sharding)**。

单主复制

复制指的是通过网络连接的多台机器上保留相同数据的副本，这主要是出于以下目的：

1. 使得数据与用户在地理上接近(减少延迟)
2. 即使系统的一部分出现故障，系统也能继续工作(提高可用性)
3. 扩展可以接受读请求的机器数量(提⾼读取吞吐量)

复制面临的主要困难是数据的变更，即数据会随着时间的推移而发生变化，如何保证多个副本之间的数据一致性是复制的核心问题，而这需要考虑并发和所有可能的故障，并对这些故障的后果进行处理。

存储数据库副本的每个节点称为 replica(副本)，当存在多个 replica 时，如何保证多个 replica 之间的数据一致性。最常见的解决方案被称为 leader-based replication(基于领导者的复制)，也称 active/passive(主动/被动) 或 master/slave(主/从) 复制。

主从复制的基本思路是：

1. 副本之一被指定为 leader/master/primary，当客户端向数据库写入时，它必须将请求发送给 leader，leader 会将新数据写入其本地存储。
2. 其他副本被称为 followers/read replicas(只读副本)/slaves(从库)/sencondaries/hot-standby(热备)，每当 leader 将新数据写⼊本地存储时，它也会将数据变更发送给所有的 followers，这个数据变更称为 replication log(复制日志) 或 change stream(更新流) 。每个 followers 从 leader 拉取日志，并按照同样的顺序相应更新其本地数据库副本。
3. 当客户想要从数据库中读取数据时，它可以向 leader 或 followers 查询，但只有 leader 才能接受写操作。

主从复制是最常见的复制方式，在很多数据库系统中都有应用：

1. 关系数据库：MySQL、PostgreSQL(9.0版本之后)、Oracle Data Guard、SQL Server 的 AlwaysOn Availability Groups
2. NoSQL 数据库：MongoDB、RethinkDB、Espresso
3. 分布式消息代理：Kafka、RabbitMQ
4. 网络文件系统：DRBD

同步和异步

上图展示了系统各个组件之间的通信：用户客户端、主库、同步从库、异步从库。想象这样一个场景：网站的用户更新他们的个人头像，即客户向主库发送更新请求，主库收到了请求，主库会将数据变更转发给自己的从库。最后，主库通知客户更新成功。

• 从库 1 的复制是 同步(synchronously) 的：主库发送消息，等待从库 1 的确认，确保从库 1 已经收到写入操作，然后再通知客户端写入成功。
• 从库 2 的复制是 异步(asynchronously) 的：主库发送消息，但在从库 2 获得确认响应前，就主动通知客户端写入成功。通常情况下，复制的速度很快，但大多数数据库系统都不能提供对复制延时的强制保证。有些情况下，从库会落后主库几分钟甚至更久，例如：从库正从故障中回复，从库的系统负载临界，节点间的网络延迟等。

使用异步还是同步复制取决于系统的需求，在关系型数据库里这通常是一个配置项，其他系统通常会硬编码这个策略。

• 异步复制：响应速度快，但是不能保证数据一致性。异步复制还会导致弱化的持久性，如果主库失效且不可恢复，则任何尚未复制给从库的写⼊都会丢失。但无论如何，异步复制已经得到了最广泛的使用，特别是在从库很多或者从库异地分布的场景里。通常情况下，基于领导者的复制都配置为完全异步。
• 同步复制：保证数据一致性，但是如果同步从库没有相应，主库就⽆法处理写入操作，主库必须阻止所有写⼊，并等待同步副本再次可用。
• 半同步(semi-synchronous)复制：严格的同步配置中，任何一个节点的中断都会导致整个系统停滞不前。所以可以使其中一个从库同步，其他从库都是异步，这样如果同步从库变得不可用或缓慢，则使⼀个异步从库同步。这保证了至少在两个节点上拥有最新的数据副本：主库和同步从库。

新从库的加入过程

有时候需要设置一个新的从库，或者是需要增加副本数量，或者需要替换一个失效的从库。这个过程面临的困难有：

1. 客户端不断向数据库写入数据，数据库总是在发生变化，简单地把数据文件从主库复制到新的从库是不够的，因为这样的数据文件是不一致的。
2. 可以锁定主库的写入操作，然后复制数据，但是这样违背了高可用性的原则。

不停机加入新的从库的过程：

1. 在某个时刻 t 获取主库的⼀致性快照，大多数数据库都提供了类似功能，少数场景下需要第三方备份工具。
2. 将快照复制到新的从库节点。
3. 从库主动连接到主库，请求时间点 t 之后的所有数据变更，这个过程称为 catch-up(追赶)。这要求快照与主库复制日志中的位置精确关联。不同的数据库系统里对该位置称呼不同，PostgreSQL 将其称为日志序列号(log sequence number, LSN)，MySQL将其称为二进制日志坐标(binlog coordinates)。
4. 当从库处理完快照之后积压的数据变更，就可以继续处理主库产生的数据变化了。

处理节点故障(如何实现高可用)

系统中任何节点都可能失效，可能是因为意外的故障，也可能是因为维护或升级。节点的失效是不可避免的，关键在于如何处理节点失效后的情况：即使个别节点失效，也要保持整个系统正常运行，并且尽可能控制失效节点对整体系统的影响。

主从复制中常见的节点失效情况包括：(1) 从库失效，(2) 主库失效。

从库失效(恢复追赶)

1. 从库记录从主库接收到的数据变更，即可以从日志中获取 发生故障以前处理的最后一个事务 的位置。
2. 从失效中恢复的从库可以连接到主库，并请求在从库断开连接时发生的所有数据变更。
3. 处理完积压的数据变更之后，从库就赶上了主库，可以照常继续接收数据变更流。

主库失效(故障切换 failover)

1. 确认主库失效 (一般通过超时和心跳检测)
2. 从从库中提升一个新的主库，需要更新客户端的连接配置，从库的数据变更流也要切换到新的主库，这个过程称为 故障切换(failover)。
   • 通过选举过程(剩余副本的多数选举)或者之前选定的 控制器节点(controller node) 来指定新的主库。
   • 新主库的最佳人选通常是拥有旧主库最新数据副本的从库(最小化数据损失)。
   • 让所有的节点同意一个新的主库，这涉及到共识算法。
3. 重新配置系统以启用新的主库
   • 客户端现在需要将它们的写请求发送给新主库。
   • 旧主库恢复连接后不会意识到自己已经不是主库，需要系统确保其成为从库。

故障切换的隐患

1. 如果使用异步复制，则新主库可能没有收到老主库宕机前最后的写入操作。在选出新主库后，如果老主库重新加入集群，新主库在此期间可能会收到冲突的写入。常见的处理方案是丢弃老主库未复制的写入，这可能会违背用户对于数据持久性的期望。
2. 如果数据库需要和其他外部存储(比如 Redis 缓存或消息队列)相协调，那么丢弃写⼊内容是极其危险的操作。
3. 脑裂(split brain)：两个节点都以为⾃己是主库，两个主库都可以接受写操作，却没有冲突解决机制，那么数据就可能丢失或损坏。一些系统可能会采取防范措施：当检测到两个主库节点同时存在时会关闭其中⼀个节点，但设计粗糙的机制可能最后会导致两个节点都被关闭。
4. 主库被宣告死亡之前的正确超时时间难以配置
   • 在主库失效的情况下，超时时间越⻓，意味着恢复时间也越长；
   • 如果超时设置太短，⼜可能会出现不必要的故障切换，这一般发生在临时负载峰值导致节点的响应时间超时，或网络故障可能导致数据包延迟的情况，那么不必要的故障切换会导致更加严重的后果。

GitHub 从库升级事故
一个过时的 MySQL 从库被提升为主库，数据库使用自增 ID 作为主键，因为新主库的计数器落后于老主库的计数器，所以新主库重新分配了⼀些已经被⽼主库分配掉的 ID 作为主键。这些主键也在 Redis 中使用，主键重用使得 MySQL 和 Redis 中数据产⽣不⼀致，最后导致一些私有数据泄漏到错误的用户手中。

节点故障、不可靠的网络、对副本一致性，持久性，可用性和延迟的权衡是分布式系统中的基本问题

复制日志的实现

1. 基于语句的复制：主库记录下它执⾏的每个写入请求(语句, statement)并将该语句日志发送给其从库
   • 相当于把每个 INSERT、UPDATE、DELETE 语句发送给从库，从库照搬执行相同的语句。
   • 隐患 1：调用 非确定性函数(nondeterministic) 的语句会在每个副本上生成不同的值，比如 NOW() 获取当前日期时间和使用 RAND() 获取⼀个随机数。
   • 隐患 2：如果语句使用了 自增列(auto increment)，或者依赖于数据库中的现有数据(UPDATE ... WHERE <condition> )，则必须在每个副本上按照完全相同的顺序执⾏它们，否则可能会产⽣不同的效果。这在并发事务场景下会成为性能瓶颈。
   • 隐患 3：有副作用的语句(例如，触发器，存储过程，用户定义的函数)可能会在每个副本上产⽣不同的副作用。
   • 5.1版本以前的 MySQL 使用的是基于语句的复制，现在在默认情况下如果语句中存在任何不确定性，MySQL 会切换到基于行的复制。VoltDB 使用了基于语句的复制，但要求事务必须是确定性的，以此来保证安全。
2. 传输预写式日志(Write Ahead Log, WAL)：主库通过⽹络将⽇志发送给其从库(复制和存储引擎使用相同的日志格式)。
   • 无论在什么存储引擎中，⽇志都是包含所有数据库写入的仅追加字节序列，可以使用完全相同的日志在另⼀节点上构建副本
     • 对于日志结构存储引擎，日志是主要的存储位置，日志在后台压缩，并进⾏垃圾回收
     • 对于覆写单个磁盘块的B树，每次修改都会先写⼊ WAL，以便崩溃后索引可以恢复到一个⼀致的状态。
   • 缺陷：日志记录的数据非常底层：WAL包含哪些磁盘块中的哪些字节发生了更改，这使复制与存储引擎紧密耦合。通常不可能在主库和从库上运行不同版本的数据库软件。
   • PostgreSQL 和 Oracle 等使用 WAL 复制日志实现。
3. 逻辑日志复制(基于行)：主库通过⽹络将⽇志发送给其从库(复制和存储引擎使用不同的日志格式)
   • 复制日志使用逻辑日志，以将其与存储引擎的物理数据表示区分开来。
   • 优点 1：由于逻辑日志与存储引擎内部分离，因此可以更容易地保持向后兼容，从⽽使 leader 和 followers 能够运行不同版本的数据库软件甚至不同的存储引擎
   • 优点 2：对于外部应用程序，逻辑日志格式也更容易解析。应用程序可以在逻辑日志上做一些改动更新，比如说复制到数据仓库进行离线分析，或建立⾃定义索引和缓存，这些技术称为 捕获数据变更(change data capture)。
   • 关系数据库中的逻辑日志实现：以行的粒度描述对数据库表的写入
     • (1) 对于插入的行，日志包含所有列的新值。
     • (2) 对于删除的行，日志包含⾜够的信息来唯⼀标识已删除的⾏。通常是主键，但是如果表上没有主键，则需要记录所有列的旧值。
     • (3) 对于更新的⾏，日志包含⾜够的信息来唯⼀标识更新的⾏，以及所有列的新值(或至少所有已更改的列的新值)。
     • (4) 修改多⾏的事务会⽣成多个这样的日志记录，后面跟着⼀条记录，指出事务已经提交。
   • e.g MySQL 的 binlog (二进制日志)
4. 基于应用程序的复制：不依赖于数据库系统，通过应用程序代码实现复制。
   • 应用场景：只复制数据的一个子集，在不同数据库之间进行复制，将复制移动到应用程序层等
   • 方法 1：读取数据库日志，使得其他应用程序可以使用数据。e.g Oracle Golden Gate
   • 方法 2：触发器允许用户注册在数据库系统中发生数据更改(写⼊事务)时⾃动执⾏的⾃定义应用程序代码，然后将更改记录到另外一个单独的表中。外部程序可以读取这个表，再加上若干业务逻辑处理，从而实现将数据变更复制到另⼀个系统。e.g Databus for Oracle / Bucardo for Postgres
   • 隐患：依赖于应用程序代码，相比其他复制方法开销更大，也更容易出错。

复制延迟

异步复制中，主库写入后并返回给客户端成功的响应，但从库还没有收到主库的数据变更，此时客户端同时向主库和从库查询数据，可能会出现数据不一致的情况。这种不一致只是暂时的，一般情况下从库会追赶上主库的数据变更，最终保持一致。出于这个原因，这种效应被称为 最终一致性(eventual consistency)。

复制延迟(replication lag) 是指从库落后于主库的时间，通常以时间单位(秒、分钟)或者数据变更单位(事务、日志)来衡量。复制延迟的概念只适用于异步复制，由于异步复制的应用场景更广泛，所以复制延迟是一个非常常见的真实问题。

Read Your Write (读己之写)

异步复制场景下，用户在写入主库后马上从从库查看数据，此时新数据可能尚未到达从库。对用户⽽言，刚提交的数据丢失了。

一般需要通过 读写一致性(read-after-write consistency)/读己之写一致性(read-your-writes consistency) 保证用户重新加载页面后能够看到自己提交的任何更新。当然，这种一致性不会对其他用户做出保证：用户一定能看到自己的写入，但不能保证其他用户何时能看到这些写入。

在主从复制系统中实现读写一致性

1. 读用户可能已经修改过的内容时，都从主库读。最简单的例子就是：从主库读取用户⾃己的档案，在从库读取其他用户的档案，因为用户个人资料信息只能由用户本人编辑。
2. 跟踪上次更新的时间，在上次更更新后的一分钟内，从主库读。或者可以监控从库的复制延迟，防⽌向任何滞后超过⼀分钟的从库发出查询。
3. 客户端可以记住最近⼀次写⼊的时间戳，系统需要确保从库为该用户提供任何查询时，该时间戳前的变更都已经传播到了本从库中。如果当前从库不够新，则可以从另⼀个从库读，或者等待从库追赶上主库。时间戳的形式可以是逻辑时间戳(日志序列号等)或实际系统时钟。
4. 如果副本分布在多个数据中心，情况会变得复杂：用户必须路由到包含主库的数据中心，以保证能够读取最新的数据。

在某些情况下读写一致性难以得到保证

在允许跨多设备请求的服务中，比如说从桌面浏览器和移动 APP 同时访问，这种情况下还需要提供跨设备的写后读一致性，用户在浏览器上修改了个人资料，然后在手机上查看，需要保证手机上能看到刚刚修改的内容。

在这种情况下，记住用户上次更新的时间戳就变得更加困难，因为⼀台设备上运行的程序不知道另⼀台设备上发生了什么。元数据需要专门部署⼀个中⼼存储。

此外，考虑到副本分布在多个数据中心的情况，很难保证来⾃不同设备的连接会路由到同一数据中心。例如用户通过台式计算机的家庭宽带连接写入数据，移动设备的蜂窝数据⽹络读取数据，设备的网络连接不同，这种情况下如果需要读主库，可能⾸先需要把来⾃同⼀用户的请求路由到同⼀个数据中⼼。

Monotonic reads (单调读)

用户首先查询一个延迟很小的从库，再查询一个延迟较大的从库。这种情况一般是用户在第一次请求后刷新网页，第二次请求被路由到一个随机的服务器。第一个查询能返回结果，第二个查询由于从库滞后返回空结果，用户 2345 先看见用户 1234 的评论，然后又看到它消失，这种情况被称作 时光倒流错误(moving backward in time)。

一般需要通过 Monotonic reads (单调读) 保证后续读取不会得到旧的数据。这是一个比 强⼀致性(strong consistency) 更弱，但比 最终⼀致性(eventually consistency) 更强的保证。

实现单调读的方式：每个用户总是从同⼀个副本进⾏读取，不同的用户可以从不同的副本读取。例如，基于用户 ID 的散列来选择副本，⽽不是随机选择副本。但是如果该副本失效，那么需要重新选择一个副本，这样还是会出现时光倒流错误。

Consistent prefix reads(一致前缀读)

Mr.Poons 问问题，Mrs.Cake 回答问题，有问才有答。假设现在有第三方观察两个人对话，Mrs.Cake 说的内容从一个延迟很低的从库读取，Mr.Poons 说的内容从一个延迟很高的从库读取，导致第三方看到的是先回答了问题再问问题，即出现了因果错误。这种错误一般发生在数据库分片场景中，即数据库的不同分区独立运行，因此不存在全局写入顺序，数据库的某些部分处于旧状态，而另外有些部分处于新状态。

一般通过 Consistent prefix reads (一致前缀读) 保证如果⼀系列写⼊按某个顺序发生，那么任何⼈读取这些写入时，也会看见它们以同样的顺序出现。

实现一致前缀读的方式：确保任何因果相关的写入都写⼊相同的分区，一般还涉及到⼀些显式跟踪因果依赖关系的算法。

如何解决复制延迟

1. 设计系统时需要对数据库是同步还是异步复制有着清醒的认识。
2. 如有必要，在应用程序中提供更强有力的保证，比如通过主库进行读取。
3. 数据库可以通过事务提供强大的保证，在单节点数据库中，事务的实现是简单的，但是在分布式数据库中，很多系统因为担心性能和可用性上的代价而放弃了事务，如何在分布式系统中实现事务是一个很大的挑战。

多主复制

单主复制中只有一个主库，所有的写入都要经过它，如果处于任何原因导致主库无法连接，数据库就无法写入。多主复制是对单主复制的自然延伸：处理写入的每个节点都必须将该数据更改转发给所有其他节点，每个 leader 同时扮演其他 leader 的 follower。

多主复制极大提高了实现的复杂性，在许多数据库中都属于实验性或者改装性质的功能，常常和其他数据库功能产生意外的冲突，例如自增主键、触发器、完整性约束等，真正实现时需要考虑的细节问题非常多，所以多主复制往往被认为是危险的领域，普通场景里尽可能避免使用。

多主复制的应用场景

仅在以下几个场景中才可能考虑使用多主复制。

运维多个数据中心(异地多活)

多主复制：在每个数据中心内使用常规的主从复制；在数据中心之间，每个数据中心的主库都会将其更改异步复制到其他数据中心的主库中。如果采取单主复制，主库必须位于某一个数据中心，用户在其他数据中心的写入请求必须经过跨数据中心写入。

• 性能上，如果采用单主复制，那么用户在一个数据中心的写入请求必须经过跨数据中心的网络连接，这会导致延迟增加。多主复制可以避免这个问题，因为每个数据中心都有自己的主库，写入请求只需要在本地处理。
• 可用性上，如果采用单主复制，那么如果主库所在的数据中心发生故障，那么整个系统将无法写入，即使是故障切换也需要时间。多主复制可以避免这个问题，因为每个数据中心都有自己的主库，即使一个数据中心发生故障，其他数据中心仍然可以写入。发生故障的数据中心恢复后，可以将数据同步回来。
• 数据中心之间的网络连接可能不稳定，远不如数据中心内部的网络连接稳定。单主复制对于数据中心的网络连接问题非常敏感，而多主复制可以避免这个问题，因为即使数据中心之间的网络连接不稳定，每个数据中心都有自己的主库，写入请求只需要在本地处理。

需要离线操作的客户端

有一种场景是：应用程序在断网之后仍然需要继续工作，比如说手机、笔记本和其他设备上的日历应用，无论设备目前有没有网络连接，用户都可以查看和编辑日历。如果是离线状态下的更改，那么当设备重新连接到网络时，这些更改应该被同步到其他设备上。

在这种场景里，每个设备都有一个充当主库的本地数据库，用户在设备上的更改会被记录在本地数据库中，然后异步地同步到其他设备上。复制延迟可以是几小时甚至几天，具体取决于何时可以访问网络。从架构的角度来看，这种场景和多数据中心的多主复制十分类似，每个设备都可以认为是一个数据中心，彼此之间的网络连接极度不稳定。有一些工具可以帮助实现这种场景，比如说 CouchDB。

协同编辑

实时协作编辑应用程序允许多个人同时编辑文档，比如说 Google Docs 和腾讯文档。这种场景下，每个用户都会在本地维护一个副本，用户的更改会被记录在本地副本中，然后异步地同步到其他用户的副本中。

写入冲突

多主复制中相对于单主复制的一个最大问题就是写入冲突。在单主复制中，所有的写入都要经过主库，但是在多主复制中，每个主库都可以接收写入请求，导致冲突的产生。比如下面的场景：用户 1 将页面的标题从 A 更改为 B，并且用户 2 同时将标题从 A 更改为 C，每个用户的更改已成功应用到其本地主库，之后异步地同步到其他主库，这时候就会产生冲突。

如何解决写入冲突

1. 最简单的策略：避免写入冲突，即确保特定记录的所有写入都是通过同一个主库进行的。例如，在用户可以编辑自己的数据的应用程序中，可以确保来自特定用户的请求始终路由到同一数据中心，并使用该数据中心的领导者进行读写。
2. 收敛(convergent)：所有副本必须在所有变更复制完成时收敛至一个相同的最终值，这种策略有多种实现方式。
   • 最后写入胜利(Last write wins, LWW)：一般给每个写入操作分配一个唯一的 ID (例如，一个时间戳，一个唱的随机数或者一个键值哈希)，当冲突发生时，选择 ID 最大的写入操作作为最终值。这种策略可能会造成数据丢失。
   • 区别于 LWW，为每个副本分配一个唯一的 ID，而不是为每个写入操作分配一个唯一的 ID，ID 编号更高的副本的写入具有更高的优先权。这种方法也会造成数据丢失。
   • 将写入值进行合并，比如用户 1 将 A 更改为 B，并且用户 2 同时将 A 更改为 C，最终的写入可以为 A/C，这种仅适用于部分特殊场景，而且会造成数据混乱。
   • 将冲突的完整信息记录下来，并在之后的某个时间点提示用户处理并合并冲突，这其中需要应用程序的支持。
3. 自定义冲突解决逻辑：在应用程序中实现自定义的冲突解决逻辑，在数据写入或读取时自动执行。
   • 写时执行：只要数据库系统检测到复制更改日志中存在冲突，就会调用冲突处理程序。e.g Bucardo
   • 读时执行：当检测到冲突时，所有冲突写入被存储。下一次读取数据时，会将这些多个版本的数据返回给应用程序。应用程序可能会提示用户或自动解决冲突，并将结果写回数据库。e.g CouchDB

自动冲突解决的相关研究

• 无冲突复制数据类型(Conflict-free replicated datatypes,CRDT)：可以由多个用户同时编辑的集合，映射，有序列表，计数器等一系列数据结构，它们以合理的方式自动解决冲突。e.g Riak 2.0
• 可合并的持久数据结构(Mergeable persistent data structures)：显式跟踪历史记录，类似于 Git 版本控制系统，并使用三向合并功能（而CRDT使用双向合并）。
• 可执行的转换(operational transformation)：Etherpad 和 Google Docs 等合作编辑应用背后的冲突解决算法。它是专为同时编辑项目的有序列表而设计的，例如构成文本文档的字符列表。

多主复制拓扑

由于有多个主库，主库将自己的数据变更发送给其他主库，如何组织这些主库之间的连接关系是一个重要的问题，复制拓扑描述的就是从一个节点传播到另一个节点的数据流向。

1. 环形拓扑：每个节点只接受来自一个节点的数据变更，并将自己的数据变更发送给下一个节点。
   • 在环形拓扑和星形拓扑中，数据变更在到达所有节点之前可能会经过多个节点。
   • 为了防止数据变更在环形拓扑中无限循环，每个节点都会被赋予一个唯一的 ID，在复制日志里每个数据变更都会标记已经通过的节点 ID，当数据变更回到最初的节点时，数据变更会被丢弃。
   • 如果只有一个节点发生故障，其他节点之间的数据变更流可能会被中断。
2. 星形拓扑：一个指定的节点接收所有的数据变更，并将数据变更发送给其他所有节点。星型拓扑可以推广到树状拓扑。
   • 星形拓扑中的中心节点可能会成为瓶颈，如果中心节点发生故障，整个系统可能会瘫痪。
3. 全连接拓扑：每个节点都接收来自其他所有节点的数据变更，并将自己的数据变更发送给其他所有节点。
   • 由于网路拥塞等原因，一些数据变更可能会传播得更快，导致因果错误，可以通过 版本向量(version vector) 技术解决该问题。

无主复制

单主复制和多主复制的一个共同特点是：每个写入操作都要经过一个特定的主库节点，从库节点只能接收来自主库的数据变更。无主复制是对这种模式的一种反向思考：每个节点都可以接收写入请求，每个节点都可以接收来自其他节点的数据变更。

无主复制最早出现在 Amazon 内部的 Dynamo 系统中，启发了后来许多无主复制模型的开源数据库设计，包括 Cassandra、Riak 和 Voldemort，这类数据库也被称为 Dynamo 风格的数据存储系统。

无主复制主要有两种实现：

1. 客户端直接把写入发送到到所有副本节点。
2. 有一个协调节点(coordinator)节点代表客户端进行写入。协调节点对于写入顺序并不敏感。

处理节点故障

无主复制配置中不存在主库，也就不存在故障切换的过程。

如上图所示，在一个 3 副本的数据库系统上，副本 3 发生故障，恰巧此时客户端 1234 并行向三个副本发出写入请求，只能收到两个副本的响应，客户端就可以认为是写入成功的。这种写入方式被称为 法定人数写入(quorum write)。

之后，失效的副本 3 恢复，在数据同步前，客户端 1234 再次向三个副本发出读取请求，会收到两个新值和一个旧值，客户端会根据版本号来判断数据的新旧，然后丢弃旧值。这种读取方式被称为 法定人数读取(quorum read)。

失效的副本 3 恢复后，还需要同步追赶其他副本的数据，一般有两种方式：

1. 读修复(read repair)
   • 客户端并行读取多个节点时，它可以从响应中检测到陈旧的副本，并将最新的值写回到陈旧的副本中。
   • 很多 Dynamo 风格的数据存储系统都实现了该机制，但是如果只在应用程序读取数据时才修复，对于读取频率较低的数据可能会导致数据不一致。
2. 反熵(anti-entropy)
   • 定期检查副本之间的数据差异，并将差异同步到其他副本。
   • 一般通过 Merkle 树来实现，Merkle 树是一种树形数据结构，可以高效地检测出两个数据集之间的差异。
   • 一般会在后台进程中运行。
   • 过程中不会以特定的顺序复制写入，相比主从复制中的复制延迟，反熵的延迟更明显。

quorum

法定人数(quorum) 是指在一个集群中，必须有多少个节点同意一个操作才能被认为是成功的。更一般地说，如果有 n 个副本，每个写入必须由 w 个节点确认才能被认为是成功的，并且必须至少为每个读取查询 r 个节点。在上面这个例子中，n = 3，w = 2，r = 2。通常情况下，读取和写入操作始终并行发送到所有 n 个副本，参数 w 和 r 决定了在认为读或写成功之前，有多少个节点需要报告成功。

法定人数(quorum) 的选择是一个权衡，如果 w 和 r 太小，可能会导致数据不一致，如果 w 和 r 太大，可能会导致性能下降。在 Dynamo 风格的数据库中，参数 n, w 和 r 通常是可配置的。

一个常见的选择是使 n 为奇数（通常为 3 或 5）并设置 w = r =（n + 1）/ 2(向上取整)。但这不是绝对的，比如可以设置 w = n 和 r = 1，使得读取速度更快，但只要有一个失败节点就会导致所有数据库写入失败，适用于写入很少且读取次数较多的工作负载。

其他的一些配置：

• 如果 w < n，即使有些节点失败，仍然可以写入成功。
• 如果 r < n，即使有些节点失败，仍然可以读取成功。
• 如果 w + r > n，可以期望在写入成功后立即读取到写入的数据。
• 对于 n = 3，w = 2，r = 2，可以容忍一个节点的失败。
• 对于 n = 5，w = 3，r = 3，可以容忍两个节点的失败。

仲裁一致性(Quorum Consistency) 的局限性

w 和 r 的选择是自由的，一般会设置为大于一半的节点数，即保证读写使用的节点交集非空。如果设置较小的值，读写操作人仍然会发送到全部 n 个节点，但只要少量的成功响应就可以认为操作成功，这样可以降低读写的延迟，而且提高了对网络分区的容忍度，可用性更高，缺点是可能会读取到过时的数据，因为读取有可能不包含具有最新值的节点。

另外，即使满足了 w + r > n，也不能保证读取到最新的数据，因为读取操作可能会读取到过时的数据，比如以下几种情况：

1. 使用了 sloppy quorum，导致w 个写入和 r 个读取操作落在不同的节点上。
2. 两个写入操作同时发生，如果根据 LWW 策略选择最新的写入，由于时钟偏差问题，真正的最新写入可能被丢弃。
3. 写操作和读操作同时发生，写操作可能仅在一部分节点上成功，读操作不确定是返回旧值还是新值。
4. 写操作只在部分副本上成功，虽然整体是判定写入失败，但是写入的节点还没来得及回滚，导致后续读取还是读取到了失败的写入。
5. 一个已写入新值的节点故障失效，恢复时又从旧值的节点同步数据，那么存储新值的节点可能会低于 w 个节点，导致不满足 quorum 的仲裁一致性。

sloppy quorum(松散法定人数)

网络中断可能将某个客户端与大量的数据库节点分隔开来，注意此时这些节点是有效的，其他客户端也可以访问到这些节点。此时，该客户端检测到的剩余可用节点数可能不足 w 或 r，读写操作都会失败。
但是需要注意的是，由于数据分区/分片机制，一个大型数据库集群里的节点数量是比 n 大得多的，虽然该客户端要求的数据所在的节点数不足 w 或 r，但是可连接的节点是超过 w 或 r 的。
站在数据库设计人员的角度，可以采取一个权衡的策略，允许接受数据写入，但是数据并不是写入到对应的分区散列的节点上，或者说，并不是包含在 n 个节点里的其他节点上，这些节点只是临时接收并存储这些数据，按原本的数据分区策略它们是不应该接收这些数据的。一旦网络中断得到回复，这些临时节点会将数据转发到正确的节点上，这种转发操作称为 hinted handoff，这样可以保证数据的一致性。
需要注意的是，这种策略还是需要保证响应节点的数量不少于 w 或 r，只是这些节点并不是数据的真正归属节点，也因此这种 quorom 的策略称为 sloppy quorum。
sloppy quorum 是不能保证写入后能够立即读取到最新数据的，数据可能存储在 w 个节点中的任意一个，在直到数据转发到正确的节点之前，读取操作都会读取到过时的数据。

原书中举了一个借钥匙和还钥匙的例子，我觉得不太好，这里可以换成发放电视购物传单的例子：
(1) 一个小区里有部分用户购买了电视，推销人员每个月都会上门发放电视购物传单，为了提高传单的覆盖率，推销人员需要统计有多少用户实际收下了传单。
(2) 推销人员有自己的 KPI，要保证小区内一半以上购买了电视的用户有收到传单，否则就认为是不称职的。
(3) 但是很多情况下，用户并不在家，推销人员只能把传单暂时交给邻居保管，该邻居并不是购买了电视的用户，但是他可以保证传单最终会送到用户手中。

并发写入与冲突

在无主复制中，由于允许多个客户端同时写入相同的数据，所以会发生与多主复制类似的写入冲突问题。在无主复制中，冲突的发生可能更加频繁，因为无主复制模糊了对写入顺序的要求，在 Read Repair 和 hinted handoff 的过程中也会出现冲突。

如上图所示，客户端 A 和客户端 B 同时向多个副本发出针对 key = X 的写入请求，客户端 A 的写入为 set X = A，而客户端 B 的写入为 set X = B。由于网络延迟和部分节点失效，事件在不同的节点以不同的顺序发生，导致不同的副本上存储了不同的值。

(1) 节点 1 接受来自 A 的写入，由于网络分区，节点 1 无法接受来自 B 的写入，所以节点 1 认为 X = A。
(2) 节点 2 首先接受来自 A 的写入，然后接受来自 B 的写入，所以节点 2 认为 X = B。
(3) 节点 3 首先接受来自 B 的写入，然后接受来自 A 的写入，所以节点 3 认为 X = A。

为了解决这个问题，无主复制系统通常会使用 LWW 策略，即选择最新的写入作为最终的写入，这样所有副本最终都能够收敛到相同的值。LWW 需要保证每个写入操作都有一个唯一的 ID，这个 ID 一般是时间戳。LWW 虽然实现了最终收敛的目标，但是可能会导致数据丢失：如果同一个 key 有多个并发写入，即使客户端侧认为写入成功，因为它们成功写入了 w 个副本，但是只有一个写入会被保留，其他写入会被丢弃，因此 LWW 不适用于对丢失数据敏感的场景。为了解决这个问题，一般需要确保一个 Key 只能写入一次并在写入后设置为只读，从而避免并发更新。Cassandra 使用 UUID 作为 key，从而为每个写入操作分配一个唯一的 ID。

并发之所以很难处理，是因为分布式系统中的时钟同步不可靠，现实中很难判断两个事件是否同时发生。为了隔绝时钟的影响，分布式系统将并发性定义为：如果两个操作都意识不到对方的存在，那么它们就是并发的，确切的发生时间并不重要。这种定义下，如果 A 事件的插入发生在 B 事件的增量之前，即 B 操作建立在 A 操作的基础上，这种情况下 B 因果依赖 (causal dependent) 于 A，A 和 B 就不是并发的。

分区/分片

术语澄清
分区(partition)在 MongoDB,Elasticsearch 和 Solr Cloud 中被称为分片(shard), 在 HBase 中称之为区域(Region)，Bigtable 中则是表块（tablet），Cassandra 和 Riak 中是虚节点 (vnode), Couchbase 中叫做虚桶(vBucket)。但是分区(partition) 是约定俗成的叫法。

分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。这意味着，即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能⼒。

分区的最大优点是提高了系统的扩展性，使得系统可以处理更多的数据和负载。不同的分区可以放在不共享集群中的不同节点上，而一个节点可能存储多个分区。每个节点可能是某些分区的 leader，同时是其他分区的 followers。

散列分区

分区是为了将数据和查询负载均匀分布在不同的节点上。如果每个节点均匀分享数据和负载，在不考虑复制的情况下，理论上 n 个节点应该能够处理 n 倍的数据量和 n 倍的单节点读写吞吐量。

大多数情况下，分区方案的选择与复制⽅案的选择是互相独⽴的。

如果分区方案选择不当，一些分区比其他分区有更多的数据或查询，即 偏斜（skew），会导致分区效率下降。数据不均衡导致的高负载的分区称为 热点（hot spot）。

根据键的范围分区(Key Range)

定义：为每个分区指定一块连续的键范围，所有键的范围都不重叠。比如字典中的字母索引，A-B 为一个分区，C-D 为一个分区，以此类推，T-Z 为一个分区。

1. 为了均匀分配数据，需要根据数据的分布情况来调整分区边界。
2. 分区边界可以由管理员手动设置，也可以由数据库自动选择配置。
3. 优点
   • 适用于范围查询，比如查找所有键在 A 和 B 之间的数据。
   • 适用于按键排序的查询，比如查找所有键按字母顺序排列的数据。
4. 缺点
   • 数据分布不均匀时，会导致热点分区。
   • 分区 key 选择的不当会导致数据分布不均匀。
5. 实际使用场景：Bigtable、HBase、RethinkDB 和 2.4 版本之前的 MongoDB。

根据键的散列分区(Hash of Key)

定义：使用散列函数将键映射到分区，避免偏斜和热点的风险。比如给定一个散列函数 hash(key) % N，其中 hash(key) 对于任意的字符串输入 key 都会返回一个范围在 [0, 2^32-1] 的整数，% N 会将这个整数映射到 N 个分区中的一个。即使输入的字符串非常相似，散列函数也会将它们映射到不同的分区中。

1. 如果已经有一个合适的散列函数，可以为每个分区指定一个散列范围，或者通过 hash(key) % N 来动态分配分区。
2. 优点
   • 适用于随机访问，因为每个键都可以映射到任意的分区。
   • 适用于均匀分布数据，避免热点分区。
3. 缺点
   • 不适用于范围查询，因为相邻的键可能映射到不同的分区。如果在基于散列的分区上执行范围查询，那么查询将需要在所有分区上执行，然后将结果合并。
   • 如果确实需要按照键的范围和顺序进行查询，可以考虑使用组合索引。比如在查询社交媒体推文的场景里，可以将用户 ID 进行散列分区，一个用户某个时间间隔内所有的推文都存储在同一个分区中，这样可以保证按照时间顺序进行查询。

负载偏斜与消除热点

哈希分区可以帮助减少热点，但在极端情况下无法完全消除热点。
考虑这样一种场景：社交媒体上的热门话题或人物，这种类型的事件会导致大量对同一个 key 的写入请求，哈希策略无法完全消除这种热点。一种可能的策略是：如果一个主键被预测为热点，可以在主键的开始或结尾添加随机数，从而可以将热点分散到多个分区中。
但是分割主键可能会导致查询变得复杂，任何读取都必须增加额外的工作，必须从所有分布的分区中读取数据并将结果合并。此外，还需要增加一些追踪热点 key 的机制，毕竟附加随机数对于绝大多数吞吐量低的 key 是没有必要的。

次级索引的分区

之前的分区方案只依赖于主键，但实际应用中还需要支持次级索引。次级索引是指除了主键之外的其他字段，不能唯一标识一条记录，比如在社交媒体应用中，用户的 ID 是主键，但是还需要根据用户的名字进行查询。

使用次级索引的分区方案

1. Partitioning Secondary Indexes by Document
   • 分区自己维护次级索引，而且仅覆盖该分区的数据。每个分区都有自己的次级索引。
   • 用户添加、更新或删除数据时，只需要处理对应分区的次级索引。因此，这种索引也被称为 本地索引(local index)。
   • 从文档分区索引中查找数据时，需要将查询发送到所有分区，然后将结果合并，这种查询方式称为 scatter/gather 查询，这种查询方式的性能取决于分区的数量和最慢的分区的响应时间。因此大多数数据库都会建议用户合理设置分区策略，以便次级索引查询可以从尽可能少的分区（最好是单个分区）中获取数据。
   • e.g MongoDB、Riak、Cassandra、Elaticsearch 等
2. Partitioning Secondary Indexes by Term
   • 构建一个覆盖所有分区数据的 全局索引(global index)，并且这个次级索引的全局索引也必须进行分区。
   • 用户查询时，首先查询次级索引，由于次级索引是全局索引，因此可以快速找到索引的分区，然后通过索引找到所有对应的主键，然后向主键所在的分区发出查询请求。
   • 优点：次级索引查询速度快，不需要向所有分区发出查询请求，只需要向包含关键字的分区发出查询请求。
   • 缺点：写入时需要更新全局索引，这涉及到多个分区的协调，写入速度较慢且复杂。因此实践中对全局次级索引的更新通常是一步的。
   • e.g Riak 的搜索功能、Oracle 数据仓库

分区再平衡

随着时间的推移，数据库会有各种变化。

• 查询吞吐量增加，需要添加更多的 CPU 来处理负载。
• 数据集⼤小增加，需要添加更多的磁盘和 RAM 来存储。
• 机器出现故障，其他机器需要接管故障机器的责任。

所有这些更改需要将数据和请求从一个节点迁移到另外一个节点，将负载从集群中的一个节点向另⼀个节点移动的过程称为 再平衡 (reblancing)。

再平衡策略需要满足以下最低要求：

• 再平衡之后，负载（数据存储，读取和写入请求）应该在集群中的节点之间公平地共享。
• 再平衡发⽣时，数据库应该继续接受读取和写入。
• 节点之间只移动必须的数据，以便快速再平衡，并减少⽹络和磁盘 I/O 负载。

常见的再平衡策略

1. hash mod N：最糟糕的做法。
   • 如果节点数量 N 发生变化，⼤多数 key 需要从一个节点移动到另一个节点，不必要的迁移举动使得这种再平衡策略的代价十分昂贵。
2. 固定数量的分区：创建⽐远比节点多的分区，并为每个节点分配多个分区，比如给 10 个节点的集群创建 1000 个分区。
   • 新节点加入集群时可以从当前每个节点中拿走一些分区。
   • 节点退出集群时可以将其分区随机归还到其他节点。
   • 优点：(1) 该策略可以解决节点数量变化时的大规模数据迁移问题。(2) 可以解决集群中的硬件不匹配问题：通过为更强大的节点分配更多的分区，可以强制这些节点承载更多的负载。
   • 缺点：(1) 由于分区数量固定，数据库第一次建立时就要确定下来。(2) 分区数不好确定：需要选择足够多的分区来适应未来的增长，但是每个分区也有管理开销，太多分区会导致资源浪费和性能下降。
   • e.g Riak、Elasticsearch、Coucbase 和 Voldemort
3. 动态分区
   • 按键的范围进行分区的数据库(如 HBase 和 RethinkDB) 会动态创建和合并分区。
   • 当分区增长到超过配置的大小时，会被分成两个分区，每个分区约占一半的数据。反之，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区进行合并。
   • 大型分区拆分后，可以将其中的一半转移到其他节点上，以便在集群中重新分配负载。
   • 优点：(1) 可以根据数据的增长和收缩动态调整分区。(2) 可以避免固定分区数量的管理开销。
   • 如果一个空数据库从一个分区开始，在最开始的一段时间内大部分节点都会处于空闲状态。为了解决这个问题，HBase 和 MongoDB 允许在一个空的数据库上配置一组初始分区（ 预分割(pre-splitting) ）。在键范围分区的情况中，预分割需要提前知道 key 的范围，而在散列分区的情况中，预分割可以根据散列函数动态生成。
4. 按节点比例分区
   • 每个节点都具有固定数量的分区，每个分区的大小与数据集大小成比例地增长。
   • 新节点加入集群时，随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中每个分区的一半，同时将每个分区的另一半留在原地。

路由查询

数据集被拆分到多个机器上运行的多个节点，客户端发出的查询需要路由到正确的节点上。

这并不是一个简单的问题，由于分区重新平衡，分区对节点的分配是动态变化的，客户端需要动态更新节点的分区分配信息。进一步地，这种情况并不仅限于数据库，如果某个有状态服务需要在多个节点上运行，以达到负载均衡和容错的高可用性目标，如何将请求路由到正确的节点上是一个重要的问题。这个问题可以概括为 **服务发现(service discovery)**。

这个问题有几个不同的解决方案：

1. **重定向查询(redirect query)**：客户端请求任意节点，如果该节点不是负责的节点，那么该节点会将请求重定向到正确的节点上。这种方案要求每个节点对整体分区拓扑有完整的视图，这样才能知道请求应该被重定向到哪个节点上。
   • e.g Cassandra 和 Riak 在节点之间使用 gossip 协议来传播分区信息的变化，请求可以发送到任意节点，该节点会将请求重定向到正确的节点上。
2. 增加一个路由层，客户端请求都发送到这个路由层，路由层负责将请求路由到正确的节点上。路由层本身不处理任何请求，仅起到负载均衡和路由的作用。
   • e.g ZooKeeper 使用了这种方案，每个节点在 ZooKeeper 中注册自己的地址，ZooKeeper 维护分区到节点的可靠映射，并通知路由层更新。
   • e.g MongoDB 依赖 config server 来维护分区到节点的映射，并使用 mongos 进程来路由查询。
3. 客户端自身维护一个分区分配表，客户端在发出请求之前，首先查询分区分配表，然后将请求发送到正确的节点上。

Reference

• Anti-entropy repair :: DataStax Enterprise 5.1