基本概念

分布式是什么

分布式系统是多个计算机, 通过网络连接, 合作来提供一些服务.

用于连接物理上分隔的机器, 允许两台机器之间进行共享, 以便合作.
通过并行提高性能.
提升容错能力.
利用物理上的隔离获得安全性. 不同功能部署在不同的机器, 提升安全性.

历史背景

分布式系统始于局域网(1980s), 当时的主流应用是DNS email
数据中心, 大型网站的发展(1990s), 搜索网站, 购物网站的发展.
云计算的出现加速了发展(2000s), 大型公司将业务迁移到云计算.
当前, 非常活跃 :)

分布式系统中的挑战

分布式系统中很多并行的部分,
分布式系统必须处理故障部分, 这些机器中的一部分可能会宕机, 但其他机器并不会停下来, 可能会分担故障机器的一些负载. 但是有时并不是发生故障, 而是网络出现问题, 这时两部分机器会继续计算和分担以为故障的那部分负载, 这就是脑裂, 这让设计分布式系统协议变得复杂.
实现整体系统的吞吐量随着机器的增加而增加

MapReduce

论文地址

是由Google的两位工程师发表的论文, 由于搜索引擎需要互联网页面的反向索引, 以便用户查询.
而这些计算需要跑好几个小时, 处理TB级别的数据, 然后发现其他的Google工程师也需要这样的应用, 计算他们自己的数据, 他们意识到编写这样的应用程序是比较困难的, 所以他们想要让非专业人士编写分布式应用变得容易.
实现的方式是让非专业人员编写 Map 函数和 Reduce 函数, 这些函数是函数式和无状态的. 然后MapReduce处理所有有关分布式的内容. 将安排程序在多台机器上运行, 并处理负载均衡. 编写Map 和 Reduce 的工程师无需关注这些.

假设现在有三个文件F1, F2, F3. 我们需要统计不同文件中各词出现的次数.
不同的文件可以同时执行 Map 函数, 因为文件之间没有相互依赖, 可以分布在不同的机器上执行.
然后将执行的结果进行 Reduce 汇总结果. Reduce 也是对某一维度进行Reduce 所以也能分布到不同的主机上进行执行. 其中从获取不同MAP结果的这个过程叫 Shuffle. 也是这些操作中最昂贵的部分.

Map Reduce Over View

在这个过程中, 如果某台机器在一定时间内没有响应 Master 下发的任务, 那么将会安排另一个 Worker 执行相同的任务. Map 函数能运行两次. 也是函数式方程的要求, 没有副作用.

Storage System

存储系统为什么重要

存储系统是容错系统运行的基石. 在此基础上, 可以使应用程序无状态化, 持久状态都存储在存储系统中. 简化了应用程序的设计.

存储系统为什么难

因为我们想要高性能, 这意味着必须要跨服务对数据进行分片(存储在多台服务器中). 但是拥有多台机器的同时, 某些机器将可能会宕机, 这意味着需要容错设计, 存储系统一般使用复制数据到多个磁盘继续规避. 但数据在多个磁盘的同时, 就会有数据的同步问题. 为了解决同步的问题, 就需要一些持久性协议. 需要发送一些消息进行同步, 这样又会导致性能下降.

所以大部分设计在: 容错, 复制性能, 一致性之间平衡.

一致性

理想中的一致性是指机器的行为就像单一系统一样, 但是并发性, 和错误让这种设计很难实现.

并发

例如, 当前有4个请求 C1 C2 C3 C4, C1 C2 请求同时写入X 但是, 请求写入的值分别为1,2. C3 C4请求想要读取x, 那么针对C3 返回什么值比较合适, 1 还是 2. 答案是 1和2都是可以, 但是不能是1 和 2 之外的值.C4 的返回值应该要与C3 相同.

错误

假如我们将数据复制在两台服务器 S1, S2 各自的磁盘中, 当发起 C1, C2写入请求时, 两个请求都能对S1, S2 进行写入, 那么这时C3请求获得值是: 1或者2, 对于随后请求的C4: 也可能是 1或者2
所以需要某些协议进行同步这些写入.

GFS

