大规模系统设计

可靠性

1.部件错误，偶发性错误，间歇性错误，永久性错误。系统要容错
2.系统失效，处理机错误：fail-silent错误，byzantine错误
3.同步与异步系统容错：同步是系统能在确定时间内对一个消息做出响应。
异步很难进行容错处理，因为不知道响应时间的上界。解决容错的方式是冗余。海明码，重传，备份（冗余处理机）。
指标：MTTF

组织冗余处理机：

主动复制

（多个处理器完全并行同时工作，一部分失效其他继续工作。所有服务器看作一个大的有限状态机+表决器）；
2k+1个服务器可以实现k容错。需要全局顺序编号，保证命令到每个服务器到达顺序一样。

主从备份

（一个作为服务器，一个失效，另一个代替）。

1. 若主服务器在处理完请求消息之后并将更新消息发送给备份服务器之后崩溃了
   ◼ 在备份服务器取代主服务器后，该请求消息会再次从客户端传到主服务器，于是该请求消息就会被处理两次。
   ◼ 若这个处理有副作用的话，那么，就可能产生问题。

2. 若主服务器在第4步之后第6步之前崩溃的话，那么，这个请求消息要被执行三次：
   ◼ 第2步主服务器执行一次；
   ◼ 第4步备份服务器执行一次；
   ◼ 在备份服务器取代主服务器之后又执行一次。

3. 拜占庭错误没法检查，奔溃服务器和服务器有点慢也没法区分。在切换服务器之后主服务器必须停止工作。

4. 什么时候在主服务器和备份服务器之间进行切换。心跳/轮询

5. 使用由主服务器和备份服务器共享的双向端口磁盘。 但磁盘会坏

分布式协作一致性

让所有未出错的处理机能够对某些问题达成一致性意见，并在有限步数内完成协作操作。
两军问题（通信不可靠）：对于无故障的处理机来说，在通信不可靠的情况下，两个进程要达到协作一致是完全不可能的。
拜占庭将军问题（处理机不可靠）：假设通信可靠，但是有叛徒。 少数服从多数2/3
但是异步系统一个处理机奔溃就没法达到一致性

可拓展性

系统怎么应对负载增加

如果系统以某种方式增长， 我们应对增长的措施有哪些；”我们该如何添加计算资源来处理额外的负载＂可能是Web服务器的每秒请求处理次数，数据库中写入的比例， 聊天室的同时活动用户数量， 缓存命中率等。
有时平均值很重要，有时系统瓶颈来自于少数峰值。最好使用百分位数，为了弄清楚异常值有多槽糕， 需要关注更大的百分位数，如p95, p99, p999
批处理系统如Hadoop中， 我们通常关心吞吐量，而在线系统通常更看重服务的响应时间

把无状态服务分布然后扩展至多台机器相对比较容易，而有状态服务从单个节点扩展到分布式多机环境的复杂性会大大增加。如果负载高度不可预测，则自动弹性系统会更加高效，但或许手动方式可以减少执行期间的意外情况

Load Banlancer

一、 系统的扩展性 (Scalability)

1. 如何在垂直扩展（升级机器）和水平扩展（增加机器）之间做取舍？

• 垂直扩展 (Scale Up)： 通过增加单台服务器的 CPU、内存或磁盘来提升性能。
  • 优点： 业务代码无需修改，实施简单，不存在分布式状态同步问题。
  • 缺点： 硬件性能有物理天花板，成本呈指数级上升；存在单点故障风险。
• 水平扩展 (Scale Out)： 通过增加服务器的数量来分担流量。
  • 优点： 理论上可以无限扩展，性价比高；天然具备高可用性（一台宕机不影响整体）。
  • 缺点： 极大增加了架构复杂度，引入了负载均衡、数据一致性、分布式事务等难题。
• 取舍： 现代大规模数据系统（如互联网大厂架构）绝大多数以水平扩展为主，在底层数据库节点上辅以适当的垂直扩展。

2. 如有多个服务器，如何进行负载均衡？ 通过在客户端和服务器之间引入负载均衡器（如 Nginx、LVS、HAProxy 或云上的 SLB）。 常用的分发算法包括：

• 轮询 (Round Robin) / 加权轮询： 均匀地将请求分发给后端节点。
• 最小连接数 (Least Connections)： 将新请求分配给当前负载最轻、连接最少的服务器。
• 一致性哈希 (Consistent Hashing)： 根据用户 ID 或 IP 进行哈希，确保同一用户的请求固定打到同一台机器，常用于缓存系统的路由。

二、 分布式一致性与容错机制

1. 如有多个副本，如何在分布式环境下保证一致性？ 这需要根据具体的业务场景在 CAP 理论（一致性、可用性、分区容错性）中做出权衡：

• 强一致性： 要求所有副本在同一时刻数据绝对一致（如金融账本）。通常采用 Raft 或 Paxos 等共识算法，通过“多数派投票确认”来保证数据同步。
• 最终一致性： 允许短时间内数据不一致，以换取系统的高可用和低延迟（如社交网络点赞）。通常利用消息队列 (MQ) 进行异步的数据同步。

2. 分布式协作的底层挑战：消息、进程与时钟

