6.824 Lab 2: Raft协议实现指南 (无剧透版)

背景

MIT6.824是一个用来学习分布式系统的非常好的资源。其中第二个课程作业就是关于Raft算法

由于在工作中涉及到分布一致性算法的调研,接触了paxos/raft算法。然后被@neutronest安利了一发,于是开始着手实现这个作业。

本文是我对这个项目的实现总结。希望能在划出重点的同时,不涉及实现细节,避免破坏大家的写代码体验。

本文唯一参考资料:In Search of an Understandable Consensus Algorithm

任务分解

在官方文档里,整个项目被分成了2A、2B、2C三个部分:

  • 2A - 投票与选举
  • 2B - 一致性
  • 2C - 可持久化

实际上,2C的工作量非常少,我们可以把2B和2C合成一个。然后单独提出几个比较重要的测试用例,划分成子项目。任务分解如下:

  • 2A - 投票与选举
  • 2B/2C - 一致性和可持久化
  • 三个难度比较高的Case
    • Test (2B): leader backs …
more ...

白话一致性协议 - Paxos、Raft和PacificA[2]

PacificA是一个框架

虽然在题目中我们把Paxos、Raft和PacificA并列,但是Paxos和Raft在论文中称自己为一种“算法”(algorithm);而PacificA对自己的定位是一种通用的,强一致的数据同步框架

在论文中,作者提到现有的可证明的数据同步协议往往过分简化了性能问题,导致看起来很美的理论设计无法转变有实际的系统(注:本篇论文应该早于Raft的论文)。所以作者的目标是将算法理论与实际相结合,进行相应的系统设计。

PacificA的实现

与Paxos和Raft不同的是,PacificA采用的算法非常简单。所以在这里我不进行太多铺垫,直接进入正题。

主从同步

PacificA使用了主从同步模型,用户的读写请求都会发往主节点,以保证强一致性。

主节点会对发来的写请求进行编号,使得所有写请求编号唯一且单调递增。这个编号也会同步到从节点。

无论是主节点还是从节点,所有的写请求都写入一个只追加的日志。主从节点都需要维护committed指针,代表在这个指针之前的数据都已经被所有节点所认可,处理“已确认”状态。从节点需要额外维护一个prepared指针,代表在这个指针之前所有的数据都处于“待确认”状态,而在prepared指针之后的数据,都是“待同步”状态。

主从之间的数据同步使用两步提交模型 …

more ...

C++类型擦除与`std::function`性能探索

什么是类型擦除

对于Python这种动态类型语言来说,是不存在“类型擦除”这个概念的。Python对象的行为并不由接口定义,而是由“当前方法和属性的集合”决定。

所以,以下的代码是完全合法的:

class Foo(object):
    def print(self):
        print 'foo'

class Bar(object):
    def print(self):
        print 'bar'

def do_print(obj):
    print obj.print()

do_print(Foo()) // print 'foo'
do_print(Bar()) // print 'bar'

但是对于C++这种静态类型语言来讲,我们就不能使用这种语法:

class Foo {
public:
    void print() { cout …
more ...

在WSL中获取Windows剪贴板中的图片

背景

Win10里面的WSL(Windows Subsystem For Linux)算是一个开发神器了,虽然功能不是100%完善,但是对于轻度开发已经足够了。现在我的日常开发,就是一个全屏CMD跑内部工具,一个全屏WSL跑tmux+vim。

(跑题了)

问题

之前的文章里,我有写到使用github做为图床,并且使用python脚本进行图片上传。但是仍有一点问题,就是之前的脚本只能上传文件,不能直接上传剪贴板里的图片。

解决

发现Windows里面有内置的访问剪贴板工具,但是只在powershell下可用。不过我们可以在WSL里直接调用exe文件(这点非常神奇),然后读出图片文件放入临时文件夹。然后我们再读出这个文件进行上传。

总的流程仍然是上传已有的图片文件,但是我们把它放在临时文件夹并隐藏了起来。看起来就是实现了WSL和Windows剪贴板的互操作。

#!/bin/bash

TMP=/mnt/c/Users/me/AppData/Local/Temp/
TMPWIN=C:\\Users\\me\\AppData\\Local\\Temp\\

ts …
more ...

白话一致性协议 - Paxos、Raft和PacificA[1]

书接上文 - Multi Paxos

在上一篇文章中,我们提到了Basic Paxos和Multi Paxos的异同。在Paxos Made Simple论文中,作者提到了Multi Paxos的一种实现。这个实现允许我们对一个连续的数据流(也可以称为复制日志,replicated log)达成共识,从而实现节点状态的一致性复制。

确定性状态机

我们可以将系统中的每一个节点抽象为一个有着确定性状态机,即给定多个状态一致的状态机,在执行同一个命令之后,其状态仍保持一致。(可以想一想编译原理里面的DFA)

Leader - 系统中唯一的proposer

如果系统中存在有多个proposer,那么就很可能会出现多个提案相互干扰的情况。虽然根据证明,最终这些提案都会收敛到一致,但是性能会非常低下。所以我们可以在系统中通过选举,选出一个leader做为主proposer(distinguishied proposer),所有的提案都由leader提出。

这样一来,在绝大多数情况下都不会出现提案相互干扰的情况。只有在leader切换的瞬间,可能会出现相同编号的不同提案,但是我们的算法可以很好的处理这种情况。

分布式系统中的“TCP”

类似于TCP协议中序列号,Multi Paxos中的每一个命令都有一个递增的编号。即我们前一个执行的命令是100号,那么下一个执行的命令一定是101号 …

more ...

白话一致性协议 - Paxos、Raft和PacificA[0]

一致性协议 - Paxos

在分布式系统当中,我们往往需要保持节点之间的一致性。在绝大多数情况下,我们需要让系统中的节点相互协调通力合作,有可能的让系统正确的工作。但是,由于分布式系统本身的特性,需要我们在不可靠的硬件上尽可能的构建可靠的系统。所以,看似简单的一致性问题成为了分布式系统领域的一个重要的课题。

Paxos算法是Leslie Lamport于1990年提出的一种一致性算法。也是目前公认解决分布式一致性问题最有效的算法之一。

Paxos算法的目标是在一个不可靠的分布式系统内,只通过网络通信,能够快速且正确地在集群内部对某个数据的值达成一致。并且保证不论发生任何异常,都不会破坏系统的一致性。

Paxos算法

另一种(简化了的)形象的问题描述 - 买车位

某小区的一些居民在抢车位,而车位只有一个。居民们达成协议,只要一个报价获得半数以上居民认可,那么提出这个出价的居民则获得了车位的所有权。

居民之间非常友善,如果知道了车位已经有了买家,就不会继续出价购买,并且会帮忙传播这个信息。

居民们都是遵纪守法的好公民,在整个过程中都只会如实的与其它用户分享信息。信息的分享是在网上,通过一对一的私密聊天进行。但是小区的手机信号非常差,我们不能保证通信的质量,一些信息可能会丢失。但是居民不会掉线。也不会失去记忆,并且通信的内容是完整的,不会被篡改的。

划重点:

  1. 需要半数以上居民的认可,才能声称拥有车位。这个居民被称为车位的“公认拥有者 …
more ...

七牛云图床自救指南(附github图床小工具)

背景

之前一直在用七牛云的存储做图床(简称白嫖)。但是免费的午餐必然不会长久,七牛要求所有bucket都要绑定备案过的域名,否则就停掉你的bucket的外链。这事我也不吐槽啥,毕竟是白嫖,也不能要求啥。

但是最智障的是,你外链停了没关系,但是我在后台portal查看文件,上面的图还是显示不了,点下载也没有反应,只显示“ [5402] 获取 bucket 域名失败”。说好不嫖了,你却又不让我走了,都没办法数据迁移的。

因为博客里的图全都存在了七牛的图床上,这么一波搞下来就非常伤。于是我积极展开自救行动。

大侦探毛利小五郎

我:你看我们天天查问题,像不像柯南在查案子?
同事:我觉得我们更像毛利小五郎。

大胆猜测七牛的portal也是使用了外链的URL,如果不绑域名的话,是没有文件的URL的。但是我手里又没有备案后的域名。事情就陷入了僵局。

七牛提供了小工具(qrsctl)让我们管理文件,我觉得这可能是个突破点,万一小工具可以把数据下载下来呢?结果也是不行,这就非常GG了。

此时,我又发现小工具有拷贝数据的功能,可以把跨bucket拷贝数据,但是我的所有的bucket都没有绑域名。也并不能解决问题。

我突然又想到,七牛云其实并没有完全禁止外链 …

more ...

容斥原理以及一些题目

什么是容斥原理

容斥原理是一种计数手段。例如在下图中,我们想不重复、不遗漏的求出包含在ABC三个集合中所包含的元素的个数,应该使用怎么样的方法呢?

image

formula

这个问题对于我们来说并不陌生,当然也并不困难。直观的方法是把所有的元素计数,再把重复的元素排除出去。这种计数的方法,有“容”有“斥”,我们讲其称做“容斥原理”。

容斥原理的应用

小规模的计数问题自然难不倒我们,我们甚至可以使用visit[]数组来记录某元素是否出现。但是当问题的规模增大时,使用数组记录这种方式需要使用更多的内存,在很多情况下,这是我们不能接受的。

考虑一个问题

问题:统计在1~N中的,能被2或3整除的数。(1 <= N <= 1e9)

我们先把这个问题拆成两部分来看:

  1. N以内的,能被2整除的数
  2. N以内的,能被3整除的数

这两个问题都非常简单,我们可以直接使用除法进行求解,其结果分别为N/2N/3

与此同时 …

more ...

实现一个无锁消息队列

目标

实现一个多读多写的无锁消息队列。

cmpxchg - 比较并替换

比较并替换(compare-and-swap, CAS)是一个用于多线程同步的原子操作。

其工作流程是:

def cmpxchg(val, oldval, newval):
    if val == oldval:
        val = newval
        return True
    return False

也就是说,只有当val等于oldval时,我们才会将val的值替换成newval。在多线程的场景下,cmpxchg用来保证多线程写的原子性。

例如,线程1和线程2都要写入val变量,但是我们需要保证只有一个线程能写成功。使用cmpxchg,能保证只有一个线程能成功的将val变量替换成新值,写失败的线程会得到False的返回值。

ACCESS_ONCE - 消除优化歧义

#define …
more ...

一种区间交问题的奇怪姿势

我们要解决什么问题

区间交问题,是我们在做题中经常遇到的问题。

例如,Insert Interval一题,就是比较直白的区间交问题:

给定一系列的整数区间,再插入一个新的区间,问合并后的整数区间是什么

类似的还有Merge Intervals

给定一系列可能有重叠的整数区间,求合并后的整数区间

另一种区间交问题的描述是时间区间相关的问题,如Time Intersection:

给定用户A和用户B的在线时间区间,问两人同时在线的时间区间

又如经典的会议室安排问题Meeting RoomsMeeting Rooms II:

给定N个会议的时间区间,问一个人能否参加所有的会议

以及

给定N个会议的时间区间,问最少需要多少个会议室

还有系统设计与API设计包装后的算法题Range Module。归根结底,都是整数区间问题的变形或者包装。

传统解法

对于这类区间问题,传统的解法是将区间使用顺序容器(如vector)保存,在查询和修改时,使用“排序+遍历”或者 …

more ...