ramcloud资料整理 · 王很水的笔记

ramcloud是一个典型的KV表格结构

针对这个表格，引入了很多设计，也有很多论文。这里整理列出这个文章

[toc]

基本架构

如图可见的四种服务类型

enum ServiceType {
    MASTER_SERVICE,
    BACKUP_SERVICE,
    COORDINATOR_SERVICE,
    ADMIN_SERVICE,
    INVALID_SERVICE, // One higher than the max.
};

水瓶扩展？hash分片

基本的api

createTable(name) → id
getTableId(name) → id
dropTable(name)

read(tableId, key) → value, version
write(tableId, key, value) → version
delete(tableId, key)

multiRead([tableId, key]*) → [value, version]*
multiWrite([tableId, key, value]*) → [version]*
multiDelete([tableId, key]*)
enumerateTable(tableId) → [key, value, version]*

increment(tableId, key, amount) → value, version
conditionalWrite(tableId, key, value, version) → version

日志设计

日志也是LSM

内存分成8MB大小的段(Segment)，分配的对象在上面进行
使用一个hashtable来记录申请的内存对象实际的内存地址
选择内存空闲程度高的段进行拷贝整理，整理后释放旧的段
整理时通过引用计数来判断对象是否存活
内存整理是并行的

持久化保证

写入日志三副本分段保存到backups service上 append log

Tombstone 的概念也和rocksdb一样的

备份恢复

并发读日志，日志是按hash分的，无重叠

复制

大名鼎鼎的raft就出自这里

其他复制设计

Consistent Unordered Replication Protocol (CURP)，这个方案比看起来要复杂的多

把binlog日志拆出来，保证日志的持久性，节省master机器的rtt

复制协议设计要点

顺序一致：若副本两个操作a, b顺序为(a,b)，则没有任何客户端在看到b的时候，看不到a
持久化：一旦提交，进程崩溃后数据依旧不丢失

一般而言，传统复制协议延迟相对高一些，或有一些缺点：

主从复制：客户端→主节点（1 RTT），主节点→ 全部从节点（1 RTT）

类Paxos协议：客户端→主节点（1 RTT），主节点→超过半数从节点（1 RTT）

Faxos Paxos和Generalized Paxos：1.5 RTTs

NOPaxos和Speculative Paxos：接近1 RTT，但需要额外硬件支持，路由路径变长使得延迟会高一些

CURP的关键思路在于：对于可交换的操作，持久化顺序可以和操作顺序不一致，从而将延迟将为1 RTT

客户端往一个临时缓冲Witness写入请求，它不含顺序信息，客户端可并行向其写入
写入Witness同时，向主节点写入，然后立刻返回，只需要1 RTT
当主节点挂掉，Witness可用于重放和恢复

注意，操作可交换，不可交换直接拒绝。，如果一个客户端更新x=1一个客户端更新x=2, witness就要拒绝两个客户端

收到拒绝的客户端主动发起一次sync把这个不可交换的操作落地

两套措施。挺不自然的方案

Crash Recovery 直接从backup中选+从witness中重放，这个重放可以乱序

重放数据时，可能造成重复执行的问题,违背线性一致性（Witness请求已经在主节点挂掉前被同步了，但还没被清除），其解决方法是使用RIFL：

它给所有的RPC赋上一个唯一ID

服务端存储该ID和请求的结果（与原子方式和更新的对象持久保存），来检测重复的请求

涉及到的rifl没有仔细研究 http://web.stanford.edu/~ouster/cgi-bin/papers/rifl.pdf
witness会有各种同步日志协议同样的gc问题
witness的可用性,witness本身要搞个高可用集群

当Witness挂掉：

配置管理器会给主节点移除挂掉的Witness，并赋上新的Witness，并通知主节点

主节点执行一次同步操作，保证f

副本容错，然后响应给配置管理器

客户端就可以使用新的Witness（从配置管理器获取）

为了防止客户端使用旧Witness进行操作，CURP给Witness表维护一个递增版本号WitnessListVersion：

当Witness变更，主节点上该版本号都会递增

客户端请求会包含该版本号，主节点可检测版本号冲突并返回错误

当主节点返回Witness版本号错误，客户端会从配置管理器获取新版本的Witness列表

内存设计 Log-Structured Memory

为什么不用定制malloc -> 内存碎片

为什么不用GC -> STW不可忍受

Log-Structured Memory实际上也是一种GC模式不过基本无延迟，目标是不影响访问

这个设计scylladb也有类似的设计

https://zhuanlan.zhihu.com/p/25937990

实现在这里 https://github.com/scylladb/scylladb/blob/master/utils/logalloc.cc

compact

有Log类维护所有的append log，其中包括LogCleaner，LogCleaner后台起线程来做扫描，有balancer

balancer有两种类型，一种是按照删除key的比例TombstoneRatioBalancer，一种是固定比率FixedBalancer

后台线程做的都是cleanerThreadEntry -> doWork唯一区别 tid不同

doWork根据balancer->requestTask来决定做什么样的compact

这里也叫两阶段清扫

Two-level cleaning

最大的改动是将Segment改为变长的模式，将所有内存分成小段(Seglet)，每个Seglet只有64KB大小，每个Segment可以由多个Seglet组成，可以不连续。其默认大小仍为8MB。将内存整理分为两部分：

压缩(Compaction)：只涉及一个内存Segment变成更小的Segment，占用了更少的Seglet数目。

联合整理(Combined cleaning)：与前文所述相同，同时会将磁盘上的backup进行整理。

前者的消耗比较小，后者的消耗比较大。策略上尽量多做前者少做后者，同时推迟后者的执行可以提高整体效率，因为整理时间越晚，越少的对象会存活，开销也就越小。