• 消息传递不可靠： 网络中随时会发生丢包、延迟或网络分区，因此系统设计必须包含重试、超时和确认机制 (ACK)。
• 进程崩溃模型： 节点确实会崩溃。内部服务集群主要防范 Fail-silent 错误（节点宕机、无响应）；而在区块链等去信任化网络中，才需要耗费巨资防范 Byzantine（拜占庭）错误（节点恶意伪造或篡改数据）。
• 异步系统： 现实中的广域网系统多为异步系统，消息到达的延迟没有理论上限，因此不能完全依赖系统的物理时钟来判断事件的绝对先后顺序（需要引入逻辑时钟）。

可维护性

设计架构演进

数据存储

列式存储（Columnar Storage）、数据仓库优化以及Apache ORC/Parquet文件格式

📊 模块一：核心原理——为什么要“竖着存”？

列式存储的核心思想很简单：不要把一行数据挤在一起，而是把同一列的数据存在一起。

1. 优势（OLAP 场景）

• 按需读取（I/O 优化）：如果查询只需要 name 和 age 两列，列式存储只读取这两列的文件；而行式存储（OLTP）必须把整行数据（可能包含100个字段）都从磁盘捞出来，非常浪费 I/O。
• 高压缩率：同一列的数据类型相同且往往具有相似性（比如全是“男/女”，或者递增的 ID），非常适合压缩（如游程编码、位图索引），大幅降低磁盘吞吐量需求。
• 向量化执行：现代 CPU 可以对连续存储的列数据进行批量 SIMD 指令优化，提升计算速度。

2. 劣势（OLTP 场景）

• 写入困难：如果要更新某一行，列式存储需要修改多个列文件，无法像行式存储（B-Tree）那样原地更新。对于压缩过的列式存储，如果在中间插入一行数据，为了保持所有列文件中行位置的一致性，可能需要重写所有列文件。

• 解决方案：通常采用 LSM-Tree (Log-Structured Merge-Tree日志结构引擎) 思路。写入先入内存（MemTable），积累多了再排序，批量以“追加”方式写入磁盘（SSTable），后台通过合并（Compaction）处理删除和更新。查询时，系统会同时检查磁盘上的列数据和内存中最近的写入，合并后返回结果。这一切对用户是透明的。（Vertica, BigTable, HBase 等均采用此方案）。

• 如果需要还原整行数据（例如第 23 行），需从所有相关列文件中提取第 23 个条目，将它们拼接。

---

⚙️ 模块二：关键技术——列式存储的“黑科技”

1. 排序与索引

• **稀疏索引 (Sparse Indexes)**：不是每一行都建索引，而是每隔一定数量的行（如 10,000 行）建一个索引条目。
  • Min/Max 索引：记录每个数据块（Stripe/Row Group）中的最大值和最小值。查询时如果 WHERE age > 100，而该块最大值是 90，系统直接跳过整个块，这叫谓词下推（Predicate Pushdown）。
• **位图索引 (Bitmap Index)**：
  • 适合低基数列（如性别、状态）。
  • product_sk = 30 对应一串二进制 1010...。
  • 位图索引非常适合数据仓库中常见的条件查询（如 WHERE 语句）：- 对于 IN 查询（如 product_sk IN (30, 68, 69)）：只需加载这三个值的位图，进行按位或 (OR) 计算即可。- 对于 AND 查询（如 product_sk = 31 AND store_sk = 3）：加载对应位图进行按位与 (AND) 计算。因为各列的行顺序相同，一列位图的第 K 位与另一列位图的第 K 位绝对对应同一行数据。
• 排序优化：在列存储中，通常会选择经常查询的列作为主排序键

  • 提升压缩率：排序后，相同的值会聚集在一起形成超长序列。使用简单的**游程编码 (Run-length Encoding)**，能将数十亿行的连续重复数据压缩到仅几千字节。

  • 冗余排序版本：由于不同的查询能从不同的排序方式中获益，且数据本就需要复制多份用于容错。因此，系统（如 C-Store, Vertica）可以在不同机器上存储采用不同列排序的数据副本，查询时自动选择最合适的一个。

2. 物化聚合与数据立方体

• **物化视图 (Materialized Views)**：把查询结果（如 SUM(sales)）直接存成物理表。虽然写入慢（需要更新聚合值），但读取极快。它在读密集的 OLAP 中比在 OLTP 中更有价值。
• **OLAP 立方体 (Cube)**：预计算多维度的聚合（如按地区、时间、产品分类的销售额网格）。物化视图的一种特殊形式，是一个由多维分组构成的聚合网格。
  • 操作方式：钻取 (Drill-down)、上卷 (Roll-up)、切片 (Slice)、切块 (Dice)、旋转 (Pivot)。
  • 优缺点：预计算使得针对特定维度的查询极快；但缺乏灵活性（无法查询未被包含在维度中的原始明细数据）。

3. 复杂数据处理 (Nested Data)

现代列式存储（如 Parquet）支持 JSON 风格的嵌套结构（Struct, List, Map）。

