[非技术向]LevelDb源码阅读总结

February 17, 2017 at 1:19 pm

又是一段时间没有更新博客了。这段时间主要有两件事,一件还是在过春节假期,另一件则是在抄写(真正意义上的抄写)LevelDb。抄写的过程根据git的提交记录来看从1月14日到2月16日大约一个月的时间,按照实际的提交次数来看,大约是不到两周,每天约6个小时,抄写的是LevelDb的1.7.0版本,原版本刨去测试性的代码大约1.3万左右,最后总计抄的大约1.2万,因为按照计划昨天应该要干完这件事,今天写个总结,所以稍微有些烂尾(挖坑不填的本性暴露无疑)。整体上基本保证了可运行,昨天或多或少修了重写抄过程中的的一些错误,基本的std::map型的功能可以得到保证,但是真正要拿来用是不太现实的,可能还存在很多bug,代码仅仅自己可以用了吧。本来打算在抄完之后写一点具体一点、技术性强一点的总结,最后发现,毕竟BigTable已经10多年,LevelDb也有六七年的历史了,相关的技术性文章很多,网上中文的源码解析也非常多非常全,所以最后打消了这种想法,打算写一篇对源码阅读抄写的认识、和阅读LevelDb的源码过程中的一些收获。 本文主要有以下几个小节: 1. 对LevelDb源码进行阅读的初衷 2. 源码抄写的一些感想 3. 从抄写中学到的一些东西 这里列出两篇个人觉得LevelDb源码解析的比较技术向、全面、透彻的中文文章以避免吃瓜观众不小心踩了坑不好跳出去: malolk.com/2016/10/11/leveldb-1.19源码阅读/ www.qkldx.net/topic/64/leveldb原理探究与代码分析 对LevelDb源码进行阅读的初衷 LevelDb是由Google的两位大牛Jeffrey Dean和Sanjay Ghemawat编写的开源的持久化KV存储的库(这两位也是BigTable论文的主要作者之二),在写这篇文章时(2017-2-17)已经发布1.18版本,源码现在已经托管在github上,并遵循New BSD协议。LevelDb的最初版本就考虑可移植性,所以现在应该支持大多的主流平台,具体的我就懒得查了。LevelDb自身是以库的形式提供的,而不是一个完整的数据库产品,没有服务器端、通信协议之类的约定,仅仅是做存储,所以阅读LevelDb的源码是无法看到一个完整的数据库的全貌的;LevelDb是inpired by BigTable的,简单地可以理解为BigTable的一个开源实现,它的整体设计,包括MemTable, SSTable,都和BigTable论文中描述的基本一致;我看的是相对早期的版本1.7.0,没有和现在的版本做过完整的对比,但从部分文件的对比来看没发现有什么较大变化;LevelDb 1.7.0由C++写成,有一个简单的C接口,整体大约1.8万行的代码,除去C接口、移植性相关代码、测试相关代码后大约1.3万行,属于可以全部阅读的代码量。 […]

条件变量入门

January 19, 2017 at 10:14 pm

