分布式存储的目标：
- 提高数据存储容量：让总体存储容量随节点增多而增大（水平可扩展）；
- 提高数据吞吐量：让总体吞吐量随节点增多而增大（水平可扩展），比如将一个大文件切片存储在多个主机内，要获取该文件时即可同时从多个主机同时进行下载；
- 提高可靠性 / 可用性：部分节点故障时数据不丢失 / 部分节点失效不影响整个系统的数据读写（容错性）；
复制
分布式数据库系统三种主流的复制 / 变更方法：单领导者（single leader，单主），多领导者（multi leader，多主） 和 无领导者（leaderless，无主）。
主从复制
每一次向数据库的写入操作都需要传播到所有副本上，否则副本就会包含不一样的数据，最常见的解决方案是基于领导者的复制（主从复制） ：
- 分布式系统中一个副本作为主库，客户端向数据库写入数据时，请求交于主库写入，其会将新数据写入其本地存储。
- 其他副本作为从库，每当主库将新数据写入本地存储时，它也会将数据变更发送给所有从库，称为复制日志或变更流。从库拉取日志并相应更新其本地数据库副本，按与主库相同的处理顺序来执行写入。
复制日志的方式：主库记录执行的每个写入语句；预写式日志（WAL，更新前先记入日志）；逻辑日志（对复制和存储引擎使用不同的日志格式）；结合触发器实现应用层的复制。
- 当客户端读取数据时，它可以向主库或任一从库进行查询。
- 从用户的角度来看：主库可写可读，从库只读。
主库失效
主库失效处理起来相当棘手：其中一个从库需要被提升为新的主库，需要重新配置客户端，以将它们的写操作发送给新的主库，其他从库需要开始拉取来自新主库的数据变更。这个过程被称为故障切换（failover） 。
故障切换可以手动执行，但更多情况下开发人员还是希望分布式系统具备自动的故障切换策略，通常步骤如下：
- 确认主库失效：大多数系统采用超时机制来判断，节点间频繁相互传递消息，如果某个节点在一段时间内无响应，就认为该节点失效。
- 选择新的主库：选举投票机制（Redis）或选定的控制器节点来指定，主库的最佳替代节点通常是拥有旧主库最新数据的从库（最小化数据损失）。
- 重配系统以启用新的主库：如果旧主库恢复，分布式系统需要确保旧主库意识到新主库的存在，并称为一个从库。
复制延迟
当应用程序从异步从库读取时，如果从库落后，它可能会看到过时的信息。这会导致数据库中出现明显的不一致：同时对主库和从库执行相同的查询，可能得到不同的结果，因为并非所有的写入都反映在从库中。这种不一致只是一个暂时的状态 —— 如果停止写入数据库并等待一段时间，从库最终会赶上并与主库保持一致（ 最终一致性 ） 。
复制延迟：写入主库到反映至从库之间的延迟，可能仅仅是几分之一秒，在实践中并不显眼。但如果系统在接近极限的情况下运行，或网络中存在问题时，延迟可以轻而易举地超过几秒，甚至达到几分钟。
多主复制
在单个数据中心内部使用多个主库的配置没有太大意义，因为其导致的复杂性已经超过了能带来的好处。
但在一些情况下，这种配置也是合理的：假设有一个数据库，副本分散在好几个不同的数据中心（可能用以容忍单个数据中心的故障，或者为了在地理上更接近用户）。
多主分布式系统中，允许独立写入，用户的体验更好。但多主复制也有一个较大的缺点：两个不同的数据中心可能会同时修改相同的数据，写入冲突是必须解决的。
复制拓扑（replication topology ） 用来描述写入操作从一个节点传播到另一个节点的通信路径。最常见的拓扑是全部到全部，其中每个主库都将其写入发送给其他所有的主库。
多主写入冲突
典型场景：两个用户同时编辑一个页面，用户
1将页面的标题从A改为B，同时用户2将页面的标题从A改为C，用户更改应用到本地主库，但异步复制时，出现写入冲突问题。
应对写入冲突的方式：
- 同步与异步冲突检测：使冲突检测同步，即等待写入被复制到所有副本，再告诉用户写入成功。（此方式失去了多主复制允许独立写入的优势）
- 避免冲突：如果应用程序可以确保特定记录的所有写入都通过同一个主库，那么冲突就不会发生。由于许多的多主复制实现在处理冲突时处理得相当不好，避免冲突是一个经常被推荐的方法。
- 收敛至一致的状态：配合时间戳、优先级或其他方法实现冲突合并。
- 自定义冲突解决逻辑：大多数多主复制工具允许使用应用程序代码编写冲突解决逻辑。
无主复制
一些数据存储系统采用不同的方法，放弃主库的概念，并允许任何副本直接接受来自客户端的写入。在一些无主复制的实现中，客户端直接将写入发送到几个副本中，而另一些情况下，由一个协调者（coordinator） 节点代表客户端进行写入，但协调者不执行特定的写入顺序。
分区
分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。这意味着，即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能力。
键值数据的分区
如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（ skew ） 。数据偏斜的存在使分区效率下降很多：在极端的情况下，所有的负载可能压在一个分区上，其余 9 个节点空闲的，瓶颈落在这一个繁忙的节点上。不均衡导致的高负载的分区被称为热点（hot spot） 。
- 根据键的范围分区。（键的范围不一定均匀分布，因为数据也很可能不均匀分布）
- 根据键的散列分区。（一个好的散列函数可以将偏斜的数据均匀分布）
一致性哈希：用于跨互联网级别的缓存系统，使用随机选择的分区边界（partition boundaries） 来避免中央控制或分布式共识的需要。
哈希分区可以帮助减少热点。但是，它不能完全避免它们：在极端情况下，所有的读写操作都是针对同一个键的，所有的请求都会被路由到同一个分区。
分区与次级索引
如果只通过主键访问记录，我们可以从该键确定分区，并使用它来将读写请求路由到负责该键的分区。
如果涉及次级索引，情况会变得更加复杂。次级索引通常并不能唯一地标识记录，而是一种搜索记录中出现特定值的方式：查找用户
123的所有操作，查找包含词语hogwash的所有文章，查找所有颜色为红色的车辆等等。次级索引的问题是它们不能整齐地映射到分区。有两种用次级索引对数据库进行分区的方法：基于文档的分区（document-based）和基于关键词（term-based）的分区。
基于文档的次级索引进行分区：
例如有一个销售二手车的网站，每个列表都有唯一的ID，称为文档ID，利用文档ID对数据库进行分区。若允许用户通过颜色和厂商过滤，需要一个在颜色和厂商上的次级索引。
每个分区是完全独立的：每个分区维护自己的次级索引，仅覆盖该分区中的文档，它不关心存储在其他分区的数据，无论何时你需要写入数据库（添加，删除或更新文档），只需处理包含你正在编写的文档 ID 的分区即可。
基于关键词的次级索引进行分区：
构建一个覆盖所有分区数据的全局索引，而不是给每个分区创建自己的次级索引（本地索引）。
关键词分区的全局索引优于文档分区索引的地方点是它可以使读取更有效率：不需要分散 / 收集所有分区，客户端只需要向包含关键词的分区发出请求。
全局索引的缺点在于写入速度较慢且较为复杂，因为写入单个文档现在可能会影响索引的多个分区（文档中的每个关键词可能位于不同的分区或者不同的节点上） 。
分区再平衡
随着时间的推移，数据库会有各种变化：
- 查询吞吐量增加，所以你想要添加更多的 CPU 来处理负载。
- 数据集大小增加，所以你想添加更多的磁盘和 RAM 来存储它。
- 机器出现故障，其他机器需要接管故障机器的责任。
所有这些更改都需要数据和请求从一个节点移动到另一个节点。 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡（rebalancing） 。无论使用哪种分区方案，再平衡通常都要满足一些最低要求：
- 再平衡之后，负载（数据存储，读取和写入请求）应该在集群中的节点之间公平地共享。
- 再平衡发生时，数据库应该继续接受读取和写入。
- 节点之间只移动必须的数据，以便快速再平衡，并减少网络和磁盘 I/O 负载。
再平衡策略：
- hash mod N：
N是节点数，通过直接取模来散列分区。如果节点数量 N 发生变化，大多数键将需要从一个节点移动到另一个节点。 - 固定数量的分区：运行在 10 个节点的集群上的数据库被拆分为 1000 个分区，每个节点管理 100 个分区。如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配。
- 动态分区：当分区增长到超过配置的大小时（在 HBase 上，默认值是 10 GB），会被分成两个分区，每个分区约占一半的数据；与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。
事务
从概念上讲，事务中的所有读写操作被视作单个操作来执行：整个事务要么成功提交（commit），要么失败中止（abort）或回滚（rollback） 。如果失败，应用程序可以安全地重试。
ACID
- 原子性（Atomicity） ：一个事务中的所有操作，要么全部完成，要么全部不完成。
- 一致性（Consistency） ：是指事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态。
- 隔离性（Isolation） ：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致，因为多个事务同时使用相同的数据时，不会相互干扰，每个事务都有一个完整的数据空间，对其他并发事务是隔离的。
- 持久性（Durability） ：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。
隔离级别（以MySQL为例）
SQL 标准提出了四种隔离级别来规避这些现象，隔离级别越高，性能效率就越低：
读未提交 RU （ read uncommitted ） ：指一个事务还没提交时，它做的变更就能被其他事务看到；
读已提交 RC（ read committed ） ：指一个事务提交之后，它做的变更才能被其他事务看到；
可重复读 RR （ repeatable read ） ：指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别（MySQL 可重复读隔离级别并没有彻底解决幻读 ，只是很大程度上避免了幻读现象的发生）；
串行化 （ serializable ） ：会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行；
分布式系统的潜在问题
分布式系统可能发生一些问题：
- 当你尝试通过网络发送数据包时，数据包可能会丢失或任意延迟。同样，答复可能会丢失或延迟，所以如果你没有得到答复，你不知道消息是否发送成功了。
- 节点的时钟可能会与其他节点显著不同步（尽管你尽最大努力设置 NTP），它可能会突然跳转或跳回，依靠它是很危险的，因为你很可能没有好的方法来测量你的时钟的错误间隔。
- 一个进程可能会在其执行的任何时候暂停一段相当长的时间（可能是因为停止所有处理的垃圾收集器），被其他节点宣告死亡，然后再次复活，却没有意识到它被暂停了。
检测系统故障 → 容忍故障 / 解决故障。
一致性与共识
分布式一致性主要关于在面对延迟和故障时如何协调副本间的状态。
大多数数据库保证的是最终一致性，即若用户停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值（不一致性是暂时的，最终都会自行解决）。
共识：让所有的节点对某件事达成一致。
线性一致性
线性一致性：使系统看起来好像只有一个数据副本。
- 单主复制。（可能线性一致）
- 共识算法。（线性一致）
- 多主复制。（非线性一致）
- 无主复制。（也许不是线性一致的）
线性一致性的代价
网络中需要在线性一致性和可用性之间做出选择 → CAP原理：
C：一致性，在分布式系统中，所有的节点在同一时刻看到的数据都是相同的。
A：可用性，系统必须一直保持可操作状态，对请求给予响应，不保证获取到最新的数据。
P：分区容忍性，即使网络通信发生故障，导致系统被分割成多个部分无法互相通信，系统仍然需要继续运行并提供服务。
CA 无法同时满足，一般是 CP（网络分区发生时，系统会拒绝一些操作保证数据的一致性） 或者 AP（网络分区发生时，系统会继续处理请求，可能返回旧的数据） 。
满足 CP 的协议：
- Zookeeper，分布式协调服务，牺牲部分可用性。
- Raft 一致性协议，保证强一致性。
满足 AP 的协议：
- Redis：异步复制，可能不一致；节点可能故障，无法及时同步。
分布式事务与共识
如果存在节点崩溃的可能性，则不可能达到完全共识的效果。
如果一个事务涉及多个节点，仅向所有节点发送提交请求并独立提交每个节点的事务可能违反原子性：提交在某些节点上成功，而在其他节点上失败。
两阶段提交（2PC）：一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。
2PC有新组件：协调者 / 事务管理器（单独进程 / 服务），2PC事务以应用于多个数据库节点（参与者）上读写数据开始。当应用准备提交时，协调者开始阶段 1：它发送一个准备请求到每个节点，询问它们是否能够提交。
- 如果所有参与者都回答 “是”，表示它们已经准备好提交，那么协调者在阶段 2 发出提交（commit） 请求，然后提交真正发生。
- 如果任意一个参与者回复了 “否”，则协调者在阶段 2 中向所有节点发送中止（abort） 请求。
潜在问题：存在单点故障问题，若任何一个准备请求失败或者超时，协调者就会中止事务。一旦参与者收到了准备请求并投了 “是”，就不能再单方面放弃 —— 必须等待协调者回答事务是否已经提交或中止。如果此时协调者崩溃或网络出现故障，参与者什么也做不了只能等待。参与者的这种事务状态称为存疑（in doubt）的或不确定（uncertain 的。
三阶段提交（3PC），协调者和参与者都引入超时机制。
- CanCommit 阶段（询问阶段） ：协调者询问所有参与者是否可以进行事务提交，参与者回复是否能够提交。
- PreCommit 阶段（预提交阶段） ：协调者会发送PreCommit消息给所有参与者，参与者执行事务但不提交，如果有人不行就全部中止
- DoCommit 阶段（提交阶段） ：如果所有参与者成功预提交（返回 ACK），协调者发送 DoCommit 请求，要求提交事务；如果有任何参与者未响应或超时，协调者发送 Abort 请求终止事务。