• **定义层 (Definition Levels)**：用来标记某个值是否为空（Null）。因为列式存储不存“空”，需要标记“从第几层开始没定义”，否则读取时会错位。
• **重复层 (Repetition Levels)**：用来标记 List（数组）在哪个层级开始重复。例如一个用户有多个地址，需要知道什么时候切换到下一个用户。

---

📂 模块三：主流格式详解——ORC vs Parquet

这两个是 Hadoop 生态中最主流的列式存储格式。

1. Apache ORC (Optimized Row Columnar)

• 背景：Hive 社区开发，针对 Hive OLAP 查询优化。
• 结构：
  • Stripe：水平切分的数据块，每个 Stripe 包含多列数据。
  • Footer：存储元数据（Schema）和统计信息（Min/Max）。
  • Postscript：文件尾部，记录压缩方式、Footer 长度等。
• 特点：内置轻量级索引，支持 ACID 事务（Hive 3.0+），对 Hive 生态支持最好。
• 稀疏索引加速：
  • 三级数据统计索引：File Level（文件级统计）、Stripe Level（确定是否需要读取该 Stripe，如最大/最小值过滤）、Index group level（默认每 10000 行一组进行统计，精确定位）。
  • 位置指针索引：帮助快速定位数据块。

2. Apache Parquet

• 背景：基于 Google Dremel 论文，由 Twitter 和 Cloudera 开发。
• 结构：
  • Row Group：缓存单元，包含多列的 Column Chunk。
  • Page：编码和压缩的基本单元。
• 特点：
  • 跨平台：支持 Avro, Thrift, Protocol Buffers 等多种数据模型。
  • 嵌套支持：原生支持复杂的嵌套数据结构（通过 Definition/Repetition Levels）。嵌套解析核心：
    • **Repetition Levels (重复级别)**：记录嵌套结构中，当前值与前一个值在哪一层节点不再共享（需创建新节点）。
    • **Definition Levels (定义级别)**：专门用于处理空值（NULL）。记录当前路径上第几层开始是未定义的，防止因空值导致后续数据错位，完美还原复杂的树状 Schema。
  • 通用性：Spark, Flink, Drill, Presto 等引擎的通用首选格式。

---

⚔️ 模块四：架构全景——OLTP vs OLAP

最后总结了数据库存储的两大流派，这是理解所有上述技术的宏观视角：

表格

维度	OLTP (联机事务处理)	OLAP (联机分析处理)
典型场景	用户日常操作（转账、下单、发帖）	数据分析师跑批（月度报表、用户画像）
查询特征	简单、频繁、基于主键查找（点查）	复杂、低频、扫描百万行数据（全表扫）
瓶颈	磁盘寻道时间 (Seek Time)	磁盘带宽 (Bandwidth)
存储引擎	行式存储 (Row-based)	列式存储 (Column-based)
数据结构	B-Tree (原地更新)	LSM-Tree (日志结构/追加写)
代表产品	MySQL, PostgreSQL, HBase	Hive, Spark SQL, ClickHouse
核心指标	高并发、低延迟	高吞吐、高压缩比

💡 总结

这份文档的核心逻辑是：为了应对大数据分析（OLAP）中海量数据扫描的性能瓶颈，列式存储应运而生。 它通过按列存储实现高压缩和按需读取，利用LSM-Tree结构解决写入难题，并通过ORC/Parquet等先进格式支持复杂的嵌套数据和高效的编码索引，最终在分析场景下实现了远超传统行式数据库的性能。

数据编码方式

程序通常（至少）使用两种不同的数据表示形式
◼ 在内存中， 数据保存在对象、结构体、列表、数组、哈希表和树等结构中。这些数据结构针对CPU的高效访问和操作进行了优化（通常使用指针）。
◼ 将数据写入文件或通过网络发送时， 必须将其编码为某种自包含的字节序列（例如JSON文档）。由于指针对其他进程没有意义， 所以这个字节序列表示看起来与内存中使用的数据结构大不一样

编码

在这两种表示之间需要进行类型的转化。从内存中的表示到字节序列的转化称为编码（或序列化等），相反的过程称为解码（或解析， 反序列化）。
许多编程语言都内置支持将内存中的对象编码为字节序列。经常与语言绑定

采用跨语言的数据表示格式，可由不同编程语言编写和读取的标准化编码， 显然JSON和XML是其中佼佼者。但是存在严重的性能问题，解析速度太慢，数据存储冗余大。

期望出现一种带有schema描述的数据表示格式，通过统一化的schema描述,可以约束每个字段的类型,进而为存储和解析数据带来优化。最终为用户自动生成各种语言的代码。
统一schema的引入，可以减少属性名称重复存储带来的开销，也有利于数据共享。

Thrift,Protocol Buffers

Apache Thrift和Protocol Buffers (protobuf) 是基于相同原理的两种二进制编码库。

Apache Avro

支持不需要中间代码的生成，直接拿schema解析

静态数据类型
动态数据类型

