大规模分布式系统问题集及解决方案(学习)
大规模分布式系统问题集及解决方案
单点一致性更新问题
问题描述：当多个用户同时更新某个数据时，如何保证最终数据的一致性。如用户A,B更新数据D，A->D+1, B->D+1，最终结果D+2。
解决方案：采用数据版本保证所有的更新都基于最新版本的数据。如原始数据(D，n)，A，B均拿到(D，n)，A更新后，数据(D+1，n+1)；此时B版本过时，更新失败，强制刷新数据后，更新数据为(D+2,n+2)。
数据分布方式的问题（平稳扩容问题）
问题描述：如何将数据均匀地分布在系统中的服务器，并在服务器增加、减少等情况下，最小化数据迁移代价。
解决方案：consistent hashing。将数据均匀hash到Q个桶中，Q远远大于机器数。这里把Q认为是虚拟节点数，每个机器根据实际能力配置不同的节点数。节点变化本质就成为hash表的变化: hash值和节点IP。淘宝tair日照表可参考。见：http://code.taobao.org/project/view/2/
(数据的移动量比传统的hash扩容小(本有1000桶变成1500桶))
单点问题
问题描述：若服务由单点提供，但该点失效后，服务将不可用。如何保证无单点服务
解决方案：
1）让系统的每个节点都可以承担起所有需要的功能。
2）主备机。
并发多核计算
blocking technique -- 充分利用CPU Cache
Blocking technique技术，即尽可能读取整块数据，块大小和L1的大小正好匹配(小于L1大小？还是L1大小的整数倍？)，在数据块上做运算，完成后，将整块数据写回内存！
尽可能让数据访问具有局部性，即一段时间内，对内存的访问，集中在特定范围内。通过定制内存管理器，可以分配较大的内存块给特定的任务使用，从而让该任务访问的内存尽可能集中。
分布式选举(分布式资源获取)
p2b 一个值为V的提案被通过了，那么编号比这个提案大的提案的值应该是V。
p2c 提出一个编号为n具有值v的提案的前提是：存在一个多数派，要么他们中没有人批准过编号小于n的任何提案，要么他们批准的提案中编号最大的(编号小于n)提案值是v。
(注：p2c隐含存在一个多数派可以推翻已经做出的决定。当提案人发现自己的提案已经无法通过时，应放弃自己的提案:多数人已经同意值v的提案。)
通过一个决议分为两个阶段：
1 prepare 阶段：
提案者选择一个提案编号 n 并将 prepare 请求发送给批准者中的一个多数派；
批准者收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则批准者将自己上次的批准回复给提案者，并承诺不再批准小于 n 的提案；
(回复有三种1 ok表示做出承诺（没有做出批准的时候）2 null表示不回复（提案编号比承诺过的编号小）3 value表示做出承诺，同时给出value（已经做出过批准的时候，value为上次批准值）)
2 批准阶段：
当一个提案者收到了多数批准者对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的批准者发送批准的请求，包括编号 n 和根据 P2c 决定的 value（如果根据 P2c 没有决定 value，那么它可以自由决定 value）。
在不违背自己向其他提案者的承诺的前提下，批准者收到批准请求后即批准这个请求。
数据备份(复制)问题
问题：多份数据的写入问题。
三种复制模式：异步，强同步，半同步。
异步模式实现简单，Master 有一个线程不断扫描操作日志文件，将最新的修改发送给 Slave，Slave 有线程接受 Master 发送的更新操作并回放，接受日志和回放一般采用两个线程。如果 Slave 宕机，以后重启时向 Master 注册，将Slave 最新的日志点告知Master，Master 为这个 Slave 启动一个同步线程从最新的日志点开始不断地传输更新操作。如果 Master 宕机立即切换到Slave或者Master 机器出现磁盘故障会丢失最后的更新。
异步模式如果要保证完全不丢数据一般采用可靠的共享存储实现。采用共享存储只需重启其它机器上的进程即可(单机进程无法保证，机器宕机)
强同步模式下，每一个修改操作需要先写入 Slave，然后写入Master 的磁盘中才能成功返回客户端。普通的强同步模式有一个问题，那就是 Slave 宕机也必须停止写服务，只能保
证可靠性而不能保证可用性。有一种比较合适的折衷，Master 保存一个Slave机器列表，每
个写操作都需要同步到 Slave 列表的所有的机器，如果发现某个Slave 连接不上，将它从 Slave列表中删除。(可用的slave节点全部更新)
半同步模式指的是有N 个Slave，数据写入到其中的 K 个 Slave 并写入 Master 本地就可
以成功返回客户端，只要K >= 1，就可以保证当 Master 宕机时，可以通过分布式选举，比如Paxos选举算法选取数据最新的Slave继续提供服务。(只需K个slave节点更新)
数据备份还需要解决一个问题：如何识别master宕机? 为了避免单点问题，slave应该具备识别master宕机的能力。异步模式下，master本身就是单点(slave节点需要连接master，交换状态)，master宕机，slave可知。强同步模式下，master和slave地位平等，区别只在于master提供服务，slave不提供服务，两者状态一致。可以引入lease机制的全局锁来识别master是否宕机，获得全局锁的机器对外提供服务。全局锁应采用类似google，chubby集群方式实现。
负载均衡: 分裂
问题：当数据服务器过载时，通过分裂数据到不同的服务器上，将服务迁移到不同的服务器上。多机分裂的难点在于如何使得多机在同一个分裂点原子地分裂。
解决方案：Bigtable 采用了另外一种思路。既然多机原子地执行分裂很难做，我们就做单机分裂好了。Bigtable 设计中，同一个子表 tablet 同一个时刻只能被一台工作机 Tablet Server 服务。由于只在一个服务节点进行分裂，问题得到了解决，底层的 GFS系统会负责文件系统的可靠性和可用性保证。
在保证单机写的情况下，分裂只在写节点(master)进行，读节点根据写节点的分裂日志进行类似分裂。
Copy-on-write与 Snapshot
问题：在高读写比例情况下，如何尽量提高读写效率？
解决方案： copy-on-write技术可以保证改变内存中的索引数据时，不影响读操作。Snapshot就是对内存中的索引数据(状态数据)做checkpoint，以保证在故障时尽快恢复服务。Copy-on-write只能提高索引数据的读写效率，并不能提供磁盘数据的访问效率。提供磁盘数据的读写效率需要依靠缓存技术: 多级缓存。内存索引--SSD(固态硬盘)热点数据()。
Copy-on-write 技术在树形结构中比较容易实现，假如我们实现一个支持 Copy-on-write
的B树，基本可以用来作为大多数管理结构的内部数据结构。
节点信息交换
问题：集群中，如何使每个节点对整个集群状态有一致的认识(状态)？
解决方案：Gossip 协议用于 P2P 系统中自治的节点协调对整个集群的认识，比如集群的节点状态，负载情况。我们先看看两个节点 A和B是如何交换对世界的认识的。
1 A 告诉B 其管理的所有节点的版本（包括 Down状态和Up状态的节点）
2 B 告诉 A 哪些版本他比较旧了，哪些版本他有最新的，然后把最新的那些节点发给A（处于Down状态的节点由于版本没有发生更新所以不会被关注）
3 A将B中比较旧的节点发送给B，同时将B 发送来的最新节点信息做本地更新
4 B 收到A 发来的最新节点信息后，对本地缓存的比较旧的节点做更新；
分布式单表事务
不懂
分布式跨表事务
不懂
数据的可靠性问题
问题描述：这是一个大问题，涉及：系统的一致性，可靠性，原子性，隔离性的问题(ACID)。
Dynamo的解决方案：Dynamo 的处理方式是把这个选择权交给用户，这就是它的N W R模型。N代表N个备份，W代表要写入至少W份才认为成功，R表示至少读取R个备份。配置的时候要求W+R > N。 因为W+R > N， 所以 R > N-W 这个是什么意思呢?就是读取的份数一定要比总备份数减去确保写成功的倍数的差值要大。也就是说，每次读取，都至少读取到一个最新的版本。从而不会读到一份旧数据。当我们需要高可写的环境的时候(论文中举例，amazon的购物车的添加请求应该是永远不被拒绝的)我们可以配置W = 1 如果N=3 那么R = 3。 这个时候只要写任何节点成功就认为成功，但是读的时候必须从所有的节点都读出数据。如果我们要求读的高效率，我们可以配置 W=N R=1。这个时候任何一个节点读成功就认为成功，但是写的时候必须写所有三个节点成功才认为成功。大家注意，一个操作的耗时是几个并行操作中最慢一个的耗时。比如R=3的时候，实际上是向三个节点同时发了读请求，要三个节点都返回结果才能认为成功。假设某个节点的响应很慢，它就会严重拖累一个读操作的响应速度。
注：一般工业界认为比较安全的备份数应该是3份。
分布式系统的数据一致性、可靠性、原子性和隔离性(ACID)。阳振坤老师的blog对此的阐述很值得看。
多点的数据一致性问题
问题描述：当数据存在备份情况下，如果保证数据更新的一致性。
Dynamo的解决方案：Dynamo 的方法是保留所有这些版本，用vector clock记录版本信息。当读取操作发生的时候返回多个版本，由客户端的业务层来解决这个冲突合并各个版本。当然客户端也可以选择最简单的策略，就是最近一次的写覆盖以前的写。这里又引入了一个vector clock算法，这里简单介绍一下。可以把这个vector clock想象成每个节点都记录自己的版本信息，而一个数据，包含所有这些版本信息。来看一个例子：假设一个写请求，第一次被节点A处理了。节点A会增加 一个版本信息(A，1)。我们把这个时候的数据记做D1(A，1)。 然后另外一个对同样key(这一段讨论都是针对同样的key的)的请求还是被A处理了于是有D2(A，2)。这个时候，D2是可以覆盖D1的，不会有冲突产生。现在我们假设D2传播到了所有节点(B和C)，B和C收到的数据不是从客户产生的,而是别人复制给他们的,所以他们不产生新的版本信息,所以现在B 和C都持有数据D2(A，2)。好，继续，又一个请求，被B处理了，生成数据D3(A，2;B，1)，因为这是一个新版本的数据，被B处理，所以要增加B 的版本信息。假设D3没有传播到C的时候又一个请求被C处理记做D4(A，2;C，1)。假设在这些版本没有传播开来以前，有一个读取操作，我们要记得，我们的W=1 那么R=N=3，所以R会从所有三个节点上读,在这个例子中将读到三个版本。A上的D2(A，2);B上的D3(A，2;B，1);C上的D4(A，2; C，1)这个时候可以判断出，D2已经是旧版本，可以舍弃，但是D3和D4都是新版本，需要应用自己去合并。如果需要高可写性,就要处理这种合并问题。好 假设应用完成了冲入解决，这里就是合并D3和D4版本，然后重新做了写入，假设是B处理这个请求，于是有D5(A,2;B,2;C,1);这个版本将可以 覆盖掉D1-D4那四个版本。这个例子只举了一个客户的请求在被不同节点处理时候的情况, 而且每次写更新都是可接受的，大家可以自己更深入的演算一下几个并发客户的情况，以及用一个旧版本做更新的情况。
注：如果备份数据只读，那么所有的更新均基于主节点数据，则退化成单点的数据更新问题。
Google的解决方案：GFS是典型的使用总控节点保证最终一致性的分布式系统。
最终一致性模型要求同一份数据同一时刻只能被一台机器修改，也就是说机器宕机时需要停很短时间写服务。
对于带有总控节点的系统，将CAP理论的定义做出适当的调整如下：
· 一致性：读操作总是能读取到之前完成的写操作结果，且不需要依赖于操作合并；
· 可用性：读写操作总是能够在很短的时间内返回，即使某台机器发生了故障，也能够通过其它副本正常执行，而不需要等到机器重启或者机器上的服务分配给其它机器以后才能成功；
· 分区可容忍性：能够处理机器宕机，机房停电或者出现机房之间网络故障等异常情况；
带有总控节点的NOSQL系统一般是最终一致性系统，允许机器宕机时停止很短时间，比如10s的部分数据写服务，但是不允许停读服务，且服务恢复时 间越短越好。大多数NOSQL系统都是对一份数据保留多个备份，同一时刻只有一个备份为主，提供写服务，其它备份为辅，同步主备份的写操作，所有的备份都 可以提供读取服务，且主备份提供保证强一致性的读服务。当主备份所在机器发生故障时，需要等一段时间才能由原来的辅备份接替主备份提供写服务。
从理论上讲，多个节点保持操作顺序完全一致只有两种思路：第一种思路是主备，同一时刻只有一个节点提供更新服务并复制到其它节点；第二种思路就是Paxos-based replication。
日志与数据一致性
日志的类型主要有：undo log，redo log，undo/redo log。最经常使用的类型为redo log和undo/redo log。 如果系统不出现异常情况， 那么日志是没有必要的，因此在讲述的时候大部分场景都是指系统异常退出重启，在叙述过程中不在重复描述这个场景前提。
注: 日志所要解决的问题：数据持久化的一致性。数据在持久化过程中可能因各种异常而出现数据的不一致状态(即不可知的中间状态)，日志就是保证当持久化异常时，让数据回退到一种一致的状态(我们不可能知道处于中间状态的数据下一个一致状态是什么，但总是可以知道之前的一致状态是什么。) 因此只有处于中间状态的数据才需要日志，处于一致状态的数据是不需要日志的。
UNDO LOG日志本质就是回退处于中间状态的数据到前一个一致状态，因此只有未COMMIT的事务需要UNDO(checkpoint的关键在此)。UNDO LOG必须记录下前一个一致状态。
REDO LOG的本质就是重做所有已完成的操作，保证所有数据最终处于一致状态。REDO LOG并不要求所有的数据立即持久化，因此可利用缓存来提高数据持久化过程的效率。
现实中的数据往往是动态更新的，大多数系统设计时也会将数据更新操作以操作日志(commit log)的形式持久化到磁盘中，如果有稳定可靠的地方，比如分布式文件系统，存储操作日志，那么每台机器上的数据分片(Tablet)都可以认为是无状态的，机器宕机时，集群中所有的机器都可以加载静态数据并从稳定可靠的操作日志存放处获取动态更新，问题得到解决。因此， 高可扩展性系统设计的关键点就在于稳定可靠的地方存储操作日志 。
备注：
对于分布式系统是初学者，没有实践的经验，对理论的理解也有限。上面这些属于学习笔记，是过去2个月零星积累的结果。绝大多数属于摘抄，文后会给出参考的资源。由于工作原因以后blog的更新会很少，是否完全停止待定。