Welcome to SunisDown’s NoteBook’s documentation!¶

这里是 SunisDown 的笔记本，用来记录一些学习的过程。通常情况下笔记是用来自己看的，同时记录一下加强记忆。

Sphinx 真是个好东西。

Contents:

Programming language¶

那么多种语言，每一种都有自己的优点与缺点。 Contents:

Python¶

人生苦短，我用Python

Contents:

Source Code of Python¶

人生苦短，我用Python

解释器与 opcode¶

先创建一个 test.py 文件。

x = 1
y = 2
print(x + y)

在 IPython 中查看

In [2]: c = compile('test.py', 'test.py', 'exec')

In [3]: c.co_code
Out[3]: b'e\x00\x00j\x01\x00\x01d\x00\x00S'

从 IPython 中可以看到，c 有很多属性，这些属性都定义在 code.h 里：

/* Bytecode object */
typedef struct {
    PyObject_HEAD
    int co_argcount;                /* #arguments, except *args */
    int co_kwonlyargcount;  /* #keyword only arguments */
    int co_nlocals;         /* #local variables */
    int co_stacksize;               /* #entries needed for evaluation stack */
    int co_flags;           /* CO_..., see below */
    PyObject *co_code;              /* instruction opcodes */
    PyObject *co_consts;    /* list (constants used) */
    PyObject *co_names;             /* list of strings (names used) */
    PyObject *co_varnames;  /* tuple of strings (local variable names) */
    PyObject *co_freevars;  /* tuple of strings (free variable names) */
    PyObject *co_cellvars;      /* tuple of strings (cell variable names) */
    /* The rest aren't used in either hash or comparisons, except for
    co_name (used in both) and co_firstlineno (used only in
    comparisons).  This is done to preserve the name and line number
    for tracebacks and debuggers; otherwise, constant de-duplication
    would collapse identical functions/lambdas defined on different lines.
    */
    unsigned char *co_cell2arg; /* Maps cell vars which are arguments. */
    PyObject *co_filename;  /* unicode (where it was loaded from) */
    PyObject *co_name;              /* unicode (name, for reference) */
    int co_firstlineno;             /* first source line number */
    PyObject *co_lnotab;    /* string (encoding addr<->lineno mapping) See
                Objects/lnotab_notes.txt for details. */
    void *co_zombieframe;     /* for optimization only (see frameobject.c) */
    PyObject *co_weakreflist;   /* to support weakrefs to code objects */
} PyCodeObject;

属性对应如下：

属性	作用
co_code	字节码指令序列
co_consts	常量列表
co_names	符号序列
llll	llllll

接着上面的例子，查看 co_code，字节码是以 byte 字符串的形式存在。通过查找 asciitable 可以看到不同的指令的含义。

In [3]: c.co_code
Out[3]: b'e\x00\x00j\x01\x00\x01d\x00\x00S'

In [4]: [i for i in c.co_code]
Out[4]: [101, 0, 0, 106, 1, 0, 1, 100, 0, 0, 83]

In [5]: [hex(i) for i in c.co_code]
Out[5]:
['0x65',
'0x0',
'0x0',
'0x6a',
'0x1',
'0x0',
'0x1',
'0x64',
'0x0',
'0x0',
'0x53']

opcode.h 中可以找到指令对应的定义，比如上面看到 101 对应 LOAD_NAME

利用 Python 提供的 dis 可以验证刚刚看到的指令。

$ python3 -m dis test.py
1           0 LOAD_CONST               0 (1)
            3 STORE_NAME               0 (a)

2           6 LOAD_CONST               1 (2)
            9 STORE_NAME               1 (b)

3           12 LOAD_NAME                2 (print)
            15 LOAD_NAME                0 (a)
            18 LOAD_NAME                1 (b)
            21 BINARY_ADD
            22 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            25 POP_TOP
            26 LOAD_CONST               2 (None)
            29 RETURN_VALUE

Python 的 Data Model¶

龟爹的品味

用Python

如果你在用Python之前已经接触过别的面向对象的编程语言，你就会发现Python 中有一些奇怪的地方，比如用 len(collection) 替代了 collection.len()。这个例子在 Python 中只是冰山一角，类似的写法就是 Python 的关键，我们讲它称为 `` Pythonic``。而这巨大的冰山就是 data model，通过 data model 描述的 API，你可以自己的 object 与语言的特性完美的结合在一起。

你可以吧 data model 看成 Python 的一种描述，它来确定语言本身的实现。像 object，iterators，functions 等

当我们使用一个框架的时候，需要实现被框架调用的各种方法(method)， j

MetaPrograming¶

Class Metaprograming¶

元类很强大，但是也不容易掌握。更多的时候，装饰器完全够用，而且更简单。

A Class Factory¶

Go¶

Let’s Go

Contents:

Go 错误处理¶

通常情况下，我们都是这么来处理 Go 里面返回的错误：

if err != nil {
    return err
}

这么写起来稍微有点麻烦，可以用下面两种方法来做：

func example1() {
    var (
        o   = Object{}
        err error
    )

    if err = o.Do1(1); err != nil {
        log.Fatal("ERROR 1", err)
    }

    if err = o.Do2(2); err != nil {
        log.Fatal("ERROR 2", err)
    }

    if err = o.Do3(3); err != nil {
        log.Fatal("ERROR 3", err)
    }

    log.Println("Ok")
}