特性	Apache Thrift (以及 Protocol Buffers)	Apache Avro
核心思想	静态类型 (Static Typing)	动态类型 (Dynamic Typing)
关键区别	靠“编号” (Tag/ID) 定义字段时必须给一个数字ID（如 1: name）。传输时只传数字，不传字段名。	靠“名字” (Name) 传输数据时，必须带上 Schema（结构定义）。它靠字段名字来匹配，而不是数字。
代码生成	必须 先写好结构定义，然后必须用工具生成 Java/Python 等代码，才能写程序。	可选 虽然也可以生成代码，但你也可以直接读 Schema 文件（JSON格式）来解析数据，不需要生成代码。
模式演化 (Schema Evolution)	较死板 你不能随便改字段名（因为传输不看名字），但可以加减字段（只要ID不冲突）。	很灵活 因为靠名字匹配，所以数据库结构（Schema）变了（比如加了一列），旧程序读新数据时能自动处理。
适用场景	适合RPC（远程过程调用） 比如微服务之间调用（C++调Python），需要高性能、低延迟。	适合大数据存储与批处理 比如 Hadoop、Hive，数据要存很久，未来可能用不同版本的程序读取。

---

3. 深入浅出：为什么 Avro 不适合 RPC，而 Thrift 适合？

文档中提到：“Thrift 和 Avro 都构建了各自的 RPC 框架……但 Avro 的 RPC 实现语言较少（主要 Java/Python/Ruby）”。

• Thrift 为什么适合 RPC（微服务通信）？

  • 因为 Thrift 传输数据时不带字段名，只带数字ID。比如 1 代表用户名，2 代表年龄。
  • 这样数据包非常小，传输速度极快。而且它强制你先生成代码，保证了客户端和服务器端的类型绝对安全。这是微服务通信最看重的。

• Avro 为什么诞生？（为 Hadoop 而生）

  • 文档提到：Hadoop 之前的系统有性能瓶颈，且只能用 Java。
  • Avro 的设计初衷是为了大数据存储。大数据场景下，你今天存的数据，可能一年后才拿出来分析。
  • 如果一年后你的程序代码变了（比如字段改名了），用 Thrift（靠ID）可能就读不出来了，或者很麻烦。而 Avro（靠名字）只要名字对得上就能读，且支持动态语言（Python/JS）直接读，不需要编译代码。

1. Solr调用：是老派的（或者通用的）Java数据访问方式。
2. Thrift：是 Facebook 弄出来的，强调高性能、跨语言，适合服务之间互相调用（RPC），靠数字ID通信。
3. Avro：是 Hadoop 创始人弄出来的，强调灵活、适合存储，适合大数据分析，靠名字匹配，不需要生成代码也能读。

一句话建议：

• 如果要做微服务，选 Thrift 或 gRPC (Protocol Buffers)
• 如果要做大数据数仓（存 HDFS），选 Avro 或 Parquet。

分布式数据存储

为什么要分布存：拓展性，容错和高可用性，延迟

垂直拓展：

共享内存架构，一个操作系统管理更多的CPU, 内存和磁盘，通过高速内部总线使每个CPU都可以访问所有的存储器或磁盘。
问题在于， 成本增长过快甚至超过了线性。一台机器尽管拥有了两倍的硬件指标但却不一定能处理两倍的负载。
高端的服务器可以热插拔很多组件（在不关闭机器的情况下更换磁盘， 内存模块， 甚至是CPU) 。但很显然， 它仍无法提供异地容错能力。

共享磁盘架构

有多台服务器， 每个服务器各自拥有独立的CPU和内存， 然后将数据存储在可共享访问的磁盘阵列上， 服务器与磁盘阵列之间往往通过高速网络连接。

这种架构多适用于数据仓库等负载， 然而通常由于资源竞争以及锁的开销等限制了其进一步的扩展能力。

无共享架构，也就是水平拓展

运行数据库软件的机器或者虚拟机称为节点。每个节点独立使用本地的CPU, 内存和磁盘。节点之间的所有协调通信等任务全部运行在传统网络（以太网）之上且核心逻辑主要依靠软件来实现。

◼ 无共享系统不需要专门的硬件，具有较高的性价比。它可以跨多个地理区域分发数据，从而减少用户的访问延迟，甚至当整个数据中心发生灾难时仍能继续工作。但也会给应用程序带来更多的复杂性

接下来讨论水平拓展多节点怎么提高性能

数据分布

数据复制

Q：如何保证副本间数据是一致的？
A：主从复制，每笔修改都进行一次更新。所有写请求都经由主节点，而任何副本只能接受只读查询。对于读操作密集的负载（如Web) , 这是一个不错的选择。

Q：同步复制还是异步复制
A：

• 把所有从节点都配置为同步复制有些不切实际。因为这样的话，任何一个同步节点的中断都会导致整个系统更新停滞不前。全异步模式:如果主节点发生失败且不可恢复，则所有尚未复制到从节点的写请求都会丢失。这意味着即使向客户端确认了写操作， 却无法保证数据的持久化。但是吞吐量会更好。
• 实践中，如果数据库启用了同步复制，通常意味着其中某一个从节点是同步的， 而其他节点则是异步模式。万一同步的从节点变得不可用或性能下降， 则将另一个异步从节点提升为同步模式。这样可以保证至少有两个节点（即主节点和一个同步从节点）拥有最新的数据副本。这种配置有时也称为半同步。

复制滞后问题：

