面向内存云的协调器选举策略

王跃飞　于炯　鲁亮

摘要：

针对ZooKeeper机制难以满足内存云（RAMCloud）低延迟、快恢复的问题，提出了一种面向内存云的协调器选举策略（CES）。首先根据内存云网络环境与协调器自身因素将协调器性能指标分为个体指标与协调器间指标两类并分别建立模型；然后将内存云的运行分为正常运行期与数据恢复期两阶段并分别建立适应度函数，再按时间比合并为总适应度函数；最后在备选协调器（RBC）的适应度值的基础上提出一个具备稳定择优性与随机性的新算子，CES首先通过筛选来排除性能较差的个体，缩小选择范围后再在理想协调器的集合中采用轮盘赌方法选择最终的个体。实验结果表明，在NS2仿真环境下CES选择的个体相比其他备选协调器数据处理延迟降低了19.35%；在搭建的内存云环境中，与ZooKeeper机制相比，CES的选择结果在快速恢复中时间减少了10.02%。在内存云的实际应用中，CES在处理单点失效问题上能有效选择性能更优的协调器，确保了低延迟、快恢复的要求。

关键词：

内存云；协调器；单点失效；适应度函数；选举策略

中图分类号：

TP393.02

文献标志码：A

Abstract：

Focusing on the issue that ZooKeeper cannot meet the requirement of low latency and quick recovery of RAMCloud， a Coordinator Election Strategy （CES） based on RAMCloud was proposed. First of all， according to the network environment of RAMCloud and factors of the coordinator itself， the performance indexes of coordinator were divided into two categories including individual indexes and coordinator indexes， and models for them were built separately. Next， the operation of RAMCloud was divided into errorfree running period and data recovery period， their fitness functions were built separately， and then the two fitness functions were merged into a total fitness function according to time ratio. Lastly， on the basis of fitness value of RAMCloud Backup Coordinator （RBC）， a new operator was proposed with randomness and the capacity of selecting an ideal target： CES would firstly eliminate poorperforming RBC by screening， as the range of choice was narrowed， CES would select the ultimate RBC from the collection of ideal coordinators by means of roulette. The experimental results showed that compared with other RBCs in the NS2 simulation environment， the coordinator selected by CES decreased latency by 19.35%； compared with ZooKeeper in the RAMCloud environment， the coordinator selected by CES reduced recovery time by 10.02%. In practical application of RAMCloud， the proposed CES can choose the coordinator with better performance， ensure the demand of low latency and quick recovery.

英文关键词Key words：

RAMCloud； coordinator； singlepoint failure； fitness function； election strategy

0引言

随着电子商务与社交网络的快速发展，越来越多的企业与组织常常面临百万级的用户并发访问与每秒数以千计的并发事务处理[1]。2011年7月，《中国计算机学会通讯》针对数据密集型计算（DataIntensive Computing， DIC）展开了专题研究[2]，并将极限事务处理（Extreme Transaction Processing， XTP）作为解决密集型应用的关键。斯坦福大学于2009年提出内存云理念，使相关问题得到良好的缓解[3]：内存云（RAMCloud）是一组以内存为存储媒介，所有数据均存储在动态随机访问存储器（Dynamic Random Access Memory， DRAM）内，硬盘仅作为数据备份。由于文件数据始终存储在内存，系统的吞吐量与时延得到了高效的优化。近年来有关内存云的研究领域逐渐得到扩展与深化：研究人员不仅对数据的管理与恢復作出了系统的改善[4-5]，同样针对数据的并发容错，存储查询提出了新的模型与框架[6-8]。目前国内也开展了相关研究，对包括磁盘节能[9]、小文件合并[10]等问题作出了优化与完善。

由于内存云协调器（coordinator）在断电等自然灾害情况下会不可避免地面临由单点失效造成的系统瘫痪问题，针对关键节点再选举，Hadoop的扩展项目ZooKeeper开源实现了Google的chubby服务，通过paxos的变种算法解决了候选节点的选举问题[11]。然而Zab（ZooKeeper atomic broadcast）协议难以支撑内存云高效的读取速率，Junqueira等[12]对Zab协议的延迟进行了分析，实验证明在单独的一个操作中，服务器间的平均延迟在100ms以上，远高于内存云的微秒级别[13]。另外，Zab协议更适用于竞选id确定的情况下执行[14]，内存云网络情况复杂，备选协调器（RAMCloud Backup Coordinator， RBC）数目较多，备选集合随情况不同数目也会有所变化。

