LevelDB 源码阅读之 Compaction

要谈论 LevelDB 的 Compaction 就不得不从 LevelDB 的整个数据写入流程入手。LevelDB 的基本写入流程大致为:

  1. 数据先写入到 WAL 日志中,做持久化
  2. 然后数据同步到mutable memtable
  3. mutable memtable大小达到Options.write_buffer_size设置的大小时,就会变成immutable memtable,并且创建一个新的mutable memtable
  4. 后台的 Compaction 线程会把immutable memtabledump 成 sstable 文件,并设置于 Level 0 层
  5. 当 Level i 达到一定条件后,就会和 Level i + 1 层的 sstable 进行合并,从而触发 Compaction 过程,并在 Level n + 1 层生成一个新的 sstable 文件

在 LevelDB 中,Compaction 大体上可以分为两类,分别是:

  • immutable memtable compaction,也叫做minor compaction,指的是将immutable memtabledump 到 sstable 文件的过程
  • sstable compaction,也叫做major compaction,指的是 sstable 文件之间的合并过程

而对于sstable compaction又可以细分为三种:

  • manual compaction,是指外部通过调用DBImpl::CompactRange接口触发的
  • size compaction,是指程序根据每个 Level 的总文件大小通过一定规则自动触发的
  • seek compaction,每个 sstable 文件内部维护了一个seek miss的 counter,当达到一定条件的时候,LevelDB 就认为这个文件需要 Compact

DBImpl::BackgroundCompaction的代码逻辑中不难看出,这些 Compaction 策略的优先级为:

分布式协议

  • 在可能存在叛军的情况下,采用合适的通讯协议,让多个将军达成共识,执行统一的作战计划
  • 二忠一叛难题
  • 它是分布式领域最复杂的容错模型
  • 莱斯利·兰伯特(Leslie Lamport)The Byzantine Generals Problem

拜占庭将军问题:三个将军的通信场景

叛军存在时的消息传递

  • 总共有三个将军,其中一个作为指挥官
  • 通过信使相互传递作战指令,进攻或者撤退
  • 所有忠诚的将军必须执行统一的作战计划,忠诚的将军必须执行忠诚的指挥官发布的指令
  • 假如 LIEUTENANT2 叛变,LIEUTENANT1 收到的作战指令就是“进攻,撤退”
  • 假如 COMMANDER 叛变,LIEUTENANT1 和 LIEUTENANT2 收到的作战指令都是“进攻,撤退”
  • 叛变人数为 m 需要已知
  • 则所有参与者的人数至少为 3m+1
  • 第一轮由指挥官发送作战指令
  • 第二轮由各位将军相互发送指令
  • 收到指令的将军按照少数服从多数的原则执行指令
  • 按照这个公式,前面的例子叛军为 1 人的情况,则需要 1 个指挥官和 3 个将军

将军叛变时的共识过程

假如 LIEUTENANT3 叛变了,那么首先指挥官向各位将军发送“进攻”的指令,由于 3 号将军叛变了,所以最终 1 号将军收到的指令是 2 个进攻,1 个撤退,2 号将军同样收到 2 个进攻,1 个撤退,这样忠诚的将军将会执行一致的指令

指挥官叛变时的共识过程

假如 COMMANDER 叛变了,分别向 1 号将军发送了“进攻”,向 2 号将军发送了“撤退”,向 3 号将军发送“进攻”,那么通过第二轮的协商后,1,2,3 号将军得到的指令都是“进攻,进攻,撤退”,这样按照少数服从多数的原则,忠诚的将军最终执行了一致的作战指令。

基于公司私有gitlab的go module实践

我们 laser 存储为了更好的跟引擎对接,适应其他团队的技术生态,决定开发一套 golang 的公共库来给大家使用。于是我们在公司私有的 gitlab 上新建了一个项目:git.yourcomp.com/ad/ads_core/adgo,并且我们想使用单一的 codebase 来管理所有的公共 library.

而且,为了更好的管理模块,我们统一使用了 go mod。

按照平时我们在 github 上拉取 go library 的惯例,我本以为直接使用go get git.yourcomp.com/ad/ads_core/adgo/xxx就能直接拉取到相应的模块了,然而在开发完功能测试的时候却发现,事实并不是想象中那样。

