< Back

数据密集系统笔记

可靠性、可伸缩性、可维护性

关于twttier的例子

推特的伸缩性挑战并不是主要来自推特量，而是来自扇出（fan-out）——每个用户关注了很多人，也被很多人关注。 “扇出：从电子工程学中借用的术语，它描述了输入连接到另一个门输出的逻辑门数量。 输出需要提供足够的电流来驱动所有连接的输入。 在事务处理系统中，我们使用它来描述为了服务一个传入请求而需要执行其他服务的请求数量”

推特一开始使用最能想到的方式，join多个表来获取时间线推文。但是因为发推频率远低于查询时间线，查询负载变得很大。

后来采用，为每个用户维护一个时间线的缓存，但用户发推的时候，插入到关注者的时间线缓存中，这样读取时间线的开销变得很小，因为结果已经提前计算好了。

但是这又给写入操作带来了大量额外的工作，推特尝试在5秒内向粉丝发送推文。

再后来，推特采用了一个折中的方案，大多数用户发送的推文会被写入粉丝主页时间线的缓存中。但是少数拥有海量粉丝的会被排除在外。但用户读取主页时间线时，分别获取出该用户所关注的名流们的推文，再与时间线缓存进行合并。这种方法能使用如一的提供良好的性能。

延迟和响应时间

通常报表会展示服务的平均响应时间（算术平均值），然而如果你想知道典型（typical）响应时间，那么平均值并不是一个非常好的指标，因为他不能告诉你有多少用户实际上经历了这个延迟。

通常使用百分位点（percentiles）会更好。如果想知道典型场景下用户需要等待多长时间，中位数是一个好的度量指标。将响应时间列表按最快到最慢排序，中位数就在正中间。一半用户的请求响应时间少于中位数，另一半比中位数长。中位数也被称为第50百分位点，有时缩写为p50。

为了弄清异常值有多糟糕，可以看更高的百分位点，比如95、99、99.9。高百分位点，也被称为尾部延迟（tail latencies），非常重要，因为他直接影响用户的服务体验。亚马逊以99.9为准，因为响应最慢的客户往往是数据量最多的客户，也就是说最有价值的客户。

由于服务器只能并行处理少量的事务（如受CPU核数的限制），所以只要有少量的请求就能阻碍后续请求，这被称作**头部阻塞（head-of-line blocking）

一个良好适配应用的可伸缩架构，是围绕着假设（assumption）建立的：哪些操作是常见的？哪些操作是罕见的？这就是所谓的负载参数。如果假设最终是错误的，那么为伸缩所做的工程投入就白费了，最糟糕的是适得其反。所以支持产品快速迭代的能力，非常重要。

可维护性

软件大部分开销不在开发阶段，而是持续的维护阶段。大多数人不喜欢维护所谓的遗留（legacy）系统，每个遗留系统都以自己的方式让人不爽，所以很难给出一个通用的建议来和他们打交道。（😂传说中的祖传代码）

关注软件系统的三个设计原则，来减少维护期间的痛苦。

  • 可操作性（Operability）
  • 简单性（Simplicity） 消除尽可能多的复杂度，使新工程师也能轻松理解系统
  • 可演化性（evolability） 使得未来能够轻松进行更改，适配需求

数据模型与查询语言

使用id的好处是，id对人类没有意义，因而永远不需要改变，任何对人类有意义的东西都可能需要在将来某个时候改变——如果这些信息被复制，所有冗余副本都需要更新。去除此类重复是数据库规范化的关键是想。

在表示多对一和多对多关系时，关系数据库和文档数据库并没有根本的不同，相关项目都被一个唯一的标识符来引用，这个标识符在关系数据库中被称为外键，在文档模型中称为文档引用。

支持文档数据模型的主要论据是架构灵活性，因局部性而拥有更好的性能，以及对于某些应用程序而言更接近于应用程序使用的数据结构。关系模型则为连接提供更好的支持以及支持多对一和多对多的关系。

如果应用程序中的数据具有类似文档的结构（一对多关系树，通常一次性加载整个树），那么文档模型是一个好主意。局限性在于，比如不能引用文档中的嵌套项目，而是需要指定路径，比如，用户xxx的xx列表中的第x项。但是只要嵌套不是太深，这通常不是问题。还有就是对连接的支持很糟糕，如果应用程序确实会用到多对多关系，那么文档模型就没那么诱人了，容易导致应用代码的更加复杂，以及更差的性能。因此，对于高度关联的数据而言，文档模型是非常糟糕的。