文献[15]对内存云使用Zab协议进行了研究，结果表明：1）单点失效后内存云仅采用随机的方法在备选协调器集群内选择协调器；2）在配置文件较小的情况下单点恢复速度低于服务器恢复速度。以上问题表明传统选举机制并不适用于内存云环境，突破延迟问题并依据网络状况才是选择备选协调器的重要方法。

本文主要针对备选协调器（RBC）的选择问题进行研究，为解决该问题，提出了一种适于内存云日志文件系统的协调器选举策略（Coordinator Election Strategy， CES）。首先，根据内存云网络拓扑与协调器自身性能，将协调器指标分为个体指标与协调器间指标并分别建立模型，这些模型能够对任意协调器进行客观评价；然后，引入遗传算法的适应度函数，为保证客观，将内存云适应度函数分为正常运行与数据恢复两阶段，之后根据时间比合并；最后，为筛选最优协调器，本文提出一个稳定的新算子，该算子能在备选集里不失随机性地选择状况良好的协调器作为最终选择。

1内存云架构

1.1内存云结构

在内存云集群中，每台服务器既是由内存构造的主服务器（Master），用作数据文件的存储；同时也是由硬盘组成的备份服务器（Backup），用来防止断电等灾害而备份内存中的数据，框架结构如图1所示。另外，集群中含一个类似Hadoop中namenode节点[16]的协调器，在集群运行与数据恢复阶段负责管理服务器，记录键值对日志，完成对应功能。

1.2内存云协调器

协调器关系到服务中心的正常运行，虽然它不涉及数据的读写，但作为建立检查点、分配和调用资源、存储数据映射信息的核心服务器，协调器在各阶段承担着监察和统筹全局的重要角色。考虑到各时期的差异，将协调器功能分为两阶段，分别是服务器正常运行时期以及数据的快速恢复时期。

1）服务器正常运行时期[17]。协调器需控制主服务器、备份服务器在线；需周期性监测是否有任意服务器宕机；需管理数据映射服务器的信息表；当客户端缓存丢失时，需与客户端连接。绝大部分时间内，集群内的服务器均是正常工作的，但并不排除突发故障等问题，若发生断电等灾害问题时协调器则会启动应急项。

2）数据快速恢复期[18]。主服务器在宕机前，数据以段（segment）的形式复制3份，并分别存储在不同的备份服务器中，协调器存储了关于当前服务器数据备份的物理位置的映射信息，作为并行恢复查找点。另外，当恢复后所有段拼接完毕，协调器需查看拼接日志的完整性。

2协调器模型

内存云网络拓扑不遵循单一结构，而是呈混合多样化，即便容纳更多服务器也能保证集群的易拓展性，图2是一个典型的内存云網络拓扑简化。

图2中S表示交换机（Switch， S），每台备选协调器C与多台聚合交换机（Aggregation Switch， AS）交互，网络内部关系复杂；当机架较多或有新的服务设备纳入时，底层交换机下还可能建立新的交换网络。根据内存云日志文件系统的运行方法与规律，可将内存云网络抽象，为RBC设置若干参数并建立模型，并将这些参数作为选举策略的重要依据。通过1.1节对协调器的功能分析以及内存云网络拓扑，现将参数划分为两类：1）个体指标；2）协调器间指标。

2.1个体指标

定义1备选协调器个体指标。备选协调器个体指标是指在内存云网络拓扑结构中，备选集内每台协调器个体特性以及网络结构特性，包括：RBC连通性、RBC中心性和剩余内存空间。

2.1.1RBC连通性

协调器的连通性是指：1）与主服务器、备份服务器的连通性；2）与客户端的连通性。内存云中，协调器为探测集群中是否存在宕机服务器，以及为管理各类在线服务器，主服务器会周期性地向协调器发送心跳，协调器如果在一段时间内没有收到心跳，就会将该服务器标记为宕机。另外，客户端存储了与主服务器直接连接的缓存数据，如若缓存丢失，客户端将尝试与协调器建立连接，并重新建立缓存。由于暂不模拟与客户端的交互，连通性仅将与各服务器的连接关系纳入考虑范围。

针对与各服务器的连接关系，RBC连通性模型建立如下：

C（c）=λ·1n∑nk=1j·Ttk（1）

