发表于

一致性保证

  1. 最终一致性是一个非常弱的保证。当系统提供了弱保证的数据库时，要认清系统的局限性。（最终一致性数据库不同副本的状态可能不同）
  2. 需要更强的一致性保证来满足一些业务的需求。

可线性化

基本思想：让系统看起来好像只有一个副本，并且所有的操作都是原子的

非线性化，看世界杯直播的例子

用户可以发现不一致是因为有系统外部的信息通道。

如何达到线性化？

问题，三个用户同时读写变量x

从用户的角度来讲，标红的request在没有线性一致保证时候可能返回任何值。

实现线性一致，要添加一个约束

由于B的读取严格在发生于A的读取之后，因此即使C的写入仍在进行中，也必须返回 1。

增加CAS操作

可串行化 VS 可线性化

可串行化

是事务隔离属性。
确保了事务执行的结果与串行执行结果一样。

可线性化

是读写寄存器的最新值保证。
跟事务没有关系。

需要线性化的场景

加锁与主节点选举

主从复制数据库，只能有一个主节点，否则会产生脑裂。

常见方法是使用锁。先获得锁的人成为主节点。

不管这个锁是如何实现的，它必须是线性一致的：所有节点必须就哪个节点拥有锁达成一致，否则就没用了。

​诸如Apache ZooKeeper 和etcd之类的协调服务通常用于实现分布式锁和领导者选举。它们使用一致性算法，以容错的方式实现线性一致的操作（在本章后面的“容错共识”中讨论此类算法）。还有许多微妙的细节来正确地实现锁和领导者选择（例如，参阅“领导者和锁”中的屏蔽问题）。
线性一致性存储服务是这些协调任务的基础。

约束与唯一性保证

注册用户名/邮箱唯一。

这种情况实际上类似于一个锁：当一个用户注册你的服务时，可以认为他们获得了所选用户名的“锁定”。

跨通道的时间依赖

看球赛中的例子。由于系统中存在额外的信道（Alice的声音传到了Bob的耳朵中），线性一致性的违背才被注意到。

如果你可以控制额外信道（例如消息队列的例子，而不是在Alice和Bob的例子），则可以使用在“读己之写”讨论过的备选方法，不过会有额外的复杂度代价。

实现线性化系统

系统容错做常见的解决方案是复制。

  1. 单主系统可能实现线性化。从主节点读或者同步更新从节点。
  2. 共识算法。通过协商一致性协议算法可以防止脑裂和读取过期数据，通过一致性算法可以实现核心数据线性化的安全存储。这是ZooKeeper与Chubby等分布式协调服务的基础算法。

法定人数读Quorum

在某些情况，即使w + r > n，也会不是线性的。

线性化的代价

​许多分布式数据库也是如此：它们是为了提高性能而选择了牺牲线性一致性，而不是为了容错。线性一致的速度很慢——这始终是事实，而不仅仅是网络故障期间。

CAP理论

CAP理论，简而言之便是：数据系统必须在一致性、可用性、分区容忍性的三角关系之中有所权衡，任何系统没有办法同时满足三种特性。

所以使用线性化的一致性自然会需要在可用性上做一些妥协， 在单Leader多Follower机制之下，需要满足线性化一致性的写入和读取的客户端必须连接到Leader。如果Leader产生中断，仍然可以读取Follower的数据，但此时就无法保证线性化的要求了。

​许多分布式数据库也是如此：它们是为了提高性能而选择了牺牲线性一致性，而不是为了容错。线性一致的速度很慢——这始终是事实，而不仅仅是网络故障期间。

顺序

顺序与因果关系

顺序有助于保证因果关系。

因果顺序不是全序。

可线性化强于因果一致性。

线性一致性

在线性一致的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。

因果性

我们说过，如果两个操作都没有在彼此之前发生，那么这两个操作是并发的（参阅“Happens-Before”的关系和并发）。换句话说，如果两个事件是因果相关的（一个发生在另一个事件之前），则它们之间是有序的，但如果它们是并发的，则它们之间的顺序是无法比较的。这意味着因果关系定义了一个偏序，而不是一个全序：一些操作相互之间是有顺序的，但有些则是无法比较的。

那么因果顺序和线性一致性之间的关系是什么？答案是线性一致性隐含着（implies）因果关系：任何线性一致的系统都能正确保持因果性。

在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。

序列号排序

我们可以使用序列号（sequence nunber）或时间戳（timestamp）来排序事件。时间戳不一定来自时钟（或物理时钟，存在许多问题，如 “不可靠时钟” 中所述）。它可以来自一个逻辑时钟（logical clock），这是一个用来生成标识操作的数字序列的算法，典型实现是使用一个每次操作自增的计数器。

这些序列号生成器不能正确地捕获跨节点的操作顺序。

Lamport时间戳

每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。 兰伯特时间戳就是两者的简单组合：（计数器，节点ID）$(counter, node ID)$。两个节点有时可能具有相同的计数器值，但通过在时间戳中包含节点ID，每个时间戳都是唯一的。

兰伯特时间戳与物理时间时钟没有任何关系，但是它提供了一个全序：如果你有两个时间戳，则计数器值大者是更大的时间戳。如果计数器值相同，则节点ID越大的，时间戳越大。

光有时间戳排序还不够

只有在所有的操作都被收集之后，操作的全序才会出现。如果另一个节点已经产生了一些操作，但你还不知道那些操作是什么，那就无法构造所有操作最终的全序关系：来自另一个节点的未知操作可能需要被插入到全序中的不同位置。

​总之：为了实诸如如用户名上的唯一约束这种东西，仅有操作的全序是不够的，你还需要知道这个全序何时会尘埃落定。如果你有一个创建用户名的操作，并且确定在全序中，没有任何其他节点可以在你的操作之前插入对同一用户名的声称，那么你就可以安全地宣告操作执行成功。

全序广播

单主复制通过选择一个节点作为主库来确定操作的全序，并在主库的单个CPU核上对所有操作进行排序。

接下来的挑战是，如果吞吐量超出单个主库的处理能力，这种情况下如何扩展系统；以及，如果主库失效（“处理节点宕机”），如何处理故障切换。

全序广播要满足两个安全属性：

  1. 可靠交付（reliable delivery）

​ 没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。

  1. 全序交付（totally ordered delivery）*

​ 消息以相同的顺序传递给每个节点。

正确的全序广播算法必须始终保证可靠性和有序性，即使节点或网络出现故障。（Retry等）

通过全序广播实现线性化一致性

全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息何时被送达（所以一个接收者可能落后于其他接收者）。相比之下，线性一致性是新鲜性的保证：读取一定能看见最新的写入值。

你可以通过将全序广播当成仅追加日志的方式来实现这种线性一致的CAS操作：

  1. 在日志中追加一条消息，试探性地指明你要声明的用户名。
  2. 读日志，并等待你所附加的信息被回送。
  3. 检查是否有任何消息声称目标用户名的所有权。如果这些消息中的第一条就你自己的消息，那么你就成功了：你可以提交声称的用户名（也许是通过向日志追加另一条消息）并向客户端确认。如果所需用户名的第一条消息来自其他用户，则中止操作。

所有节点同意一个写请求到底是提交成功还是中止。可以保证线性化写入。

上述步骤在读取时不能保证线性。因为消息传递的延迟性，所以读操作的结果可能是过时的。

当然这里可以通过返回最新日志消息的位置，通过查询位置，等待所有条目需要读取的条目被写入，再进行读操作，便能够达到读操作的线性一致性。（在ZooKeeper中通过sync()操作实现），或者可以通过强制读取Leader节点，显然Leader节点上的数据一定是最新的结果。

分布式事务与共识

需要集群节点一致性的场景举例：

  1. 主节点选举
  2. 原子事务提交

原子提交与两阶段提交

提交事务的结果有可能通过事后执行另一个补偿事务来取消，即补偿事务。但从数据库的角度来看，这是一个单独的事务，因此任何关于跨事务正确性的保证都是应用层负责。

两阶段提交

两阶段提交（two-phase commit）是一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。 它是分布式数据库中的经典算法。 2PC在某些数据库内部使用，也以XA事务的形式对应用可用（例如Java Transaction API支持）或以SOAP Web服务的WS-AtomicTransaction 形式提供给应用。

新增组建协调者。协调者通常在请求事务的相同应用进程中以库的形式实现（例如，嵌入在Java EE容器中），但也可以是单独的进程或服务。

参与者不能单方面放弃，必须等待协调者决定

协调者崩溃，那么参与者不知道接下来如何行动。

可以完成2PC的唯一方法是等待协调者恢复。这就是为什么协调者必须在向参与者发送提交或中止请求之前，将其提交或中止决定写入磁盘上的事务日志。

三阶段提交

前提：假定网络延迟有界，节点响应时间有界。无界情况下不能保证原子性。

实践中的分布式事务

许多云服务由于其导致的运维问题，而选择不实现分布式事务。

异构分布式事务的原子提交协议。不同于分布式数据库内部的事务。

XA事务

X/Open XA（扩展架构（eXtended Architecture）的缩写）是跨异构技术实现两阶段提交的标准。它于1991年推出并得到了广泛的实现：许多传统关系数据库（包括PostgreSQL，MySQL，DB2，SQL Server和Oracle）和消息代理（包括ActiveMQ，HornetQ，MSMQ和IBM MQ） 都支持XA。

​XA不是一个网络协议——它只是一个用来与事务协调者连接的C API。其他语言也有这种API的绑定；例如在Java EE应用的世界中，XA事务是使用Java事务API（JTA, Java Transaction API）实现的，而许多使用Java数据库连接（JDBC, Java Database Connectivity）的数据库驱动，以及许多使用Java消息服务（JMS）API的消息代理都支持Java事务API（JTA）。

数据库服务器不能直接联系协调者，因为所有通信都必须通过客户端库。

停顿时间仍持有锁

如果协调者已经崩溃，需要20分钟才能重启，那么这些锁将会被持有20分钟。如果协调者的日志由于某种原因彻底丢失，这些锁将被永久持有 —— 或至少在管理员手动解决该情况之前。

从协调者故障中恢复

许多XA的实现都有一个叫做启发式决策（heuristic decistions）的紧急逃生舱口：允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定。要清楚的是，这里启发式是可能破坏原子性（probably breaking atomicity）的委婉说法，因为它违背了两阶段提交的系统承诺。因此，启发式决策只是为了逃出灾难性的情况而准备的，而不是为了日常使用的。

分布式事务的限制

运维问题：

  1. 如果协调者没有复制，而是只在单台机器上运行，那么它是整个系统的失效单点（因为它的失效会导致其他应用服务器阻塞在存疑事务持有的锁上）。令人惊讶的是，许多协调者实现默认情况下并不是高可用的，或者只有基本的复制支持。
  2. 许多服务器端应用都是使用无状态模式开发的（受HTTP的青睐），所有持久状态都存储在数据库中，因此具有应用服务器可随意按需添加删除的优点。但是，当协调者成为应用服务器的一部分时，它会改变部署的性质。突然间，协调者的日志成为持久系统状态的关键部分—— 与数据库本身一样重要，因为协调者日志是为了在崩溃后恢复存疑事务所必需的。这样的应用服务器不再是无状态的了。
  3. 由于XA需要兼容各种数据系统，因此它必须是所有系统的最低标准。例如，它不能检测不同系统间的死锁（因为这将需要一个标准协议来让系统交换每个事务正在等待的锁的信息），而且它无法与SSI 协同工作，因为这需要一个跨系统定位冲突的协议。
  4. 对于数据库内部的分布式事务（不是XA），限制没有这么大，例如，分布式版本的SSI 是可能的。然而仍然存在问题：2PC成功提交一个事务需要所有参与者的响应。因此，如果系统的任何部分损坏，事务也会失败。因此，分布式事务又有扩大失效（amplifying failures）的趋势，这又与我们构建容错系统的目标背道而驰。

支持容错共识

共识算法必须满足：

  1. 一致同意（Uniform agreement）

​ 没有两个节点的决定不同。

  1. 完整性（Integrity）

​ 没有节点决定两次。

  1. 有效性（Validity）

​ 如果一个节点决定了值 v ，则 v 由某个节点所提议。

  1. 终止（Termination） 由所有未崩溃的节点来最终决定值。

一致同意和完整性属性定义了共识的核心思想：所有人都决定了相同的结果，一旦决定了，你就不能改变主意。

有效性属性主要是为了排除无意义的解决方案：例如，无论提议了什么值，你都可以有一个始终决定值为null的算法。

摒弃容错性：可以指定一个节点成为Leader，由Leader节点做出所有的决定。但是，如果Leader节点失效，则系统陷入瘫痪。两阶段提交协议之中的协调器就是一个Leader，一旦协调器失效了，系统无法进行工作。而更好的协商一致性算法要求，即使某些节点失效了，系统仍然能够正常工作。当然，如果所有节点都崩溃了，并且没有一个节点正在运行，那么任何算法都不可能鸡血运行，所以说算法可以容忍的故障数量是有限的：事实上，可以证明任何协商一致算法至少需要大多数节点正常运行，来确保协商一致。

共识算法