或者:

func must(err error) {
    if err != nil {
        log.Fatal(err)
    }
}

func example2() {
    o := Object{}

    must(o.Do1(1))
    must(o.Do2(2))
    must(o.Do3(3))

    log.Println("Ok")
}

参考：errors-are-values

Lisp¶

Contents:

ChezScheme Implementation¶

Chez Scheme does not employ a byte-code representation. The complier generates machine code directly, either in memory or to disk(via compile-file and related procedures). Nor does Chez Scheme have a VM in the sense of a program that interprets byte code. It does have a run-time architecure that dictates the structure of objects, the heap, stacks, thread context, etc. The generated machine code directly manipulates elements of the run-time architecture in cooperation with the storage manager and oter parts of the run-time system, just as one would expect the code generated by a JIT compiler for JVM code todo.

Some of the papers mentioned above describe how elements of Chez Scheme’s run-time architecture are (or once were) structured and manipulated, and most of the structure is codified in s/cmacros.ss and c/globals.h, but the architecture is otherwise undocumented.

ChezScheme-issue-144

Rust¶

Contents:

Rust 变量¶

fn main() {
    let x: i32 = 20;
    println!(x);
}

用 let 来声明一个变量，可以显示的声明类型，也可以不直接初始化声明类型，但是需要注意的是，声明类型之后，必须要显式的初始化这个变量。比如这么做是错的

let x: i32
println!(x)

错在没有初始化变量

还有一点需要注意，Rust 里面变量是 immutable 的，如果想要赋一个新的值，就需要先把这个变量显示的声明为可变的，如下：

let mut x = 2;
println!(x)
x=5;
println!(x)

Rust 函数¶

Rust 函数的默认返回值有点诡异

fn foo(bar: i32) -> i32 {
   if bar > 10 {
       bar - 10
   } else {
       bar -3
   }
}

还有一个需要注意的是 expressions 和 statements 的区别， expressions 会有返回值， stattements 不会。

Tools¶

一些常用的工具

Contents:

Emacs: The Editor of God’s¶

多窗格（MULTIPLE WINDOWS）¶

Splitting Windowns¶

C-x 2

在当前窗口的下面再分一个窗口

C-x 3

在当前窗口的左边分一个窗口

C-x 0

杀死当前窗口

key	command
C-x 0	delete-windown	杀死当前窗口
C-x 1	delete-other-windows	仅保留当窗口，杀其他窗口
C-x 2	split-window-below

fio¶

磁盘测试工具，可以拿来测试磁盘的随机读写性能。地址 fio

里面有很多参数可以调整，可以通过命令行参数的形式来启动，也可以指定一个配置文件。

随机读¶

比如我想测硬盘的随机读的性能, 可以用下面的配置 random-read-test.fio

[random-read]
rw=randread
size=4G
directory=/data1/readtest
iodepth=16
bs=500B
thread
runtime=60
numjobs=16
rate_iops=22

然后执行:

fio ./random-read-test.fio

GDB¶

启动 GDB¶

gdb 可执行文件名

比如要调试 beansdb，则直接输入 gdb beansdb

设置断点¶

break main

break 可以简写成 b

断点可以通过函数名，当前文件内行号等设置：

break 函数名
break 行号
break 文件名:行号
break 文件名:函数名
break +偏移量 #当前位置之后 3 行
break -偏移量
break *地址

如果不设置指定断点，则默认是下一行设置断点。

可以通过 info 来看有哪些断点

i b # info break

运行¶

直接在 gdb 里面执行 run 命令就可以，如果本身有参数，还可以在后面加参数，比如启动某一个服务的时候需要配置文件，则需要在 run 后面跟响应的参数：

run -conf /etc/xxxxoooo.conf

显示栈帧¶

显示所有栈帧¶

backtrace

bt

info stack

where

显示前 `N` 个栈帧¶

bt N

显示最后 `N` 个栈帧¶

bt -N

显示局部变量与栈帧¶

bt full

显示变量¶

print

p

显示寄存器¶

info reg

i r

也可以在寄存器前添加 $ 显示各个寄存器的内容。

p $sp

p 输出信息的可以使用不同的格式

p/格式变量

格式列表如下:

格式	说明
x	十六进制
d	十进制
u	无符号十进制
o	八进制
t	二进制
a	地址
c	字符串
f	float
s	string
i	机器码

x 可以显示内存中的内容，格式跟 p 类似

x/格式地址

x/10i $pc // 查看 pc 寄存器指向地址开始的10条汇编

单步调试¶

n/next 下一步
s/step 下一步,可以进入函数内部
nexti 下一行汇编
stepi 下一行汇编,可以进入函数内部
c/continue 继续执行直到下一个断点

监视点¶

watch xxx // xxx 发生变化时暂停, xxx 通常为变量
awatch xxx // xxx 被访问或者发生变化时暂停
rwatch xxx // xxx 被访问时

改变变量的值¶

set variable xxx=123

attach 到进程¶

需要调试一个已经启动的进程时，可以这么做。

gdb

(gdb) attach 1234 //1234 为进程号

保存历史记录：¶

set history hilename demo.gdb
set history save

puppent¶

penv diggle2 # 检查一下是否有别人在prun penv diggle2 me prun diggle2 #在diggle2上实验，gu penv diggle2 back commit 后back就行!

Others¶