并非所有的写入都反映在从副本上，如果同时对主节点和从节点发起相同的查询，可能会得到不同的结果。这是暂时的不一致。比如：

单调读保证，如果某个用户依次进行多次读取， 则他绝不会看到回滚现象，比如确保每个用户从固定副本中读取
前缀一致读：对于一系列按照某个顺序发生的写请求， 那么读取这些内容时也会按照当时写入的顺序。比如确保任何具有因果顺序关系的写入都交给一个分区来完成， 但该方案真实实现效率会大打折扣。

配置新从节点

如何做到在不停机、数据服务不中断的前提下完成从节点的设置？

心跳+选举机制

变数

节点失效、网络不可靠、副本一致性、持久性、可用性与延迟之间各种细微的权衡， 实际上正是分布式系统核心的基本问题。

（1）如果使用了异步复制， 且失效之前， 新的主节点并未收到原主节点的所有数据；在选举之后， 原主节点很快又重新上线并加入到集群，原主节点未意识的角色变化(脑裂)， 还会尝试同步其他从节点，新的主节点很可能会收到冲突的写请求。
原主节点上未完成复制的写请求就此丢弃.没有很好解决冲突的办法,系统会采取措施来强制关闭其中一个节点.
(2 ) 某个数据并非完全同步的MySQL从节点被提升为主副本， 数据库使用了自增计数器将主键分配给新创建的行， 但是因为新的主节点计数器落后于原主节点（即二者并非完全同步），它重新使用了已被原主节点分配出去的某些主键，而恰好这些主键已被外部Redis所引用， 结果出现MySQL和Redis之间的不一致， 最后导致了某些私有数据被错误地泄露给了其他用户。

复制日志

1. 基于语句的复制
   每个INSERT、UPDATE或DELETE语句都会转发给从节点， 并且每个从节点都会分析并执行这些SQL语句， 如同它们是来自客户端那样。
   非确定性函数的语旬， 如NOW()，RAN()，语句中使用了自增列， 或者依赖于数据库的现有数据，有副作用的语句（例如， 触发器、存储过程、用户定义的函数等），会导致每个副本表现不一样
2. 基于预写日志(WAL)传输
   所有对数据库写入的字节序列都被记入日志。日志描述的数据结果非常底层： 一个WAL包含了哪些磁盘块的哪些字节发生改变， 诸如此类的细节。
   这使得复制方案和存储引敛紧密耦合。如果数据库的存储格式从一个版本改为另一个版本， 那么系统通常无法支持主从节点上运行不同版本的软件。
   允许从节点的软件版本比主节点更新，则可实现数据库的不停机升级。
3. 基于行的逻辑日志复制
   关系数据库的逻辑日志通常是指一系列记录来描述数据表行级别的写请求:
   
   逻辑日志与存储引擎逻辑解耦， 因此可以更容易地保持向后兼容， 从而使主从节点能够运行不同版本的软件甚至是不同的存储引擎
   

多主节点复制

在多主节点模型中，每个写操作都可以在本地数据
中心快速响应， 然后采用异步复制方式将变化同步到其他数据中心。有效屏蔽了数据中心之间的网络延迟。

避免冲突

• 多主复制存在一个很大的缺点：不同的数据中心可能会同时修改相同的数据， 因而必须解决潜在的写冲突。

应用层可以保证对特定记录的写请求总是通过同一个主节点，这样就不会发生写冲突。从用户的角度来看，这基本等价于主从复制模型。

收敛于一致状态