执行go get后,实际上会请求"https://git.yourcomp.com/ad/ads_core/adgo?go-get=1"这个地址,如果使用-insecure选项,则会请求"http://git.yourcomp.com/ad/ads_core/adgo?go-get=1",正常情况下回返回meta tag:

<html>
  <head>
    <meta
      name="go-import"
      content="git.yourcomp.com/ad/ads_core git http://git.yourcomp.com/ad/ads_core.git"
    />
  </head>
</html>

这是 go remote import 的协议,meta tag 的格式一般为

使用c语言模拟lisp语法

使用 c 语言的 macro 操作,能够很简单的用 c 语言模拟 lisp 语法。

#ifndef LISP_H_OTE1HWPK
#define LISP_H_OTE1HWPK

#include <stdio.h>
#include <stdlib.h>

#define define(ret, name, args, block) \
    ret name args { return block; }

#define if(expr, block1, block2) \
    expr ? block1 : block2

#define eq(a, b) \
    a == b

#define neq(a, b) \
    a != b

#define sub(a, b) \
    a - b

#define mul(a, b) \
    a * b

#define add(a, b) \
    a + b

#define div(a, b) \
    a / b

#endif /* end of include guard: LISP_H_OTE1HWPK */
define(int, factorial, (int n),
       if(eq(n, 0),
          1,
          mul(n, factorial(sub(n, 1)))))

define(int, main, (void),
       (printf("10! = %d\n", factorial(10)), EXIT_SUCCESS))
CFLAGS = -Wall -include "lisp.h"

TARGET=factorial

all:
	gcc -o $(TARGET) $(TARGET).c $(CFLAGS)

clean:
	rm -f $(TARGET)
liubang@venux-dev:~$ make
gcc -o factorial factorial.c -Wall -include "lisp.h"
liubang@venux-dev:~$ ./factorial
10! = 3628800

Spring Boot With BDD

BDD(Behavior Driven Development),行为驱动开发,是一种敏捷软件开发的技术,它鼓励软件项目中的开发者、QA 和非技术人员或商业参与者之间的协作。

BDD 的重点是通过与利益相关者的讨论取得对预期的软件行为的清醒认识。它通过用自然语言书写非程序员可读的测试用例扩展了测试驱动开发方法。行为驱动开发人员使用混合了领域中统一的语言的母语语言来描述他们的代码的目的。这让开发者得以把精力集中在代码应该怎么写,而不是技术细节上,而且也最大程度的减少了将代码编写者的技术语言与商业客户、用户、利益相关者、项目管理者等的领域语言之间来回翻译的代价。

结合我们项目开发使用的 spring boot 2.x,下面我们来具体说明如何在实际项目中使用 BDD。

<cucumber.version>4.2.5</cucumber.version>

...

<dependency>
    <groupId>io.cucumber</groupId>
    <artifactId>cucumber-junit</artifactId>
    <version>${cucumber.version}</version>
    <scope>test</scope>
</dependency>

<dependency>
    <groupId>io.cucumber</groupId>
    <artifactId>cucumber-java</artifactId>
    <version>${cucumber.version}</version>
    <scope>test</scope>
</dependency>

<dependency>
    <groupId>io.cucumber</groupId>
    <artifactId>cucumber-spring</artifactId>
    <version>${cucumber.version}</version>
    <scope>test</scope>
</dependency>

BDD 其实也是依赖 junit,然后调用Cucumber的 Runner 来运行相应的测试。

多线程编程

这篇文章主要是为了帮助大家熟悉 POSIX 线程库以及在实际开发中使用它的特性。我们会具体讲解如何利用这个线程库定义的不同工具 来解决编程中的问题。当然这里隐含了一个假设,就是读者已经了解过并行编程(或者多进程)的相关概念,如果没有这些背景知识 的话,读者可能会感觉到很难理解。不过也没关系,我的另一篇教程里边有专门为只具备线性编程思维的读者提供了对并行编程理论 和相关术语的讲解。

同样的,我假设聪明的你已经熟悉了异步编程模型,那些经常使用桌面环境的人会更容易去接受多线程编程的理念。