其他，零零散散

Contents:

GoBeansDB¶

Why¶

CArray

type CArray struct {
    Body []byte
    Addr uintptr
    Cap  int
}

A: 这里数据结构是重复的，为什么这么做？

Q: 用C来管理内存，减少 GC 压力

// HStore

type HStore struct {
    buckets   []*Bucket
    gcMgr     *GCMgr
    htree     *HTree
    htreeLock sync.Mutex
}

// HTree
type HTree struct {
    sync.Mutex

    /*
     *            Root of hstore.tree
     *               /  | ... \
     *              /   |      \
     * depth -->  ht1  ht2     htN     # root of bucket trees (also are the leafs of hstore tree)
     *             ^
     *             |
     *            pos
     *
     * #bucket (number of buckets) = 16 ^ bucket_tree.depth
     */

    // depth is level (0-based) of root Node (of this htree) in hstore.tree
    depth int

    // bucketID is position (offset) of this htree in the list of htrees at same level.
    bucketID int

    /* runtime */

    // level[0][0] is root of a htree,
    // levels[i] is a list of nodes at same level `i` of htree,
    // Node stores the summary info of its childs.
    // Height of htree = len(levels)
    levels [][]Node

    // leafs is the place to store key related info (e.g. keyhash, version, vhash etc.)
    leafs []SliceHeader

    // tmp, to avoid alloc
    ni NodeInfo
}

type Node struct {
    // count is the number of keys (with version > 0) under this node.
    count uint32

    // hash is the summary of it's child nodes.
    hash uint16

    // isHashUpdated is true iff the hash value of node is updated.
    isHashUpdated bool
}

type NodeInfo struct {
    node   *Node
    level  int
    offset int
    path   []int
}

NOTE¶

htree.go::getLeafAndInvalidNodes // 看起来没有返回数据，但是更新了tree 的 ni

Bitcask¶

厂里的 BeansDB
里面用的存储模型用的是 Bitcask。 而我刚好要维护 BeansDB 的 Golang
版本，所以看一下这论文，顺便做一下记录。

BeansDB 是我厂大牛
的作品，可惜我来豆厂的时候，Davies 已经去 Databricks 写
Spark 去了

一个 Bitcask
实例可以看成一个目录，目录下面放了数据文件，而每次操作都会写入到
active
的文件中，当这个文件大小达到一个阈值之后，就新建一个文件，之前的文件只读，不可以再写入数据。

+-------------------------+
|                         |
|                         |
| +-------------------+   |
| | active data file  |   |
| |                   |   |
| +--          /------+   |
|    \---------           |
| +--------------------+  |
| | order data file    |  |
| +--------------------+  |
| +--------------------+  |
| | order data file    |  |
| +--------------------+  |
| +--------------------+  |
| | order data file    |  |
| +--------------------+  |
| +--------------------+  |
| | order data file    |  |
| +--------------------+  |
|                         |
+-------------------------+

状态为 active 的文件在写入的时候，只能在文件尾部做 append 操作，这样可以减少不必要的磁盘检索。

每一条 K/V 数据的格式也非常简单

      |---------------------CRC converage -----------------------------------------|

                       size of
                  +-----------------+
                  |                 |
                  |                \|/
+-----------------+----------------------------------------------------------------+
| crc | tstamp | k|z | value_sz | key      | value                                 |
+----------------------------------------------------------------------------------+
                          |                                      /|\
                          |                                       |
                          +---------------------------------------+
                                   size of

这样，每次写入，都是将一条新的记录 append 到状态为 active

的文件中。即便是 删除 操作也是追加一条特殊的记录。

当写入操作完成之后，需要更新保存在 内存 中的一个 keydir
哈希树。keydir 里面保存着每一个 key 对应的文件，已经这个 key
在文件中的偏移量。

+-------------------------------------------------------------------+
|      +----------------------------------------------------------+ |
| key -|file_id | value_sz | value_pos | tstamp                   | |
|      +----------------------------------------------------------+ |
|                                                                   |
|      +----------------------------------------------------------+ |
| key -|file_id | value_sz | value_pos | tstamp                   | |
|      +----------------------------------------------------------+ |
|                                                                   |
|      +----------------------------------------------------------+ |
| key -|file_id | value_sz | value_pos | tstamp                   | |
|      +----------------------------------------------------------+ |
+-------------------------------------------------------------------+

value_post --> 值的位置

发生一次写入操作时， keydir 会随着本地数据的写入而自动更新。老的数据还会保存在硬盘上面，但是之后的读操作都是使用新的 keydir ，后面我们会看见 merge 操作最终会把旧数据移走。

Column Store¶

Row¶

row store

1	2	3	4

Column¶

1         2       3        4
+----+  +----+  +----+   +-----+
|    |  |    |  |    |   |     |
+----+  +----+  +----|   +-----+
|    |  |    |  |    |   |     |
|    |  |    |  |    |   |     |
|    |  |    |  |    |   |     |
|    |  |    |  |    |   |     |
|    |  |    |  |    |   |     |
|    |  |    |  |    |   |     |
|    |  |    |  |    |   |     |
+----+  +----+  +----+   +-----+

利用 CPU 缓存¶

vid value index

Developer Testing¶