其中：C（c）表示协调器c的连通性（connectivity）；n为集群中服务器数量； j为主服务器向协调器发送心跳次数，次数较多统计越为准确；T为系统设置的心跳周期；tk是协调器记录的服务器k在j次心跳循环中总接收时间；为协调连通值与其他因素的关系，插入在最后计算适应度值时连通性的权重λ，可依据情况改变大小。可以观察到连通性反映了平均接收心跳时间，能够以时间衡量影响主服务器与协调器通信路径的因素。这是因为数据中心网络拓扑中接入层、汇聚层的光纤带宽是相同的，当协调器欲与某服务器通信，需经过若干交换机到达机架交换机（TopofRank switch， ToR），再将消息转发至目标服务器中，如图3。因此真正影响接收时间的实际是通信路径中的交换机以及路径长度等因素。

若系统采用双向心跳机制时，即协调器在周期时间也向主服务器发送心跳，同样可以采用式（1）来判断各协调器连通性能，但需注意tk是受前若干次心跳时间影响的，需要控制心跳次数j统一才可判断各协调器连通值大小。内存云数据中心能支持混合型网络拓扑结构以实现应用广泛、拓展灵活等特性，与协调器间存在较少交换机的服务器则具有很大的优势，考虑到与协调器的通信距离、强度等问题，这类服务器在获得、提交数据等方面将具有更高的优先级。

2.1.2RBC中心性

RBC中心性表示该协调器在网络拓扑中的作用和影响力，用来评估周围服务器节点与该协调器连接的紧密性。一般的，若某协调器连接交换机在网络中所处位置占据了该网络所有最短路径中的绝大多数，则说明该协调器在网络的核心位置，所发出的信息指令也能更迅速地传递到网络中的各台服务器内。

为评估任意备选协调器影响力，引入节点介数[19-20]概念。包括内存云的众多网络中，在关键路径上能够传递信息的节点的重要性并不亚于具备重要信息的节点。节点介数能够客观反映RBC中各个协调器在网络拓扑的中心化程度，是网络节点重要性的关键标志。协调器介数值表示如下：

B（c）=∑s≠t≠Sσst（Sc）σst（2）

RBC中心性的计算可依照介数的计算方法。式（2）中σst表示从s到t的所有最短路径数目；分子部分σst（Sc）表示在所有的最短路径中，协调器c所连接交换机S经过的数目。B（c）的值越大，表示协调器c处理的信息路径越多，网络位置也就越为核心；若协调器位于网络边缘且与服务器连接，则中心性为零。

2.1.3剩余内存空间

剩余内存空间指除了必须存储的数据信息外协调器剩余空间大小。剩余空间有以下作用：1）与主服务器并行地交互数据。协调器虽不负责数据的读写，却存在很高的数据吞吐量。假设集群中含1024台主服务器，平均每台主服务器更新并传递100MB数据备份信息，考虑集群中的主服务器在同一时刻发送更新数据，则协调器至少应含有100GB剩余空间以供并行交互。2）剩余空间有效地保障了用户与协调器的通信。绝大部分的用户在初期需要和协调器建立通信连接服务，以获取主服务器地址等消息，应有足够大内存空间保证与用户动态链接。

协调器剩余内存空间的数学模型定义如下：

CFS=1γ{CRS-∑ni=1（maplist+iso）-∑ni=1cache-∑ni=1∑objectsbackupId}（3）

式（3）描述了协调器剩余空间（Coordinator Free Space， CFS）的计算方式，其中：γ用作在计算适应度函数时对CFS大小的调整，可通过训练获得。协调器总内存容量（Coordinator RAM Space， CRS）中包含以下存储信息：

1）∑ni=1（maplist+iso）表示n台主服务器存储的数据映射表以及备份镜像的总空间。主服务器数据块（object）的键值对一般存储在表单中，当用户请求主服务器数据或该主服务器宕机后协调器均需按表单查找源数据；另外，协调器应同样存储类似数据的备份镜像，以方便RBC的数据同步。

2）∑ni=1cache表示协调器与集群内所有主服务器通信信息的缓存空间总和协调器作为中枢节点必须存储于各个主服务器的通信信息并建立缓存，方便用户以及主服务器的接入。

3）∑ni=1∑objectsbackupId表示集群中每台主服务器每个数据块备份地址信息占用的空间总和。每台主服务器包含任意多个数据块，每个数据块备份在任意3个备份服务器中。