• 对于多主节点模型，不存在顺序写入， 所以最终值也会变得不确定。(主节点1接受到请求把标题更新为B, 然后更新为C; 而在主节点2, 则是相反的更新顺序。两者都是正确的。
  

多主节点复制的拓扑结构：请求从一个节点的传播到其他节点的通信路径。

单主节点和多主节点复制的核心思路：
即客户端先向某个节点（主节点）发送写请求， 然后数据库系统负责将写请求复制到其他副本。由主节点决定写操作的顺序，从节点按照相同的顺序来应用主节点所发送的写日志。

配置多主节点

每个主节点都可以接受写操作，后面复制的流程类似：处理写的每个主节点都必须将该数据更改转发到所有其他节点。每个主节点还同时扮演其他主节点的从节点。

冲突

不同的数据中心可能会同时修改相同的数据， 因而必须解决潜在的写冲突。如果是主从复制数据库，第二个写请求要么会被阻塞直到第一个写完成，要么被中止（用户必须重试）。在多主节点的复制模型下，这两个写请求都是成功的，并且只能在稍后的时间点上才能异步检测到冲突，那时再要求用户层来解决冲突为时已晚。
每个设备都有一个充当主节点的本地数据库（用来接受写请求）， 然后在所有设备之间采用异步方式同步这些多主节点上的副本，同步滞后可能是几小时或者数天， 具体时间取决于设备何时可以再次联网。

处理：
处理冲突最理想的策略是避免发生冲突，即如果应用层可以保证对特定记录的写请求总是通过同一个主节点，这样就不会发生写冲突。
收敛于一致状态：

拓扑结构：有固定的写请求从一个节点的传播到其他节点的通信路径。

无主节点复制

客户端将写请求发送到多个节点上，读取时从多个节点上并行读取， 以此检测和纠正某些过期数据。

问题：
节点失效时写入数据库：失败，后续需要重新写入。

如果有n个副本，写入需要w个节点确认，读取必须至少查询r个节点，则只要w + r > n, 读取的节点中一定会包含最新值。r 和w是用于判定读、写是否有效的最低票数。对于读多写少的负载，设置w=n和r = l比较合适，这样读取速度更快，但是一个失效的节点就会使得数据库所有写入因无法完成quorum而失败。

读到旧数据：当一个客户端从数据库中读取数据时， 它不是向一个副本发送请求， 而是并行地发送到多个副本。客户端可能会得到不同节点的不同响应， 包括某些节点的新值和某些节点的旧值。可以采用版本号技术确定哪个值更新。

网络中断怎么办：放松的仲裁

一个网络中断可以很容易切断一个客户端到多数数据库节点的链接。尽管这些集群节点是活着的，而且其他客户端也确实可以正常链接，但是对于断掉链接的客户端来讲，情况无疑等价于集群整体失效。

这是在解决两个问题：

1. 当原本负责存储数据的节点都挂了或连不上时，怎么办？（引出“宽松的仲裁”）
2. 当数据分布在世界各地时，怎么读写才快？（引出“多数据中心操作”）

1. 宽松的仲裁与数据回传：灵活变通的“临时寄存”

背景：
在标准的无主复制中，如果你要存一份数据，系统规定必须存到指定的 N 个节点上（比如 N=3），并且要有 W 个（比如 W=2）确认才算成功。

问题：
假设网络断了，或者那指定的 3 个节点刚好都挂了。虽然集群里还有其他几千个节点是活着的，但按照死板的规定，你连不上那指定的节点，就没法写入，系统就报错。

解决方案：宽松的仲裁
系统决定“变通”一下。既然指定的节点连不上，那我就先把数据存到任何能连上的 W 个节点上，哪怕它们本来不属于这组数据的“法定”存储位置。

• 比喻：你要把快递送到指定的“3号仓库”，结果路断了。快递员（客户端）为了不延误，把快递暂时寄存在了路口的“便利店”（非指定节点）。只要凑够了签收人数，就算投递成功。

后续：数据回传
一旦网络恢复，或者指定的“3号仓库”修好了，那个“便利店”会把暂存的快递转交给“3号仓库”。

• 术语：这个“转交”的过程就叫数据回传或暗示移交。

代价（非常重要）：
虽然这样大大提高了写入成功率（只要有任意节点活着就能写），但牺牲了一致性。

• 风险：如果你写完立刻去读，读取请求可能还是发给了原来的那组节点（它们还没收到回传的数据），结果你就读不到刚才写进去的最新值。
• 现状：Riak 默认开启这个功能（优先保可用），Cassandra 默认关闭（优先保一致，但也支持开启）。

2. 多数据中心操作：因地制宜的“就近原则”

背景：
当你的数据库节点分布在北京、上海、纽约时，网络延迟很高。如果每次写入都要等纽约的节点确认，用户体验会非常差。

解决方案：
系统允许客户端“就近”确认，而不必等待全球所有节点。

这里提到了两种不同的实现流派：

• 流派一：Cassandra / Voldemort 模式（全局视野，本地确认）

  • 机制：系统眼里， N （副本总数）是全球所有数据中心的节点总和。但是，配置规则时允许“偏心”。
  • 操作：客户端写入时，只要本地数据中心的几个节点确认了，就立刻返回成功。至于同步到远程数据中心（如纽约），那是后台异步慢慢做的事。
  • 比喻：你在北京分公司签合同，只要北京这边的3个领导签字就算生效了，不需要等美国总部的签字。

• 流派二：Riak 模式（本地视野，后台复制）

  • 机制：系统把每个数据中心看作独立的集群。 N 仅指当前数据中心内的节点数。
  • 操作：客户端只跟本地数据中心玩。数据中心之间的数据同步，是在后台像“多主复制”那样异步进行的。
  • 比喻：北京分公司和上海分公司各管各的，写完本地就算完，两个分公司之间自己私下传阅文件。

总结

这段话的核心逻辑是：

1. 为了在极端故障下也能写入，我们发明了宽松的仲裁，允许数据先存在“临时节点”上，回头再搬运（回传），但这可能导致短暂的读不到新数据。
2. 为了在跨地域网络下也能快，我们发明了多数据中心优化，允许客户端只等“本地节点”确认，不用苦等全球同步。

冲突

在无主复制（如Dynamo）系统中，当多个客户端同时修改同一个数据时，系统如何检测并解决这些“冲突”，最终让所有数据副本达成一致。
讲了两个核心问题：

1. 如何定义“谁更新”？ 是简单粗暴地看时间，还是聪明地看因果关系？

2. 如何解决冲突？ 是丢弃旧数据，还是把它们都保留下来让应用层处理？

   **最后写入者获胜 (LWW)**：每个写入操作都会带上一个时间戳。当发生冲突时，系统会比较时间戳，只保留最大的那个，其他的版本都会被无情地覆盖掉。
   在网络延迟不稳定的情况下，时间戳并不能真实反映操作的先后顺序。

   版本矢量：不只看时间，而是通过追踪数据的“家谱”（版本历史）来判断操作之间的关系。因果依赖：如果操作B是在操作A的基础上进行的（比如B知道A的存在），那么A就发生在B之前。B可以安全地覆盖A。并发：如果操作A和操作B互不知道对方（比如两个人同时修改同一个文件），那么它们就是并发的。系统无法判断谁该覆盖谁，必须将两者都保留下来。
   

数据分区

数据复制可以提高可扩展性，但是面对一些海量数据集或非常高的查询压力，复制技术还不够，我们还需要将数据拆分成为分区，也称为分片。

◼ 不同的分区可以放在一个无共享集群的不同节点上。这样一个大数据集可以分散在更多的磁盘上，查询负载也随之分布到更多的处理器上。

怎么分区？

关键字分区。但是万一关键词是时间戳依然会导致热点。
要均匀，不能倾斜（系统热点）-》随机分配，哈希。失去了区间查询和有序相邻的特性。

大多数的系统今天仍然无法自动消除这种高度倾斜的负载，而只能通过应用层来减轻倾斜程度。例如， 如果某个关键字被确认为热点，一个简单的技术就是在关键字的开头或结尾处添加一个随机数，将访问分散。但读数据时，需要将分散的数据进行合并。

二级索引

二级索引的最大问题是它和数据分区不是完全对应的，二级索引不像主索引那样可以唯一确定数据。有两种设计二级索引的方法
◼基于文档的二级索引分区

这种索引方法中，每个分区完全独立， 各自维护自己的二级索引，且只负责自己分区内的文档而不关心其他分区中数据。也被称为本地索引

◼基于词条的二级索引分区
全局索引。为避免成为瓶颈， 不能将全局索引存储在一个节点上。所以，全局索引也必须进行分区， 且可以与数据关键字采用不同的分区策略。可以直接通过关键词来全局划分索引，或者对其取哈希值。

对于词条分区来讲，这需要一个跨多个相关分区的分布式事务支持，写入速度会受到极大的影响，所以现有的数据库都不支持同步更新二级索引。实践中，对全局二级索引的更新往往都是异步的。

分区再平衡

随着时间的推移， 数据库可能总会出现某些变化：
◼ 查询压力增加， 因此需要更多的CPU来处理负载。
◼ 数据规模增加， 因此需要更多的磁盘和内存来存储数据。
◼ 节点可能出现故障， 因此需要其他机器来接管失效的节点。
所有这些变化都要求数据和请求可以从一个节点转移到另一个节点。这样一个迁移负载的过程称为再平衡（或者动态平衡）。

分区再平衡通常至少要满足：

◼平衡之后，负载、数据存储、读写请求等应该在集群范围更均匀地分布。
◼再平衡执行过程中，数据库应该可以继续正常提供读写服务。
◼避免不必要的负载迁移，以加快动态再平衡，并尽显减少网络和磁盘I/O影响。

分区分配策略

◼hash mode N：数据hash后除以N(节点数)的余数就是对应存入的节点分区。 需要的数据迁移太多
◼固定数量的分区

◼动态分区
当分区的数据增长超过一个可配的参数阈值(如10GB) , 它就拆分为两个分区，每个承担一半的数据量。 如果大量数据被删除， 并且分区缩小到某个阈值以下， 则将其与相邻分区进行合并。
预分裂策略：直到达到第一个分裂点之前，所有的写入操作都必须由单个节点来处理，而其他节点则处于空闲状态。初始分区
◼按节点比例分区
固定数量的分区与动态分区策略，分区的数量都与节点数无关。

请求路由

1. 随机节点一直转发到有请求分分区为止
2. 全部发到路由层。路由层本身不处理任何请求， 它仅充当一个分区感知的负载均衡器。
3. 客户端感知分区和节点分配关系。 客户端可以直接连接到目标节点
   都用共识协议算法知道分区和节点的关系
   

分布式一致性原理

三态：成功、失败与超时。
CAP理论:
在一个分布式系统（指互相连接并共享数据的节点集合 ） 中 ， 当 涉 及 读 写 操 作 时 ， 只 能 保 证 一 致 性（Consistence ） 、 可用性 （ Availability ） 、 分 区 容 错性（Partition Tolerance）三者中的两个，另外一个必须被牲。

BASE：Basically Available（基本可用）、Soft state（软状态，数据同步的过程存在延时） 和Eventually consistent（最终一致性）

BASE比较乐观。先返回估计值、加入任务队列，相信最终还是可以一致的。BASE看是响应时间上的损失还是功能上的损失。
ACID比较悲观，在每个操作结束时都强制保持一致性。

一致性协议

在系统的可用性和数据一致性之间进行反复的权衡。
二阶段提交协议、三阶段提交协议和Paxos算法。

2PC

准备阶段：
➢ 协调者向所有参与者发送事务内容，询问是否可以提交事务，并等待所有参与者答复。
➢ 各参与者执行事务操作，将 undo 和 redo 信息记入事务日志中（但不提交事务）。
➢ 如参与者执行成功，给协调者反馈 yes，即可以提交；如执行失败，给协调者反馈 no，即不可提交。
提交阶段：
➢ 如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(rollback)消息；否则，发送提交(commit)消息。
➢ 参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意：必须在最后阶段释放锁资源)
缺点
◼ 同步阻塞：在2PC的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，也就是说， 各个参与者在等待其他参与者响应的过程中，将无法进行其他任何操作。
◼ 单点问题：一旦协调者出现问题，那么整个2PC流程将无法运转。更为严重的是， 如果协调者是在阶段二中出现问题的话，那么其他参与者将会直处于锁定事务资源的状态中，而无法继续完成事务操作。
◼ 数据不一致：在阶段二，当协调者向所有的参与者发送Commit请求之后，发生了局部网络异常或者是协调者在尚未发送完Commit 请求之前自身发生了崩溃，导致最终只有部分参与者收到了Commit 请求。于是，这部分收到了Commit 请求的参与者就会进行事务的提交，而其他没有收到Commit 请求的参与者则无法进行事务提交，于是整个分布式系统便出现了数据不一致性现象。
◼ 太过保守：如果在阶段一，参与者出现故障而导致协调者始终无法获取到所有参与者的响应信息的话，这时协调者只能依靠其自身的超时机制来判断是否需要中断事务，这样的策略显得比较保守。换句话说，2PC没有设计较为完善的容错机制，任意一个节点的失败都会导致整个事务的失败。