在分布式系统之中存在许多协商一致性算法算法如：Paxos，Raft，Zab等等。本篇之中，不会涉及到不同算法的全部细节，会通过他们来了解一些高级思想。

这里的一致性算法符合全序广播的特性，全序广播需要以相同的顺序向所有节点精确地传递一次消息。在每一轮的协商之中，每个节点都可以提出下一个要发送的消息，然后由协商达成一致，并在系统之中传递的下一条消息。所有节点共同决定以相同的顺序传递相同的消息，且消息不重复，消息不会被破坏，也不会凭空产生。（这里忽略拜占庭问题，如果需要引入拜占庭容错，需要采用类似于区块链之中的Pow算法）

主从复制与共识

要选出一个领导者，我们首先需要一个领导者。要解决共识问题，我们首先需要解决共识问题。我们如何跳出这个先有鸡还是先有蛋的问题？

epoch number与法定人数（Quorum）

迄今为止所讨论的所有共识协议，在内部都以某种形式使用一个领导者，但它们并不能保证领导者是独一无二的。相反，它们可以做出更弱的保证：协议定义了一个时代编号（epoch number）（在Paxos中称为投票编号（ballot number），视图戳复制中的视图编号（view number），以及Raft中的任期号码（term number）），并确保在每个世代中，领导者都是唯一的。

​在任何领导者被允许决定任何事情之前，必须先检查是否存在其他带有更高时代编号的领导者，它们可能会做出相互冲突的决定。

因此，我们有两轮投票：
第一次是为了选出一位领导者，
第二次是对领导者的提议进行表决。

关键的洞察在于，这两次投票的法定人群必须相互重叠（overlap）：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举。

共识的局限性

  1. 性能
  2. 复杂

节点在做出决定之前对提议进行投票的过程是一种同步复制。
共识系统总是需要严格多数来运转。
​共识系统通常依靠超时来检测失效的节点。
有时共识算法对网络问题特别敏感。

成员与协调服务

如何使用ZooKeeper这样的服务？

作为应用开发人员，你很少需要直接使用ZooKeeper，因为它实际上不适合当成通用数据库来用。更有可能的是，你会通过其他项目间接依赖它，例如HBase，Hadoop YARN，OpenStack Nova和Kafka都依赖ZooKeeper在后台运行。这些项目从它那里得到了什么？

ZooKeeper与etcd的特点：

  1. 不用保存大量数据
  2. 数据库复制中，每条消息代表的是数据库写请求

ZooKeeper模仿了Google的Chubby锁服务，不仅实现了全序广播（因此也实现了共识），而且还构建了一组有趣的其他特性，这些特性在构建分布式系统时变得特别有用：

  1. 线性一致性的原子操作
    使用原子CAS操作可以实现锁
  2. 操作的全序排序
    一个单调递增的事务ID（zxid）和版本号（cversion）
  3. 失效检测
    心跳链接
  4. 变更通知
    通过订阅通知，客户端不用再通过频繁轮询的方式来找出变更。

场景1:
节点任务分配。主节点选举。分区资源（数据库，消息，文件，actor）分配。
场景2:
服务发现。查找需要服务的IP地址。
场景3:
成员服务。查看成员是否Live。

发表于

所有可能出错的事情一定会出错

故障与部分失效

单节点的应用，质量合格情况下，操作有确定性。要么完全正常工作，要么就是完全失败（硬件问题，等）。
分布式系统，有多台节点的时，情况发生了根本变化。多接点复杂性，部分失效（网络分区）。

云计算和超算

  1. 一个极端是高性能计算。计算密集型的科学任务。
  2. 另一个计算是云计算。通用计算机用网络连接，弹性/按需分配资源。
  3. 传统企业数据中心介于二者之间。

基于互联网的系统，与高性能计算有很多不同：

  1. 服务是不可离线计算的，需要随时为用户提供低延迟服务。
  2. 硬件廉价的单节点聚合，故障率高。
  3. 节点之间通过网络连接
  4. 系统越大，局部组建失效的概率就越大
  5. HA的要求
  6. 节点之间额通讯可能不可靠。

所以系统的故障处理设计非常重要。软件要能够处理这种故障。要知道系统故障时候预期的行为。

不可靠的网络

基于不可靠的组建构建可靠的系统

  1. 纠错码
  2. TCP在不可靠的IP层提供可靠传输。

现实中的网络故障

人为+机器故障。发生概率高。

设计方面：出现网络问题，软件的应对策略需要容错和恢复。除了容错措施，还可以做的就是给用户提示错误信息。

运维方面：推荐人为的触发网络问题，来测试系统的反应情况。

检测故障

软件系统需要自动检测节点失效的功能。包括以下的设计：

  1. 不向已经失效的节点继续发送request
  2. 主从模式，主节点失效后，要触发选举新主。

确定问题出在哪里有可能很困难。如果想知道一个请求是否执行成功，需要应用级别的恢复。

超时与无限期的延迟

存在过场等待，误判节点死亡的可能。

2d+r设置理想的超时时间。但是异步网络系统对响应延迟没有任何保证。

网络延迟的根源是排队

  1. 多对一的发送，接收的单节点负载过重，发生拥塞。队列慢后被丢弃，引发重传。
  2. 接收放机器的CPU忙碌。处理延迟。
  3. 虚拟化导致的CPU占用。
  4. TCP流量控制

TCP vs UDP

不稳定网络环境下，超时设置：

  1. 超时的设置可以通过实验一步步确定。
  2. 自适应的动态超时调整。

同步与异步网络

拨打电话的网络是同步网络，预留了带宽资源。端到端的延迟有界。资源利用率低。

TCP是基于共享带宽的。IP协议本身就有排队的影响。有不确定性。但是资源利用率高。

延迟是成本和收益的相互博弈的结果。

不可靠的时钟

有两种时间问题：

  1. 测量持续时间。（request的发送到响应的时间间隔）
  2. 某个定点的时间值。（特定的日期时间，触发事件）

NTP协议，同步机器时钟。

单调时钟与墙上时钟

  1. 墙上时钟。某个时间点。Linux上的clock_gettime(CLOCK_REALTIME)和Java中的System.currentTimeMillis()
  2. 单调时钟，测量时间段。Linux上的clock_gettime(CLOCK_MONOTONIC)，和Java中的System.nanoTime()都是单调时钟

时钟同步与准确性

需要同步的是单调时钟；硬件时钟和NTP可能会出现问题：

  1. 计算机中的石英钟不够精确：它会漂移（drifts）（运行速度快于或慢于预期）时钟漂移取决于机器的温度.
  2. 本地时钟和NTP时钟差距过大，出现时间突然倒退或者前进。
  3. NTP因为网络延迟，对精度产生影响。
  4. NTP服务器本身错误。
  5. 闰秒
  6. 虚拟化导致的一些毫秒级的延迟。
  7. 用户故意设置错误时间。

依赖同步的时钟

​如果你使用需要同步时钟的软件，必须仔细监控所有机器之间的时钟偏移。时钟偏离其他时钟太远的节点应当被宣告死亡，并从集群中移除。这样的监控可以确保你在损失发生之前注意到破损的时钟

时间戳与事件顺序

跨节点的事件排序。使用墙上时钟。采用LWW策略会出现的问题。

节点之间的时间偏差会导致数据顺序排序有问题。

更安全的方式
所谓的逻辑时钟是基于递增计数器而不是振荡石英晶体，对于排序事件来说是更安全的选择（请参见“检测并发写入”）。逻辑时钟不测量一天中的时间或经过的秒数，而仅测量事件的相对顺序（无论一个事件发生在另一个事件之前还是之后）。相反，用来测量实际经过时间的时钟和单调钟也被称为物理时钟。我们将在“顺序保证”中查看更多订购信息。

时钟置信区间

使用公共互联网上的NTP服务器，最好的准确度可能达到几十毫秒，而且当网络拥塞时，误差可能会超过100毫秒

因此，将时钟读数视为一个精确的时间点是不应该的——它更像是一段时间范围：例如，一个系统可能以95％的置信度认为当前时间处于本分钟内的第10.3秒和10.5秒之间，它可能没法比这更精确了

Spanner中的Google TrueTime API，它明确地报告了本地时钟的置信区间。

全局快照的同步时钟

快照隔离中会需要单调递增的事务ID。如果一个写入发生在快照之后，那么这个数据就对该快照不可见。单机容易实现。

在多接点的环境中，需要复杂的协调产生这个唯一的递增ID。
（跨所有分区）全局单调递增的事务ID可能很难生成。事务ID必须反映因果关系：如果事务B读取由事务A写入的值，则B必须具有比A更大的事务ID，否则快照就无法保持一致。在有大量的小规模、高频率的事务情景下，在分布式系统中创建事务ID成为一个站不住脚的瓶颈。

更晚的事务会有更大的时间戳。当然，问题在于时钟精度的不确定性。Spanner以这种方式实现跨数据中心的快照隔离。​ 为了确保事务时间戳反映因果关系，在提交读写事务之前，Spanner在提交读写事务时，会故意等待置信区间长度的时间。这样读事务会处于足够晚的时间，两个事务之间的置信区间不会重叠。

进程暂停

例子：数据库主节点确定自己是否被其他节点宣布死亡，要用到租约。是一个带有超时的锁。任何一个时刻只有一个节点可以持有这个租约。

1
2
3
4
5
6
7
8
9
10
11
while(true){
	request=getIncomingRequest();
	// 确保租约还剩下至少10秒
	if (lease.expiryTimeMillis-System.currentTimeMillis()< 10000){
		lease = lease.renew();
	}

	if(lease.isValid()){
    	process(request);
	}}
}

如果程序执行中出现了意外的停顿呢？例如，想象一下，线程在lease.isValid()行周围停止15秒，然后才终止。

发生的原因：

  1. GC
  2. 虚拟化挂起
  3. 操作系统上下文切换时，切换到另一个进程话费了更多的时间。
  4. 同步磁盘访问
  5. 内存页面抖动

所有的这些时间都是可以随时抢占正在运行的进程。在之后恢复。

分布式系统中的一节点不许假定执行过程中的任何时刻都可能被暂停，而且时间不确定。

响应时间保证

仔细调教系统，避免很多次的这种暂停。

调整垃圾回收影响

​ 一个新兴的想法是将GC暂停视为一个节点的短暂计划中断，并让其他节点处理来自客户端的请求，同时一个节点正在收集其垃圾。如果运行时可以警告应用程序一个节点很快需要GC暂停，那么应用程序可以停止向该节点发送新的请求，等待它完成处理未完成的请求，然后在没有请求正在进行时执行GC。

这个想法的一个变种是只用垃圾收集器来处理短命对象（这些对象要快速收集），并定期在积累大量长寿对象（因此需要完整GC）之前重新启动进程

这些措施不能完全阻止垃圾回收暂停，但可以有效地减少它们对应用的影响。

知识，真相，谎言

真相由多数觉得（法定人数）

一个节点发生故障的可能性有很多。自身故障；网络通讯丢失；GC过长；

节点不能根据自己的信息来判断自身的状态。目前分布式算法都依靠法定票数。最常见的法定票数是取系统节点半数以上。

主节点与锁

只允许有一个实例存在的例子：

  1. 只允许一个节点作为数据库分区主节点
  2. 特定资源的锁（事务获取资源锁）
  3. 不能重复的用户名

要处理节点被宣布失效后的降级操作。

Fencing令牌

我们假设每次锁定服务器授予锁或租约时，它还会返回一个fencing令牌（fencing token），这个数字在每次授予锁定时都会增加（例如，由锁定服务增加）。然后，我们可以要求客户端每次向存储服务发送写入请求时，都必须包含当前的fencing令牌。

对于不明确支持fencing令牌的资源，可能仍然可以解决此限制（例如，在文件存储服务的情况下，可以将防护令牌包含在文件名中）。但是，为了避免在锁的保护之外处理请求，需要进行某种检查。

拜占庭故障

伪造令牌，有节点故意破坏。

拜占庭故障（Byzantine fault），在不信任的环境中达成共识的问题被称为拜占庭将军问题

现实中的例子：

  1. 航空航天的硬件，被辐射发生故障。
  2. 在多个参与组织的系统中，一些参与者可能会试图作弊或者欺骗他人。

解决拜占庭容错的系统协议异常复杂；容错的嵌入式系统还需要硬件层面的支持。

普通的web应用不需要拜占庭容错，因为可以由服务其全权觉得请求是不是合法。在那种没有这种中央决策机制的点对点网络中，拜占庭容错才更为必要。

大多数拜占庭式容错算法要求超过三分之二的节点能够正常工作。

如果攻击者可以渗透一个节点，那他们可能会渗透所有这些节点，因为它们可能运行相同的软件。因此传统机制（认证，访问控制，加密，防火墙等）仍然是攻击者的主要保护措施。

弱的谎言形式以及预防：

当系统由于硬件，bug，配置错误发生了错误，可以采取一些方案来让系统更可靠：

  1. TCP/UDP内置的校验和
  2. 总是检查用户的输入是否合法
  3. NTP客户端配置多个时间服务器

理论系统模型与实践

