实现一个无锁消息队列

目标

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

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 ...

Bw-Tree:在新硬件平台上的新B-Tree

ARS 与 Bw-Tree

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

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

一些基于key-value(键-值)模型的nosql的内部实现正是使用了Hash表,例如Redis1、memcache、Riak等。

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

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

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

在现代硬件上的Bw-Tree

现代多核CPU

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

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

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

more ...

Windows Azure Storage Made Simple

加机器就是一把梭

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

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

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

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

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

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

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

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

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

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

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

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

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

补充一点理论知识

CAP理论 …

more ...

Metaprogramming in .NET 读书笔记 - 1

什么是 Metaprogramming (元编程)

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

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

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

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

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

元编程的实现

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

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

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

Why do I quit Leetcode contest?

Foreword

The title is quite "Yin-ish" as it seems, but I'm not a "Yin-ist". You know what I mean.

Why I quit?

I did a quite a good job in Leetcode Weekly Contest, at least in my point of view. I won a 4th place and a 6th place in …

more ...