3PC与二阶段提交不同的是，同时在协调者和参与者中都引入超时机制。

Paxos

Paxos的目的是在非拜占庭条件下，当多个并行进程提出不同的操作命令（下文统称为倡议）时，如何能够达成一致。

Paxos协议下不同并行进程可能承担的三种角色如下：
◼倡议者（Proposer）：倡议者可以提出提议（数值或操作命令等）以供投票表决；
◼接受者（Acceptor）：接受者可以对倡议者提出的提议进行投票表决，从众多提议中选出唯一确定的一个；
◼学习者（Learner）：学习者无倡议投票权，但是可以从接受者那里获知是哪个提议最终被选中；

🗳️ Paxos 的两轮投票流程

Paxos的核心是一个两阶段的投票过程，以确保不会出现两个不同的议案同时被通过。

第一阶段：准备阶段 (Prepare)

这个阶段的目标是“锁定”投票权，并了解之前的投票情况。

1. 发起提案：一位提议者（比如议员A）想提出一个议案（比如“吃火锅”）。他不能直接让大家投票，而是先给议案编一个唯一的、递增的编号（比如101），然后向所有接受者广播一个“准备投票”的请求，编号为101。
2. 做出承诺：接受者收到请求后，会检查这个编号101是不是自己见过的最大编号。
   • 如果是：他会向提议者A做出两个承诺：
     • 承诺一：我保证不再接受任何编号小于101的新提案。
     • 承诺二：我会把我之前投过票的、编号最大的那个议案（如果有的话）告诉你。
   • 如果不是（比如他已经承诺过编号102的提案）：他就会忽略或拒绝议员A的请求。