计时方面：

  1. 同步模型
  2. 部分同步模型
  3. 异步模型

处理节点失效：

  1. 崩溃-中止模型
  2. 崩溃-恢复模型
  3. 拜占庭（任意）失效模型

对于fencing令牌生成算法模型要求：

  1. 唯一性
  2. 单调递增性
  3. 可以用性

安全性和活性

安全性通常被非正式地定义为，没有坏事发生，而活性通常就类似：最终好事发生。但是，最好不要过多地阅读那些非正式的定义，因为好与坏的含义是主观的。

在刚刚给出的例子中，唯一性（uniqueness）和单调序列（monotonic sequence）是安全属性，但可用性是活性（liveness属性。

发表于

事务主要是为了应对可能的出错情况。硬件软件的失效，应用与数据库节点之间的连接出问题，客户端竞争导致的写入覆盖等问题。

数据库事务，主要是为了简化应用层的编程模型。并非每个应用都需要事务机制。

深入理解事务

关系型数据库都支持事务，有些非关系型也支持。

很多新一代数据库（NoSQL）放弃了事务，或者替换为比其更弱的保证。

ACID

不符合ACID标准的系统有时被冠以BASE

A 原子性

提交过程中发生故障，事务会终止，并且丢弃或者撤销之前的部分更改。

C 一致性

对数据的一组特定陈述必须始终成立。即不变量（invariants），例如在会计系统中，所有账户整体上必须借贷相抵。

一致性本质上要求应用层来维护状态的一致（或者守恒）。

I 隔离性

如果两个客户端同时访问一条记录，可能会遇到并发问题（带来竞争条件）。

计数器的例子。

传统的数据库教科书将隔离性形式化为可序列化（Serializability），这意味着每个事务可以假装它是唯一在整个数据库上运行的事务。

然而实践中很少会使用可序列化隔离，因为它有性能损失。一些流行的数据库如Oracle 11g，甚至没有实现它。在Oracle中有一个名为“可序列化”的隔离级别，但实际上它实现了一种叫做快照隔离（snapshot isolation） 的功能，这是一种比可序列化更弱的保证。

D 持久性

持久性 是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。

在历史上，持久性意味着写入归档磁带。后来它被理解为写入硬盘或SSD。最近它已经适应了“复制（replication）”的新内涵。

单对象与多对象事务

数据库提供的保证是

  • 原子性， 要么全部成功，要么全部失败。
  • 隔离性， 同时运行的事务之间不应互相干扰。

违反隔离性的例子，邮件系统的未读邮件计数器和邮件，在写入的时候不应该被其他客户端读区到不一致的状态。

单对象写入

一些数据库也提供更复杂的原子操作，例如自增操作。同样流行的是 比较和设置（CAS, compare-and-set） 操作，当值没有并发被其他人修改过时，才允许执行写操作。

多对象事务

需要多对象事务的情况：

  1. 关系型，外键插入时的正确性验证。
  2. 文档型，更新非规范化（因为缺乏连接能力）信息时，一次更新多个文档。
  3. 二级索引的更新

处理错误与中止

错误发生不可避免，但许多软件开发人员倾向于只考虑乐观情况，而不是错误处理的复杂性。例如，像Rails的ActiveRecord和Django这样的对象关系映射（ORM, object-relation Mapping） 框架不会重试中断的事务—— 这个错误通常会导致一个从堆栈向上传播的异常，所以任何用户输入都会被丢弃，用户拿到一个错误信息。这实在是太耻辱了，因为中止的重点就是允许安全的重试。

弱隔离级别

出于这个原因，数据库一直试图通过提供事务隔离（transaction isolation） 来隐藏应用程序开发者的并发问题。从理论上讲，隔离可以通过假装没有并发发生，让你的生活更加轻松：可序列化（serializable） 的隔离等级意味着数据库保证事务的效果与连续运行（即一次一个，没有任何并发）是一样的。

实际上不幸的是：隔离并没有那么简单。可序列化 会有性能损失，许多数据库不愿意支付这个代价。因此，系统通常使用较弱的隔离级别来防止一部分，而不是全部的并发问题。这些隔离级别难以理解，并且会导致微妙的错误，但是它们仍然在实践中被使用。

读已提交（Read Commited）

  1. 读数据库时，只能看到已经提交的数据（防止脏读）
  2. 写数据库时，只能覆盖已经提交的数据（防止脏写）

防止脏读

如果一个事务可以看到另一个事务还没有完全提交的数据，那么就是脏读。

读已提交的隔离级别可以防止脏读。

需要防止脏读的情况：

  1. 一个事务需要修改多个对象，并且这些对象有一致性的保证。例如电子邮件的例子。
  2. 如果事务发生中止，所有的写入都要回滚。如果发生脏读，那么会看到一些会被回滚的数据，可能会造成麻烦。

防止脏写

两个事务更新同一个对象，如果一个事务的写入操作覆盖了另一个事务尚未提交的一部分，那么就是脏写。

读已提交的隔离级别可以防止脏写。通常的方式是推迟第二个写请求，直到前面的事务提交成功（或者中止）。

二手车买卖的例子，买同一辆车，车主和销售发票的所有者要一致。

实现读已提交

数据库通常使用行级锁来防止脏写。

防止脏读，用锁太重了。大多数数据库通常都会对待更新的对象，维护旧值和当前持有写锁的事务的新值两个版本。

快照级别隔离和可重复读（Repeatable Read）

读已提交解决不了一些场景中的问题，会导致错误。

银行转账的例子。

爱丽丝在银行有1000美元的储蓄，分为两个账户，每个500美元。现在一笔事务从她的一个账户中转移了100美元到另一个账户。如果她在事务处理的同时查看其账户余额列表，不幸地在转账事务完成前看到收款账户余额（余额为500美元），而在转账完成后看到另一个转出账户（已经转出100美元，余额400美元）。对爱丽丝来说，现在她的账户似乎只有900美元——看起来100美元已经消失了。

这种异常被称为不可重复读（nonrepeatable read）或读取偏差（read skew）

还有一些场景不能容忍暂止的不一致，数据备份，分析查询和完整性检查场景。

快照级别隔离是常见的解决手段。快照隔离是一个流行的功能：PostgreSQL，使用InnoDB引擎的MySQL，Oracle，SQL Server等都支持。

实现快照级别隔离

与读取提交的隔离类似，快照隔离的实现通常使用写锁来防止脏写。

但是读取不需要任何锁定。从性能的角度来看，快照隔离的一个关键原则是：读不阻塞写，写不阻塞读。

为了实现快照隔离，数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它并排维护着多个版本的对象，所以这种技术被称为多版本并发控制（MVCC, multi-version concurrentcy control）。

图种说明了，如何在PostgreSQL中实现基于MVCC的快照隔离【31】（其他实现类似）。当一个事务开始时，它被赋予一个唯一的，永远增长[^vii]的事务ID（txid）。每当事务向数据库写入任何内容时，它所写入的数据都会被标记上写入者的事务ID。

表中的每一行都有一个 created_by 字段，其中包含将该行插入到表中的的事务ID。此外，每行都有一个 deleted_by 字段，最初是空的。如果某个事务删除了一行，那么该行实际上并未从数据库中删除，而是通过将 deleted_by 字段设置为请求删除的事务的ID来标记为删除。在稍后的时间，当确定没有事务可以再访问已删除的数据时，数据库中的垃圾收集过程会将所有带有删除标记的行移除，并释放其空间。

一致性快照的可见性规则

当一个事务从数据库中读取时，事务ID用于决定它可以看见哪些对象，看不见哪些对象。通过仔细定义可见性规则，数据库可以向应用程序呈现一致的数据库快照。

索引与快照级别隔离

如何支持索引？

  1. 直接指向对象的所有版本。
  2. Copy on write。每次修改时候，复制一个B-tree。后台回收和压缩。

防止更新丢失

例子，两个并发的计数器更新。

如果应用从数据库中读取一些值，修改它并写回修改的值（读取-修改-写入序列），则可能会发生丢失更新的问题。如果两个事务同时执行，则其中一个的修改可能会丢失，因为第二个写入的内容并没有包括第一个事务的修改。

场景，递增计数器；更新账户余额；对复杂对象的一部分修改；两个用户同时编辑wiki页面。

原子写操作

有些数据库支持的原子操作。可以避免在应用层的“读取-修改-写入”操作。

1
UPDATE counters SET value = value + 1 WHERE key = 'foo';

像MongoDB这样的文档数据库提供了对JSON文档的一部分进行本地修改的原子操作，Redis提供了修改数据结构（如优先级队列）的原子操作

显示加锁

Select … for update 加行锁

这是有效的，但要做对，你需要仔细考虑应用逻辑。忘记在代码某处加锁很容易引入竞争条件。

自动检查更新丢失

另一种方法是允许它们并行执行，如果事务管理器检测到丢失更新，则中止事务并强制它们重试其读取-修改-写入序列。

丢失更新检测是一个很好的功能，因为它不需要应用代码使用任何特殊的数据库功能，你可能会忘记使用锁或原子操作，从而引入错误；但丢失更新的检测是自动发生的，因此不太容易出错。

原子比较与设置

CAS，

例如，为了防止两个用户同时更新同一个wiki页面，可以尝试类似这样的方式，只有当用户开始编辑页面内容时，才会发生更新：

1
2
3
-- 根据数据库的实现情况，这可能也可能不安全
UPDATE wiki_pages SET content = '新内容'
  WHERE id = 1234 AND content = '旧内容';

ABA问题？

冲突解决和复制

在复制数据库中（参见第5章），防止丢失的更新需要考虑另一个维度：由于在多个节点上存在数据副本，并且在不同节点上的数据可能被并发地修改，因此需要采取一些额外的步骤来防止丢失更新。

如“检测并发写入”一节所述，这种复制数据库中的一种常见方法是允许并发写入创建多个冲突版本的值（也称为兄弟），并使用应用代码或特殊数据结构在事实发生之后解决和合并这些版本。

另一方面，最后写入为准（LWW）的冲突解决方法很容易丢失更新，如“最后写入为准（丢弃并发写入）”中所述。不幸的是，LWW是许多复制数据库中的默认值。

写入偏差与幻读

医院排班on call的例子。并发请假，导致应用的错误。

写偏差的特征

它既不是脏写，也不是丢失更新，因为这两个事务正在更新两个不同的对象。在这里发生的冲突并不是那么明显，但是这显然是一个竞争条件：如果两个事务一个接一个地运行，那么第二个医生就不能歇班了。异常行为只有在事务并发进行时才有可能。

如果无法使用可序列化的隔离级别，则此情况下的次优选项可能是显式锁定事务所依赖的行。

1
2
3
4
5
6
7
8
9
10
11
BEGIN TRANSACTION;
SELECT * FROM doctors
  WHERE on_call = TRUE 
  AND shift_id = 1234 FOR UPDATE;

UPDATE doctors
  SET on_call = FALSE
  WHERE name = 'Alice' 
  AND shift_id = 1234;
  
COMMIT;

更多写偏差的例子

  1. 会议室预定系统，double booking
  2. 多人游戏, 棋盘上同时移动不同的棋子，但是要预防违反游戏规则。
  3. 申请同一个用户名，重名问题，可以使用Unique Key
  4. 防止双重开支，超额支付信用或者存款。

产生写偏差的原因

一个事务中的写入改变另一个事务的搜索查询的结果，被称为幻读。

物化冲突

如果幻读的问题是没有对象可以加锁，也许可以人为地在数据库中引入一个锁对象。

例如会议室预定，可以想象创建一个关于时间槽和房间的表。要创建预订的事务可以锁定（SELECT FOR UPDATE）表中与所需房间和时间段对应的行。

这种方法被称为物化冲突（materializing conflicts），因为它将幻读变为数据库中一组具体行上的锁冲突

在大多数情况下。可序列化（Serializable） 的隔离级别是更可取的。

串行化（Serialize）

最强的隔离级别。

数据库保证，如果事务在单独运行时行为正确，则它们在并发运行时仍然正确，换句话说，数据库防止所有可能的竞争条件。

目前大多数提供可序列化的数据库都使用了三种技术之一，本章的剩余部分将会介绍这些技术。

  1. 字面意义上地串行顺序执行事务（参见“真的串行执行”）
  2. 两相锁定（2PL, two-phase locking），几十年来唯一可行的选择。（参见“两相锁定（2PL）”）
  3. 乐观并发控制技术，例如可序列化的快照隔离（serializable snapshot isolation）（参阅“可序列化的快照隔离（SSI）”

真的串行执行

单线程循环执行事务。

基础：

  1. 内存中可以加载应用需要的所有数据，之后的事务操作都在内存中，快。
  2. OLTP一般都很快，只是少量的读写。

串行执行事务的方法在VoltDB/H-Store，Redis和Datomic中实现。

使用存储过程

具有单线程串行事务处理的系统不允许交互式的多语句事务。应用程序必须提前将整个事务代码作为存储过程提交给数据库。

存储过程优缺点

缺点
  1. 厂商们在存储过程的语言不一致；
  2. 代码难以管理；难调试；难测试；
  3. 如果写了不好的存储过程，会对数据库性能产生很大的影响；