论文地址
GFS 是为了 MapReduce设计的存储系统. 特点是大, 有着大的数据集. 快, 自动分片到不同的磁盘. 全局使用, 所有应用看到的是同样的文件系统. 容错能力, 自动容错.
不过GFS也有缺陷, Master是单节点, 容易有单点故障. 存在某些不一致.

设计

应用向 Master 查询数据所在区块. 然后根据返回的区块信息去对应的GFS chunk server 读取.

Master

拥有文件名到块句柄数组的映射, 信息存储在内存中, 所以能很快的响应.

对每个块句柄, 包含一些额外的数据: 比如版本号, 拥有该块句柄副本的服务列表(并且其中有主节点和从节点), 还有租约时间(lease time).

除此之外还有日志和检查点. 日志主要存储了文件变化信息, 例如创建新文件, 文件映射变化等操作. 存放在稳定的存储中.

master 在回应用户请求前, 会先将变化写入日志中, 这样当master出现故障或崩溃. 可以通过重放日志来重建内部状态. 这样返回给客户端也是一致的. 基于这种情况, 文件名和块句柄的映射可以不用额外存储, 通过日志就能重建. 但是需要记住每个块最新的版本号, 否则无法区分块句柄最新的版本号是什么(因为最新的chunk server可能挂了).

读取和写入

读取

应用携带要读取的文件名加上偏移量向master请求文件所在的服务器地址列表/偏移量(比如文件中的第几个byte)所在数据的块句柄/还有版本号.
应用收到这些信息后将会缓存在本地, 向最近的一个chunk server 发送读取文件的请求.
chunk server检查应用使用的版本是否有问题(避免读取到旧的数据), 没问题就发送数据给应用.

写入

Write Control and Data Flow
写入的大部分所在reduce执行完成后, 将结果追加到GFS文件系统中, 而不是进行修改.

客户端先与Master进行交互, 以确定要将数据写入到何处.
服务端通过文件名查询相关的块句柄, 查询相关的服务器列表, 但此时有两种情况. 存储块的服务器列表是否已经划分主从节点. 如果是第一次访问, 服务器列表还没有选出主从节点, Master将增加版本号, 并保存到磁盘中, 并随机选取一个作为主节点, 主从节点将使用这个版本号组成复制组, 也会将版本号保存在磁盘中, 并商定租约时间(lease time). 最后Master 将主节点, 从节点列表, 版本信息返回给客户端.
客户端将数据发送到最近的一个节点中, 最近一个节点将这些数据通过网络管道发往其他节点.当数据被推送到所有的服务器时, 进入下一步. 这时服务器还不会进行存储.
这一步,客户端会向主节点发送消息, 比如一个append消息. 主节点将会检查版本号是否相同, 租约时间是否有效. 因为如果租约无效, 可能有另一个主节点. 两项检查完成后会选择一个offset进行写入.
主节点会通知从节点写入的偏移位置是多少.
从节点告知主节点写入完成
主节点响应客户端告知写入完成, 如果任意一个从节点写入失败了, 那么主节点将会告知客户端写入失败.

当写入失败时, 客户端可能会重新发起一次请求, 此时主节点将会使用新的offset

一致性问题

假如现在有三台服务器, 分别为P, S1, S2. 当前的版本号为10.
当客户端准备获取数据, 并已从master请求到相关信息缓存了. 此时S2与P, S1出现网络问题, 但与客户端的网络正常. master 此时给P 和 S1 发送的新的版本号, 但是 S2 无法同步. 此时客户端使用旧的版本号还能从S2上读取数据, 但是文件的最新版本号已经增加了.

不同场景下, 对于一致性的要求是不一样的.

主备应用程序总结

容错能力

主要处理的错误是Fail-stop, 是在基础设施故障, 或者计算机组件不能很好的工作. 使计算组停止运行.
逻辑错误, 配置错误, 无法处理伪造的错误信息. 这些错误主备应用程序无法处理.

主要挑战

如果错误发生在主节点, 那么从节点可能会假设主节点已经失效. 所以需要某些方法避免陷入两个主节点的情况—脑裂
如何保持主备节点同步, 当主节点故障时, 从节点能直接从主节点故障的地方开始. 这要求从节点总是最新的. 以便操作能继续进行.这意味着我们在主备节点需要按照正确的顺序进行变更, 要避免非决定论(non-determinism)就是在主节点上的操作, 在从节点中也有相同的效果.
故障转移过程中出现的情况.