剩余内存大小关系到集群运行状况，是评价RBC的重要指标。一般备选RBC集合中剩余内存由于初始化、网络位置不同等因素大小不一，因此内存较高的协调器更能够保证数据交互的平稳与存储的安全。

2.2协调器间指标

定义2备选协调器间指标。备选协调器个体指标是指在内存云网络拓扑结构中，备选集内每台协调器网络结构特性，包括：1）RBC相互关联性；2）其他因素。

2.2.1RBC相互关联性

若某RBC被最终选为协调器，则该协调器将与RBC时刻保持大量的信息交互，这是因为协调器需在RBC集合中同步、备份数据镜像，以防止当前协调器宕机后数据丢失。为表示RBC内部的通信长度，引入平均路径长度作为参数用以评估当前协调器各RBC关联程度的高低。

协调器与RBC间关联程度表示如下：

R=1D=1/（∑Ci=1dijkstra（c，i））（4）

数据中心规模较大，消息存在多路径选择。式（4）中：dijkstra（c，i）表示从定点协调器到某一个RBC之间的单源最短路径，C表示RBC集合内的备选协调器数量。该算法的累加部分为从源点到RBC集合中全部服务器的最短路径距离之和，距离D越长，关联程度越低。

平均路径长度一般用来描述内存云数据包的通信有效性，通信路径越短，有效性越強。依照内存云网络部署可以简单有效评估该协调器与RBC间的通信能力，判断协调器间的紧密程度。

2.2.2其他因素

目前的一些复杂网络分析提供了一些判断节点性质的标准，这些标准作为网络的分析方法为内存云协调器的网络结构分析提出了参考依据：如Google采用的PageRank算法不仅能够排列网页，同样的原理也能定位并计算网络节点的重要程度；另外，安全因素同样也应纳入考虑范畴之内，局部网络拓扑的脆弱性容易引发恶性网络攻击，安全网络下的协调器则更被优先考虑。

3协调器选择策略

3.1遗传算法在RBC集合的应用

遗传算法是解决最优化问题的良好途径，通过选择、交叉、变异处理基因与染色体，遗传算法能够遴选出较为满意的个体传递到下一代种群里。

在内存云数据中心集群中，可以将RBC集合看作需要被遴选的初始化种群，为选出状态最佳的协调器，可依據第2章讨论的内容建立合适的适应度函数，该函数能够客观反映理想化的协调器在任意阶段的必备条件，根据适应度函数对每台RBC的计算，可以衡量并评价集合内每台RBC与最优效果的接近程度。

3.2适应度评估函数

为解决不同的问题，遗传算法对适应度函数有着不同的要求。针对大部分简单的计算，算法始终执行唯一的适应度函数，处理问题虽然简单明确，但容易引发计算初期的未成熟收敛问题以及后期的竞争区分度不高问题。内存云协调器工作内容按时间划分可分为服务器运行期以及快速恢复期，两个阶段对协调器要求各不相同，为客观分析RBC集合内各协调器指标，两阶段可分别创建不同的适应度函数。

3.2.1运行期适应度函数

通过第2章对RBC模型的建立与性质的探讨，并结合正常运行的协调器工作内容，分析并建立运行期适应度函数如下：

frun=（C+B+CFS）·R（5）

其中：C、B、CFS、R分别表示协调器的连通性、中心性、协调器剩余空间以及RBC间通信状况。参考第2章运行期协调器任务，对评价标准讨论如下：首先，协调器需要及时与主服务器、备份服务器甚至丢失缓存的客户端发送消息，频繁的通信不仅能够及时探测失效节点，而且可以在第一时间获取各主服务器数据更新信息的状况并及时记录，因此需将协调器的连通性C和中心性B考虑在内；其次，内存云工作期间协调器会不定期接受各个主服务器发送的数据，数据并行传送时对协调器内存大小有较高的要求，因此适应度函数纳入CFS因素；最后，RBC相关性R在运行与恢复期都起到至关重要的作用，不仅能在运行时周期地将数据镜像复制传递到RBC集合中，而且恢复期间允许从其他RBC中获取需要的数据，因此R值是参照的重要因素。

3.2.2快速恢复期适应度函数

快速恢复期与运行期大致相同，不同的是对协调器网络性能要求比正常运行时高很多。参照快速恢复机制，任意服务器宕机后需要尽快恢复完毕，而恢复的关键便是协调器能否将要求的数据信息快速及时地发送给主服务器并接受响应。这不仅考量了协调器与服务器是否连通，同时检测了协调器是否处于网络核心以及其通信影响力。

另外，为防止大量服务器同时瘫痪，协调器间的关联R也存在要求，这是因为内存云在面对大量服务器瘫痪情况时可采用多协调器共同恢复机制。通过对快速恢复期协调器任务分析，可建立适应度函数如下：

frecovery=C·B·R（6）

协调器对网络的要求很高，在适应度函数中表示为C·B，代表了某节点连通性与中心性的乘积，这是由内存云即时性要求决定的。倘若某节点具有网络连通优势且与周围服务器连接紧密，则被选为协调器的概率也就大大提升。

3.2.3协调器适应度函数

综合两阶段不同要求所提出的不同适应度函数，得到如下总适应度函数：

F=αfrun+βfrecovery（7）

其中α， β为两阶段适应度函数系数，α∶ β表示在内存云集群中所有服务器正常运行与任意服务器宕机次数之比。两阶段适应度函数之和能够客观评价某RBC在不同时期的综合情况，适应度越高的RBC越接近理想状态。

3.3协调器选择策略

选择算子以RBC集合内每台服务器的适应度评估值为基础，按一定规律选择一台理想的协调器。内存云网络结构中RBC可够部署在核心层任意位置，若依照比例选择采用轮盘赌的方式存在很高的不稳定性；若仅取计算后值最高的RBC则丧失了随机性，同样理想的RBC可能因为特殊问题不能入选。

目前关于算子理论的发展已经非常成熟，针对以上的特殊情况，结合择优与随机特性提出一种适于内存云环境下选择RBC的算子方法。该方法能够遴选出理想RBC作为新的集合，将轮盘赌的随机选择缩小在质量很高的RBC集合中。

算法说明：设在RBC集合内含N台备选协调器，通过期望生存值（Expected Value， EV）与轮盘策略选择最终的协调器C。

4实验与分析

4.1实验设计与环境

4.1.1实验设计

实验首先通过协调器模型与选择策略模拟推举出最终协调器，再根据不同协调器下消息传递时延、数据恢复时间选择RBC内实际最优者，通过比对CES与实验结果的一致性判断选择策略的优劣。

实验首先在NSG2包内创建45个节点，其中包括C0至C4共5个协调器模拟节点，为模仿内存云网络，将环形、星形、总线三类构成混合状拓扑结构，仿真拓扑简化如图4所示。

配置节点与链路参数并生成tcl脚本文件，将文件运行在Fedora系统环境下的NS2.35版本平台上，编写协调器属性值算法；其中连通性的精简伪码如下：

最后执行仿真实验，仿真时间60s，并对生成的trace文件进行分析。根据第3章所讨论的协调器选择策略，对实验中RBC内5台协调器计算适应度函数frun与frecovery（忽略剩余内存空间大小），按9∶1控制正常运行与恢复频率，计算得到总适应度函数F后，按选择策略算法1执行。根据适应度大小和对稳定性的控制，可对期望生存值的扣除因子作适当调整。

协调器需要时刻获取主服务器传递的数据，并向RBC传递备份数据。同样大小的数据在网络中传输，依靠网络的结构差异与路由机制的不同，延迟高低实际上是存在区别的。图5中5个协调器的数据传输延迟基本上随着数据量的增加而升高，可以观察到，C3于RBC中基本处于最小延迟状态。实际上NS2在模拟中存在一些非客观因素，数据延迟的大小更依赖节点传输的路径长度，在这种情况下，C3延迟依然较低，这是由于其处于网络拓扑中心环状处，且与节点密集区距离较近，因此延迟低于其他RBC。相应的如C1或C4在传输相同数据情况下延迟较大，这是由于传输经过节点多。若在内存云真实环境下，可能会在接收、传递、转发消息过程中出现请求高、任务排队等情况。

4.2.2数据恢复时间分析

数据恢复时间是衡量当前协调器性能的重要参数，然而在仿真环境下，NS2难以测试内存云的恢复时间。本节实验通过搭建内存云模拟环境，建立15个节点，其中包括10台服务器，以及构成RBC的5台协调器；每台主服务器内存16GB，硬盘100GB，内存云版本为1.0。

当前数据中心处理单点故障问题的主流方法为ZooKeeper和chubby。为检验CES效果，选择ZooKeeper作为实验对照。ZooKeeper是开源Hadoop中的一个子项目，能够下载并安装使用[21]。内存云数据备份在备份服务器中，当某台服务器宕机后，备份服务器需要将存储的数据表单提交至协调器，并将恢复数据传递至新的替代服务器内，实验通过执行CES，选择出最佳协调器C1，通过恢复时间比对执行ZooKeeper后的最佳协调器C2。

图6展示了CES与ZooKeeper选择结果对数据恢复时间的影响。C1与C2在恢复过程中影响差异基本维持在200～300ms，在最初恢复数据小的情况下，不同协调器对恢复时间影响可以忽略不计；当恢复数据增加时，差异变得明显且稳定。虽然单个主服务器容量不大，但从图6的趋势能够判断，若需恢复100GB的情况下，不同协调器对恢复时间还是有影响的。

造成差异的原因是由于CES选择的协调器能够更快获取备份服务器主键，或者能够更快查询到需要数据的物理位置等信息。ZooKeeper在内存云的处理情况是将失效节点配置信息随机传递给相邻协调器，并未将该协调器个体指标与周围网络纳入考虑范围，因此最终选择结果不及CES客观。

5结语

目前的一些大型数据中心如Yahoo！等在面对单点失效问题时均采用ZooKeeper机制[22]，相似的数据中心之间，类似方法策略也具有一定的移植性。由于内存云的存储介质与大部分数据中心具有本质差异，相关方法难以结合吞吐大、时延小等特性，因此考虑结合内存云特殊架构下的单点恢复策略也就显得更加紧迫。

通过面向协调器建模并分析模型，建立双时期适应度函数并合并，计算函数并求解算子等一系列的执行过程，不仅能够在RBC集合中选举出优秀理想的协调器作为内存云网络中任务调度资源分配的承担者，同样能对选举参与者状态作出有效评估，对各服务器网络最佳位置提供有效参考。当然，选举策略同样存在一定的缺陷，表现如下：1）将来的完善中，可以把网络安全、绿色计算等因素纳入建模研究范畴。协调器作为服务中心首先不应存在被黑客攻击的安全隐患，另外在研究消息传递路径时也应考虑能耗因素。1）选举策略下的框架结构并未将网络安全、绿色计算等因素纳入建模研究范畴。协调器作为服务中心首先不应存在被黑客攻击的安全隐患，另外在研究消息传递路径时也应考虑能耗因素。2）若在最初部署時协调器网络位置分布过于密集，差异较低，则CES效果并不显著，更适宜直接采用随机轮盘的形式。

下一步将针对优化内存云快速恢复网络拓扑进行探索与改进，结合图论、网络群体演化等相关技术，对内存云主服务器数据段的备份位置展开分析。在恢复中，数据的备份位置会影响到恢复时间、效率等关键指标，因此拟划分适当的域并在域中建立环状网络结构，使恢复性能获得新的优化。至于域内服务器的建模与部署，则是下一步重点考虑的问题。

参考文献：

[1]

秦秀磊，张文博，魏峻，等.云计算环境下分布式缓存技术的现状与挑战[J].软件学报，2013，24（1）：50-66.（QIN X L， ZHANG W B， WEI J， et al. Progress and challenges of distributed caching techniques in cloud computing[J]. Journal of Software， 2013， 24（1）： 50-66.）

[2]

肖侬.数据密集型计算[C]// 中国计算机学会通讯，北京：中国计算机学会，2011，7（7）：6-7.（XIAO N. Dataintensive computing[C]// CCF 2011： Communications of the CCF， Beijing： CCF， 2011，7（7）：6-7.）

肖侬.数据密集型计算[J].中国计算机学会通讯，2011，7（7）：6-7.（XIAO N. Dataintensive computing[J]. Communications of the CCF， 2011，7（7）：6-7.）

[3]

OUSTERHOUT J， AGRAWAL P， ERICKSON D， et al. The case for RAMClouds： scalable highperformance storage entirely in DRAM [J]. ACM SIGOPS Operating Systems Review， 2010， 43（4）： 92-105.

[4]

RUMBLE S M， KEJRIWAL A， OUSTERHOUT J. Logstructured memory for DRAMbased storage [C] // Proceedings of the 12th USENIX Conference on File and Storage Technologies. Berkeley， CA： USENIX Association， 2014： 1-16.

[5]