单元测试(Unit test) 小段程序，从系统中隔离出来单独测试。可能是一个类，一个小程序
组件测试(Component test) 类，包从完整的系统中隔离出来做测试
集成测试(Integration test) 多个类，包，组件，或者子系统进行联合测试。这种测试应该越早进行越好，两个类可以集成测试就尽快测试
回归测试(Regression test) 重复之前的测试用例
系统测试(System test) 运行整个软件进行测试

一个项目规模越大，真正写代码的时间占比会减少。而架构，测试，集成占用的时间比例会增长。

开发人员测试软件的要点：

对需求测试，确保需求完成。这部分测试用例应该在开始写代码直接就写好测试用例。
对架构的关注点测试，确保架构被实现。这些测试也应该先于代码实现。
基础测试
使用检测表，记录在这个项目中犯过的错误。

TDD¶

先写测试，可以将引入去缺陷到发现并排除权限直接的时间缩减至最短。
先写测试或者后写测试，在写测试这上面花的时间一样多。
先写测试，更容易发现BUG，也更容易修复BUG
先写测试，会强迫你先考虑需求与架构设计，这样对于自己的成长更好，也容易写出优质的代码。
先写测试，可以暴露不合理的需求，一个烂需求，没有办法很好的实现功能测试

** 测试很好，但测试不是万能的 **

Limitations of Developer Testing¶

clean tests 开发人员通常只会写让代码正常运行的测试，比如用正常的数据来做测试，而不是拿脏数据来测试
100% 的覆盖率不代表测试到位

DEBUGING¶

调试可能会占到开发周期的 50%，懂调试的工程师可能只需要花普通工程师1/3的时间来做调试工作。

寻找缺陷¶

科学的调试¶

通过可重复的实验收集数据
根据相关数据设计构造一个假说
设计一个实验来证明或者反证这个假说
证明或者反证假说
根据需要重复上面的步骤

上面是大概的步骤

下面是方法

将错误的状态文档下来: 如果一个BUG只是时不时的出现，那几乎没有可能找出产生BUG的原因。能够让BUG稳定的复现是工作中比较有挑战的事情。

确定错误的来源（也就是那个Error/Fault）
1. 收集产生缺陷的相关数据
2. 分析所收集的数据，并构造对去缺陷的假设
3. 确定怎样去证实或者证伪这个假设。比如通过测试或者通过检查代码
4. 按照 2-c 的方法对假设作出结论
修补缺陷
对修补的地方进行测试
查找是否有类似的错误

IF 语句¶

如何写好代码是永不过时的话题，if 作为代码中不可缺少的部分，也是将代码写优雅必须要掌握的。

在写 if 语句的时候，通常遵循一下原则：

首先写常见的情况，在处理补常见的。常见情况的代码清晰，代码可读性要高
确保等量分支正确类似 > >= 混用的情况
正常的情况放在 if 的后面，异常情况放在 else 后面。

if ifSuccess {
// do something
} else {
// do something
}

if 子句后面应该有意义

if Success {
} else {
// do something
}

上面例子里面，if 的子句里面没有任何逻辑，这种代码看起来有点怪，可以修改成

if !Success {
// do something
}

考虑 else 子句

上面的例子里面只写了 if 语句，后面并没有跟 else，这种情况下需要确认自己是否考虑周全，并且在注释里面说明为什么没有 else 语句

Minimize Filesystem Caching Effects¶

有的时候需要判断某一个文件被 Linux 缓存了多少。nocache 是一个非常不错的工具。足够小巧，无痛安装。

Install¶

git clone https://github.com/Feh/nocache.git

cd nocache

make

这样 nocache 目录下就有相应的可执行文件。cachestats 可以插件一个文件被缓存了多少

Example¶

./cachestats /test/275.000.idx.hash

pages in cache: 0/53443 (0.0%)  [filesize=213771.4K, pagesize=4K]

结果显示没有文件被缓存了0%

如何取一个好的变量名¶

当我写一个需要长期维护的项目时，取变量名变成一个非常重要的事。尤其是同事拿着代码看不懂其中的含义，需要再解释一遍的时候。如何取一个优雅的变量名，应该是很多小伙伴都头疼的问题。变量又不是狗，我们不能觉得这个名字可爱，那个名字酷，叫起来方便就直接按上，之所以绞尽脑汁想一个变量名，无非是为了让小伙伴们阅读起来更加方便。一个好的变量名应该是可读的，而不是需要让别人在阅读自己代码的时候需要通过上下文来判断这个变量代表什么含义。一个好的变量名应该也是容易记住的，这样别人在阅读代码的时候可以大概知道这个变量在前面用过。

选择好的变量名¶

准确的表述变量代表的事物¶

这个要求并不简单，尤其是对于母语不是英文的人来说，比如我。这也是我在取变量名的时候遇见的最大的问题。

一些比较好的例子如下：

customerID/pageCount/

比较反人类的命名是直接用 a/b/c 这些没有含义的字符来作为名字。

合适的长度¶

一个优雅的变量名不应该太长，比如我要取一个变量名来代表豆瓣核心系统的软件工程师这个事物，

softwareEngineerAtDouban

理想情况下变量名长度应该在 10 到 16个字符之间，放宽要求可以控制在 8 到 20 个字符之间。变量名太短可能会导致无法传达足够的信息变量名太长写起来麻烦，而且会让代码的视觉结构不那么清晰。

变量名中的计算值限定词¶

Total Sum Average Max String Record 这种限定词放在变量名的最后。