状态转移复制

在主节点与客户端节点通信的过程中, 每隔一段时间有个检查点. 检查点将状态备份给从节点.或是在响应客户端之前将状态备份给从节点.

复制状态机(RSM)

将客户端发给主节点的操作, 同时发送至从节点, 从节点执行完成后, 向主节点进行确认. 主节点再返回至客户端.

什么级别的复制

程序级别的复制( GFS 中的文件追加)
机器级别的复制, 因为系统以及程序的运行都是基于X86的指令, 如果在这个级别, 无需修改系统和程序就能做到主从节点容错. 不一定要使用物理主机, 使用虚拟机即可.

VMware的容错方案

论文地址

通过虚拟机的方式, 使复制对应用程序透明. 无需设计主备复制的方式. 使用这种方式, 给客户端的直观感受是一台主机.
但是这时单核主机的解决方案, 所以一台计算机上的多个程序或多个线程不能并行运行.

Vm-FT是将自己与虚拟化技术融合的一层技术, 处于虚拟机与实体硬件之间. 当物理机发出中断时, 先被VM-FT捕获, VM-FT可以选择何时传递给虚拟机. 所以VM-FT不仅会吧发送的中断发送给虚拟机, 还能通过日志通道发送到备份的机器上的VM-FT. 备份机器上的虚拟机也会执行相同的操作, 也可能会发送相关的网络包, 但是是在虚拟机上, 发送的动作也会被VM-FT捕获, 而VM-FT知道自己是备份机器, 所以会忽略这些操作, 并不会发送真实的网络包.
除此之外, 主备机器都将使用同一个网络存储节点.
当主备出现通信失败时, 将会在存储节点争夺(test-and-set)一个信号量, 初始值为0, 以原子的方式进行更新. 当其中一台设置成功时, 另一台将会自己是第二台更新的, 并且终结自己. 此时恢复成只有一台的情况. 恢复备份节点是通过人工的方式.

虽然VM-FT的目标是有着完全一样的状态, 但是会有差异来源.例如不确定的指令(比如获取当前时间, 主备执行的时间不同, 获取的数值也不同), 或者中断的时机不一致. 处理不确定的指令时, 会将指令的结果一并传输.

主节点仅在收到备份节点的响应后才能向客户端发送结果, 如果备份节点没有回应, 那么将会超时. 客户端也许会向备份节点发情请求.

Raft

论文地址

之前提及协议的问题

前几个提到的分布式方案的主节点都是单个节点, 是为了避免脑裂. 但是会造成单点故障. 但是可能对于这些系统不是问题.

为什么不通过复制会产生单点故障的主机, 进行避免.我们通过(test-and-set)服务进行举例.

如上图所示, S1, S2为(test-and-set)服务, C1向S1, S2进行请求. 确定C1是主节点.
有一种可能S2是出现故障,宕机了, 所以C1对S2的请求失败了. 但是S1的请求成功过返回了, 此时C1确认成为新的主节点.
但是如果S2是因为网络分区的原因, 导致C1访问不了S2. 但是却正确更新了S1. 此时C2也进行了访问. 成功更新了S2. 所以整个系统发生了脑裂.

是因为C1在此时无法区分S2究竟是宕机了, 还是网络问题.
而这是Raft或是其他协议的基础: 多数原则.
也就是得到大部分的服务响应, 那就是最终结果. 例如有服务S1, S2, S3. C1 的请求得到了 S1, S2的响应,那么就认为请求是成功的.

如果你想能够容忍f个节点宕机, 那么就要部署2f+1的节点.

大概15年前提出了两种协议: Paxos, View-Stamped replication.
在2014年时提出了: Raft

如何使用Raft复制状态机(RSM)

当你在Raft的基础上构建K/V服务时, Raft Leader在收到GET/PUT请求时, 会先交给Raft模块, 追加到日志的末尾.Raft与其他服务器进行交互, 复制这个日志. 其他服务收到这个操作时, 也将操作追加到日志中. 并提交响应. 最后更新到键值服务模块. 然后向客户端响应. 更新完成.

如果这时, 作为Leader的那台主机宕机了, 那么其他从节点,将会选举出新的Leader.
Leader 将会有多个, 管理不同的分片.