文档数据库有时被称作无模式（schemaless），但这具有误导性，因为读取数据的代码通常假定某种结构——即存在隐式模式，但不由数据库强制执行。一个更精确的术语是读时模式（schema-on-read），数据的结构式隐含的，只有在数据库被读取时才被解释），相应的是写时模式（schema-on-write），传统关系数据库中，模式明确，数据库确保所有数据都符合其模式。

读时模式类似编程语言中的动态（运行时）类型检查，而写时模式类似于静态（编译时）类型检查。

mysql在执行alter table的时候会复制整个表，所以在对大表操作的时候要格外谨慎。（MySQL通常会创建一个新表，将原表数据复制过去，然后替换原表。这样做的目的是保证数据一致性和支持回滚，但会导致操作期间占用大量磁盘空间和时间，尤其是大表）

图数据模型

  • 属性图 属性图模型中，每个顶点包括：
    • 唯一标识符
    • 一组出边
    • 一组入边
    • 一组属性（键值对）

每条边包括：

  • 唯一标识符
  • 边的起点/尾部顶点
  • 边的终点/头部顶点
  • 一组属性（键值对）
CREATE TABLE vertices (
  vertex_id  INTEGER PRIMARY KEY,
  properties JSON
);

CREATE TABLE edges (
  edge_id     INTEGER PRIMARY KEY,
  tail_vertex INTEGER REFERENCES vertices (vertex_id),
  head_vertex INTEGER REFERENCES vertices (vertex_id),
  label       TEXT,
  properties  JSON
);

CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

Cypher查询语言

是属性图的声明式查询语言，为Neo4j图形数据库而发明。 举例：查询出生于美国，后来移民欧洲的所有的人的名字 一个person顶点，会有一个叫做born_in的出边指向美国的任意位置，还有一条叫做living_in的出边指向欧洲的任意位置。 可以有多种查询路径，比如扫描所有人，检查每个人的出生地和居住地，返回满足条件的人。或者从地方方向查找。 用Cypher语言可以很简洁的描述：