好久没更了呃。最近终于闲下来瞎看了一些东西,但是目前能单独整理出来的并不多,关于条件变量,算是第2次接触了,但是见到的时候还是一脸蒙蔽,所以这次更详细地学了一下。本来打算再看一下用条件变量来解决生产者消费者问题,研究一下条件变量的实现细节的,但是相关内容比较多,而且条件变量目前用到的并不多,所以暂时不多做展开,就是简单入一下门好了。 本文包含一下几个小节: 1. 条件变量及其初衷 2. 条件变量的使用:以pthread库为例 3. c++11中条件变量的使用 条件变量及其初衷 条件变量(condition variable)是多线程编程同步问题中的一个典型设计,和信号量类似,是建立在底层锁结构之上的一种同步机制。通常来讲,条件变量和信号量可以用来实现相类似的功能,比如解决生产者消费者问题,某种意义上可以说,条件变量是简陋版的信号量。条件变量的设计初衷从这个名字本身就可以很明显地体现出来。在多线程环境中,我们经常会遇到这样的场景:某个线程需要等某个条件成立时才能继续进行,而这个条件的成立过程由其它线程来完成。典型的例子是父线程在创造子线程之后,希望等到“子线程运行结束”这个条件结束,再继续执行之后的代码。问题的代码描述如下: void *child(void *arg) { printf("child\n"); // XXX how to […]

无锁编程(三):实现无锁的队列

September 19, 2016 at 4:20 pm

距离上一篇正篇已经隔了整整三个月了,之前学的知识也全都忘光了,无论如何,今天开始慢慢填坑吧。 上一篇我们实现了一个简单的无锁的栈,并且介绍了无锁编程中经常涉及的一些概念,如CAS原语。今天我们开始实现一个无锁的队列。在传统的编程中,队列的实现并不比栈来得困难,但是在无锁编程中,两者还是有显著的差别。在栈中,我们只需关心栈顶这样一个位置的情况,而在队列中,元素从队列的尾部进入队列,却是从头部出去,这样我们就需要兼顾两端在无锁的情况下线程安全。 事实上,在多线程编程中,队列的使用比栈要多得多,所以实现无锁的队列,才真正意味着无锁技术得到了实际应用。 本篇主要包含以下内容: 1. 入队操作的设计 2. 出队操作的设计 入队操作的设计 我们首先来讨论入队操作的设计。在上一节栈的设计中,我们的入栈操作只需保证栈顶得到及时的更新就可以了,但是在入队操作中,我们要进行两个操作,首先将队尾元素的next指针域指向新的元素,接着需要将tail指针也指向这个新的元素。这样我们就需要进行两次CAS操作,初步的想法如下(我们假设节点的结构和上一节的栈的节点结构一致): void enqueue(const T &val) { Node *node = new Node; […]

无锁编程-番外篇(一):并发正确性条件

July 17, 2016 at 3:03 pm

关于并发条件下的正确性,实际上是并发编程的基础,在最初打算总结这个系列的时候,本来是将这部分内容放在第一篇来讲的,但是这部分东西比较偏理论,容易造成看了不知道在讲什么的感觉,所以最终还是把它移到了番外篇中,剧情则是接在正篇的第二篇之后。本文可能会引用第一篇和第二篇当中的一些内容作为补充的例子,但是整体上是偏于独立的。 文章的大概分布如下: (1)并发以及正确性条件 (2)静态一致性 (3)序列一致性 (4)线性一致性 (5) 阻塞与非阻塞、无锁 (6)静态一致性和序列一致性的差别 (7)序列一致性和线性一致性的差别 这部分网上的资料查找下来感觉相对较少,查到的资料也大多比较晦涩、术语比较多,本文还是希望可以以直白的语言介绍相关的概念,如果有空再补充上比较数学化的部分。 由于我对这部分的内容也是基本上从完全不知道到慢慢了解这样一个过程,所以本文的行文顺序不会从一开始就把每一个概念都解释得非常清楚,那样会导致关于每一个概念的东西一下子变得非常的多,而这些概念之间相互又有关系,最终就变成了一本难以阅读的教科书;本文的顺序是先初步这些概念,对这些概念一个模糊的影响之后,再逐步介绍、解释其中比较模糊的部分,并通过实例来进行更好地说明,希望通过这种方式可以达到先是“好像大概知道是个什么东西了”然后是“原来是这样一个东西”的感觉。 并发以及正确性条件 并发(concurrency)这个名词大家都不陌生,从单词的角度来说,就是指一些事情同时发生。从计算机的角度来讲,指的是对某些内容的同时访问,一个典型的例子就是多个线程对同一块内存进行并发的访问;对于一个实际例子来说的话,可能是多个线程同时往一个共享的队列里进行入队操作。在研究并发编程之前,我们首先回顾一下非并发的操作。所谓的非并发也称为序列(sequential),表示按照固定的顺序执行操作。在当前的线程模型中,如果是一个单线程程序,那么它执行操作的方式就是序列性的,最终它的操作会变成一条条按顺序执行的机器码。 在单线程模型中,对于一个功能,或者说一个数据结构,比如队列,它的实现是否正确,是很容易去判断的。一个队列A,如果先是1入队,再是2入队,那么接着进行出队操作,获得的必然是1;如果获得的不是1,那么显然这个数据结构的实现是有问题的。在这里,一个方法的调用可以看作一个点或者一个事件,不必考虑它执行的时间,而仅仅考虑这个方法所带来的对象状态的转变。对于方法enq(1),会将一个队列从空的状态到队列头部有1的状态。 但是在多线程模型中,要定义正确性就比较困难了。在多线程模型中,不能再将方法看成一个点了,而是看成一个区间。这个区间的起点是这个方法被调用(invocation)的时间,而这个区间的终点就是这个方法调用返回(response)的时间。或者说把一个方法看成两个事件,一个是被调用事件,一个是应答事件。如果一个方法已经发生了调用事件但还没有发生应答事件,那么称这个方法处于待定状态(pending)。简单地说,就是这个方法已经被调用了但是还没有返回。 假设一个队列Q,线程A将1入队,同时线程B将2入队,那么在这之后线程C进行出队操作,得到的是多少才算是正确的呢?这实际上取决于我们的应用场景的实际需求。为此,我们下面介绍三种用来衡量程序的实现是否正确的条件:静态一致性、序列一致性和线性一致性。在此之前,我们先给出这几个正确性条件都具有的一个通用的原则。 设想一个数据结构实现了类似寄存器的功能,线程A往里写入7,同时线程B往里写入-3,那么最终线程C从中读取时应该读取7还是读取-3呢,取决于具体的情况,但是我们显然不愿看到读到-7的情况,即读到的值是两个线程操作的一个混合。 原则1:所有的操作都必须按照某种顺序依次执行。 也就是说,不论中间发生的过程是怎么样的,最终给我们的结果和按照某一顺序依次执行这些操作的效果是一样的,我们不希望看到这种混合的无效状态,对于上面的例子,我们要么读到7,要么读到-3。 […]

无锁编程(二):无锁的栈

July 16, 2016 at 11:28 am

在第一篇介绍了无等待(wait-free)和无锁(lock-free)的基本概念之后,第二篇通过实际的无锁的堆栈的例子,从代码的角度上去理解无锁。本文主要分成以下几个部分: 1. 普通的堆栈 2. 有锁的堆栈 3. CAS操作 4. 无锁的栈 由于仍然是本系列起步的部分,所以一步步从最普通的堆栈开始讲起。 普通的堆栈 这里所说的堆栈也就是传统意义上FILO的线性数据结构,这里我们采用链表的形式进行栈的设计,下面是一个简单的堆栈的实现。 template <typename T> class Stack { public: struct […]

无锁编程(一):无锁的基本概念

July 3, 2016 at 5:19 pm

不知不觉又要开一个新的系列了,之前还有无数的系列,还有无数的坑要填,接下来还有找工作...... 由于最近一直在接触无锁方面的内容,为了不让学到的东西打水漂,在这里开一个系列记录一下学习到的东西。理想中的目标是从无锁编程的基本概念讲起,逐步完成一个无锁的栈、无锁的队列、无锁的链表,最终实现一个无锁的跳表,当然,整个系列可能又会跨度很长甚至太监,一贯如此...... 作为本系列的第一篇文章,我们通过一些例子,理解所谓的无锁(lock-free),对“无锁”这个词有一个粗略的理解,在后续的文章中,会对这个概念进行展开,从而较为全面地理解无锁。 无锁(lock-free, lock-freedom)是一个比较难定义的概念。第一,这个概念在过去有很多不同的意思,近年才逐渐收敛,大家才统一了它的意思,这不仅仅是在国内如此,国外也是一样;第二,这个已经被统一的概念非常的拗口,而且初看时也很难理解到底为什么要有这样的定义。无论如何,这个概念在逐步的发展中,在很多地方发挥了传统的编程模型所不能做到的一些优美的特性。 我们先简单地回顾一下锁,这里以互斥锁为例。 pthread_mutex_t mutex; void *print_msg(void *arg) { pthread_mutex_lock(&mutex); for (int i=0; i<15; ++i) { printf("output […]