LogCleaner::Balancer::requestTask(CleanerThreadState* thread)
{
    if (isDiskCleaningNeeded(thread))
        return CLEAN_DISK;

    if (!cleaner->disableInMemoryCleaning && isMemoryLow(thread))
        return COMPACT_MEMORY;

    return SLEEP;
}

isDiskCleaningNeeded
- 线程id不是1，false，一个线程就足够了
- cleaner->segmentManager.getSegmentUtilization() >= MIN_DISK_UTILIZATION true
- isMemoryLow(thread) false 不到不得已不去清理，disableInMemoryCleaning同理
- compactionFailures > compactionFailuresHandled 有compact失败，那更得去compact
- TombstoneRatioBalancer 最终逻辑
  - const int U = cleaner->cleanableSegments.getUndeadTombstoneUtilization(); const int L = cleaner->cleanableSegments.getLiveObjectUtilization(); if (U >= static_cast<int>(ratio * (100 - L))) return true;
- FixedBalancer最终逻辑只要是磁盘访问比总数访问小于设定，那就compact把数据压一下，肯定是有很多被删的key了
  - if (100 * diskTicks / totalTicks > cleaningPercentage) return false;

isMemoryLow

    // We need to clean if memory is low and there's space that could be
    // reclaimed. It's not worth cleaning if almost everything is alive.
    int baseThreshold = std::max(90, (100 + L) / 2);
    if (T < baseThreshold)
        return false;

doDiskCleaning
- getSegmentsToClean
  - chooseSegmentFunction 两种算法边界条件objectCount > MAX_LIVE_OBJECTS_WRITTEN_PER_PASS
    - costBenefit 有个公式，根据各种代价来计算，可以是文件存活/文件创建时间/访问时间等, 排好序然后挑前面的，然后想家，直到满足条件为止
    - gready，每次都找utilisation最大的，满足条件就放到结果里，然后判定是不是满足边界条件,不满足再搜一次，找倒数第二小的，加起来，再算
    - 很难说这两种哪个更好，反正数据集比较小
- getSortedEntries(segmentsToClean, outEntries, &localMetrics); 拿到活的数据
- relocateLiveEntries(entries, survivors, &localMetrics);重新分配数据
  - relocateEntry
    - LogEntryRelocator relocator(survivor, buffer.size());
    - ObjectManager entryHandlers.relocate(type, buffer, reference, relocator); log的构造是吧logentryhandler填的this log(context, config, this, &segmentManager, &replicaManager)
    - relocateObject, 重新放回hashtable（服了，和fasterkv差不多）不过没有整体address的概念，所以可以大胆的删文件
- segmentManager.cleaningComplete(segmentsToClean, survivors); 更新结果
```
    // Update the previous version's ReplicatedSegment to use the new, compacted
    // segment in the event of a backup failure.
    assert(newSegment->replicatedSegment == NULL);
    newSegment->replicatedSegment = oldSegment->replicatedSegment;
    oldSegment->replicatedSegment = NULL;
    newSegment->replicatedSegment->swapSegment(newSegment);
    
    injectSideSegment(newSegment, NEWLY_CLEANABLE, guard);
    freeSegment(oldSegment, false, guard);
```
doMemoryCleaning 这个比较复杂
- 看代码实现，就是对segment循环两次
```
    // Take two passes, writing out the tombstones first. This makes the
    // dead tombstone scanner in CleanableSegmentManager more efficient
    // since it will only need to scan the front of the segment.
    for (int tombstonePass = 1; tombstonePass >= 0 && !empty; tombstonePass--) {
        for (SegmentIterator it(*segment); !it.isDone(); it.next()) {
            LogEntryType type = it.getType();
    
            if (tombstonePass && type != LOG_ENTRY_TYPE_OBJTOMB)
                continue;
            if (!tombstonePass && type == LOG_ENTRY_TYPE_OBJTOMB)
                continue;
```
  第一阶段就是把tombstones 已经删除的key跳出来，第二遍把其余的跳出来,relocate走不同的流程
  
  这和一个循环做两件事有啥区别么？This makes the dead tombstone scanner in CleanableSegmentManager more efficient since it will only need to scan the front of the segment.
- getSegmentToCompact
- LogSegment* survivor = segmentManager.allocSideSegment(FOR_CLEANING MUST_NOT_FAIL,segment);
- 循环走relocateObject/relocateTombstone
  - relocateObject 查引用，更新hashtable append，否则直接删掉
  - relocateTombstone类似上面的算法，如果有引用，就更新hashtable append，否则就更新tablestat删掉
  - TableStats::decrement

CleanableSegmentManager update，在调用get的时候就会更新，选出需要compact的对象

代码走读

开发者架构入门 https://ramcloud.atlassian.net/wiki/spaces/RAM/pages/6848729/For+New+Developers+-+Understanding+Reads+in+RAMCloud

// StatsLogger logger(context.dispatch, 1.0);

MemoryMonitor monitor(context.dispatch, 1.0, 100);

Server server(&context, &config);

server.run(); // Never returns except for exceptions.

参考资料

图来自https://ramcloud.atlassian.net/wiki/spaces/RAM/pages/6848659/RAMCloud+Presentations?preview=/6848659/42369038/RAMCloud%20LL%20Datacenter%20(Nov%202015).pptx
ramcloud的论文非常多https://ramcloud.atlassian.net/wiki/spaces/RAM/pages/6848671/RAMCloud+Papers 这里尽量总结
CURP总结
- https://keys961.github.io/2020/05/18/论文阅读-CURP/
- https://zhuanlan.zhihu.com/p/59991142
- https://zhuanlan.zhihu.com/p/89598831
内存设计和两阶段清理 http://www.gemini-store.com/2020/04/02/log-structured-memory-paper/