Leader在下一次与follower进行同步日志是, 还将进行确认上一次同步的日志已经写入K/V服务中, 此时follower也将会把上一次同步的内容写入K/V服务中.

为什么信息要存在日志中:
要能够重传. 日志能够维护原有的顺序. 因为任意一个都可能会崩溃所以需要持久化. 需要一些空间去做试探性的提交. 重要的一点是, 日志在所有主机上都是相同的.

日志大概会存储对K/V 数据库执行的指令, 还有所处哪个Leader的term信息.

Leader 的选举

Leader 会定期的发送心跳, 表明自己还将是Leader. 心跳包含, 我的日志长度, 我的最后一项是什么.follower 收到心跳时, 将会重置选举时间.

当follower F1 到达选举时间时, 将会提升自己的term编号. 之后将会联系其他的follower, 例如F2 , 如果联系上了, 那么会获得F2的选票, 此时F1 成为了新的Leader并且更新了term.

假如旧的领导者此时联系上了, 并且向新的领导者发送请求,要求同步.将会被拒绝并返回最新的termID.旧的领导发现term的ID大于自己的ID, 将会变为追随者.

但是可能会遇到一个问题: 分裂选举(split vote)
当F1到达选举时间时, F2 也可能同时到达选举时间. 所以都将票投给自己了. 没有人能当选Leader直至选举过期. 所以为了避免这个情况. 选举超时的时间是随机的.(选择150ms ~ 300ms内的时间)

选举超时比心跳快的话, 会丢失数据(一条?). 所以选举超时时间需要比网络超时, 一些心跳久一点. 至少等待大概3~4次RPC的时间. 有时间去重试RPC. 再增加一些随机值.避免同时选举. 但是时间久了就表示系统要停止服务的时间延长. 所以又要使停机时间短. 实验室的到的时间是在1秒内回复都挺不错的.

选举时每位投票者,包括选举人投给自己. 都需要记录自己将票投给了谁. 因为在此过程中可能会失败. 以防在恢复时, 忘记了自己投过票, 重新进行投票.并且一次选举期间只能投票一次, 不能改变投票记录.

日志可能会产生分歧(Logs may diverge)

假设我们现在有三台服务S1,S2,S3. 目前存储的日志是term ID为3时存储的.
然后此时S1已将新数据写入索引12, 准备向其他节点广播时崩溃了.

有可能S1作为从节点在term3时崩溃, S2又在term4时崩溃, S3 被选为term5的主节点.

所以日志会有各种各样的分歧.

也有可能会出现上图的情况, 那么现在,对于A-F节点来说. 哪些节点会被拒绝, 哪些会被接受, 哪些会视情况而定.

如果d当选了Leader,那么term7将会被强制同步到其他节点.
如果d宕机了,c当选,那么term7的记录将会被丢失.
term2因为其他节点都没有, 会被term4覆盖.

此外如果途中a~f进行选举,那么只有acd可能成为leader.
如果选举过程中follower发现自身日志最后结尾的term版本比候选者高,那么将会告诉候选者,我的term比你高, 你应该变回follower, 并拒绝投票.

我的问题是, 当一个有副作用的请求, 被推送至Leader时, 此时已经完成folloer的复制, 但是这时候Leader宕机了, 新选举出的Leader是否会进行执行这个操作, 那是否客户端重复执行后, 会导致数据错误,执行两次?或者每次客户端的操作需要带上term进行复查,或者是有id进行去重?

Leader 选举的条件:

获得大多数的选票
要有最新的数据

Log Catch Up

持久化

raft 回复

在节点崩溃后, Raft 怎么进行恢复
策略一: 重新加入, 之前的记录全部都清除, 通过其他节点传来的日志进行重放操作, 但是因为需要重放系统运行以来所有的操作, 恢复将会变得比较缓慢.
策略二: 使用自身持久化的状态进行重建后, 加入分布式系统.
需要持久化的信息: 投票给了谁/当前term(前两者确定了每次选举选票的唯一性)和已有日志

服务恢复

节点奔溃后, 服务怎么恢复.

重放日志重建状态. 和上一节一样.
使用快照, 这样可以对日志进行裁剪(缩短日志的长度), 比如服务快照了到i索引的日志, 那么可以通知raft可以删除0到i索引的日志

