Abstract: In order to solve the problem of low using rate, RAMCloud would change the positions of objects, which would cause the failure for Hash to localize the object, and the low efficiency of data search. On the other hand, since the needed data could not be positioned rapidly in the recovery process of the data, the returned segments from every single backup could not be organized perfectly. Due to such problems, RAMCloud Global Key (RGK) and binary index tree, as solutions, were proposed. RGK can be divided into three parts:positioned on master, on segment, and on object. The first two parts constituted Coordinator Index Key (CIK), which means in the recovery process, Coordinator Index Tree (CIT) could position the master of segments. The last two parts constituted Master Index Key (MIK), and Master Index Tree (MIT) could obtain objects quickly, even though the data was shifted the position in the memory. Compared with the traditional RAMCloud cluster, the time of obtaining objects can obviously reduce when the data throughput is increasing. Also, the idle time of coordinator and recombined time of log are both declining. The experimental results show that the global key with the support of the binary index tree can reduce the time of obtaining objects and recovering.

Key words: RAMCloud, log-structure, binary index tree, object localization, fast recovery

摘要： 内存云(RAMCloud)通常通过移动数据的位置来解决内存利用率低的问题,致使Hash表数据定位失效,查询数据效率低下;另一方面,在数据恢复过程中由于不能快速定位到需要的数据,每台备份服务器返回的数据段不能更好地组织起来。针对以上问题,提出内存云全局键(RGK)及二叉树索引。RGK分为三部分:定位到主服务器、定位到段以及定位到数据块。前两部分构成协调器索引键(CIK),在恢复中借助构造的协调器索引树(CIT)能够定位到段所在的主服务器;后两部分构成主服务器索引键(MIK),数据在内存中位移后也能通过主服务器索引树(MIT)快速获取到数据。与传统内存云集群相比,主服务器获取数据块的时间随数据吞吐量的增大而明显减少;协调器在闲散时间、重组日志时间等方面均有下降。实验结果表明,全局键在构造的二叉索引树的支持下能有效缩短获取数据及快速恢复的时间。

关键词: 内存云, 日志结构, 二叉索引树, 数据块定位, 快速恢复