优点
  1. 吞吐量高

分区下的串行

需要对所有分区加锁。如果有多个二级索引，性能会很差。

串行小结

在特定约束条件下，真的串行执行事务，已经成为一种实现可序列化隔离等级的可行办法。

  1. 每个事务都必须小而快，只要有一个缓慢的事务，就会拖慢所有事务处理。
  2. 仅限于活跃数据集可以放入内存的情况。很少访问的数据可能会被移动到磁盘，但如果需要在单线程执行的事务中访问，系统就会变得非常慢^x。
  3. 写入吞吐量必须低到能在单个CPU核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。
  4. 跨分区事务是可能的，但是它们的使用程度有很大的限制。

两阶段加锁2PL

不是分布式中的两阶段提交2PC。

对象只要有写入（修改或删除），就需要独占访问（exclusive access） 权限：

  1. 如果事务A读取了一个对象，并且事务B想要写入该对象，那么B必须等到A提交或中止才能继续。 （这确保B不能在A底下意外地改变对象。）
  2. 如果事务A写入了一个对象，并且事务B想要读取该对象，则B必须等到A提交或中止才能继续。 （读取旧版本的对象在2PL下是不会出现的。）

在2PL中，写入不仅会阻塞其他写入，也会阻塞读，反之亦然。

而快照隔离使得读不阻塞写，写也不阻塞读。

实现2PL

每个对象有一个读写锁来隔离写操作。

2PL用于MySQL（InnoDB）和SQL Server中的可序列化隔离级别，以及DB2中的可重复读隔离级别。

读与写的阻塞是通过为数据库中每个对象添加锁来实现的。锁可以处于共享模式（shared mode）或独占模式（exclusive mode）

锁规则：

  1. 若事务要读取对象，则须先以共享模式获取锁。允许多个事务同时持有共享锁。但如果另一个事务已经在对象上持有排它锁，则这些事务必须等待。
  2. 若事务要写入一个对象，它必须首先以独占模式获取该锁。没有其他事务可以同时持有锁（无论是共享模式还是独占模式），所以如果对象上存在任何锁，该事务必须等待。
  3. 如果事务先读取再写入对象，则它可能会将其共享锁升级为独占锁。升级锁的工作与直接获得排他锁相同。
  4. 事务获得锁之后，必须继续持有锁直到事务结束（提交或中止）。这就是“两阶段”这个名字的来源：第一阶段（当事务正在执行时）获取锁，第二阶段（在事务结束时）释放所有的锁。

由于使用了这么多锁，所以很容易发生事务A被卡住等待事务B释放它的锁，反之亦然。这种情况称为死锁。数据库自动检测死锁之后会终止事务，然后重启事务排队。

2PL性能

缺点，性能差（吞吐量低，响应时间不确定）。

谓词锁

会议室预定例子。查询所有会议室，和update/insert会议室预定。

锁定一个范围的查询对象。

索引区间锁

谓词锁性能不佳：如果活跃事务持有很多锁，检查匹配的锁会非常耗时。因此，大多数使用2PL的数据库实际上实现了索引范围锁（也称为间隙锁（next-key locking）），这是一个简化的近似版谓词锁。

可串行化的快照隔离（SSI）

性能不好（2PL）或者扩展性不好（串行执行）的可序列化隔离级别。

更好的选择，一个称为可序列化快照隔离（SSI, serializable snapshot isolation） 的算法是非常有前途的。

悲观与乐观的并发控制

2PL是悲观机制，如果有竞争可能出错，那么等到安全之后再做。像多线程编程种的互斥。串行执行可以称为悲观到了极致。

相比之下，序列化快照隔离是一种乐观（optimistic） 的并发控制技术。如果可能发生冲突，那么先继续执行，等到提交时候，数据库检查是否冲突。如果有冲突则中止，接下来重试。

如果事务之间竞争不大，乐观并发控制会比悲观控制高效很多。如果冲突很多，则性能不佳。

SSI，所有的读操作都是基于一致性快照。通过算法检测冲突，来决定是否中止事务。

需要考虑的冲突情况

检测对旧MVCC对象版本的读取（读之前存在未提交的写入）

在事务43想要提交时，事务42 已经提交。这意味着在读一致性快照时被忽略的写入已经生效，事务43 的前提不再为真。

为何在提交时才检查？为了高效支持长时间读事务的性能。

检测影响先前读取的写入（读之后发生写入）

当事务写入数据库时，它必须在索引中查找最近曾读取受影响数据的其他事务。这个过程类似于在受影响的键范围上获取写锁，但锁并不会阻塞事务到其他事务完成，而是像一个引线一样只是简单通知其他事务：你们读过的数据可能不是最新的啦。

性能

对比2PL，串行。对于读密集的负载性能好。

事务中止的比例会影响SSI的性能。

发表于

数据分区的主要目的—提高可扩展性。也就是应对增长的负载，把负载均匀的分布到各个机器/节点上。

数据分区与数据复制

通常结合使用，也就是每个分区在多个节点都存有副本。

一个节点可能有一个或多个分区。每个分区都有自己的主副本。

Key-Value 数据分区

如何决定哪些记录放在哪个节点上？

如果分区不均匀，那么会导致某些分区节点比其他分区承担更多的数据量的查询负载，成为倾斜。会导致分区效率下降。

避免热点的最简单的方法是将记录随机分配给各个节点。可以比较均匀的分布数据。但是有一个缺点，当读区特定数据时，无法知道保存在哪个节点，所以必须并发读所有节点。这可以改进。

基于Key的区间分区

为每个分区指定一块连续的key范围，就像百科全书一样。

Bigtable使用了这种分区策略，以及其开源等价物HBase。

  • 优点，每个分区可以按照key排序（类似SSTables和LSM-Trees），可以轻松支持区间查询。
  • 缺点，某些访问模式会导致热点。

基于关键字哈希值分区

用来解决数据倾斜和热点问题。

哈希函数的选择，不能使用内置的哈希函数，例如Java的Object.hashCode,同一个Key的返回值可能在不同的进程中不一样。

每一个分区是一个哈希范围。

分区的边界可以是均匀的，也可也是伪随机选择（一致性哈希）。

缺点，丧失了良好的分区查询特性。在MongoDB中，如果使用了哈希分片模式，则区间查询会发送到所有的分区上。

Cassandra在两种分区策略中做了折中。使用了主key哈希，其他列区间的方式。可以支持在其他列上的高效区间查询。

一致性哈希
是一种平均分配负载的方法，最初用于CDN，描述了重新平衡的特定方法。正如我们将在“重新平衡分区”中所看到的，这种特殊的方法对于数据库实际上并不是很好，所以在实际中很少使用。

组合索引 例如社交网络的（user_id, update_timestamp）。可以高效的检索一个用户在一段时间的所有更新，按照时间戳排序。

负载倾斜与消除热点

基于哈希的分区方法可以减轻热点，但是无法完全避免。极端情况就是所有的读写操作都是针对同一个key。社交网络上的名人有几千万粉丝的例子。

解决方法：应用层来减轻倾斜程度。

  • 写入 例如如果某个关键字被确定为热点，就在关键字开头或者结尾加一个随机数。这样只需要一个两位数的十进制数就可以把关键字分不到100个不同的关键字上。
  • 读取 需要从所有100个关键字中读取数据然后进行合并。

因此只有对少量关键字附加随机数才有意义。需要额外的元数据来标记哪些关键字进行了特殊处理。

分区与二级索引

二级索引，情况变得复杂。不能唯一表识一个记录，而是用来做特定值的查询。例如红色的车，包含hogwash的文章。

基于文档分区的二级索引

也称为本地索引。每个分区有自己的索引。

搜索时候，需要将查询发送到所有的问去，然后合并所有的返回结果。这种方法也叫做分散/聚集。查询代价高昂。

尽管如此，它还是广泛用于实践：MongoDB，Riak，Cassandra，ElasticSearch，SolrCloud，VoltDB。。。

基于词条的二级索引分区

构建全局索引。全局索引也必须进行分区。可以与数据关键字采用不同的分区策略。

读取更为高效。不需要分散/聚集。

写入较慢且非常复杂。更新单个文档时，需要涉及到多个二级索引，写放大。所以，现有数据库都不支持同步更新二级索引。

实践中，二级索引的更新都是异步的。

分区再平衡

应对数据库的变化，例如：

  1. 查询压力增加，需要更多的CPU处理负载。
  2. 数据规模增加，需要更多的磁盘和内存。
  3. 节点故障，需要其他机器接管失效节点。

以上这些变化都要求数据和请求从一个节点转移到另一个节点。这样一个迁移负载的过程成为再平衡。

再平衡的目标：

  1. 平衡后，负载，存储，读写请求等应该更均匀。
  2. 再平衡过程中，可以正常的读写。
  3. 避免不必要的负载迁移，尽量减少网络和磁盘IO影响。

再平衡策略

坏方法：取模 mod N

如果N变化，就会产生迁移。频繁的迁移增加了再平衡的成本。

简单的解决方法：固定数量分区

  1. 首先，创建远超过实际节点数的分区。然后为每个节点分配多个分区。
  2. 接下来，如果集群中添加了新节点，就从现有节点中匀走几个给新节点，直到分区再次达到全局平衡。
  3. 如果删除节点，则执行相反的措施。

迁移过程中，总分区数不变。也不会改变关键字到分区的映射关系。

需要调整的是，分区与节点的对应关系。

分区大小应该恰到好处。

动态分区

HBase和RethinkDB等采用了动态创建分区的策略。当分区数据增长超过一个可配置的阀值，就将它拆分为两个分区，每个承担一半的数据量。反过来也是。

动态分区不仅适用于关键字区间分区，也适用于基于哈希的分区策略。

按节点比例分区

每个节点具有固定数量的分区。Cassandra和Ketama采用了这种方式。

当节点数不变时，每个分区的大小与数据集大小保持正比的增长关系。当节点数增加时，分区则会调整的更小。

新节点加入集群时，会随机选择固定数量的现有分区进行分裂，然后拿走这额分区一半的数据量。

随机选择分区边界，前提是要求采用基于哈希的分区。这也符合一致性哈希。

自动与手动再平衡

推荐手动，避免意外发生。

请求路由

客户端请求时，如何直到应该链接哪个节点？

属于服务发现的问题。任何通过网络访问的系统都有这样的要求，尤其是当服务目标支持高可用时。

处理策略：

  1. 允许客户端链接任意的节点。如果请求的节点能满足客户端查询，则返回，否则转发到下一个合适的节点。
  2. 客户端的请求都发送到一个路由层，路由层来转发请求到可以处理的节点。
  3. 客户端感知分区和节点的关系，直接连接到目标节点。

如何应对变化？很多分布式系统依赖一个独立的协调服务（如ZooKeeper），跟踪集群范围内的元数据。每个节点都向Zookeeper中注册自己，ZooKeeper维护了分区到节点的映射。客户端或者路由层订阅这个映射，当有改变时，会通知订阅者更改。

​
Cassandra和Riak采取不同的方法：他们在节点之间使用流言协议（gossip protocol） 来传播群集状态的变化。请求可以发送到任意节点，该节点会转发到包含所请求的分区的适当节点（处理策略的方法1）。这个模型在数据库节点中增加了更多的复杂性，但是避免了对像ZooKeeper这样的外部协调服务的依赖。

执行并行查询

目前只关注了读写单个关键字的建大查询，大多数是NoSQL分布式数据存储所支持的访问类型。

然而，通常用于分析的大规模并行处理（MPP, Massively parallel processing） 关系型数据库产品在其支持的查询类型方面要复杂得多。一个典型的数据仓库查询包含多个连接，过滤，分组和聚合操作。 MPP查询优化器将这个复杂的查询分解成许多执行阶段和分区，其中许多可以在数据库集群的不同节点上并行执行。涉及扫描大规模数据集的查询特别受益于这种并行执行。

发表于

分布式数据系统

分布式数据系统的设计目的

  1. 扩展性，当数据量或者读写负载增长的时候，如何分散到多台机器上
  2. 容错与高可用性， 当单机出现故障，如何可以让系统继续工作。
  3. 延迟考虑，就近为用户选择数据中心来提供服务。

系统扩展的方式和考虑的问题

系统的扩展能力

水平扩展和垂直扩展。共享内存架构与共享磁盘架构。成本问题。资源竞争问题。

无共享结构

通过网络互联的节点，通过软件实现核心逻辑，提供统一的服务。
性价比高。
可以做到性能更强大。

复制与分区

将数据分布在各个节点上的方法。分区和复制。

数据复制

能够在多台机器上存储相同的数据副本。达到以下目的：

  • 低延迟访问
  • 高可用性
  • 提高吞吐量

本章假设是数据规模比较小，一份数据拷贝可以完整的保存在一个机器中。分布式数据库成为主流也是最近发生的事情。

主节点和从节点，主从架构

一个节点负责写入，其他节点负责读。写入节点负责更新所有的从属节点。

工作流程：

  1. 指定一个副本为主，程序中对数据库所有的写操作都发送到这个主节点，主节点把数据写入自己的数据库中。
  2. 主节点写完自己的数据后，把对数据的更改作为log或者更改流发送给所有的从属副本。每个从属副本得到更新日志后，完成数据写入本地的操作。
  3. 客户端 读区数据时候，可以在任何节点上执行查询。但是只有主节点可以写。

具有主从复制功能的数据库

关系型，PostgresSQL, MySQL, Oracle Data Guard, SQL Server。
非关系型，MongoDB， RethinkDB和Expresso。
分布式消息队列，Kafka，RabbitMQ

同步复制与异步复制

这是复制中非常重要的一个设计选项。对于关系型数据库，同步和异步是可以可配置的。而其他系统，只能hardcode一个选择。

  • 节点1是同步，主节点需要等节点1写完之后才能向客户端确认
  • 节点2是异步，主节点不需要等节点2给出完成写入的信息，就可以向客户端确认。

同步复制从节点的优点，从节点一直保留着最新的数据copy。如果主节点出现故障，从节点可以继续提供访问最新数据的能力。
缺点，如果同步节点无法确认，无论是网络原因还是其他原因，写入总会失败。主节点需要阻塞所有的写入操作直到从节点完成响应。

最佳配置是，一个同步节点，剩下的都是异步节点。这种配置也叫半同步。

达到极限吞吐量，就是全异步节点。但是无法保证持久化。有点是，无论从属节点怎么落后，都可以继续响应写入。
异步模式听起来不靠谱，但是还是被广泛使用，特别是那些从节点数量巨大或者分布地理环境特别广的情况。需要解决复制滞后问题。

增配新的从节点

如何加一个新的从节点？

简单的把数据文件拷贝是不够的，因为客户端有可能在复制的时候继续更新原来的数据。
锁定数据库，使其不可写，直到复制完成，会影响可用性。

解决方案操作步骤：

  1. 主节点在某个时间点生成快照文件。
  2. 把快照文件拷贝给新的从节点。
  3. 从节点连接到主节点，请求快照之后的更新日志。
  4. 从节点在快照文件的基础上执行这些更新日志，成为趋赶。接下来可以继续处理主节点的更新变化。并重复1到4.

处理节点失效

从节点失效：追赶式恢复

请求故障前最后一个事务滞后所有的更改，并且趋赶。

主节点失效：节点切换

需要把某个从节点升级成主节点。可以手动，可以自动。

自动切换步骤：

  1. 确认主节点失效。基于超时的机制：节点间互发心跳。
  2. 选举新的主节点。选离主节点版本最新的节点，来最小化丢失数据的风险。
  3. 重新配置系统，使主节点生效。客户端需要把写请求发送给新的主节点。等原来的主节点上线时，要把它降级为从。
主节点切换时会遇到的问题
  1. 异步复制的从节点，如果主节点挂掉之前，新的主节点并没有接收到最新的数据。这样当原来的主节点又上线后，需要处理写冲突的问题。通常的解决方案是原来主节点上没有完成复制数据丢弃掉。
  2. 丢弃数据的方案很危险。与主键分配有关，GitHub泄漏Private数据的例子。
  3. 两个节点都认为自己是主，称为脑裂。很危险，两个节点都接受写的请求，没有很好解决冲突的方法。可能需要强制关闭其中一个节点。
  4. 需要选择一个合适的超时时间来检测主节点失效。

复制日志的实现底层方式

基于语句的复制

执行SQL。有不适用的场景：

  1. 非确定性函数语句，NOW（） RAND（）等
  2. 自增列问题
  3. 有副作用的语句（触发器，SP，自定函数）

基于预写日志（WAL）传输

存储引擎的磁盘数据结构。每个写操作都是追加写的方式写入日志：

  • 日志结构的存储引擎（SSTables，LSM-trees）。日志是存储方式
  • Btree的覆盖写结构，每次都会写WAL日志。

不管哪种，都是日志。可以在另一个节点上构建copy。

缺点 日志描述的数据结构非常底层，与存储引擎紧密耦合。数据库升级如果存储格式改版，可能会有问题。
复制协议必须要求版本严格一致，升级就必须停机。

基于行的逻辑日志复制

与存储引擎采用不同的日志格式。

  1. 对于行插入，日志记录相关列的新值
  2. 对于行删除，日志表识这一行被删除
  3. 对于行更新，日志记录所有列的的新值

事务执行时影响到多行，会产生多个这样的日志记录，最后是一个commit日志。MySQL的binlog使用该方式。

这样的逻辑日志，容易向后兼容。

基于触发器的复制

优点高度灵活，
触发器执行自己写的应用代码，将数据的更改记录到一个单独的表中，然后外部逻辑处理这个表，完成自定义的逻辑，例如复制到另一个系统。
缺点开销更高

复制滞后问题

主从结构的复制，对于读操作密集的应用，如Web，是一个不错的选择。可以创建多个副本，来让读请求分配到就近的节点。

这种体系下的扩展，只需要添加更多的从副本，就可以提高服务器的吞吐量。但这种扩展一定是异步复制。这样会有复制滞后的问题。

这种不一致是一个暂时状态，但是并没有保证多长时间内会一致。也叫最终一致性（eventually consistency）。

读自己的写

用户自己的刚刚提交的数据，返回提交成功，但刷新页面后又看不到数据。可能是因为第二次读，是读到了一个没有最新数据的节点。

我们需要写后读一致性

基于一些业务场景的方案：

  1. 用户修改自己的资料场景。读用户可能已经修改过的内容时，都从主库读。别人无法修改这份数据，只有一个客户端会修改时，需要客户端配合记录修改的操作。
  2. 如果这份数据可以被多个人修改，上面的方法就不行了。需要用其他的标准来决定是否去主库读。例如可以跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。还可以监控从库的复制延迟，防止任向任何滞后超过一分钟到底从库发出查询。
  3. 客户端可以记住最近一次写入的时间戳，服务器检查这个时间戳和从库的同步时间比较。来验证数据是否有效。
  4. 如果副本分布在多个数据中心，则需要一个中心路由判断。

多客户端时会变得更复杂。需要跨设备的读写一致性。

其他问题：

  • 记住用户上次更新时间戳的方法变得更加困难。元数据需要一个中心存储。
  • 如很难保证来自不同设备的连接会路由到同一数据中心

单调读

读到新值后，之后不再会读到旧值。

看到新的评论刷新后又消失的例子。

确保每个用户总是固定的从一个副本中读数据。不要随记路由。

需要解决节点失效的影响。

前缀一致读

聊天记录的复制问题。对话，问答的happen before逻辑，需要在复制时候解决。不要乱序

这个是分区数据库的一个特殊问题，需要前缀一致读

一个解决方案时确保有因果关系的数据写入都交给一个分区解决。但是会影响效率。也有新的算法来解决逻辑先后问题。

复制滞后的解决方案

当需要对写后读等问题支持的时候，一定要小心同步复制和异步复制的配置问题，与系统设计时的思考一致，不然会出大问题。

应用层可以解决滞后问题，但是代价是更复杂更容易出错。

分布式事务，有人断言，最终一致性是分布式系统最终的选择。

多主节点复制

适用多数据中心的架构，如果是一般的单数据中心，还是主从好，因为简单不容易出错。

主从问题就是主节点网络中断后，写入操作都会出问题。

多主结构，就是有多个主节点接收写操作。数据中心之间的复制，由各自主节点之间通信，而数据中心内部的复制，由其中的主节点，复制到其他的从节点。

适用场景

多数据中心

多领导者配置中可以在每个数据中心都有主库。 图中展示了这个架构的样子。 在每个数据中心内使用常规的主从复制；在数据中心之间，每个数据中心的主库都会将其更改复制到其他数据中心的主库中。

单主，多主复制之间的差异：

  1. 性能。
    主从架构会影响写入延迟。多主结构，对于本地数据中心可以快速响应，然后用异步复制，复制到其他数据中心。
  2. 容忍数据中心失效
    多主更好。没有切换操作。
  3. 容忍网络问题
    多主更好。
商业数据库支持

多主复制MySQL的Tungsten Repliactor，PostgreSQL的BDR，Orcale的GoldenGate。

多主的缺点

必须处理写入冲突。

由于多主复制都是现在数据库中新增的高级功能，有些交互，触发器函数，自增主键等会有副作用。有些人认为多主很危险，应该尽量避免。

离线客户端操作

例如日历，Todo，会议安排等。每一个设备都是一个充当主节点的本地数据库。当设备再次上线时候，需要与服务器同步。

CouchDB就是为这种操作模式设计的。

协作编辑

Google Docs。

可编辑力度非常小，也会有多主复制的挑战—写入冲突。

处理写冲突（多主）

解决多主复制的最大问题。例子，多人编辑Wiki。

同步与异步冲突检测

简单的允许多主节点并行接受写请求，会产生冲突问题。

同步方式，需要所有主节点确认写入后才能返回，失去了多主节点的优势，退化成了单主结构。

避免冲突

  • 总是把特定用户的更新请求路由到特定的数据中心。基本等价于主从模型
  • 问题在于，如果某个数据中心故障，之前的配置需要被修改到可用的数据中心时，会有问题。无法避免冲突。

收敛于一致状态

  • 给每个写入分配一个类似UUID的东西，选最高的ID为胜者。缺点，数据丢失。
  • 为每个副本分配一个UUID，预先制定副本之间的优先级。缺点，数据丢失。
  • 合并冲突数据。
  • 保留冲突信息，给应用层解决。（时候解决冲突，可能需要提示用户）

自定义冲突解决逻辑

最适合的方式可能还是应用层程序来解决冲突。

在写入和读时执行冲突解决代码的逻辑：

  • 写时执行
    只要数据库系统在执行复制的change日志时，监测到冲突，就调用应用层的冲突解决程序。
    Bucardo支持写Perl。这个解决方法通常只能后台运行。
  • 读时执行
    发现冲突时，把所有的冲突值都暂存起来。下一次读时，把这些值一并返回给应用层。让用户来处理。
    CouchDB采用这样的处理方式。

冲突的定义

根据业务场景区分。有些显而易见，例如两个人同时修改一个record的某一列。有些不是这么直接，例如会议室预定系统，或者有限商品的秒杀系统。

自动冲突解决

冲突解决规则可能越来越复杂，而且自定义代码很容易出错。

一些方法：

  1. CRDT（conflict-free replicated datatypes），map orderedlist counter，可以用内置的方式自动解决。
  2. 使用可合并的数据结构。类似git的合并。
  3. 操作转换（operational transformation）是Google Docs等背后的解决方法。专门为可同时编辑的有序表设计。

拓扑结构

三种多主的复制拓扑结构

环形为防止无限循环，每个节点需要一个UUID，复制的时候带上已经完成过的节点ID。

星型和环形的问题，是节点故障。修复之前会影响其他节点。

全链路问题，某些链路快，某些慢，会导致复制日志覆盖，产生类似前缀一致读的问题。

无主节点复制

设计思路：放弃使用主节点，允许任何副本直接处理写请求。

这类数据库也被称为Dynamo风格数据库（不是AWS的那个，AWS的DynamoDB是单主架构）。

在一些无领导者的实现中，客户端直接将写入发送到到几个副本中，而另一些情况下，一个协调者（coordinator）节点代表客户端进行写入。但与主库数据库不同，协调者不执行特定的写入顺序。我们将会看到，这种设计上的差异对数据库的使用方式有着深远的影响。

节点失效时写入数据库

核心思想，并发读多个副本，使读到最新数据的概率达到最高。

读修复与反熵

  • 读修复。并行读多个副本时，可以检测到过期的返回值。适合被频繁读取的场景。
  • 反熵。后台进程不断查找副本之间的差异，完成更新。

​并不是所有的系统都实现了这两个;例如，Voldemort目前没有反熵过程。请注意，如果没有反熵过程，某些副本中很少读取的值可能会丢失，从而降低了持久性，因为只有在应用程序读取值时才执行读修复。

读写quorum（法定人数）

w + r > n

写至少需要确认w个节点，读必须读到r个节点，n是副本总数。

通常w=r=（n+1）/ 2，也可以灵活配置。例如读多写少的情况，可以配置w=n，r=1.但是更容易写入失败。

仲裁条件定义了可以容忍的失效节点个数。

Quorum一致性的局限性

关键在于读写有重叠。即使在w+r》n的情况下，也存在返回旧值的边界条件。主要取决于现实情况：

  1. 如果采用了sloppy quorum
  2. 并发写冲突时候，需要根据时间戳挑选胜者，如果时钟偏差，会造成数据丢失。
  3. 读写同时发生，写操作可能只完成了一半节点，返回新旧值有不确定性。
  4. 如果写入失败，已经成功的节点不会回滚。会读到新值。
  5. 其他边界情况

无法得到复制滞后问题的一致性保证。

监控旧值

​
从运维的角度来看，监视你的数据库是否返回最新的结果是很重要的。

sloppy quorum与数据回传
  • 容错能力。网络中断，无法满足法定人数，会使系统无法读，
  • 无法满足法定人数时的出错处理。是否把错误返回客户端，或者是否还接收写请求。
  • 放松仲裁方案允许不满足法定人数的写
  • 一旦网络恢复，临时节点需要向原主节点完成数据传输（回传）。

​在所有常见的Dynamo实现中，sloppy quorum是可选的。在Riak中，它们默认是启用的，而在Cassandra和Voldemort中它们默认是禁用的。

多数据中心操作

n是所有数据中心的节点总数。配置时，可以指定每个数据中心各有多少副本。

Cassandra和Voldemort在正常的无主模型中实现了他们的多数据中心支持。客户端通常只等待来自其本地数据中心内的法定节点的确认。

Riak将客户端和数据库节点之间的所有通信保持在一个数据中心本地，因此n描述了一个数据中心内的副本数量。数据库集群之间的跨数据中心复制在后台异步发生，其风格类似于多领导者复制

检测并发写

Dynamo风格的数据库允许多个客户端同时写入相同的Key，这意味着即使使用严格的法定人数也会发生冲突。
读修复或带数据回传时也可能会产生冲突。

解决冲突：

最后写入胜利（丢弃并发写入）

强制排序，例如时间戳，最大的获胜。是Cassandra唯一支持的冲突解决方法，也是Riak中的一个可选方案。

LWW（last write wins）缺点，牺牲数据永久性。
如果丢失数据不可接受，LWW是解决冲突的一个很烂的选择。

与LWW一起使用数据库的唯一安全方法是确保一个pk只写入一次，然后视为不可变，从而避免对同一个key进行并发更新。

Happens-before关系和并发

需要一个算法判断两个操作是否并发。比如插入之后才会更新。

确定先后关系

购物车的例子。

算法工作流程：

  1. 服务器维护pk的版本号
  2. 客户端读时，返回所有的值的最新版本号。（写前必须读）
  3. 客户端写pk时，必须传入之前读的版本号，读到的值和新值合并后的集合。
  4. 服务端接收到特定版本的写入时，覆盖版本号。

合并同时写入的的值

购物车例子中，加入商品操作，可以合并，去掉重复值。

删除适用墓碑标记。

使用专门的数据结构，CRDT。支持高校合并，删除标记。

版本矢量

多副本没有主节点的购物车。

需要为每个一个副本和每个主键都定一个版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本中看到的版本号。这个信息指出了要覆盖哪些值，以及保留哪些值作为兄弟。

所有副本的版本号合集成为版本矢量。也有虚线版本适量。

另外，就像在单个副本的例子中，应用程序可能需要合并兄弟副本。

发表于

应用程序在根据需求不断的变化时，往往会对其存储的数据有更改的情况。

当数据格式或者模式发生变化的时候，经常需要对应用程序的代码修改。对于一个大型程序，这并非容易。

  1. 服务器应用需要滚动升级。这样部署新版本的时候，不需要停止服务。
  2. 客户端升级，只能寄希望于用户。很有可能用户永远不会升级。

升级中需要考虑的亮点：

  1. 向前兼容。新代码读老数据。（容易）
  2. 向后兼容。老代码读新数据。（难）

数据编码格式

程序中的数据，至少有两种不同的表示形式

  1. 内存中。
  2. 写入文件或者发送到网络中。

两种形式之间的转换，成为序列化Serialize和反序列化Deserialize。或者编码Encode，解码Decode。

语言特定的格式

比如Java中java.io.Serializable接口；Ruby的Marshal；Python的pickle等。

这类编码的问题：

  1. 编码和语言绑定在一起，无法跨语言使用。
  2. 安全问题。远程执行任意代码。可以恢复成任意类，意味着Decode的过程中需要有能力创建任意的类。
  3. 向前向后兼容问题。
  4. 效率低。比如Java内置序列化。

JSON，XML与它们的二进制遍体

XML被批评主要在于其冗长和不必要的复杂。JSON受欢迎主要是在Web浏览器中的原生支持。CSV格式简单，功能弱一些。

它们都是文本格式的，可读性强。但也有问题：

  1. 数字编码有很多模糊的地方。XML和CSV中无法区分数字和数字组成的字符串；JSON不区分整数和浮点数，而且不指定精度。
  2. 对Unicode字符串支持好，但是不支持二进制数据。所以人们使用Base64将二进制数据编码成String来传递。
  3. XML和JSON都有可选的模式支持。数据的正确性解释，取决于模式中的信息，
  4. CSV没有任何模式，需要程序解释。

二进制编码

更紧凑更快的解析格式。可以节省空间和时间。在TB级别的数据时尤其关键。

MessagePack

最最基础的二进制化JSON方式

1
2
3
4
5
{
    "userName": "Martin",
    "favoriteNumber: 1337,
    "interests": ["daydreaming", "hacking"]
}

上图的二进制的结构解读：

  1. 第一个字节0x83，表示接下来是包含三个fields的对象（第四位0x03，高四位0x80）
  2. 第二字节0xa8，表示接下来的字符串，长度为八个字节
  3. 再往下的八个字节时ASCII的字段，userName
  4. 在接下来7个字节前缀0xa6表示后面有六个字节，Martin

结论：
整体编码占用66个字节，比原始的JSON编码（81个）少一些，但是不明显。

下面的方案中只用32个字节就可以完成同样记录的二进制化。

Thrift与Protocol Buffers

它们都是基于相同原理的二进制编码方式。都需要使用模式（Schema）来编码任意数据。

  • 使用Thrift的接口定义语言（IDL）来描述模式：

    1
    2
    3
    4
    5
    struct Person {
        1: required string       userName,
        2: optional i64          favoriteNumber,
        3: optional list<string> interests
    }

  • 使用Protocol Buffers的等效模式定义看起来非常相似：

    1
    2
    3
    4
        required string user_name       = 1;
        optional int64  favorite_number = 2;
        repeated string interests       = 3;
    }

Thrift和Protocol Buffers都有各自的代码生成工具，并支持各种编程语言。应用程序可以直接使用生成的代码完成Encode，Decode的工作。

Thrift的BinaryProtocal与CompactProtocol

  • BinaryProtocal

    需要59个字节。

  1. 每个字段有一个类型注视（是字符串，整数，列表等），并可以指定长度（字符串长度，列表的count）
  2. 与MessagePack最大的区别是没有字段名。

  • CompactProtocol

    只需要34字节。

  1. 通过将字段类型和标签号打包在一个字节中。
  2. 使用可变长度整数。 1337，不用一个字节中的全部8位都表示数值。使用两个字节编码，每个字节的最高位表示是否还有更多字节。
  3. 可变长度整数意味着，-64到63的数字可以用一个字节表示，-8192到8191之间用两个字节。

Protocol Buffer编码

只有一种编码模式。与CompactProtocol很类似。只用33个字节。

不同之处：

  1. 表示字段位置和类型的一个压缩的字节中的位数分配不同
  2. 表示数字的填充方式不同。例如1337的表示一个是最左，一个是最右。
  3. 表示列表的方式不同，Thrift是有列表type，而protocol buffer是用重复的field tag来表示列表或者数组
  4. 没有end of struct

一个细节，optional字段对于编码encode的结果没有任何影响（二进制中不会体现一个field是optional的）。optional的体现在于在Runtime 时后可以做检查，捕获错误。

字段标签和模式演化

如何保证修改模型时候，既保证向前又保证向后兼容呢？

可以根据之前的例子看出，每个字段的标签号码（1，2，3等），与它的类型整合在一个字节中。由此看出field tag对编码数据的含义至关重要。

  1. 不能随便改字段的标签，会导致现有的编码无效。保证这个原则，实现向后兼容。
  2. 可以添加新的字段，只需要用一个新的标签。如果老代码读到带有新标签的数据，那么会忽略。这样可以向前兼容。
  3. 新增字段不可以是required字段，或者没有默认值的字段，向后兼容。违反的结果，会让老数据无法被新代码读。
  4. 删除字段只可以删除可选字段，老代码读新数据时才不会出检查问题，向前兼容。

数据类型和模式演化

改变数据类型会如何？可能是可以做的，但是风险在于丢失精度或者数据截断。

  1. 例如一个32位整数变成一个64位的整数。新代码可以读老数据，因为可以用0填充缺失的位。如果是老代码读64位的数据，使用32位int存，则会截断。
  2. Protocol Buffer中没有数组或者列表。所以如果把单值的类型变成列表类型的，老代码读新数据，只会留下最后一个值。而新代码没什么问题。

Avro

另一种二进制编码格式。由于Thrift不适合Hadoop的用例，因此Avro在2009年作为Hadoop的子项目启动。

Avro也用模式来制定数据结构的编码。它有两种语言：一种是Avro IDL，用于人工编辑，一种是基于JSON的易于机器读。

基于Avro IDL的模式的例子：

1
2
3
4
5
record Person {
    string                userName;
    union { null, long }  favoriteNumber = null;
    array<string>         interests;
}

其等价JSON格式如下：

1
2
3
4
5
6
7
8
9
{
    "type": "record",
    "name": "Person",
    "fields": [
        {"name": "userName", "type": "string"},
        {"name": "favoriteNumber", "type": ["null", "long"], "default": null},
        {"name": "interests", "type": {"type": "array", "items": "string"}
    ] 
}

主要区别：

  1. 模式中没有标签号，是目前见过的所有编码中最紧凑的。
  2. 字节序列中也没有类型信息。只是连在一起的一些列值组成。字符串是长度加UTF-8的字节流，整数使用可变长度编码（与CompactProtocol相同）。但是并没有任何信息表示这些field是什么类型。

如何解析？
需要预先读区模式信息的数据，然后按照模式的顺序，遍历这些字段。

然后直接用模式中的字段信息来决定每个field到底是什么类型。

这意味着，读取数据的代码，必须使用当时写入数据是使用的模式，才可以正确还原数据。如果中间有任何不匹配，都无法解析。

Avro中的写模式和读模式

  • 写模式。encode时，使用的模式，可以将这个模式编译在应用中。
  • 读模式。decode时，应用代码依赖的模式，这个模式可能是在应用程序build过程中基于模式语言动态生成的。

Avro关键思想 ，写模式和读模式不一定需要完全一样，只需要兼容。当数据被Decode的时候，Avro的 Library通过对比查看写模式和读模式之间的差异，把数据从写模式转换成读模式，然后继续decode。Avro规范定义了这种解决方法的工作原理。

假如写模式和读模式的字段顺序不同，也没有关系，如果读的过程中遇到了只有在写模式中出现的字段，那可以忽略。如果在一个字段只在读模式中有，那么可以填充默认值。

Avro模式演化

  1. 只能添加或删除有默认值的字段。
  2. 如果添加一个没有默认值的字段，破坏了向后兼容性
  3. 如果删除一个没有默认值的字段，破坏了向前兼容性。
  4. null值的处理。

关键问题，写模式是什么？读模式如何直到某一个数据是用那个写模式编码的？

这个问题要取决于Avro使用的上下文：

  1. 有很多记录的大文件。
    Avro常见场景。尤其是Hadoop的上下文中。上百万的数据，都是用相同的模式编码。这种情况下，该文件的写入模式可以嵌入到文件的开头。Avro可以制定一个文件格式来做到这一点。
  2. 具有单独写入记录的数据库
    数据库中的记录，可能是在不同的时间点写入的。每个时间点可能使用不同的写入模式。最简单的发难是在每个编码记录的开始处，包含一个版本号，制定着写入模式的版本。在数据库的一个地方存储所有的写入模式列表。这样读取时可以直到数据的写入模式。Espresso就是这样工作的。
  3. 通过网络连接发送记录
    连接双方可以在建立连接时，协商模式的版本，然后在这个连接会话中使用这个模式。这也是Avro RPC的协议原理。

动态生成的模式

Avro的一个重要优点就是不包含任何标签号。

不包含标签号是好理由： 动态生成模式更友好。

关系型数据库，使用二进制方式，把内容转存到一个文件的例子。

  1. 根据关系模型，生成Avro模式。并使用这个模式编码，把数据库内容倒入Avro对象容器文件中。列名对应Avro的field
  2. 如果数据库的关系模型发生变化，则可以更新Avro的模式，使用新的Avro导出数据。不需要关注模式的改变，字段是通过名字来表识的，所以更新后的写模式仍然可以和老的读模式匹配。

相比之下，Thrift和Protocol Buffer都需要手动分配新的标签。而且还需要完成从数据库列名到新标签的映射。

代码生成和动态类型语言

  1. 静态类型语言
    Thrift和Protocol Buffer依赖于代码生成。定义了模式之后，可以跨语言使用模式。对于Java，C++等语言非常有用。可以转换成内存结构，并且支持IDE的类型检查。
  2. 动态语言（Javascript，Ruby，Python），因为没有编译时检查，代码生成没有什么意义。
  3. Avro为静态语言也提供了代码生成的工具，但是它也可以在在不生成代码的情况下使用。如果是一个嵌入了writer模式的对象容器文件，可以简单的使用Avro库打开，并用和JSON文件一样的方式查看。因为文件是字描述的。

模式的优点

  1. 模式语言简单。原理简单，使用更简单，广泛的编程语言支持。
  2. 比JSON，XML，CSV，更紧凑
  3. 模式有文档价值，不需要额外的手工维护的文档

数据流模式

数据库

向数据库中存储内容，就是在给未来的自己发送消息。

这种情况下，向后兼容是非常重要的。否则新代码无法读取存在数据库中以前写入的数据。

需要注意的一点是，老代码读区新代码写入的数据时，更新后又写会数据库，要当心不要丢失新数据格式的原来的信息。

将数据重写（迁移）到一个新的模式当然是可能的，但是在一个大数据集上执行是一个昂贵的事情，所以大多数数据库如果可能的话就避免它。

基于服务的数据流：REST与RPC

Web的方式，基于HTTP。

  1. 使用客户端（浏览器，移动应用，PC应用等）访问服务器数据。
  2. 使用服务器访问另一个服务器的Web服务。这样的应用构建方式最近叫做微服务。

微服务的关键设计目标是，通过使服务可独立部署和演化，让应用程序更易于更改和维护。这样每一个团队可以能够经常发布新的版本，而不必与其他团队协调。因此服务器和客户端之间的数据编码必须在不同版本的API之间兼容。

REST使一种HTTP服务的设计理念。SOAP基于XML，基于Web服务时，API被称为WSDL，支持代码生成。SOAP严重依赖工具，代码生成和IDE支持，与SOAP集成的成本很高。

RESTful的API更简单，格式如OpenAPI，Swagger。
由于互联网上存在广泛的安全威胁，REST的安全生态系统非常强大，从防火墙到OAUTH（身份验证/授权）

远程过程调用RPC的问题

看起来像是在使用本地方法。但是有缺陷需要解决：

  1. 网络请求不可预测。速度方面，网络失败，需要准备重试的逻辑。
  2. 可能超时，没有结果。无法知道发生了什么。
  3. 重试的时候，需要保证调用的方法有幂等性保证。
  4. 序列化时的问题，效率方面，编程语言方面的限制。

RPC发展

这种新一代的RPC框架更加明确的是，远程请求与本地函数调用不同。例如，Finagle和Rest.li 使用futures（promises）来封装可能失败的异步操作。Futures还可以简化需要并行发出多项服务的情况，并将其结果合并。 gRPC支持流，其中一个调用不仅包括一个请求和一个响应，还包括一系列的请求和响应。

使用二进制编码格式的自定义RPC协议可以实现比通用的JSON over REST更好的性能。但是，RESTful API还有其他一些显着的优点：对于实验和调试（只需使用Web浏览器或命令行工具curl，无需任何代码生成或软件安装即可向其请求），它是受支持的所有的主流编程语言和平台，还有大量可用的工具（服务器，缓存，负载平衡器，代理，防火墙，监控，调试工具，测试工具等）的生态系统。由于这些原因，REST似乎是公共API的主要风格。 RPC框架的主要重点在于同一组织拥有的服务之间的请求，通常在同一数据中心内。

RPC的数据编码和演化

假定所有的服务器都会先更新，其次是所有的客户端。只需要在请求上具有向后兼容性，并且对响应具有前向兼容性。

RPC方案中的向前向后兼容的解决方法，可他们在数据编码中使用的方法也有关。

异步消息传递，消息代理

中间件，可以低延迟的响应web请求。

优点：

  1. 如果接收方不可用，可以当作缓冲区，暂存消息，等恢复之后一起消费，实现HA。
  2. 可以自动重新发送消息到崩溃进程。防止丢消息。
  3. 结偶发送方和接收方，双方不需要知道对方的IP
  4. 支持广播，一条消息被多个人接收
  5. 子系统之间结偶

可以使用任何编码方式。只要兼容。

分布式Actor框架

并发编程模型。逻辑封装在Actor中。不直接操作线程。

由于每个Actor一次只能处理一条消息，因此不需要担心线程，每个Actor可以由框架独立调度。

分布式Actor框架中，编程模型被用来跨多节点进行scaling。位于不同节点之间的通讯可以使用encode decode的方式进行网络数据传输。

分布式Actor框架的实质是将消息代理（MQ等）和Actor编程模型集成到一个框架中。

三种流行的分布式Actor框架对于消息encoding的方式：

  • 默认情况下，Akka使用Java的内置序列化，不提供前向或后向兼容性。 但是，你可以用类似Protocol buffer的东西替代它，从而获得滚动升级的能力。
  • Orleans 默认使用不支持滚动升级部署的自定义数据编码格式; 要部署新版本的应用程序，您需要设置一个新的群集，将流量从旧群集迁移到新群集，然后关闭旧群集。 像Akka一样，可以使用自定义序列化插件。
  • 在Erlang OTP中，对记录模式进行更改是非常困难的（尽管系统具有许多为高可用性设计的功能）。 滚动升级是可能的，但需要仔细计划。 一个新的实验性的maps数据类型（2014年在Erlang R17中引入的类似于JSON的结构）可能使得这个数据类型在未来更容易。

发表于

Removal

remove some particular char from string

slow,fast two pointer

remove all leading/trailing/duplicated empty spaces from string

slow,fast two pointer, with handling special cases

De-duplication

slow,fast two pointer

Substring -> strstr

reversal

replacement

Advance

moving letters around(ABCD1234 => A1B2C3D4)

permutation(use DFS)

Decoding/Encoding

Longest substring that contains unique chars

Reg Matching

发表于

数据库只需要做两件事，1. 插入数据时候保存数据；2.之后读数据时，返回之前的结果。

数据库核心：数据结构

为了高效查找数据库中特定键的值，我们需要一个数据结构：索引（index）。索引是从主数据衍生的附加（additional）结构。这是存储系统中一个重要的权衡：精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度。

哈希索引

key-value 数据的索引。

最简单的索引策略，保存一个内存中的hashmap，把每一个key映射到特定的字节偏移量，这样就可以找到每一个key的位置。

这个理念是Bitcask（Riak中的默认索引引擎）的核心做法。只要所有key可以放入内存，只需要一次磁盘寻址，就可以把value加载到内存中。

压缩

所有的新的数据都以日志的样子追加到一个文件中，如何避免文件越来越大最后耗尽磁盘的空间？

  1. 压缩。将日志分解成一定的大小的段，当超过时候，就关闭它。后续的写入会写入新的段文件中。然后可以分别压缩这些段。这样的压缩意味着，在每一个段日志中丢弃重复的key，只保留最近的更新。
  2. 多个段一起压缩，合并。由于段日志在写入后不会再修改，那么可以合并几个段的日志，到一个新的文件中。旧的日志可以删除。

在这样的多段设计下，每个段都有自己的hashmap。查找过程就是一个段一个段的查询。由于有段合并，段的总数不会很多。

实现中的重要问题

  1. 文件格式
    CSV不是日志的最佳格式。更快更简单的是二进制格式，首字节存字符串长度，然后跟上原始字符串。
  2. 删除记录
    插入墓碑标记
  3. 崩溃恢复
    服务重启时，需要扫描所有的段来恢复hashmap，这样使得服务器重启变慢。Bitcask通过将每个hashmap的快照映射到磁盘，加速崩溃恢复。
  4. 部分写入的记录
    Bitcask采用了校验和，发现损坏部分就丢弃。
  5. 并发控制
    通常实现的选择只有一个写线程，简化了并发。而文件都是追加的写入，读并发更好。

为什么不原地更新？

  1. 顺序写比随机写性能更好。特别是在磁盘。
  2. 文件是追加和不可变的，崩溃恢复更简单。
  3. 合并段的操作可以避免文件出现碎片。

哈希索引的局限性

  1. 必须把key全部装入内存。即使在磁盘上维护hashmap，也很难保证高效的随机IO访问。处理哈希冲突也很复杂。
  2. 区间查询效率不高。只能逐一查询。

SSTables和LSM-Tree

之前的段文件只可以追加，并且不要求key有序。现在我们可以对段文件的格式做一个简单的改变：我们要求键值对的序列按键排序。这就是SSTables（Sorted String Tables）的数据格式。我们还要求同一个key只会出现在一个段中。

SSTables优点：

  1. 合并段更简单。就像merge sort一样。
  2. 内存中的hashmap索引是稀疏的。
    在文件中查找key时，不需要在内存中保存所有的key。例如查询handiwork时，不需要handiwork在hashmap中有可以。而知道handbag和handsome的偏移量时，因为key已经排序，可以从handbag开始扫描到handsome就可以确定handiwork在不在。
  3. 压缩时，可以利用稀疏索引，降低了IO带宽。

构建和维护SSTables

要解决排序问题。方法是，

  1. 在内存中保存一个排序结构，比如红黑树，AVL树。
  2. 在插入修改时候可以很快的响应。
  3. 可以顺序的读区它们。

存储引擎工作流程

  1. 写入时，将数据加入内存表中，可以是红黑树实现。
  2. 当内存中的红黑树大小超过阀值时，把它用SSTable的格式写入磁盘。
  3. 处理读请求时，先尝试查询内存表，如果miss就查询磁盘段文件s。
  4. 周期性的执行合并和压缩。丢弃被覆盖和删除的值。

用SSTable实现LSM-Tree（Log-structured Merge-Tree）

上面的算法时LevelDB和RocksDB使用的，用于嵌入到其他应用的key-value存储引擎。类似的存储引擎也用在了Cassandra和HBase中，这两个引擎都源于Google的BigTable论文。最初这个索引结构在早起的系统中被命名LSM-Tree。因此，基于合并和压缩的排序文件原理的存储引擎，通常都被称作LSM存储引擎。

全文搜索，Lucene是ElasticSearch和Solr的索引引擎。采用了类似的方法保存字典。全文索引复杂的多，但想法类似。

性能优化

  1. 查询不存在的key时，会从内存开始扫描到磁盘的最后一个段。解决方法是，Bloom Filter。
  2. 压缩合并的时机。分为大小分级和分层压缩两个方法。一个是小的SSTables被连续合并到大的旧的SSTables。另一个是key的范围分裂成多个更小的SSTables，旧数据被移动到单独的层级。

由于数据是按照排序存储，因此可以高效的执行区间查询。因为磁盘是顺序写入的，LSM-Tree的写入吞吐量可以非常高。

B-trees索引

应用最广泛的索引结构。和SSTable一样，B-tree保留按key排，也可以实现高效的范围查询。

B-tree将数据库分解成固定大小的块和页（4KB or more）。这种设计更接近底层硬件，因为磁盘也是固定大小的块的排列。

每个页，可以用地址标志，是磁盘地址，而不是内存。这样可以用这些页面引用构造一个树状页面进行索引。索引的根是一个页面，之后的查找根据地址，读取响应的页。

分支因子。

大多数数据库的索引适合3-4层的B-tree.因此不需要遍历非常深的页面层次即可找到所需的页。

B树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

使B-tree可靠

B-tree底层的基本操作是使用新数据覆盖磁盘的旧页。磁盘是覆盖扇区，对于SSD，擦除和重写的存储芯片块很大，情况更复杂。

页面溢出，需要分裂页时，也要覆盖其父页对更新后的两个子页的引用。属于复杂操作。在完成更新前发生崩溃，可能会产生孤儿页面。

崩溃恢复，使用redo Log。写数据之前先写日志。

并发控制。

优化B-tree

  1. 一些数据库不是用覆盖页，而是做复制。
  2. 保存key的缩略信息而不是完整的key，来节省空间。只需要提供足够的信息来描述key的起止范围。
  3. 页可以存在磁盘的任何位置。可能回有随机的IO，而不是连续的。有些B-tree尝试实现对B-tree进行布局，但是随着树的增长，这个顺序会越来越难维护。
  4. 添加额外指针。左到右的指针，加速遍历。

对比B-tree, LSM-tree

根据经验，LSM-Tree写入更快，而B-tree读更快。读取通常在LSM—Tree中较慢，因为要检查多个不同的数据结构和SSTables。

LSM-Tree优点

  1. LSM只写入一次数据（不考虑写放大（写入引起的压缩和合并）），而B-tree写入两次（一次redo log，一次数据本身）。
  2. LSM可以成熟比B-tree更大的吞吐量。有时具有较低的写放大，顺序写入速度快。
  3. 可以支持更好的压缩，文件比B-tree小很多。没有B-tree产生碎片的问题。

LSM-Tree缺点

  1. 响应延迟不确定，因为压缩和合并。
  2. 由于配置问题，会出现压缩跟不上写入速度的问题。来不及合并，直到磁盘空间不足。
  3. 事务支持不如B-tree

其他索引

在索引中存储值

索引中存储行或则行的具体位置（堆文件法）。将索引行直接存在索引中，聚集索引。MySQL的InnoDB存储引擎中，表的主键是聚集索引，二级索引引用主键。

多列索引

级联索引，通过将一列追加到另一列，将几个字段组合成一个键。只能从前到后匹配。B-tree和LSM-tree都无法高效的应对这种查询。

更常见的索引空间，R树。PostGIS使用PostgreSQL的广义搜索书索引实现了地理空间索引作为R树。

全文搜索和模糊索引

之前的搜索都是准确匹配，而不能应对类似的key的搜索，例如错误的拼写。

Lucene引擎支持在某个编辑距离内的模糊搜索。LevelDB中这个内存中的索引是一些key的稀疏集合。但在Lucene中，内存中的索引是key中的字符串序列的有限状态机，类似字典树。这个自动机可以转换成Leveshtein自动机，支持编辑距离内的搜索。

在内存中保存所有内容

内存数据库。例如Memcached，做缓存。数据在重启后可以恢复。

内存数据可以更快的原因，是因为它们可以避免使用写磁盘的格式对内存数据结构编码的开销。

提供了给予磁盘索引难以实现的数据结构，例如Redis中的优先级队列和集合。

可以使用反缓存的方法，当没有足够的内存时，将一部分不常用数据倒入磁盘，类似操作系统的虚拟内存。

将来的NVM（non-volatile memory）技术广泛的普及，也可能很大的改变存储引擎的设计。

事务处理OLTP与分析处理OLAP，

事务意味着允许客户端进行低延迟读区和写入，相比于只能周期性的运行的批处理作业。事务不一定具有ACID属性。

OLTP每次返回少量的数据，随机访问，低延迟要求。OLAP对大量数据访问，批量导入（ETL）或事件流，内部分析师，为决策提供支持。

数据仓库

数据仓库是一个单独的数据库，分析师可以在不影响OLTP的情况下，任意使用数据仓库。数据仓库包含公司所有OLTP数据库的只读副本。

单独使用数据仓库的优势在于数据仓库可以针对分析访问模式进行优化。本文前半部分讨论的索引模型只适合与OLTP而不适合做分析查询。

OLTP数据库和数据仓库的差异

数据仓库也支持SQL查询接口，但是和OLTP的实现差异很大。

一些数据库（SQL Server和SAP HANA）在同一产品中支持事务处理和数据仓库。然而，它们是两个独立的存储和查询引擎，只是通过一个SQL接口来访问。

一些商用的数据仓库，Teradata，Vertica，SAP HANA等很贵。还有开源的基于Hadoop的SQL项目，例如Apache Hive，Spark SQL，Cloudera Impala，Facebook Presto，Apache Tajo和Apache Drill. 其中一些是基于Google Dremel而构建的。

星型与雪花型分析模式

许多数据仓库都使用了星型模式，也称为维度建模。

这种模式的中心是一个所谓的事实表。事实表的每一行表示在特定时间发生的事件。

通常，事实被捕获为单独的事件，这样之后的分析具有很大的灵活性。

事实表中的列是属性，其他列可能会引用其他表的外键，成为维度表，这些维度代表事件的发生地点，时间，方式和原因。

名称星型模式来源于关系表可视化的适合，事实表位于中间，被一系列维度表包围。

该模型的一个变体成为雪花模型，其中维度进一步细分为子空间。例如，dimproduct表中的每一行可以再次向外引用品牌和类型的外键。这样更规范，但是更复杂。分析人员一般首选星型。

典型的数据仓库中，表都非常宽，事实表通常超过100列，甚至几百列。维度表也可能很宽。

列存储

主要关注事实表的海量数据问题，通常有万亿行、PB级别的数据。

虽然通常事实表超过100列，但是一般一次分析也只会访问其中的4，5列。如何高效的执行这中类型的查询？

OLTP系统中，数据库的存储都是面向行的。如果属性超过100列，那么需要把很多不需要的数据读入内存，然后丢弃。非常低效。

面向列存储，不是将一行的内容存在一起，而是把每一列的所有值存在一起。

列压缩

面向列的存储非常适合压缩。一直技术是位图编码。

每一个不同的值一个位图，位图的位数是行数。

Bigtable模型仍然主要是面向行的。

内存带宽和矢量化处理

除了减少需要从磁盘加载的数据量之外，列存储也有利于高效利用CPU的周期性。

列存储中的排序

列的存储如果是按照某个常见的顺序，例如date，就可以做类似于SSTables的索引机制。注意单独排序某列没用，需要正行排序。

数据仓库管理员需要基于经验选择合适的排序列，可以单列也可以是多列。这样查询优化器可以更高效。

另一个好处是可以进行压缩。可以进行游程编码，位图那样。

几种不同的排序

  1. C-Store的改进。用不同的方式存储相同的数据。使不同的排序查询都获益。也就是通过排序后的冗余数据加速。
  2. 列排序，类似于面向行的二级索引。区别是，列的索引中，存的是值而不是地址。

列存储与写操作

上述的优化，都是对读的优化，这会让写变得更困难。类似B-tree的就地更新的操作，对压缩列是不可能的。

一个方案是类似LSM-tree。先写入内存的排序数据结构，然后在一定的时候把内存的数据顺序的倒入磁盘，接着进行有可能的文件合并。这样查询的时候需要检查内存中的数据，和磁盘中的数据。这对于查询方是透明的。

聚合：数据立方体和物化视图

数据仓库不是一定要用列存储的。但是列存储因为查询分析更快，所以正在迅速普及。数据仓库另一个方面是物化聚合，就是把常用的查询物理存储化，缓存一些查询结果。

实现：物化视图。 物化视图的常见特例称为数据立方体或OLAP立方。它是按不同维度分组的聚合网格。以沿着每行或每列应用相同的汇总，并获得一个维度减少的汇总（按产品的销售额，无论日期，还是按日期销售，无论产品如何）。

缺点是数据立方体不具有查询原始数据的灵活性。因此，大多数数据仓库试图保留尽可能多的原始数据，并将聚合数据（如数据立方体）仅用作某些查询的性能提升。

发表于

语言的边界就是世界的边界

数据模型可能是软件开发中最重要的部分了，因为它们的影响如此深远：不仅仅影响着软件的编写方式，而且影响着我们的解题思路。

关系模型与文档模型

关系型 RDBMS

关系模型致力于将数据库本身的实现细节隐藏在更简洁的接口之后。数据被组织成表，每个关系都是Tuple的无序集合。

应用场景
你今天在网上看到的大部分内容依旧是由关系数据库来提供支持，无论是在线发布，讨论，社交网络，电子商务，游戏，软件即服务生产力应用程序等等内容。

需求Transaction

文档型 NoSQL

NoSQL数据库出现，有以下几个原因：

  1. 关系型数据库的扩展性不够，包括对非常大的数据集或者非常高的写入吞吐量。
  2. 开源免费。
  3. 关系模型不能很好的支持特殊性的查询操作。
  4. 渴望一种更具多动态性与表现力的数据模型

对象关系不匹配

如果数据存储在关系表中，那么需要一个笨拙的转换层，处于应用程序代码中的对象和表，行，列的数据库模型之间。模型之间的不连贯有时被称为阻抗不匹配（impedance mismatch)
像ActiveRecord和Hibernate这样的对象关系映射（object-relational mapping, ORM）框架可以减少这个转换层所需的样板代码的数量，但是它们不能完全隐藏这两个模型之间的差异

LinkedIn简历的例子，一对多

一个User和他相关的项目有一对多的关系。除了使用在其他表中加入UserID作为外键；使用有些SQL数据库支持的列的数据格式为JSON/XML，
它更适合用JSON来表示。因为，简单，它主要是一个自包含的文档。文档模型优势在于如果要读区一份简历，局部性更好。一次查询就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
{
  "user_id": 251,
  "first_name": "Bill",
  "last_name": "Gates",
  "summary": "Co-chair of the Bill & Melinda Gates... Active blogger.",
  "region_id": "us:91",
  "industry_id": 131,
  "photo_url": "/p/7/000/253/05b/308dd6e.jpg",
  "positions": [
    {
      "job_title": "Co-chair",
      "organization": "Bill & Melinda Gates Foundation"
    },
    {
      "job_title": "Co-founder, Chairman",
      "organization": "Microsoft"
    }
  ],
  "education": [
    {
      "school_name": "Harvard University",
      "start": 1973,
      "end": 1975
    },
    {
      "school_name": "Lakeside School, Seattle",
      "start": null,
      "end": null
    }
  ],
  "contact_info": {
    "blog": "http://thegatesnotes.com",
    "twitter": "http://twitter.com/BillGates"
  }
}

这样的结构意味着数据存在一对多的关系，也就是树状结构

多对一，多对多

建立例子中的region_id, industry_id,主要解决了重复问题。可以避免歧义，做本地化支持，更好的搜索，等等。消除重复，就是数据库范式化的核心思想。

IMS的层次模型

支持多对多的关系有些困难，而且不支持联结。

网络模型（network model） 已经淘汰

存指针，而不是外键。是一条开始于根（root）的路径。更改变得很困难。

关系模型（relational model）

关系模型使用外键访问，也类似一选择了一条访问路径，区别在于，这个是由查询优化器自动生产的，一般不必过多的考虑。

文档数据库的比较

在表示多对多关系时候，关系模型与文档模型并没有不同，都是有相关的一项唯一标示符引用。关系模型中叫外键，文档模型中叫文档引用。可以使用链接操作或者后续的操作来解析这个引用。

选哪个

要考虑多方面的差异，包括容错性，并发处理。

关于模型中的差异，以下，

哪个更简单

如果应用本身有着类似文档的结构（树状结构，一对多），那么使用NoSQL。

关系型模型，倾向于模型中数据的分解。他把文档结构分解成多个表，有可能使得模式更为笨重，增加代码复杂度。

文档模型的局限性有，不能直接读取文档中的嵌套项，而是要全部读取，例如读区用户id为251的用户中职位列表的第二个。

对于连接的支持，是否是问题取决于应用本身，需不需要这种场景。

对于高度关联的数据，文档模型可能不是很适合。

文档模式的灵活性

可以将任何key-value添加到文档数据库中，而且读取时，客户端也无法保证文档会包含那些字段。

文档模型是schema on read，
关系模型是schema on write。

读时模式类似于编程语言中的动态（运行时）类型检查，而写时模式类似于静态（编译时）类型检查。就像静态和动态类型检查的相对优点具有很大的争议性一样【22】，数据库中模式的强制性是一个具有争议的话题，一般来说没有正确或错误的答案。

允许某些原因下，集合中数据是异构的。

查询数据的局部性

局部性优势在于，需要同时访问文档中大部分内容时，加载一次文档即可。但如果每次只访问文档中的一小部分，有些浪费。

更改文档时，会重写整个文档，因此通常建议，文档应该尽量的小，并且避免写入时候增加文档大小。

NoSQL在为文档分配空间时候，会多分配一些，以防修改更新时候，空间不足，引起空间搬家的昂贵操作。

NoSQL与关系型数据库的结合

数据查询语言

SQL是一种声明式查询语言，与IMS和CODASYL命令式不同。

声明式查询语言不需要关心实现。由数据库查询引擎来优化实现。可以在不改变查询语句的情况下提高性能。可以利用并行执行的优化。

Web中的声明式查询就是CSS，比Javascript的命令式查询要好。

MapReduce查询 介于声明式和命令式之间

一些NoSQL数据存储（包括MongoDB和CouchDB）支持有限形式的MapReduce，作为在多个文档中执行只读查询的机制。

查询的逻辑用代码片断来表示，这些代码片段会被处理框架重复性调用。它基于map（也称为collect）和reduce（也称为fold或inject）函数，两个函数存在于许多函数式编程语言中。

map和reduce函数在功能上有所限制：它们必须是纯函数，这意味着它们只使用传递给它们的数据作为输入，它们不能执行额外的数据库查询，也不能有任何副作用。这些限制允许数据库以任何顺序运行任何功能，并在失败时重新运行它们。然而，map和reduce函数仍然是强大的：它们可以解析字符串，调用库函数，执行计算等等。

MapReduce是一个相当底层的编程模型，用于计算机集群上的分布式执行。像SQL这样的更高级的查询语言可以用一系列的MapReduce操作来实现（见第10章），但是也有很多不使用MapReduce的分布式SQL实现。请注意，SQL中没有任何内容限制它在单个机器上运行，而MapReduce在分布式查询执行上没有垄断权。

图状数据模型

解决复杂的多对多关系。

社交图谱

顶点是人，边指示哪些人彼此认识。

网络图谱

顶点是网页，边缘表示指向其他页面的HTML链接。

公路或铁路网络

顶点是交叉路口，边线代表它们之间的道路或铁路线。

图的存储，就是存定点和边。

  1. 任何顶点都可以有一条边连接到任何其他顶点。没有模式限制哪种事物可不可以关联。
  2. 给定任何顶点，可以高效地找到它的入边和出边，从而遍历图，即沿着一系列顶点的路径前后移动。（这就是为什么例2-2在tail_vertex和head_vertex列上都有索引的原因。）
  3. 通过对不同类型的关系使用不同的标签，可以在一个图中存储几种不同的信息，同时仍然保持一个清晰的数据模型。

这些特性让建模很灵活。有利于演化：添加应用功能时，容易扩展用，更能应对变化，使用合适的的数据结构。

Cypher查询语言

Neo4j图形数据库

SQL的图查询

与Cypher比显得笨拙

三元存储与SPARQL

所有信息都是三个部分存储（主体，谓语，客体）。

RDF数据模型

类似XML，更冗长。 不区分属性和边。

有工具支持生成RDF格式的数据模型。

SPARQL查询语言

采用RDF数据模型的三元存储查询语言。类似一次性SELECT操作完成。

Datalog基础

比较老，适合处理复杂数据。每次实现一块。