什么是线性一致性

线性一致性规定了 put 和 get 操作可以返回的值.

整体顺序
实时匹配
读取操作返回最后一次写入.

能妥否通过历史记录, 整理成一个整体顺序, 即使这些操作是并发执行的.

ZOOKEEPER

复制状态机

在内网中一次网络请求响应时间大概是1ms, 在3台主机的情况下, Leader 只要获得其中一个follower的响应, 就能被确认.
然后将数据写入持久化存储所需的时间大概是2ms, 所以leader和其中一个follower写入总耗时为2ms.
所以当一个请求到响应需要耗时5ms, 那么一秒钟大约能响应(1000ms/5ms = 200)

zookeeper

上图中X轴表示的是, 所有请求中, 读取请求的百分比. y轴表示的是每秒操作数.
从图中我们可以看到, 当所有都为写操作时, 3台机器的情况下.每秒能接受21000的写入请求.
而当机器增多的情况下, 反而每秒写入的性能下降, 这是因为领导者需要和更多的机器进行通信. 当然如果和单台机器进行比较, 那么肯定会超过21K的每秒写入.

那么设计者是怎么做到的, 主要是两个关键想法:

所有请求是异步的, 或者说客户端可以一次向Zookeeper提交多个操作, 然后领导者将多个操作一次写入
对读操作做了一些特殊的操作, 允许读取在任何一台服务器处理

线性一致性(这节课又重复了一遍)

≈行为像一台机器

即使操作实际上同时进行, 可以按照整体顺序进行排序
顺序与实际时间顺序吻合
读取操作返回最后一次写入

zookeeper 没有提供线性一致性, 改变了定义. 所以zookeeper 看起来不会像单台机器.

线性化的写入
但是没有读取的线性一致性, 提供了两种保证:

请求的FIFO: 当客户端发起两个请求, 第二个请求的响应总是在第一个后边
读取: 可以看到本客户端最后的一次写入. 其他客户端也许会看到旧的数据, 但是与最新数据不会差太多, 相同的客户端重复读取数据, 不会得到比之前读取到的更旧的数据.

zookeeper的客户端会运行一个循环,尝试获取一个或者锁住文件, 其他的客户端在锁住的情况下将会进行自旋, 当拥有锁的调用release之后, 其他客户端将会获得通知. 并重新开始竞争.

一个更好的锁
所有想要获取锁的客户端, 按照链式的方式监听前一个客户端的锁文件, 例如1编号的客户端,监听0客户端的文件, 当0客户端释放文件时,1将获得通知.

称为 tick lock

zlock

当锁的持有者失效了, 那么就当是释放锁了
使用案例:

用于leader选举
“soft” lock 发生两次是可以接受的

实现状态复制

运行所有的操作在Raft/Paxos之上
使用配置服务器, 并进行主备复制

链式复制

在链式复制的模式中, 服务器将会以链式的方式进行传递复制, 客户端需要进行写入操作时, 将会请求head服务器, 然后head服务器将会传递给下一个服务器, 当下一个服务器完成写入时,也将传递给下一个,直至尾部(tail)写入完成, 由尾部节点对客户端进行写入确认

客户端发出读取操作时, 将会请求尾部节点. 这样隐含保持了一致性.

崩溃的情况

head崩溃
直接将head进行剔除,并使用配置服务器进行更新配置, 将S2以后的升级为新的链,并以S2作为头部.
中间节点崩溃了, 配置服务器将会通知前后节点, 中间的节点崩溃了, 所以需要形成新的链. 上一个节点需要将最近的数据同步至,崩溃节点的下一个节点.
尾部崩溃, 直接去除尾部,客户端需要从配置服务器获取最新的尾部节点ip. 客户端将会重试. 获取之前操作的结果.

增加新节点

增加新节点时, 将尾部的节点信息拷贝至新节点. 同时旧的尾部节点需要记录开始复制为止,新尾部还未同步的内容. 当前面旧日志完成复制后, 新尾部向旧尾部进行请求复制开始之后的新的内容. 旧尾部将还未同步内容发送至新尾部, 此时客户端向旧尾部的请求将被拒绝,并被告知有新的尾部, 但在此时, 新尾部是不能处理请求的, 当所有内容同步完毕后才能进行.