MATCH
    (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
    (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

但是如果用关系型数据库则比较困难，需要类似递归的去查找。所以不同的数据模型是为不同的应用场景而设计的，选择适合应用程序的数据模型非常重要。

存储与检索

世界上最简单的数据库，用两个bash函数实现：

#!/bin/bash
db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

db_set name 'kobe'
db_get name

因为在文件尾部追加写入通常是非常高效的，所以db_set函数其实有非常好的性能。 但是因为查找性能是O(n), 所以如果数据量很大的话，db_get的性能就很差了。所以需要加上索引，但是任何类型的索引通常都会减慢写入速度，因为每次写入数据都要更新索引。

哈希索引

将所有的键的哈希映射都放在内存中，记录了对应的数据文件中的偏移量，指明了可以找到对应值的位置。写入的时候追加写入文件，还要更新对应的散列映射。

例如Bitcask，提供高性能的读写，但是所有的键必须能放入可用内存中，因为哈希映射完全保留在内存中。（会占用一些内存，一个键几十字节，百万级的键需要几百兆，所以大多数情况其实是可以接受的）

为了追求更高的性能，一直追加写入文件，那要如何避免用完磁盘空间呢？一种好办法是，将日志分位特定大小的段，当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后我们就可以堆这些段进行压缩（compaction）：丢弃日志中重复的键，只保留每个键最近的更新。

由于压缩段经常会使得段变得很小，我们也可以在执行压缩的同时将多个段合并在一起。段被写入后永远不会被修改，所以合并的段被写入一个新文件。合并压缩可以在后台完成，在进行中，我们仍然可以继续使用旧的段文件来正常提供读写请求。合并完成后使用新的合并段，旧的可以简单的删除掉。（听上去很完美优雅😍）

这里写一下分段大概会有的一个流程。 首先索引里记录了文件名和偏移量。决定进行分段时，停止当前文件的写入，开始写入新文件（活跃文件）。

对非活跃文件进行压缩合并，这个过程会参考当前内存索引，来排除掉一些已经无效的数据（比如数据已删除，比如活跃文件中有更新的数据），这样只留下有效数据。 完成合并后，会生成一个索引快照。

然后通知主线程进行切换，切换的时候更改文件指向为合并后的文件，以及比对内存中的索引和索引快照来生成新的索引（只有在更新索引的过程中是要暂停写入的，其余时候都是正常写入）。这样就完成了索引和文件的更新。

一些真正实施中重要的问题是：

  • 文件格式 csv不是日志的最佳格式。使用二进制格式更快，更简单，首先以字节为单位对字符串长度进行编码，然后使用原始字符串。（不需要转义） 比如一条日志记录，按照这样的格式来记录： 
    [记录头部][Key 长度][Value 长度][Key 内容][Value 内容]


00 00 01 97 7E 2B 3A C0   # 时间戳 (8 字节)
00 00 00 07               # key 长度 (4 字节 = 7)
00 00 00 05               # value 长度 (4 字节 = 5)
75 73 65 72 31 32 33      # "user123"
68 65 6C 6C 6F            # "hello"
  • 删除记录 如果要删除一个键及其关联的值，则必须在数据文件中附加一个特殊的删除记录，当日志被合并时，逻辑删除告诉合并过程放弃删除键的任何以前的值。
  • 崩溃恢复 原则上可以通过从头到尾读区整个段文件来恢复每个段段哈希映射。但是如果段文件很大，这可能需要很长时间。bitcask通过每个段的哈希映射快照来更快的加载。
  • 部分写入记录 数据库可能随时崩溃，包括在写日志的途中。
  • 并发控制 写操作是以严格顺序的顺序附加到日志中的，所以常见的实现选择是自由一个写入线程。数据文件段可以被多个线程同时读取。

只追加不覆盖的写入方式，一方面是快，另一方面是崩溃恢复简单，因为如果采用覆盖的方式，在覆盖更新的途中崩溃了，那么导致新值没写成功，旧值也不完整。

哈希索引的局限性：

  • 散列表必须能放进内存 原则上可以在磁盘上保留一个哈希映射，不幸的是磁盘哈希映射很难表现优秀。
  • 范围查找效率不高

SSTable/LSM树

算是上面的一种改进，核心思路是保证段文件内数据的有序，从而在合并段文件的时候，可以像归并排序一样合并，非常简单高效。

具体做法：

  • 插入的时候先写WAL，来便于崩溃恢复
  • 再写内存，在内存中通过平衡树来维护数据的有序。这块内存被叫做内存表（memtable）
  • 等内存表大到一定程度之后写入到磁盘上的SSTable文件，此时数据就是有序的。写完后，日志就可以删除掉了。
  • 查找时，先找内存表，没有的话再从新到旧找SSTable文件，因为数据已经有序，所以可以直接按二分查找，快速定位

优点在于他不需要将所有数据的索引都放到内存中，同时合并SSTable文件的时候效率更高。

但是查找的时候需要挨个查找，所以文件数量太多的话会影响效率。

给予这种合并和压缩排序文件原理的存储引擎通常被称为LSM存储引擎（Log-Structured Merge Tree）。

这种方式比Bitcask那种有更高的写入吞吐量，我查了很多，好像根源在于写WAl的效率比实际写数据文件要快。WAL文件结构极其简单，纯粹的顺序追加，操作系统可以最大化地进行优化。虽然都是顺序I/O，但是好像存在着一些差别。

B树

上面的日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序编写段。而B树将数据库分解成固定大小的块或页面，传统上为4KB，并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。

具体做法，有一个页面会被指定为B树的根，查找一个键时，从这里开始。如果更新一个值，则搜索包含该键的叶页，更改页中的值，并写回到磁盘。如果要添加一个新键，先要找到范围包含这个键的页面，然后添加到页面。如果没有足够的空间来容纳新键，则将其分为两个半满页面，并更新父页面的范围。

因为更新操作是采取的覆盖，而不是像日志那种只追加，所以为了崩溃恢复，B树也会用到WAL（也被叫做redo log）。

以及多线程同时访问的时候，需要仔细的并发控制——否则线程可能会看到树处于不一致的状态。

页面可以放在磁盘上的任何位置，所以可能会因为频繁的磁盘寻道而降低效率。而LSM树在合并过程中一次又一次的重写存储的大部分，所以他们更容易使顺序键在磁盘上更彼此靠近。

B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。这个方面使得B树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在B树索引中，这些锁可以直接连接到树

内存数据库

反直觉的是，内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实。即使是基于磁盘的存储引擎也可能永远不需要从磁盘读取，因为操作系统在内存中缓存了最近使用的磁盘块。相反，它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。

除了性能，内存数据库的另一个有趣的领域是提供难以用基于磁盘的索引实现的数据模型。例如，Redis为各种数据结构（如优先级队列和集合）提供了类似数据库的接口。因为它将所有数据保存在内存中，所以它的实现相对简单。

列存储

在分析类（OLAP）查询中，通常只会select几个列，而行存储是将一行中所有值都相邻存，哪怕你只需要很少的列，也需要将整行加载到内存中，解析并过滤掉不要的属性。

而列存储将一列中的所有值存储在一起，查询时只读取需要的列即可。

列压缩

由于某些列可能只有一定范围内的值，比如国家名称之类的。那么一列里就会有很多重复值，这就利于压缩。

比如有下面的数据：

行号country
1Japan
2USA
3Japan
4UK
5Japan
6USA
可以用下面这样的位图（bitmap）
取值位图表示（每位对应一行）
-----------------
Japan1 0 1 0 1 0
USA0 1 0 0 0 1
UK0 0 0 1 0 0
当查询where country = 'Japan' or country = 'USA'的时候，只需要执行Japan和USA的按位或即可，然后选出每个位为1对应的那些行即可。

位图非常高效

  • 位图是纯二进制，占用空间极小。
  • CPU进行按位运算极快。

关于写操作，由于顺序位置的问题，插入的时候必须始终更新所有列文件。这里可以用前面的LSM树的方案，先写到内存中，在这里他已经是排序好的，等到特定时候再批量写入磁盘。

编码与演化

从内存中表示到字节序列的转换称为 编码（Encoding） （也称为序列化（serialization） 或编组（marshalling）），反过来称为解码（Decoding）（解析（Parsing），反序列化（deserialization），反编组(unmarshalling)

json,xml,csv各有各的问题，比如json不能处理大整数，只能用字符串来表示。xml冗余等等。但是对于很多需求来说已经足够好了，作为数据交换格式来说，只要各个组织意见一致即可，格式美观、是否高效都无所谓了。

二进制格式如protobuf比json那些压缩率更高，而在相对于json用字段名来标识数据，protobuf用标签号码来标识，在处理兼容问题的时候会更好一些。 比如新代码改了一个字段名，并不会影响旧代码读取数据，因为并不依赖字段名来读取。

avro没有标签号码，所以他比protobuf要更省一点，也因此读取的时候必须使用与写入数据的代码完全相同的模式，才能正确解码二进制数据。

不依赖标签号码，但是他依赖于模式，解析的时候需要写入的模式，所以如果将模式包含到每条记录中去的话，模式可能比数据大得多，那你没有标签号码节省的空间就没有意义了。

有几个办法，比如avro常用于hadoop环境中，用于出处包含数百万条记录的大文件，所有记录都是用相同的模式进行编码。这种情况只要在文件开头包含一次模式进去即可。或者比如在数据库中的记录，都配上一个版本号来表示写入的模式版本。

RPC和REST RPC试图向远程网络服务发出请求，看起来与在同一进程中调用编程语言中的函数或方法相同（这种抽象称为位置透明）。看起来很方便，但是根本上是有缺陷的，在于网络请求与本地函数调用非常不同。

本地函数调用可预测，而网络请求则复杂得多，可能会有网络问题，也可能远端计算机本身有问题。本地调用执行时间每次基本差不多，但是网络调用则每次可能都差很多。以及两边可能用不同的编程语言实现，数据类型的翻译会是一个问题。

使用二进制编码格式的自定义RPC协议可以实现比通用的JSON over REST更好的性能。但是RESTful api还有其他一些显著的优点：方便实验和调试（只需要浏览器或者curl命令即可），能被所有主流的编程语言和平台所支持，还有大量可用的工具的生态系统。

由于这些原因，REST似乎是公共API的主要风格，RPC框架的主要重点在于同一组织拥有的服务之间的请求，通常在同一数据中心内。

分布式数据

数据复制算法

  • 领导者与追随者

一个主库配合多个从库的方式，主库接收写入操作，从库读取主库的日志来完成更新，或者也叫做复制。

复制是通过同步还是异步？完全同步不太现实，那样的话，任何一个节点中断会导致整个系统停滞不前。实际上，如果在数据库上启用同步复制，通常意味着其中一个从库是同步的，其他都是异步的，这样至少保证在两个节点上拥有最新的数据副本，这种有时也叫做半同步。不过通常情况，基于领导者的复制都是完全异步的。

处理节点宕机

  • 从库失效：追赶恢复。

    从库重启后，连接到主库，获取断开时发生的所有数据变更即可。

  • 主库失效：故障切换。

    这种情况相当棘手，其中的一个从库需要被提升为新主库，需要重新配置客户端，写操作发给新主库，其他从库需要从新主库拉取数据变更。

    有可能会出现的大麻烦：

    • 如果是异步复制，有可能有尚未完成复制的数据，会出现一些写入冲突，最简单的办法就是直接丢弃掉，但是可能会打破客户对于数据持久型的期望。
    • 如果数据库需要和其他外部存储相协调，那么丢弃写入内容是极其危险的。一个github事故中，使用自增ID作为主键，而新主库落后于老主库，所以重新分配了一些已经被老主库分配过的主键。而这些主键也在redis中使用，主键重用使得数据不一致，导致一些私有数据泄漏到错误的用户手中。
    • 可能出现两个节点都以为自己是主库。使得数据可能丢失或者损坏。

这些问题没有简单的解决方案，因此即使软件支持自动故障切换，不少运维团队还是更愿意手动执行故障切换。

复制日志

  • 基于语句的复制 主库直接将写入请求（语句）发给从库，比如关系数据库中的insert，update语句，然后从库执行该sql，就像从客户端收到一样。听上去合理，但是有很多问题。

    • 非确定性函数的调用，比如now(), rand()。
    • 自增列，每个副本必须按照完全相同的顺序执行。当有多个并发执行的事务时，这可能会成为一个限制。
    • 有副作用的语句（如触发器，存储过程，用户定义的函数）

  • 预写式日志（WAL） 在任何一种情况下，日志都是包含所有数据写入的仅追加字节序列。

主要缺点是日志记录的数据非常底层：wal包含哪些磁盘块中的哪些字节发生了更改。使得复制与存储引擎紧密耦合。如果数据库将其存储格式从一个版本更改为另一个版本，通常不可能在主库和从库上运行不同版本的数据库软件。

PostgreSQL和Oracle等使用这种方式。

这看上去一个微小的实现细节却可能对运维产生巨大的影响。如果复制协议允许从库使用比主库更新的软件版本，则可以先升级从库，然后执行故障切换，使升级后的节点之一成为新的主库，从而执行数据库软件的零停机升级。如果复制协议不允许版本不匹配（传输WAL经常出现这种情况），则此类升级需要停机。

  • 逻辑日志复制（基于行） 关系型数据库的逻辑日志通常是以行的粒度描述对数据库表的写入的记录序列：
    • 对于插入的行，日志包含所有列的值
    • 对于删除的行，日志包含足够的信息来唯一标识已删除的行
    • 对于更新的行，日志包含足够信息来唯一标识更新的行，以及所有列的新值

mysql的二进制日志使用这种方式。

逻辑日志与存储引擎内部分离，因此可以更容易地保持向后兼容，从而使领导者和跟随者能够运行不同版本的数据库软件甚至不同的存储引擎。

  • 基于触发器的复制 上面列举的都是由数据库系统实现的，不涉及任何应用程序代码。通常情况下，这就是你想要的。但是有些情况可能需要更多灵活性，比如你只想复制数据的一个子集等。可以使用数据库自带的触发器和存储过程，只是通常比其他复制方法有更高的开销，也更容易出错。

复制延迟问题

（说起来也神奇，今天请假休息，但是看到群里客户报了一个估计就是复制延迟的问题，然后我刚好今天看这本书的这块地方）

简单来说就是由于异步复制导致数据滞后。

  • 读己之写 从主库进行写入数据，去从库读取数据。如果写完马上去读的时候，用户可能看不到刚提交的数据，以为丢失了。这种情况，需要读己之写一致性。其他用户的写入允许稍后才会看到，保证用户自己的输入已被正确保存。

    • 直接从主库读自己的数据，他人的数据去从库读
    • 如果应用中大部分内容都可能被用户编辑，那上面的方法就没用了， 因为大部分都从主库读，拓展从库就没有意义了。这种时候可以跟踪上次更新的时间，比如更新后一分钟内，从主库读。
    • 客户端可以记住最近一次写入的时间戳，系统需要该时间戳之前的变更都已经复制到从库了。

另外一种复杂的情况是，用户从多个设备请求服务，这种情况需要提供跨设备的写后读一致性。

  • 单调读

    异步从库读取的另外一个异常例子是，用户可能遭遇时光倒流。简单来说就是，每个从库的延迟并不一样，多次从多个从库读取，可能会出现刚刷出来的数据再刷一下就不见了的情况。

    单调读仅意味着如果一个用户顺序地进行多次读取，他们不会看到时间后退。一种实现方式就是确保同一个用户总是从同一个副本进行读取。

  • 一致前缀读

    分区数据库中的一个特殊问题。有这么一种情况，a给b发送了一条消息，b进行了回复。发送消息的作为观察者的c有可能先读到回复，再读到a的消息。

    如果数据总是以相同的顺序写入，则读取总是会看到一致的前缀，所以这种异常不会发生。但是再许多分布式数据库中，不同的分区独立运行，因此不存在全局写入顺序，用户可能会看到数据库中某些部分处于较旧的状态，某些处于较新的状态。

多主复制

上面的情况都是单一的领导者，一般适用于单个数据中心的情况。如果有多个数据中心，分布在多个地方，那就可以考虑多个领导者。每个数据中心使用常规的主从复制，在数据中心之间，每个数据中心都会将其更改复制到其他数据中心的主库中。

如果多个数据中心依然使用单个领导者，那么远距离用户因为网络延迟，写入时间就会增加。数据中心之间的通信通常穿过公共互联网，这可能不如数据中心本地网络可靠。

故障切换时，每个数据中心可以独立于其他数据中心继续运行，并且发生故障的数据中心归队时，复制会自动赶上。

缺点

  • 两个数据中心可能会同时修改相同的数据，需要解决写冲突的问题。
  • 多主复制在许多数据库中都属于改装功能，所以常常存在微妙的配置缺陷，经常会出现意外的反应。因此，多主复制往往被认为是危险的领域，应尽可能避免。

写入冲突并不好解决，所以最简单办法可能是避免冲突。

大多数主从复制工具允许应用程序代码编写冲突解决逻辑。

关于自动冲突解决的一些研究：

  • 无冲突复制数据类型

    是可以由多个用户同时编辑的集合，映射，有序列表，计数器等一系列数据结构，他们以合理的方式自动解决冲突。

  • 可合并的持久数据结构

    显示跟踪历史记录，类似于Git版本控制系统。

  • 可执行的转换

    Google Docs等合作编辑应用背后的冲突解决算法。

无主复制

最早的一些复制数据系统是无领导的，但在关系数据库主导的时代，这个想法几乎被忘却。在亚马逊将其应用于内部的Dynamo系统后，又流行了起来。（困惑的是，aws提供的DynamoDB却是基于单领导的）

一些实现中，客户端直接将写入发送到几个副本中，还有一些这通过一个协调者节点代表客户端进行写入。

当有一个节点故障时，并行的写入副本时该节点就错过了，其他节点写入成功，因此客户端会认为写入成功而忽略错过的了一个节点的事实。而当节点恢复后，当有用户去并行的从各个节点读数据的时候，就会读到这个节点旧的值。通过各个节点的数据的版本号可以判断哪个是更新的。

两种复制方案

  • 读修复

    当客户端并行读取多个节点时，可以检测到任何陈旧的响应，此时可以将新值写回到该副本。

  • 反熵过程

    通过后台进程不断查找副本之间的数据差异，并将缺少的数据从一个副本复制到另一个副本。与基于领导者的复制不同的是，此反熵过程不会以任何特定的顺序复制写入，并可能会有显著的延迟。

读写的法定人数

对三个副本的写入即使只有两个成功，写入依然是成功的，读的时候只要读两个副本就一定能得到一个新值。

更一般的来说，如果有n个副本，每个写入必须由w节点确认才能被认为是成功的，查询的时候必须查询r个节点（来保证获取新值），也就是必须w+r>n。这个r和w就被称为法定人数的读写。

尽管法定人数似乎能保证读取返回最新的写入值，但在实践中并不那么简单。比如，写入成功的副本数小于w，那么整体会判定写入失败，但是成功的副本并没有回滚，后续依然有可能读取到失败的写入值。等等许多问题。

监控陈旧度

基于领导者的复制，因为写入按照相同的顺序应用于领导者和追随者，可以根据节点在复制日志中的位置，对比领导者的当前的位置就能测量出复制滞后量。

但是无领导复制系统中，没有固定的写入顺序，这使得监控变得困难。