优点：

变量名最重要的含义部分，应该放在最前面。统一规则之后，可以避免 totalRevenue 合 revenueTotal 这种有歧义的变量名。

一致性可以提高可读性，简化维护工作。

变量名中的对仗词¶

begin/end
first/last
locked/unlocked
min/max
next/previous
old/new
opened/closed
visible/invisible
source/target
source/destination
up/down

特定类型的命名¶

命名循环下标¶

如 i j k 这些可以放在简单的循环里面，但是还是建议取有意义的名字。

命名状态变量¶

如果你在猜测某段代码的含义，就应该考虑重新命名。

命名临时变量¶

临时变量用户存储计算的中间结果，作为临时占位符，以及存储内存管理值（housekeeping）

不要因为变量是临时的就随意的命名。

命名布尔值¶

类似于 done error found success 这些是好的布尔值变量。但是 status 就不是一个好的名字。

使用肯定的布尔值变量名，notFound notdone notSuccessful 这些不是好的变量名

Distributed System¶

分布式系统 Contents:

Table engines¶

clickhouse¶

数据是如何存储的

怎么写入输入，怎么读取数据
支持哪些查询方式，是如何支持的
并发的数据访问
需要的时候设置索引
多线程
数据 replication

TinyLog¶

作为数据存放在磁盘上的引擎，TinyLog 属于最简单的那种。没一列数据都单独存储在一个压缩的文件里面。写入数据的时候，数据直接追加在文件的尾部。并发的访问有下面这些限制： 1. 如果读写操作同时执行，读操作会报错 2. 如果写并发，数据会出问题。推荐的做法是，写一次，然后在需要的时候反复的读。 Queryies 操作是在单个执行流里面执行的，所以这个引擎是给小规模的数据量准备的，推荐是`1,000,000` 行。 … 处理小批量数据的时候，TinyLog 被拿来存储中间数据。

## Log 拿来放短期数据，一次性数据，测试

Memory¶

拿来做测试，也可以拿来小规模数据的快速计算。推荐 100,000,000 行数据。系统会用

## Merge

本身不存储数据，但是可以同时从任意多个 table 里面读取数据。

Distirbuted¶

Distributed engine 不存储数据，但是支持在多个服务器上做分布式查询。

Distiributed（calcs, default, hits[, sharding_key]) 里面的参数分别是集群名数据库名，表名, 以及一个可选的 sharding key

clacs 是集群名字 default 是 database name hits 是 table name sharding key 是 sharding keys

除了直接从 remote servers 上面直接读取数据之外，我们还可以利用 remote server 做一些处理。比如在执行一条含有`GROUP BY` 的查询语句时，数据会在 remote servers 上执行 aggr 操作，然后把执行 aggr 之后得到的中间结果作为响应返回给请求服务器，然后再做进一步的 aggr。

你可以在多个 replicas 之间做 LB。

想往集群里面写入数据时，同城有两种方法：

1. 可以定义好哪些要在哪些服务器上面做数据写入。这是

？？？

GoBeansDB 架构设计(1)¶

从产品转系统有一段时间了，转到核心系统之后一直在维护 GoBeansDB，最近也在慢慢的熟悉另外一个新的项目（暂时保密）。

BeansDB 是豆瓣内部实现的分布式存储系统，最开始的时候是 Davies 用 C 来实现的。2015 年的时候，内部决定开始用 Go 来重新写 BeansDB，然后 xiufeng 与 zzl 就实现了现在的 GoBeansDB。

为什么要自己实现一套 k/v 存储¶

我在刚刚接手 GoBeansDB 的时候，想过这个问题。既然有那么多优秀的数据库系统，为什么豆瓣还需要自己重新实现一套 k/v 存储？这个问题可以拆分成两个方面，一个是为什么要用 K/V 数据库。一个是为什么要自己造轮子。

首先是因为数据大，而且数据是非结构化数据，像豆瓣的日记，就是一批很长的字符串。
其次是非常多的随机读。
有的时候会有大量的写操作
不需要外键什么的

上面四点可以排除掉类似 MySQL 这种传统的关系型数据库。

排除掉传统的关系行数据库之后，就需要对比现存的 K/V 数据库。

现在比较流行的 K/V 数据库有 LevelDB ， MongoDB ，还有 Cassandra ，现在看来这些项目都足够成熟。但是如果追溯到 BeansDB 项目最开始的时候，也就是 2012 年的时候，那个时间点并没有太好的选择。即使现在看来，除了 Cassandra 之外，像 LevelDB， MongoDB 也不能满足我们的目标：

读写都需要比较低的 latency
数据量非常大，所以数据要写在磁盘上，数据库需要能够容纳比内存大的多的数据
高可用，单点故障不影响系统正常运行
高吞吐，尤其是针对写操作
能够快速恢复有问题的节点

这 5 点也可以排除调 MongoDB 与 LevelDB 。

当然上面这些都是我做的推断，但是这些应该都不是最主要的原因。最主要的原因应该是豆瓣的工程师文化比较好，鼓励工程师去寻找一个最贴合业务的解决方案，并且这个工程师的团队还足够强，两者缺一不可。如果没有很强的工程师文化，可能会直接引入开源的解决方案，虽然不一定合适，但是应该足够解决痛点。如果工程师实力不够，也就没有能力去自己实现一套类似的系统。而且与其去引入一个复杂的，自己无法完全掌控的开源项目，不如自己实现一套贴合业务的，简单的系统。这样内部可以根据业务的需要来作调整，同时自己实现一个系统也比完全掌握一个庞大的开源项目要简单。一旦出现问题也比较容易找到问题所在。