当我们谈到 POSIX 线程的时候,肯定会有人心生疑惑:“我们应该使用哪个标准下的 POSIX 线程?”。由于 POSIX 线程标准已经修订了好 多年,人们会发现,依据不同标准的实现有不同的函数集,不同的默认值和不同的细微差别。所以在此说明的是,本教程使用的是 v0.5 版的 Linux 内核中的线程库,使用其他操作系统和使用其他版本的读者,需要阅读一下你们对应的系统文档来同本文中的实例进行对应。同时,有些示例代码中使用到了阻塞式的系统调用,它们不能再用户级的线程库中很好的工作(参考另一篇文章:parallel programming theory tutorial 来获取详细信息)。好了,说了那么多,主要是为了能保证文章中的示例代码能够在其他系统中正常使用,从而提高跨平台性。

线程是一个迷你版的进程,它们拥有自己的栈,能够执行给定的一段代码。但是不同于进程的是,线程通常与其他线程共享记忆体(而 每个进程都拥有一个独立的记忆体区域)。一个线程组就是一个执行相同代码的线程的集合,他们共用记忆体,可以访问相同的全局变 量,拥有同样的文件描述符等等,他们以并行的方式执行(可能是时间片的方式,或者对于多核心系统,他们会真正平行执行)。

使用线程组而不是普通顺序执行程序的好处是多个操作可以同时进行,当一些事件产生的时候,他们能立马被处理(例如:如果我们有 一个线程处理用户接口,另一个线程处理数据库查询,那么我们可以在处理很多用户查询的同时,依然能够响应用户的输入)。

使用线程组而不是进程组的好处是线程间的上下文切换要比进程间的上下文切换要快很多(上下文切换是指系统从一个正在运行的线程或进程切换到去执行另一个线程或进程)。此外,线程间的通信也远远比进程间通信要高效很多。

线程编程有利也有弊,由于线程组共享记忆体,如果一个线程破坏了记忆体,那么其他线程也要受到牵连。但是进程就不同了,操作系 统会将进程之间隔离开,如果一个进程破坏了它的记忆体,那么其他进程不会受到影响。使用进程的另一个好处是,不同的进程可以运 行在不同的机器上,但是线程必须运行在同一台机器上(至少通常情况下是这样的)。

当一个多线程程序启动执行到main()函数的时候,就会有一个线程运行,这是一个全程线程(full-fledged thread,或者叫主线程),如果想创建一个新的线程,程序中需要使用pthread_create()函数

#include <stdio.h>
#include <pthread.h>

void *do_loop(void *data)
{
    int i; // counter, to print numbers
    int j; // counter, for delay
    int me = *((int *)data);
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 50000; j++) // delay loop
            ;
        printf("'%d' - Got '%d'\n", me, i);
    }

    // terminate the thread
    pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
    int       thr_id;    // thread ID for the newly created thread
    pthread_t p_thread;  // thread's structure
    int a = 1;           // thread 1 identifying number
    int b = 2;           // thread 2 identifying number

    // create a new thread that will execute 'do_loop()'
    thr_id = pthread_create(&p_thread, NULL, do_loop, (void *)&a);

    // run 'do_loop' in the main thread as well
    do_loop((void *)&b);

    return 0;
}

上述这段代码需要特殊说明的是:

使用正则表达式开发一个高性能路由

原文地址:http://nikic.github.io/2014/02/18/Fast-request-routing-using-regular-expressions.html

前一些日子,我发现了一个叫做Pux的路由库,这个路由库声称自己比现有的路由要快很多,为了实现这个特点,该库使用了 C 语言编写了 PHP 扩展。

然而,当我瞅了几眼它的代码后,我非常怀疑这个库在路由过程中做了错误的优化,而且我能够很容易在不适用扩展的情况下做出更高性能的实现。 当我在看了 benchmarking 代码后更加确定了我的怀疑,因为我发现这里仅仅只是对及其确定的单个路由做了测试。

为了进一步研究这个问题,我写了一个轻量的路由库:FastRoute。这个库中实现的分发过程接下来我会具体描述。为了给出一些前期印象,这里先给出一个 同 Pux 库的 benchmark 结果:

1 placeholder  | Pux (no ext) | Pux (ext) | FastRoute
-----------------------------------------------------
First route    | 0.17 s       | 0.13 s    | 0.14 s
Last route     | 2.51 s       | 1.20 s    | 0.49 s
Unknown route  | 2.34 s       | 1.10 s    | 0.34 s

9 placeholders | Pux (no ext) | Pux (ext) | FastRoute
-----------------------------------------------------
First route    | 0.22 s       | 0.19 s    | 0.20 s
Last route     | 2.65 s       | 1.78 s    | 0.59 s
Unknown route  | 2.50 s       | 1.49 s    | 0.40 s

这个 benchmark 使用了 100 个路由,分别对最好和最坏的情况做了测试。而且分两个方面进行:一个是只包含一个占位符的路由,另一个是包含 9 个占位符的路由。整个过程 重复了上千次。

c++编程之标准库和STL

C++提供了很多库:

  1. 标准 ANSI C 库都可以移植到 C++中。不同于 ANSI C 库的是,C++中需要在库名前加上"c"前缀,而且去掉".h",例如<cmath>对应于 C 语言就是<math.h><cstdlib>对应于 C 语言的<stlib.h>
  2. C++新增的库,例如 <iostream><iomanip><string><fstream><sstream>
  3. C++STL:包括容器,迭代器,算法和函数对象
  4. Boost C++库
  • <cstring>:待会解释
  • <cmath>:数学计算相关的库
  • <cstdlib>:通用工具,例如异常(abort, exit, EXIT_SUCCESS, EXIT_FAILURE);环境相关(getenv);动态内存管理(malloc, free, calloc, realloc),字符解析(atoi, atof, atol, strtod), 伪随机序列生成(rand, srand, RAND_MAX);数组搜索和排序(bsearch, qsort)
  • <cctype>:字符类型检测(isalpha, isdigit, isalnum, isspace, isupper, islower, isblank, iscntrl, isgraph, isprint, ispunct, isxdigit)和字符转换(toupper, tolower)
  • <climits>, <cfloat>:Size and limit of integer types (INT_MAX, INT_MIN, UINT_MAX, CHAR_BIT; and SHRT_XXX for short, LONG_XXX for long, LLONG_XXX for long long, CHAR_XXX for char) and floating-point types (DBL_MIN, DBL_MAX, DBL_DIG, DBL_MIN_EXP, DBL_MAX_EXP; and FLT_XXX for float, LDBL_XXX for long double)
  • <ctime>:time, difftime, clock, gmttime, localtime, and etc.
  • <cstdio>: C’s IO operations (scanf, printf, fscanf, fprintf, fopen, fclose, etc)
  • <cassert>, <cerrno>, csignal>: 断言和错误
  • <clocale>:本地化
  • <cstdbool>, <cstdint>, <cstddef>, <cstdarg>:
  • <cuchar>, <cwchar>, <cwcchar>: Unicode 字符
  • <ios>, <iostream>, <istream>, <ostream>, <fstream>, <sstream>
  • <iomanip>
  • <string>
  • <regex>
  • <random>
  • <limits>
  • <stdexception>, <exception>
  • <complex>, <tuple>, <valarry>
  • <locale>
  • <typeinfo>
  • <chrono>
  • 其它:<codecvt>, <new>, <ratio>, <system_error>, <type_traits>

STL 主要由以下头文件提供:

c++编程之字符和字符串

在头文件<cctype>(相当于 C 语言中的<ctype.h>),包含了一下字符处理函数:

FUNCTIONEXAMPLE
int isalpha(int ch);//如果 ch 是字母,返回 1,否则 0
int isdigit(int ch);//如果 ch 是数字,返回 1,否则 0
int isalnum(int ch);//如果 ch 是字母或数字,返回 1,否则 0
int isxdigit(int ch);//如果 ch 是十六进制数字[0-9A-Fa-f],返回 1
int isupper(int ch);//如果 ch 是大写字母,返回 1
int islower(int ch);//如果 ch 是小写字母,返回 1
int toupper(int ch);//转成大写字母
int tolower(int ch);//转成小写
int isspace(int ch);
int ispunct(int ch);//是否是标点符号
int iscntrl(int ch);//是否是 control
int isprint(int ch);//是否是可打印字符
int isgraph(int ch);//是否图形表示

回顾一下,我们知道 C++支持两种类型的字符串: