背景

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 …

书接上文 - 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号 …

一致性协议 - Paxos

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

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

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

Paxos算法

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

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

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

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

划重点：

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

背景

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

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

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

大侦探毛利小五郎

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

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

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

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

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

什么是容斥原理

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

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

容斥原理的应用

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

考虑一个问题

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

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

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

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

与此同时 …

目标

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

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 …

Update[220504]: 原来这种数据结构叫珂朵莉树啊，真神奇。。。

我们要解决什么问题

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

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

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

类似的还有Merge Intervals：

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

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

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

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

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

以及

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

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

传统解法

对于这类区间问题，传统的解法是将区间使用顺序容器（如vector …

ARS 与 Bw-Tree

nosql数据库从本质上说，都属于ARS（Atomic Record Stores，“原子记录存储”）。

最常见的“原子记录存储”一种实现就是朴素的Hash表：通过一个特定的key，来读写一条独立的数据记录。

一些基于key-value（键-值）模型的nosql的内部实现正是使用了Hash表，例如Redis¹、memcache、Riak等。

而有一些nosql数据库为了支持高效的key-sequential（键-序列）查找，采用了tree-based²数据结构进行数据存储，所以B-Tree成为了一些数据库（both nosql and sql）的首选。

本文介绍了一种基于新型硬件的高性能ARS实现，其核心技术有：

1. 页式内存管理
2. Bw-Tree，一种基于B-Tree的树存储结构
3. 基于日志的存储管理

在现代硬件上的Bw-Tree

现代多核CPU

多核CPU带来了高并发，但是同时也引入了锁竞争和缓存失效问题。

为了讲解锁竞争，这里我们举一个经典的例子：多线程计数器。

我们都知道，如果不使用锁来保护计数器变量的话，那么最终的结果几乎不可能是正确的。多个线程中 …

加机器就是一把梭

没有什么问题是加一千台机器解决不了的，如果有，就再加一千台。
—— 《21天精通分布式系统》

分布式系统在设计之初，是为了解决单机系统的可用性和可扩展性问题的。

举个例子，单机系统就是雇一个小弟替你干活，但是这个小弟不太靠谱，偶尔泡个病号不上班，偶尔工作太多一个人干不过来。

分布式系统就是雇一群小弟帮你干活，偶尔有一两个小弟泡病号，我们会有富裕的人力顶上，工作太多我们可以继续拉新的小弟入伙，美滋滋。

这个比喻很好的描述了单机系统和分布式系统之间的关系。所以一种可能的分布式系统就是这个样子的：

我们将相同功能的服务器组成一个整体，通过一个load balancer对外提供服务。

这样的系统初步解决了我们的问题，在面对可扩展性和可用性的问题时，我们会：

• 容量不足就加机器
• 单机挂掉了就把流量调度到其它的节点上

不过单纯的加机器并不能完全满足我们的需要。对于CPU密集型的服务，增加副本数可以有效的均摊计算压力，但是对于存储密集型的服务，我们需要增加分库逻辑才能有效的增加系统的计算能力。

例如我们有100G的数据，但是数据库的容量最多只支持50G。这样无论怎么样增加副本都不能解决问题。如果我们将100G的数据均分，存储在两个50G的分库上，我们就可以支持单机系统容纳不了的数据了。

我们还可以把多个这样的分布式子系统组合起来，就可以组成一个小有规模的分布式系统了。现在我们在使用的一些服务，仍在使用这种模型。

上面分布式模型虽然有效，但是引入了一个严重的问题：因为节点之间是隔离的，并且只能通过消息传递进行通信与协调，所以基本无法完全保证副本之间保持一致的内部状态。

这就是所谓的一致性问题。

补充一点理论知识

CAP理论 …

什么是 Metaprogramming (元编程)

元编程从字面上理解就是“能处理程序的程序”。

这里的“处理”，有两个意思。

一是“编写”、“生成”，最经典例子就是编译器，它将我们的所编写的高级语言翻译成机器代码。编译器就像建筑工人，将“蓝图”（高级语言）转化成“高楼大厦”（机器语言）。还有一个我们经常用到的就是“宏”(Macro)。我们可以在代码中使用预先编写好的宏，在编译期，宏会被自动展开成相应的代码。这样的好处是用机器带替人类劳动。

“处理”的另外一个意思就是“处理自己”，元编程让程序在运行时了解自己的状态，并动态的扩展并执行的相应逻辑。

当然，最高级的“处理”就是能完全代替人脑的人工智能。如果那一天到来，我们就距离生活在Matrix里不远了。

元编程的实现

元编程主要实现在编译期前后以及运行时。

元编程主要依赖于以下技术：

• 代码生成(code generation)
• 反射(reflection)
• 汇编重写(assembly rewriting)
• 表达式 …