为什么要用 Go 重新实现 BeansDB¶

BeansDB 是用 C 来实现的，为什么现在改用 Go 来实现？

一个很重要的原因是 Go 的代码相比与 C 更容易维护。对一个工程师而言，Go 的学习成本比 C 要低很多。

还有 Go 的标准库也足够完善，不需要用 C 来重复造轮子。而且 BeansDB 的瓶颈是 IOPS，Go 的执行效率虽然比 C 差，但是也不会成为瓶颈。

GoBeansDB 的架构设计¶

GoBeansDB 是基于 Dynamo 与 Bitcask 两篇论文来做的实现，这里优先讨论基于 Bitcask 实现的存储引擎。Bitcask 有一个缺点在于所有的 key 值都必须放在内存里面，GoBeansDB 这这个基础之上做了一些优化，绕过了 Bitcask 这个痛点。

GobeansDB 的存储有有两个比较重要的组成部分，一个是索引(htree)，一个是数据文件(data)。索引与数据文件组成 Bucket。Bucket 的概念类似与关系行数据库里面的 table，在 GoBeansDB 的实现中就是给一个 Bucket 分配一个文件夹，这个文件夹下面放着相关的数据。每个 Bucket 下面一次只允许打开一个文件。打开的这个文件会一直保持打开的状态，一直等到追加到活跃文件超出阈值。文件超出阈值之后就关闭，然后新建一个新的继续添加。data 文件一旦关闭之后，文件就转换成为不活跃的数据文件。无法再往这个 data 文件上面追加数据。

状态为 active 的数据文件只做追加操作，这样连续的写入操作也不会明显增加磁盘的 IO 使用量。这种设计也极大的简化了数据的写入操作。

上面的图简单描述了 Bucket 内部文件的架构，每条数据里面包含TS（TimeStamp）,Flag，Ver（Version），ValueHash，RecSize（单条记录的主要内容的大小）,Value，crc（key，value，header 的 crc），ksz（Key Size）,vsz（Value Size）,pos（Position，这条记录在文件中的位置）,Header。

当插入新数据的时候，直接在文件尾部添加这种结构的数据。删除操作是对原有的数据做更新操作，并将 Ver 绝对值+1，转变为负数。

在文件写入完成之后，需要更新内存里面的数据结构，也就是前面提到的 HTree，HTree 是一个 Hash Tree，结构如下

levels 表示真是的树状结构， leafs 是树的叶子，保存着真实的数据。

这种数据结构下读取一个值也非常简单，大多数情况下最多只需要一次 seek 。我们首先在 Htree 中通过 levels 找到 key 对应的 leafs ，然后通过 leafs 里面的报错的 Pos 来拿到文件编号（chunkID）以及 offset，这样就可以通过文件编号（chunkID）和 offset 来拿到保存的数据。在很多情况下文件系统的缓存会让这个读操作比预期的要快。

到这里关于 GoBeansDB wirte/delete/read 相关的操作都已经基本完成。但是仅仅这样还不能完备。

GC 操作¶

GoBeansDB 的模型非常简单，write/delete 操作都是在文件尾部追加新的数据，这样存在一个问题就是占用的磁盘空间比真实的数据要多。所以我们引入了 GC 机制来回收垃圾，释放内存与磁盘空间。在 GoBeansDB 中，可以通过配置文件来设置只回收 N 天之前的数据，比如一个周之内的数据我们认为还会有改动或者其他操作，先保留一段时间。同时我们引入增量 GC 的机制，之前做过 GC 操作的数据，则认为不需要进行第二次 GC。

GC 的过程是将 datafile 里面已经过时的数据清除掉，比如旧版本的value，已经删除掉的key。

Chronos On mesos¶

最近经常遇到某一个任务疯狂的跑，占用太多集群资源导致正常的任务无法正常进行的情况。

之前海盗在的时候，尝试在写一个叫 evermind 的项目，用来管理公司内散布在各个角落的脚本。可惜出师未捷，海盗在项目完成之前离职了。

后来开晨会的时候，兆龙说起 chronos 有类似的功能。也就有了我现在做的事儿，了解一下 chronos 是不是满足我们这边的需求。

定时任务¶

chronos 可以直接添加任务，使用 ISO 8601 格式来替代 cron 的语法

依赖于其他任务的不能直接添加定时任务，但是可以通过指定多个 parents 来实现类似的子任务定时

任务依赖¶

任务可以指定多个 parents

任务失败¶

任务失败会重试

任务类型¶

都是短任务，跑一段时间会结束的那种。不能拿来跑 run-ever

删掉父任务¶

删掉父任务之后，子任务继承父任务的执行频率

Novel Erasure Codes for Big Data¶

分布式存储中经常用 replication 来保证系统的可靠性，但是如果使用 three-replicated 这种方法，系统对于存储资源的浪费比较严重。而 erasure codes 就是拿来解决存储资源浪费的问题。RS(Reed Solomon) codes 也是用来解决类似问题，虽然 RS codes 可靠性跟对磁盘的利用率都很高，但是他在恢复数据的时候付出的代价太大，这也是 erasure codes 存在的价值。