链式复制与Raft的比较

客户端的请求分布到 Head 节点和 Tail 节点
头部只需要发送一次复制请求, 发送的信息更少
读取操作仅由尾部处理
简单的崩溃处理

有一个故障就需要重新配置

并行读取的扩展

将要存储的信息分布到不同的链中, 例如将数据分为三份, 每份存储在不同的链中.

这样每个节点都有头和尾部, 每台服务器都能利用上.
这样也能达到zookeeper的读取性能上线
同时兼有扩展和线性一致性的能力

客户端怎么决定从哪个链中读取: 论文中没有说明这个点, 可能是从配置服务器中读取的.
上述方案可能导致某一条链路,

Frangipani

Frangipani是一种分布式的文件存储系统, 相对于传统的NFS(网络存储系统), Frangipani是运行在客户机上, 通过客户机之间的通信虚拟化出共享的文件系统.

Frangipani 实现中的挑战

缓存一致性, 不同的机器修改可见
当两个工作站想要在同一个文件夹进行增加文件时, 至少一个修改不会覆盖另一个. 操作需要是原子性的
如何从崩溃中恢复

缓存一致性

使用一个锁服务器, 锁服务器会存储将当前某个文件被哪台工作站占有了的列表, 工作站中同样也会存储自身拥有哪些文件的锁, 以及当前的状态是繁忙(busy)还是空闲(idle).
同时有一条规则: 去缓存一个文件前, 必须要有这个锁

Frangipani 协议

当W1 工作站向LS 服务器请求f文件的锁时, LS 将会在表中增加一条记录,说明W1 已经获取了f文件的锁, W1将会在本地的锁的记录上增加f文件的记录, 然后w1就能进行修改文件. 当一次修改完成后, W1中存储的锁的状态将会从busy变为idle, 当需要写入f时,因为本地已经持有锁了,所以不会像LS进行请求. W2 需要获取f文件的锁时, 向LS请求. LS发现已经交给W1了, 所以向W1通知请求收回锁, W1 收到通知后,将会把变化写入 Petal ,当写入完成后, 通知LS可以收回锁了. 此时LS 再响应W2的获取锁的请求, 在这期间W2将会处于等待请求.

原子性

对于每一个缓存需要创建一个inode锁, 并将记录写入inode, 并在文件系统中添加条目f 已经分配的 inode number, 因为需要原子的方式进行更新,所以要对分配的inode 进行加锁,在释放inode的锁时, 如果观察到LS要求释放 f 文件的锁, 那么此时将会将缓存刷新到Petal, 完成后将向LS发送已释放锁的消息

崩溃复原 - 预写式日志(write ahed log)

在更新Petal之前先更新log
然后工作站应用更新

崩溃的情况

在写入日志之前崩溃 => 将会丢失日志
在写日志之后崩溃 => ls 服务器等待W1的锁租期到期, 然后启动demon恢复
写入日志后崩溃 => 没听清

重放日志过程中的注意点

因为每台工作站中都会保存操作日志, 假设如下情况:
当w1 删除了文件f, 而 W2 在 W1 删除之后创建了文件f, 此后W1奔溃, W3demon进行复原W1的操作, 此时直接复原将可能会将w2中创建的文件f删除.
所以为了避免执行时候的覆盖, 且由于每次操作inode都需要获取对应的锁, 所以对于每个inode都有个版本号, 所以在进行恢复的时候, 需要进行对比当前的inode的版本号和log中的版本号, 如果log中的版本号小于inode中的那么将不会执行操作.

Frangipani总结

讨论了缓存一致性
分布式锁, 锁服务器, 租期, 授予, 请求, 撤销
分布式恢复

分布式事务

主要遵循: ACID
A: 原子性
C:一致性
I: 事务相互隔离
D: 持久性

Isolation: 可串形化

意思是当两个事务同时请求执行, 但是最终的执行结果必有先后.

并发控制

悲观解决方案 (引入锁)
乐观方案 (无锁): 如果不是串行化, 那么将会被终止

two-phase locking ( lock per record)

事务在使用之前都需要一个锁
事务获得的锁,只有在结束(提交或者终止)才能释放

怎么检测死锁

