Sinfonia: a new paradigm for building scalable distributed systems-- 翻译理解【1】
论文 pdfSinfonia: a new paradigm for building scalable distributed systems，原文在参考文献中。
本文是对论文第 1～第四小节的翻译加上理解，画了些图便于理解。文中可能出现 mini-t 是笔者对于 minitransaction 的缩写。文中很多都是笔者自己的理解，也有很多漏掉之处，更详细的资料还请阅读原论文
1.Intruduction
业界构建分布式系统的方式通常是依靠以通信为基础的共识算法(协议)、这些东西晦涩难懂 很难开发。毕竟就算论文摆在眼前，也看不懂，更别提以此为基础去进行开发了。
所以论文引入了一个 类似于共享内存的系统 Sinfonia
它具有高扩展性，以及 mirco-事务原语等特性
与 db 相比，它的性能更高，更能够应对高度频繁的操作(例如 fs 中的不断更新删除文件等)；而与传统的 共享内存 系统相比，它具有事务特性以及更高级别的扩展能力，可以部署到几百个节点
并以 Sinfonia 为基础，花费 1～2 人月分别构建了 SinfoniaFS 和 SinfoniaGCS(group communication service) 代码也都是在 4000 行左右。非常的方便快捷。
具体的实现细节和原理可以在下文中找到
2.ASSUMPTIONS AND GOALS
Sinfonia 被设计在 data center 中工作，并不适用于复杂网络环境下公网和 p2p 系统。当数据中心网络分区时会暂停服务(毕竟这个情况很少见，且大多数时候 data center 此时也是不可用状态)。作为在内网数据中心运行的服务，暂时没有构建安全系统
系统并没有考虑拜占庭式的失败(出于对节点的信任)，Sinfonia 的目标是帮助对基础设施的构建、例如分布式文件系统，lock managers 等需要提供可靠性，一致性以及扩展性的系统。
These applications need to provide reliability, consistency, and scalability. Scalability is the ability to increase system capacity proportionately to system size. In this paper, capacity refers to processing capacity, which is measured by total throughput.
3.Design
3.1 Principles
Principle 1. Reduce operation coupling to obtain scalability
耦合的操作会导致不同节点运行的并行度降低(因为存在操作顺序的依赖，并行度自然降低)，Sinfonia 的设计之一就是通过不强加的数据结构(例如 db 的 table、redis 中的 list 和 set 等)、来降低数据操作的耦合性。完全通过细粒度的 地址空间 address space 进行操作
Principle 2. Make components reliable before scaling them
简单来说就是 拓展节点时要先确保节点可用，且具有容错性。
3.2 Basic components
Sinfonia 主要由 memory node 与 user library 构成，user library 会按照 memory node 的机制对数据进行存取。每个 memory node 会有自己单独的 linear space 地址，所以数据的全局地址就由 (memory-node-id,address)构成，至于数据到底是存储在内存还是磁盘 取决于应用具体的场景
文中介绍到如果设计一个统一的全局地址(去掉 momory node id 的影响)、就会丢失 node locality 特性，最好让数据在本机节点进行处理、然后广播到 replicate 那边(data striping)。大大节省网络带宽
3.3 Minitransactions
minitransaction 允许 application 在多个 memory node 中更新数据，并保证 Atomic，Consistency，Isolation(Durablity 需要时也可以有)。
他们对 transaction 进行了一些细微的改造让它能适应更大并发量的支持，在这之前可以先了解一下传统分布式事务的做法。 其实还应该有一个 client(即具体是哪个应用需要分布式事务的支持，sinfonia 把 client 和 coordinator 合二为一了)
在 Sinfonia 系统中 coordinator 就是 applicatoin、participant 就是 memory node
我们观测到这个执行步骤 是可以进行优化的。例如 事务最后的 action 并不影响最终的 commit 或者 abort、则可以将这 transaction last action 放在两阶段提交的第一个阶段中 这个优化并不会影响事务的语义，并且可以节省一个网络的 communication round-trip
就算 transaction last action 的结果会影响最终的 commit 或者 abort、如果这时 participant 能够知道 coordinator 是如何做决策的，还是能够将最后的 action 搭载到 commit 阶段。例如事务最后的 action 是 read（这时如果 partitcipaint 知道 如果读到的数据 返回 0 就 abort、1 就 commit）然后协调器可以将此操作搭载到两阶段提交，参与者可以读取该项目并调整其投票以在结果为零时中止
而事实上，是有可能将整个 transaction 都搭载到 commit 协议中的，所以我们设计了 mini transaction 来优化整个事务的性能。
阅读图中的 Semantics of a minitransaction 可以得到整体的语义
1.通过 compare 操作对数据进行检测（类似 cas 中判断 新老数据是否相等）
2.如果符合函数传入的条件，则进行 1.通过 read 操作取回对应的数据 2.通过 write 操作写入对应的数据
Thus, the compare items control whether the minitransaction commits or aborts, while the read and write items determine what data the minitransaction returns and updates.
Minitransaction 的语义可以组成多个强大的原子操作
1. Swap. A read item returns the old value and a write item replaces it.
2. Compare-and-swap. A compare item compares the current value against a constant; if equal, a write item replaces it.
3. Atomic read of many data. Done with multiple read items.
4. Acquire a lease. A compare item checks if a location is set to 0; if so, a write item sets it to the (non-zero) id of the leaseholder and another write item sets the time of lease.
5. Acquire multiple leases atomically. Same as above, except that there are multiple compare items and write items. Note that each lease can be in a different memory node.
6. Change data if lease is held. A compare item checks that a lease is held and, if so, write items update data.
在 SinfoniaFS 中 minitransaction 最常用于校验数据是否进行了修改并进行写入操作，这点 SinfoniaFS 是最常用的，因为文件系统 application 在缓存中存储了 inode 信息以及文件的元数据信息，存在和 memory node 不一致的情况，因此需要频繁的进行 compare
也可以是单纯的 compare 操作，用于判断是否所有的 match 都满足。这点用于只读的文件
从目前的步骤看，实现 minitransaction 的代价是非常高的。
3.4 Caching and consistency
Sinfonia 本身并不在 application node 进行缓存操作，但是它鼓励这么做。给 application 更大的自由度、本身管理分布式系统的数据是一件很有挑战的事情，不过 Sinfonia 通过 minitransaction 通过以原子方式对缓存数据进行校验并更新的方式简化了这些操作的难度。
3.5 Fault tolerance
Sinfonia 针对不同的 application 提供了不同的容错等级、最小的都是 application 级别的 crash 容错。额外提供了额外的几个级别
Masking independent failures. If a few memory nodes crash, Sinfonia masks the failures so that the system continues working with no downtime.
Preserving data on correlated failures. If many memory nodes crash in a short period (e.g., in a power outage) without losing their stable storage, Sinfonia ensures that data is not lost, but the system may be unavailable until enough memory nodes restart.
Restoring data on disasters. If memory nodes and their stable storage crash (e.g., due to a disaster), Sinfonia recovers data using a transactionally-consistent backup.
为了提供这些容错的等级，Sinfonia 使用了 4 种不同的机制：4 种机制都有自己的缺陷，结合使用才真正是一个完善的 fault-tolerance
1.disk images：为了高效选择异步将 memory node 中内存数据写入磁盘，但是当掉电时会有部分 cache 没有刷入磁盘
2.logging：为了弥补 disk image 的缺陷，可以加一个用于记录 data 的 log，写内存的时候同步要写日志，以便于故障的恢复操作
3.replication：通过 log 恢复总是要时间的，这段时间系统会变得不可用、这时就通过副本对外提供服务、确保系统不会有 downtime。目前 Sinfonia 使用 primay-copy replication、为了减少对同步的依赖也可以使用状态机和 paxos 机制进行同步
4.backup：它是对 Sinfonia 数据的事务一致性 进行镜像备份，它不会暂停系统的运行，而是从日志不断的进行构建。
下图是使用了不同的机制后的容错说明
3.6 Other design considerations
Load Balancing
Sinfonia 为了加强 data locality 特性，是让 application 选择往哪个 memory node 进行写入的，那么自然会带来负载的不均衡。这点 Sinfonia 并没有提供通用的处理方式，只是会将每个 memory node 的负载情况定时汇报给 application、由应用的开发者决定策略。
Colocation of data and computation
一些应用需要进行数据和计算的托管、这点在 Sinfonia 中很简单，就是将 appliction node 和 memory node 放在同一个机器中，然后 appliction 中设置偏向于将数据放入本地节点，而 Sinfonia 则会通知哪些 memory node 是属于本地的。
4. IMPLEMENTATION AND ALGORITHMS
这部分会详细解释 Sinfonia 是如何实现 minitransaction 的，以及对传统的两阶段提交做了哪些改进。
4.1 Basic architecture
回想一开始我们介绍的基础结构，Sinfonia 由 application node 装上 user library 以及完全独立的 memory node 构成。它们之间通过 rpc 进行通信、而 minitransaction 也是基于此构建的。
Memory node 需要记录 redo-log 同时还需要运行 replication-protocol、进行副本的同步。实际上是一个比较复杂的过程.
首先是大家都有的 UNDO 和 REDO 日志，此外还有一些用于节点恢复的信息也要记录到参与者的 binlog 中。同时考虑到参与者即是 DSM（Distributed Shared Memory）的 memory node，而 memory node 是需要 replica 来增加系统可用性的，因此这些 binlog 也需要进行 replica。当然，binlog 的压缩和整体状态的 snapshot 也必不可少。除此之外，还需要考虑上面提到的 minitransaction 的恢复机制，需要额外的扫描和恢复两套节点。
4.2 Minitransaction protocol overview
我们对两阶段提交进行了改造，简单来说就是针对各种能够提前确认 commit 或者 abort 情况、能够提前结束这个两阶段提交的事务。
所以做了很多的改造，同时也引入了很多的问题。例如 Sinfonia 的事务 coordinator 也是 client、如果 coordinator 挂了、事务就会一直锁着知道 coordinator 恢复，所以它的场景就需要在 coordinator 不在的情况下 进行恢复。
传统的方式是 三阶段提交，加入额外的步骤去解决这个 coordinator 挂掉 一直锁的情况，而 minitransaction 则是想要尽量的缩减这个阶段。
所以 Sinfonia 是在 participant 中进行 lock、而不是在 coordinator 进行。这是因为 participant 本身就是存储数据的 memory node、它如果失败了 那么这个 appliction 本身就会变得不可用。那么在 coordinator 中就会缺少传统分布式事务中的 log 记录、取而代之的是在每个 participant 中进行记录投票。当所有参与者都投完了之后，才算是 transaction 成功。
所以为了避免死锁，Sinfonia 采用的简单的方案是、每个参与者在两阶段提交中的 phase-1 到 phase-2 中间 进行短暂的 lock、如果尝试 lock 失败则不阻塞（直接返回 abort），这个方案在锁频繁的时候是会出现很多错误的，但是当负载不高的时候是很高效的。
Lock granularity is a word, but we use range data structures to efficiently keep track of locked ranges。
当有因为获取不到 lock 而失败的情况、minitransaction 会在之后随机时间内进行重复的尝试，retry it
4.3 Minitransaction protocol details
Minitransaction 在上节中有简单的介绍、包括 compare，read 和 write 三个简单的操作。先进行 compare、如果 compare 条件失败这个事物直接 abort。
这个是微事务的具体流程
简单来说，就是在第一阶段 coordinator 会生成一个独特的事务 tid，并且发送到 participant 中。
1.每个 participant 都会尝试去 lock minitransaction 中涉及的 address （不阻塞）
2.执行 compare 操作，判断事务是否能够满足匹配条件；如果 compare 成功，则进行 read 然后将 write 操作进行 buffer
3.follows 决定 vote，如果所有 locations 都能够 lock、且 compare items 都成功，这个 vote 才算 committing 否则就 abort
第二阶段
coordinator 会告诉所有的 participant 如果 votes 都 committing 则会通知它们这个 commit 的消息。接受到 commit 的消息之后则会进行真正的 write 操作，否则会在 buffer 中 abort 它们。同时 participant 也会释放所有的锁（这个锁就是在 phase-1 和 phase-2 中间这个时段）
这个方案细节中 coordinator 并不会记录日志，不像传统的标准两阶段提交 If the minitransaction aborts because some locks were busy, the coordinator retries the minitransaction after a while using a new tid. This retrying is not shown in the code.
只有当 participant 自己投出了 commit 票，write 操作会记录在 redo-log 中用于故障恢复工作。compare 和 read 操作并不会记录
participant 中会保存一些数据结构来记录
1.所有有疑问的 tids (in-doubt)
2.强制放弃的
3.已经提交的
4.所有的记录
Code for coordinator p:
Code for each participant memory node q:
详细的流程描述，还是伪代码清晰，画成流程图要表示严谨的分支，图会比较复杂
4.4 Recovery from coordinator crashes
Sinfonia 的体系中分布式事务 coordinator 和 client 归属到一起了，如果在执行 mini-transaction 的时候 coor 挂了，那么就会导致事务无法结束。
为了解决这个问题、Sinfonia 在体系内引入了第三方的 recovery coordinator 组件，专门用来解决这个问题。它的定义是要解决以下问题：
当 coordinator 挂掉，它需要补上这个缺位、同时在 recovery 期间如果 memory node 挂掉也不能影响
当原 coordinator 恢复，可能存在两个 recovery ，要确保不影响最终的事务结果
那么 recovery 节点是如何感知原 coor 挂掉的呢？它其实会去监测各个 memory node 节点里 in-doubt 中的 tid、如果超时了还在这里的话，就会着手进行恢复的动作。
当进行 recovery 的时候，恢复节点其实并不知道这些 minitransaction 的具体意义的，它只有一个 tid。实际上 recovery coordinator 介入分为两个步骤：
1.要求所有没有投票的 participant 投 abort、其他投了票的则保持原票即可
2.然后会让强制投了 abort 的 participant 将对应的 tid 加入 forced-abort 列表中，防止原 coordinator 重启后进行恢复 要求它继续投票(这样就投了两次票)
然后再释放所有被 lock 的地址。这样即使多个 recovery 同时执行也不会影响结果，因为票都已经投完了，重复执行也是幂等的。
4.5 Recovery from participant crashes
当 participant 挂了，在它上面的运行的 minitransaction 都会阻塞着（并不像传统的两阶段提交、会让这个节点上的事务自动失败）。我们需要讨论的情况分两种，1.如果节点的持久化存储也没了（意味着 redo log 也没了）如何恢复？当然这种情况比较少见，会在 4.9 节进行专门的讨论，这里主要谈论的是磁盘还在的情况。
在之前的 3.5 节介绍过容错的方式，里面有包括 disk image 和 redo log、其实就是对机制的详细介绍。
可以看到整个流程，中因为有两个地方是有 buffer 差别的，所以流程复杂一些。而且为了避免原 participant 和 recovery 节点并发恢复出问题，对同一个 tid 投出了不同的 action 结果，直接强制的将其写入 forced-abort 中
4.6 Recovery from crash of the whole system
当系统发生很大的问题，整个系统需要重启。这时候如何进行恢复呢？当 memory node 重启时会向 manager 发送一个 reboot 的信号，从而让 manager 节点开始做整体恢复工作：让各个 memory node 互相发送最近的 tid 的 vote 情况，来解决上一小节里 decided list 和 redo-log 不一致的情况，
4.7 Log garbage collection
上面 4.5 小节中介绍了 redo-log 实际上会定期同步到 disk image 中，那么在 redo-log 中的数据就会变得没用，需要进行清理 也就是标题中的 log garbage collection。清理的逻辑是：
只有在每个参与的 memory node 都写进 redo-log 的 tid、才能够写进 disk image 中。
为什么需要每个 memory node 都满足条件？这是防止有些节点 crash 后 redo-log 的状态不一致，而这个设计体系中还会让 memory node 定期向其他所有参与的节点发送 tid 的同步到 disk image 的结果、来解决这种不一致的问题。
实际上当从 redo log 中删除 tid、在 decided list， all-log-tids 等列表也可以删除了。除了 forced-abort 列表，这个列表应用于 node recovery 都是节点 crash 过未记录的 tid，可能发生原 coordinator 还在运行这个事务、而具体的 participant 的 redo-log 中已经没有该 tid 了(原本这个 tid 被放入 forced-abort 就是为了防止多个 coordinator 同时进行 recovery、把它从里面删除，那么原 coordinator 就会继续执行这个 mini-t)、那么就会继续的执行这个 mini-t、可以参考 4.3 节的图，mini-t 详细执行的过程，会在第三步去判断这个 tid 是否在 forced-abort 中。
所以 Sinfonia 会有一个独特的机制来回收 forced-abort、定义了一个系统全局的 epoch number，每小时一次缓慢自增、让所有 memory node 保存当前的 epoch number，coordinator 则是可以通过 memory node 发给它们的 message 中获取该 epoch number
所以每个 mini 中实际上是会包括 epoch 的信息的，Sinfonia 定义了 stale(陈旧的概念) 是落后了当前至少两个版本，到时候会清理落后版本的 tid。会有两种情况可能清理错了 tid、
minitransaction 执行了 1 个多小时，那么就会清理掉最近的事务（概率很低、因为 mini-t 都是很短暂的）
coordinator 的 epoch 状态落后了，并没有同步最新的情况。这种情况下 需要重试了(由于落后的 epoch 原因导致直接失败的，估计会触发额外的同步机制)
4.8 Further optimizations
如果数据只存储在一个 memory node、那么仅有一个 participant 会参与投票，整个事务只需要一个阶段就够了，不需要等待其他 participant 的投票。这更加促进了 node locality 的特性，促使 appliction 往同一个阶段写相关数据(if space allowed)
如果是 read-only data，更节省了写 redo-log 的时间，因为它不会遭到修改、所以在节点恢复时也不需要从 redo-log 中找到最新修改的 value 了。
4.9 Consistent backups
Sinfonia 可以达到事务一致性的数据备份，做法是：所有的 memory node 都会保存记录最新在 redo-log 的 mini-t 称之为 L、然后将 L 写到 disk image 中(这时会锁住 disk image 防止其他的写入) 、这并不会妨碍到正常的工作（因为一般流程都是先写入 redo-log），当所有节点的 L 都成功写入 disk image，如果节点的 本地文件系统/存储设备 支持 backup 或者 snapshot、就可以很方便的进行这个工作。
而为了防止各个节点不断有新的事务进来、破坏了事务一致性、就需要在所有节点都没有未完成的事务的时候 让所有节点同时的进行备份。为了达到这样的效果 Sinfonia 专门为备份的场景做了处理，也是两阶段的步骤：1.将所有 memory node 的所有 address 都锁起来，防止新事务的执行。2.启动上述的做法，并立即释放锁
为什这个场景不像是之前的 mini-t 的两阶段呢，可以不进行阻塞锁。这是因为 mini-t 的过程本身只适合于少量节点参与的场景，backup 是所有 memory node 都参与的大型场景，如果还是非阻塞锁，可能就会导致一直有新的事务进来，一直执行不了 backup。因此 backup 采取的是阻塞式，并且会按照顺序进行来防止死锁(多个 backup 同时进行时)
4.10 Replication
如果需要的话 Sinfonia 也可以使用标准通用的技术进行 replicate、但 Sinfonia 采取的是将 replicate 的过程嵌入集成到 mini-t 的 phase-1 中，当写入 redo-log 时会同步向其他 replication 节点发送写请求，并且接受 ack 机制。
primary-copy 机制其实是很简单的，但它有一个缺陷就是：依赖于同步机制。但如果是在一个异步系统中，就可能发生 false fails-over、即可能在 primary 存活的情况下 replication 也是 active 的，造成系统的不一致情况。对此，Sinfonia 也只是有一个缓解的方案，采用了数据中心常用的一个工具 lights-out management ，可以在远程直接对机器进行关机或者开机(无论 cpu 是什么状态都可以)，当发生 fail over 的时候直接将 primary 进行关闭处理。当然为了能够彻底解决这个问题，Sinfonia 还预留的拓展 使用状态机或者 Paxos 的方式进行 repliaction。
科普异步 primary-copy：
异步复制在故障切换时可能会导致部分已经 commit 的数据丢失。一般的方案都是采用类似于 paxos 的协议进行补偿。
至于论文中提到的 异步复制导致的类似‘脑裂’问题、并没有查到资料
4.11 Configuration
在 Application 节点中 logical memory node 的 id 很简单，是一个很小的数字。但是 physical node id 是由 ip 加上一个 application id 组成的。将逻辑 id 与实际 id 映射关联起来的是 Sinfonia 的一个目录服务，它包含一个确定的 dns 服务，通过提供 replicated 来提高可用性。当 application 启动时，会缓存这部分映射关系，而当由新的节点加入，则目录服务会通知响应的节点去更新。
论文上半部分总结：
论文介绍了一种新的分布式系统构建体系——Sinfonia、的确是与笔者之前接触过的分布式系统构建方式（共识算法）例如 paxos 和 raft 等协议驱动的数据最终一致性保障的体系很不一样。论文中给我最大印象的就是 mini-t 的详细实现步骤、它是如何改进两阶段提交的分布式事务以及如何解决改造之后面对的一些问题的，是一种非常新奇的设计。
很推荐关注分布式领域的同学们仔细的阅读 4.3 小节
参考
Marcos K Aguilera, Arif Merchant, Arif Merchant, Mehul Shah, Mehul Shah, Alistair Veitch, Alistair Veitch, Christos Karamanolis, and Christos Karamanolis. 2007. Sinfonia: a new paradigm for building scalable distributed systems. Sosp'07 41, Figure 1 (2007), 159–174. https://doi.org/10.1145/1323293
还未添加个人签名 2018.12.10 加入
还未添加个人简介
评论