这篇论文将展示如何突破这些限制。

INTRODUCTION¶

Balabala

因此，Facebook 转向 erasurce coding 技术，以便可以节省存储空间。jk

Reliable, Scalable and Maintainable¶

Reliability¶

The system should continue to work correctly.

Scalability¶

As the system grows(in data volume, traffic volume, complexity), there should be reasonable ways of dealing with that growth.

Maintainability¶

People should be able to work on it productively

无用的 CAP 理论¶

很多分布式系统中都无法避开 CAP 这个理论，从 Consistency/Availability/Partition tolerance 三个特性里面选出两个来实现。实际上，这三个特性放在一起让人来选择很容易误导人，因为这三个选项里面，有一个是必须要面对的选项，像网络问题，这是一个无论如何都需要面对的问题。

通常情况，如果网络没有问题，那一个系统也就同时可以保证 Consistency/Availability，但是当网络出现问题的时候，你就需要从 Consistency 与 Availability 中选择一个来实现。所以对与 CAP 理论更好的解释是，当你在 Partitioned 状态下，选择 Consistency 还是 Availability。一个稳定的网络可以减少这种选择，但是有的时候，这种选择是无法避免的。

在讨论 CAP 时，对于 Availability 的定义都有一些矛盾的地方，很多说 highly available (fault-tolerant) 系统，通常跟 CAP 里面的 availability 不是一回事。总之，在 CAP 里面有很多让人误解的地方，并且他也不能帮助我们更好的理解某一个系统。

分布式计算之 MPC¶

MPC¶

MPC 是一个拿来分析数据交换代价的模型。BSP 模型属于MPC 里比较有代表性的一个。BSP 模型只关心数据交换的成本，忽略计算成本。BSP 通常被抽象成 shared-nothing 架构，并且在很多大数据处理系统中应用很广泛。

如下图所示，我们有一个集群，集群中还有 p 个实例节点。每个独立的节点都有自己的处理器跟内存。在这里面我们可以用处理器来代替集群中的实例或者是服务器。这 p 个处理器通过网络后者是 channels 连接到一起，每一个处理器都可以从其他的任意处理器上面接收数据，或者发送数据到其他任意处理器上面。

计算过程可以抽象成 steps 或者是 rounds，每一个 round 包含两个独立的步骤：

计算单元：处理器计算当前节点的数据
数据交换单元：处理单元之间，通过发送和接收来交换数据。

输入的数据 input 会被初始化，然后切分成不同的 partition 分给这 p 个处理单元。我们用 IN 来表示输入数据的规模，没有什么特殊情况的话， IN 就是这个数据数据的条数，或者是 bits 大小。把 input 的数据切分成不同的 partition 并没有什么确切的方法，怎么切分不重要，重要的是在计算单元能够正确的处理被分配到当前节点的数据。计算结束后，我们需要保证 output data 都保存在这 p 个处理单元的内存里面。相比与让同一个节点持有所有的 result，这个要求要低一些，但是在并行的数据处理系统中， output 有的时候甚至会比 input 更大，分布式的保存在 p 个处理单元上是必要的。在这里我们用 OUT 来表示 output data 的规模大小。

我们对处理单元的计算性能，或者是节点之间数据的交换方式没有特别的要求，这个模型只关注几个参数：处理单元的个数，rounds 的次数，以及数据交换成本。

MPC 模型的参数¶

处理单元个数 p

处理单元个数 p 意味着有 p 个资源并行处理数据，理论上讲 p 值越大，处理速度就越快。拿 MapReduce 来举例的话，p 等价于最多有多少个的 mapper ，也等价于最多有多少个 reducer。

rounds 个数 r

r 代表了这个算法需要跑多少轮之后才能结束，处理单元之间需要进行多少次数据同步。每一次 round，都是以最慢的那个 processor 为准，所以随着 r 的增加，处理时间，也会随着增加。我们在设计算法的时候， r 越小约好。

负载/数据交换成本 L

MPC 模型中最重要的就是数据交换成本。我们用任意一个 p 上面的任意一组 r 中 size 最大的那组数据来表示 L。如果要统计整过计算过程中的数据交换成本，就需要把所有 processor 的所有 round 的数据量都累加起来。

最大负载定义如下

\[L\stackrel {def} {=} \max_{u=1}^p \max_{k=1}^r L_{u}^{(k)}\]

总的负载定义如下：

\[C\stackrel{def} {=} \sum_{u=1}^{p} \sum_{k=1}^{r} L_{u}^{(k)}\]

需要注意的是，总输入的数据规模 IN 肯定是不大于 C，而 C 不大于 r*p*L，也就是

IN ≤ C ≤ r*p*L

输入数据 input 在第 0 轮 round 也就是在初始化的时候，会平均分给所有的 processor ，所以从每一个 processor 都可以在初始化的时候都可以被表示为

\[L_{u}^{(0)} \stackrel{def} {=} IN/p\]

MPC 模型下一个算法的负载，主要是受限于 input 数据的规模大小， processor 数量，以及 rounds 数量。