OUSTERHOUT J， GOPALAN A， GUPTA A， et al. The RAMCloud storage system [J]. ACM Transactions on Computer Systems， 2015， 33（3）： Articl No. 7.1-55

[6]

STUTSMAN R， LEE C， OUSTERHOUT J. Experience with rulesbased programming for distributed， concurrent， faulttolerant code [C]// Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference. Berkeley， CA： USENIX Association， 2015： 17-30.

[7]

TINNEFELD C， KOSSMANN D， GRUND M， et al. Elastic online analytical processing on RAMCloud [C]// Proceedings of the 16th International Conference on Extending Database Technology. New York： ACM， 2013： 454-464.

[8]

TINNEFELD C， KOSSMANN D， BOESE J H， et al. Parallel join executions in RAMCloud [C]// Proceedings of the 2014 IEEE 30th International Conference on Data Engineering Workshops. Washington， DC： IEEE Computer Society， 2014： 182-190.

[9]

魯亮，于炯，英昌甜，等.内存云架构的磁盘节能策略[J].计算机应用，2014，34（9）：2518-2522.（LU L，YU J，YING C T， et al. Energyefficient strategy for disks in RAMCloud[J]. Journal of Computer Applications， 2014， 34（9）： 2518-2522.）

[10]

英昌甜，于炯，鲁亮，等.基于小文件的内存云存储优化策略[J].计算机应用，2014，34（11）：3104-3108.（YING C T， YU J， LU L， et al. An optimization storing strategy based on small files in RAMCloud [J]. Journal of Computer Applications， 2014， 34（11）： 3104-3108.）

[11]

RIVETTI N， CORSARO A. State based Paxos[C]// Middleware Industry 13： Proceedings of the Industrial Track of the 13th ACM/IFIP/USENIX International Middleware Conference. New York： ACM， 2013： Article No. 4.

[12]

JUNQUEIRA F P， REED B C， SERAFINI M. Zab： highperformance broadcast for primarybackup systems [C]// DSN 11： Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks. Washington， DC： IEEE Computer Society， 2011： 245-256.

[13]

RUMBLE S M， ONGARO D， STUTSMAN R， et al. Its time for low latency [C]// Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems. Berkeley， CA： USENIX Association， 2011： 11-16.

[14]

HUNT P， KONAR M， JUNQUEIRA F P， et al. ZooKeeper： waitfree coordination for Internetscale systems [C]// Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2010：11.

[15]

ONGARO D， RUMBLE S M， STUTSMAN R， et al. Fast crash recovery in RAMCloud [C]// SOSP 11： Proceedings of the 23rd ACM Symposium on Operating Systems Principles. New York： ACM， 2011： 29-41.

[16]

BORTHAKUR D. The hadoop distributed file system： architecture and design[EB/OL]. （20070701） [20151005]. http：//hadoop.apache.org/common/docs/r0.18.2/hdfs_design.pdf.

BORTHAKUR D. The hadoop distributed file system： architecture and design[EB/OL]. （20070701） [20151005]. http：//web.mit.edu/～mriap/hadoop/hadoop0.13.1/docs/hdfs_design.pdf.

[17]

RUMBLE S. Memory and object management in RAMCloud [D]. Stanford： Stanford University， 2014： 5-22.

[18]

STUTSMAN R. Durability and crash recovery in distributed inmemory storage systems [D]. Stanford： Stanford University， 2013.

OUSTERHOUT A J. Undergraduate durability and crash recovery in a distributed inmemory storage system [D]. Stanford： Stanford University， 2013： 17-47.

[19]

FREEMAN L C. Centrality in social networks conceptual clarification [J]. Social Networks， 1979， 1（3）： 215-239.2012年

[20]

王元卓，于建業，邱雯，等.网络群体行为的演化博弈模型与分析方法[J].计算机学报，2015，38（2）：282-300.（WANG Y Z， YU J Y， QIU W， et al. Evolutionary game model and analysis methods for network group behavior [J]. Chinese Journal of Computers， 2015， 38（2）： 282-300.）

[21]

The Apache Software Foundation. ZooKeeper： because coordinating distributed systems is a zoo [EB/OL].[20151112]. https：//zookeeper.apache.org/doc/r3.5.1alpha/index.pdf.

[22]

JUNQUEIRA F P， REED B C. The life and times of a ZooKeeper [C]// PODC 09： Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. New York： ACM， 2009： 4.