第二阶段：接受阶段 (Accept)

这个阶段的目标是正式提交议案并争取多数票。

1. 收集反馈：提议者A需要等待，直到收到超过半数的接受者发回的“承诺”。这是Paxos算法的关键，只要有过半数的节点达成一致，系统就能继续工作。
2. 确定最终议案：收到过半数的承诺后，提议者A需要决定最终让大家投哪个议案。
   • 情况一：如果所有接受者的回复里都没有提到他们之前投过票，那么提议者A就可以放心地提出自己的原始议案：“我们中午吃火锅”。
   • 情况二：如果有任何一个接受者的回复里提到了他之前投过的议案（比如“吃烧烤”），那么提议者A必须放弃自己的议案，转而选择这些历史议案中编号最大的那个（比如“吃烧烤”）。这一步是保证数据一致性的核心，它确保了新的提案不会推翻旧的共识。
3. 正式投票：提议者A将最终确定的议案（无论是“吃火锅”还是“吃烧烤”）连同编号101，再次广播给所有接受者，请求他们正式接受。Accept(101, “吃烧烤”)
4. 完成共识：接受者收到正式投票请求后，只要这个提案的编号（101）不小于自己承诺过的最大编号，就会接受它。一旦超过半数的接受者都接受了同一个议案，这个议案就被正式通过了（Chosen）。
5. 宣布结果：学习者监听到议案被多数接受后，就会向全系统宣布：“最终决定，我们中午吃烧烤！”

• 如果旧提案（100号）未通过：你仍然要在101推动它，这是为了帮助系统在未来达成共识，防止出现分歧。
• 如果没有任何旧提案：你可以推动自己的新提案。

🤔 为什么要这么麻烦？

你可能会问，为什么不直接投票？

这正是Paxos的精妙之处。通过“准备阶段”的锁定和历史查询，Paxos巧妙地解决了多个提议者同时竞争的问题，并确保了一旦某个值被多数节点接受，后续的所有提案都必须尊重这个值。这就像议会规定，一旦某个法案通过，后续所有新法案都不能与之冲突，从而保证了整个系统状态的一致性。