MPC 模型通常由两种实现，一个是 stateless MPC 模型，每个 processor上的数据在当前这一个 round 结束的时候，都会被清除。每一个 round 开始的时候，这些 processor 只含有当前 round 接受的数据。还有一个是 stateful MPC 模型，这个模型中， processor 上内存里面的 state 会被保留到下一轮，而 stateless 模型下， processor 则是通过对自己发送或者接收数据来维护这个 state 。总的来说，每个含有 r 轮负载为 L 的 stateful MPC 算法可以被一个含有 r 轮，负载为 L'=r*L 的 stateless MPC 算法来代替。在 stateless 的 MPC 模型中，每一轮计算中，都可以产生最终结果的一部分。而在 stateful 的 MPC 模型中，最终结果则通常在最后一轮 round 中产生，而不会在过程中的 rounds 里。

实际上我们设计 MPC 算法的时候，最关注的点就是尽可能的减少运行时间。总的运行时间跟两个单元组成，1）每个节点上的处理时间，这个取决于负载 L 、这个节点上运行的算法以及这个节点的处理器性能。2）一共需要处理多少轮 r 。而我们更多的假设 r=1 或者是不限制 r 有多少轮，然后只对 L 做优化，因为 r 的大小取决于 input 输入的数据多少，以及集群中有多少 processor ，可以优化的空间有限。

Speedup and scaleup¶

MPC是被作为 shared-nothing 架构的一种抽象而被设计出来的。而 speedup 和 scaleup 是 shared-nothing 系统的两个基本的参数。对于固定的数据 input ， speedup 简单来说，当我们增加 processor 数量的时候，处理数据的速度也要随之线性的增加。如果我们把 processors 的个数 p 直接 *2，那处理数据的速度也应该 *2 ，但是实际系统中， speedup 都不会线性的增长。 scaleup 是当 input 数据增加的时候，我们可以通过增加 processors 的数量来保持性能。比如当 input 的数据量 *2 的时候，我们可以通过增加一倍的 processor 个数来保证系统的性能。理论情况的的最优状况 scaleup 也是线性的，但是实际情况下这个也做不到。

MPC模型中，不管是 speedup 还是 scaleup ，都严重依赖于负载 L 以及每个节点上算法的运行时间。我们假定 r 是一个固定的数值，输入为 IN ， processor 个数为 p ，节点上的负责 L 则为 L(IN,p) 。为了简化问题，我们不考虑每个节点上面处理数据的计算时间，直接用 Time=O(L) 来表示每个 processor 上面的处理时间。在上面几种假设下， speedup 的公式为 f(p) = L(IN, 1)/L(IN, p) = c/L(IN, p) ， scaleup 的公式为 g(t) = L(IN, p)/L(IN*t, t*p) = c'/L(IN*t, p*t) 。大多数的算法的负载为 :

\[L=O(IN/p^{\delta})\]

且0 < 𝛿 ≤ 1。

Database¶

Database

Contents:

MVCC Rules¶

From a performance point of view, readers should never block writers, and writers should never block readers. With this principle, database can handle long-running read queries at the same time as processing writes normally, without any lock contention between the two.

Rules¶

At the start of each transaction, the database makes a list of all the other transactions that are in progress at that time. Any writes that those transactions have made are ignored, even if the transactions subsequently commit.
Any writes made by aborted transacations are ignored.
Any writes make by transacations with a later transacation ID(i.e., which started after the current transacation started) are ignored, regardless of whether those transacations have commited.
All other writes are visible to the application’s queries.

Indices and tables¶

搜索页面

Welcome to SunisDown’s NoteBook’s documentation!¶

Programming language¶

Python¶

Source Code of Python¶

解释器与 opcode¶

Python 的 Data Model¶

MetaPrograming¶

Class Metaprograming¶

A Class Factory¶

Go¶

Go 错误处理¶

Lisp¶

ChezScheme Implementation¶

Rust¶

Rust 变量¶

Rust 函数¶

Tools¶

Emacs: The Editor of God’s¶

多窗格（MULTIPLE WINDOWS）¶

Splitting Windowns¶

fio¶

随机读¶

GDB¶

启动 GDB¶

设置断点¶

运行¶

显示栈帧¶

显示所有栈帧¶

显示前 N 个栈帧¶

显示最后 N 个栈帧¶

显示局部变量与栈帧¶

显示变量¶

显示寄存器¶

单步调试¶

监视点¶

改变变量的值¶

attach 到进程¶

保存历史记录：¶

puppent¶

Others¶

GoBeansDB¶

Why¶

NOTE¶

Bitcask¶

Column Store¶

Row¶

Column¶

利用 CPU 缓存¶

Developer Testing¶

TDD¶

Limitations of Developer Testing¶

DEBUGING¶

寻找缺陷¶

科学的调试¶

IF 语句¶

Minimize Filesystem Caching Effects¶

Install¶

Example¶

如何取一个好的变量名¶

选择好的变量名¶

准确的表述变量代表的事物¶

合适的长度¶

变量名中的计算值限定词¶

变量名中的对仗词¶

特定类型的命名¶

命名循环下标¶

命名状态变量¶

命名临时变量¶

命名布尔值¶

Distributed System¶

Table engines¶

clickhouse¶

TinyLog¶

Memory¶

Distirbuted¶

GoBeansDB 架构设计(1)¶

为什么要自己实现一套 k/v 存储¶

为什么要用 Go 重新实现 BeansDB¶

GoBeansDB 的架构设计¶

GC 操作¶

显示前 `N` 个栈帧¶

显示最后 `N` 个栈帧¶