超时一段时间, 就认为有死锁, 终止任意一个
分布式系统中实时构建事务等待图(wait-for-graph), 探针节点之间是否有一个循环.

two-phase commit

Spanner

支持广域事务(wide-area transactions)
读写事务, 由两阶段加锁和两阶段提交实现使用Paxos算法
只读事务, 可以由任意数据中心处理: snapshot Isolation(快照隔离), 依赖时钟同步(synchronized clocks)

挑战

读取的本地分片需要有最新的写入
事务支持跨分片
只读和读写事务必须都是串行化的

读写事务

只读事务

从本地的分片读取: 快, 不过也带来了问题, 怎么保持一致性或串行化
没有锁, 可被读写锁阻塞
没有两阶段提交

执行本地副本时, 怎么获得正确性

事务是可串行化的: 只读事务介于读写事务之间, 不能只看到读写事务的一部分(不能交错执行)
外部一致性(事务级别): 如果事务T1再T2之前提交, 那么T2必须要能看见T1的写入, 这样的要求与线性一致性有点相似

一个不好的方案 ( Read latest commited value)

由于只读事务会被阻塞, 而又总是读取最新提交的数据, 这样违背了一致性

快照隔离(snapshot Isolation)

为了避免上述情况的出现, Spanner使用了快照隔离. 这是一个数据库中的概念.
为每个事务分配一个时间戳:
对于读写事务, 是事务提交时
对于只读事务, 是事务开始时
然后按照时间戳的顺序执行所有事务
每个replica 保存多个键值, 以及他们的时间戳, 例如: 当时间戳为10时X的值为多少, 当时间戳为20时x的值为多少.
所以有时候, 这被称之为多版本数据库或者多版本存储, 对于每次更新,保存数据项的一个版本, 这样就能回溯

但因为只读是在 Paxos 的本地 Replica 中进行, 那么可能 Replica 中还未有关于该时间戳之前的数据,
Spanner 使用称为”Safe time”的方案, Paxos 或者 Raft 也使用时间戳标记发送的数据, 在此机制下, 如果你想要读取15时间戳下的数据, 那么你就得等待时间戳大于15的写入, 也需要等待已准备好但是还未提交的事务.

时钟

由于使用了时间戳, 那么机器的时间将是重要的.
对只读事务的影响将是最大的
当 Replice 机器的时间戳过大时, 那么可能会导致只读事务因为没有后续时间戳的读写事务导致不能返回, 等待时间过长
如果时间戳过小, 将会读取到之前事务的值, 破坏一致性.(例如原先要读取时间戳为15的但是读取到了7的, 而在10时正好有一次提交)

时钟同步( Clock synchronized)

时间同步是困难的, 因为会发生时间漂移, 使用原子钟可以解决

使用延迟执行

因为每台机器时间不准的原因, 当我们请求时间时, 会返回一个时间戳和大概误差的时间, 例如, 10 ± 5, 那么获得的时间范围就是[5, 15], 然后事务的开始时间, 就去时间间隔的最后部分, 也就是15, 也就肯定是大于或者等于真实的时间. 这个时间会被作为,只读事务的开始时间或者读写事务的提交时间. 并且提交的动作也会被延迟到, 15之后进行.

FaRM

配置

将数据库的存储放置在内存中,

事务的操作需要用到OID(对象ID)

内核旁路(kernel-bypass)

使用RDMA技术, 将网卡的发送接收队列,直接与FaRM应用的内存进行映射, 绕过操作系统的限制.

应用线程将会遍历相关的接受队列, 从其中获取RDMA类型的包, 只读目标机器内存的叫one-side RDMA, 另一种写入的称之为 write RDMA. 如果成功将会收到网卡的反馈

如何以事务的方式使用RDMA

目前为止学习的事务协议, 两阶段提交, 等. 这些协议都是需要服务端参与的. 比如需要获取锁, 或者运行一些验证步骤, 意味着你必须要将代码运行在服务器上.
而RDMA 没有提供在服务器上运行代码的能力. 所以论文作者需要设计一种协议,允许实现两阶段提交和事务, 减少或者禁止服务端参与.

解决方案: 使用乐观控制并发

在只读情况下不需要获取锁, 但是还是需要一些机制(版本号)来检验获取的值是新值还是旧值.
写入时需要有一个验证步骤, 检查写入冲突, 要写入的对象是否已经被修改了, 如果已经被修改,那么就终止事务. 否则正常提交.

严格并发的正确性

不会得到X = 1, Y =1的结果.
因为当T2进行提交时, 需要校验Y变量的情况, 此时T1还未提交完成, Y上有持有锁的标记. 所以此时T2会自动终止

FaRM 总结

很少的冲突
需要足够的内存
在一个数据中心使用
需要特定硬件 UPS 和支持 RDMA 的网卡

Spark

相比Hadoop更加广泛的支持. Spark是基于内存计算的, 支持多MapReduce

编程模型: RDD (resilient distributed dataset) ( 更新一点的叫 DataFrame )

在Spark中数据是以RDD的方式进行操作的, 作用于 DDR 的操作主要有两种: Transformations, Actions. 只有在执行Action时, Spark才会进行计算.Transformations是将一个RDD转成另一个RDD.
RDD 是只读的. 只能中现有的 RDD 生成 RDD.

每个分区的计算需要上一个分区的依赖,为宽(wide)依赖, 可能需要依赖不同分区的结果. 为窄(narrow)依赖, 判断的依据是否只需要依赖父分区, 且可以只在一台机器上执行.

如何容错

当worker宕机了之后, 将会丢失内存和RDD分区, 只能通过重新进行调度运行那个分区. 但是对于宽依赖的分区不一样, 可能因为后续的分区运行失败, 而要运行所有的父分区, 所以需要设置检查点(check point)这样才能减少崩溃带来的时间消耗. 快速得到结果

迭代计算: PageRank

Hash Partition

总结

RDD是由函数转换产生的, 它们以谱系图的形式聚集在一起.

Memcached

网站的演化

最开始的简单web版本是由HTTP服务器, 后端例如PHP, 数据库组成. 但这样的配置在用户增多之后将会变的棘手.

幸运的是, 这很容易解决. 使用一台单独的机器运行数据库, 存放持久化的数据. 再使用多台前端机器进行处理请求. 如果你有很多用户, 就多部署几台前端就行, 因为前端是无状态的.

一个简单的MYSQL设置可能能够支持每秒十万的简单事务读取. 如果用户的请求总数超过十万. 那么就需要一种不同的方案.
所以下一个方案是分片, 将存储的机器分为多台机器. 但是还有很多前端机器.
但将数据分片后, 当需要进行跨分片事务时, 将会比较麻烦, 可能需要两阶段锁进行限制.

所以我们可以减轻数据库对读取事务的处理, 通过增加缓存. 让数据库大部分时间专注于写事务. 这种结构适合大多数业务为读的请求.

但这带来的一大挑战便是, 怎么保持数据库和缓存的一致. 另一挑战便是怎么防止数据库超载.
因为当使用缓存能够承载了例如每秒10亿次查询, 当缓存出现故障, 那么这些请求都将直接涌向数据库.

一致性: eventual ( 最终一致性? )

写入一致性由数据库完成
读取的数据为落后数据也是OK的, 但是除了一种情况: 同一个客户端写入, 并立即读取.

缓存的失效方案 ( Invalication of caches )

会在运行数据库的同时运行一个Squeal的程序, 当检测到某个键被修改时, 通知缓存进行删除. 当客户端向缓存发起查询时, 发现没有相关k的数据, 将会直接去数据库进行查询. 然后将查询的结果存入缓存中. 这样的缓存称之为旁路缓存.

Q: 为什么不先更新cache中的信息, 然后再更新数据库.
A: 可能因为执行的顺序不同导致, 缓存中新的数据被覆写.

挑战 / 如何保护数据库

新集群在投入使用前, 从旧集群复制数据来避免, 因为新集群的缓存全为空, 导致大量请求涌向数据库.
惊群(thundering herd) 一个值非常热门, 然后因为更新导致缓存中的数值失效删除. 大量想要这个值的请求涌向数据库. 解决的方案是, 当你请求这个键时, 会得到两种情况. 一是你有权限进行更新, 然后将会发起向数据库查询的请求, 或者是得到一个等待时间, 大约这个时间之后, 重新发起请求就能得到该值.
当有 memcached 宕机了, 将请求转向 gutter pool.