什么是“基于演示的开发”？

有一天和一个同事吃饭，我们聊到了大学里面做项目的事情，他说在大学的时候，他们那流行一种说法叫“基于演示的开发”，我心想这是什么高端的软件开发方法学?原来其实就是说对于作为课程中需要完成的小项目，后台功能是真的完成了，还是fake的，这个无所谓，只要当向其他人进行演示的时候，只要系统的界面好看些，系统“看起来”是功能完整的就行了，因此取名“基于演示的开发”。

虽然我是第一次听到这个说法，但在学校的时候，大部分同学都是基于这套“理论”进行小项目开发的。后台真有连接数据库吗？不一定，只要把结果直接写在代码里面就可以了；点击开始运行某算法，真的运行了吗？不一定，只要把预期的结果直接返回就行了。这种“造假”，在我大学本科期间，甚至研究生期间，比比皆是。说实话，我自己也造过假，只不过比别人少很多罢了。

为啥会有那么多“基于演示的开发”呢？说白了，你随便弄个可以演示的DEMO，和自己认认真真、辛辛苦苦的开发，最后的结果是一样的，前者的结果甚至会更好，我干嘛费劲呢？反正老师也就是随便看看，大部分也不会问什么细节（有的计算机专业的老师，我都对TA的计算机知识的掌握程度表示怀疑），就是个走过场。

三位同学的三件事

说到这里，我想起来了大学三个同学的三件事情：

同学A，学习挺刻苦，考试成绩很好。大学学习JAVA课程的时候，老师让每个人做一个基于JSP（全称：Java Server Pages，当年很流行的）的小网站，然后交一个设计文档。结果A同学不会写也不想写这个JSP，然后就随便写了几个HTML的网页，截个屏，写了个文档交差了，结果他截屏的时候，居然把浏览器地址栏也放进去了，地址栏里面赫然显示着xxx.html！我们在这个文档发回来的时候发现了A同学的“亮点”，貌似老师也没发现。。。

（之后同学A考研考上了某著名985大学，读完硕士，去美国读计算机博士了）

同学B，学习挺刻苦，考试成绩很好。本科期间倒是没什么太多的故事，他本科毕业之后，一心想读研，考了一年又一年，考了两年还是三年，好不容易考上了某著名985大学的软件学院。我平时觉得同学B编程能力也不是很强啊，为啥会选实用性较强的软件学院呢？有次我碰到他就问了他这个问题，他说，这个学校的软件学院，研究生入学考试不用考上机编程，只用做卷子和面试就可以了。。。。

（同学B读硕士的时候，只知道去上海某著名外企实习过一段时间，毕业之后下落不明）

同学C，学习上（个人感觉）不像前两位那么刻苦，不过成绩也不错。据说，只是据说，他大学四年期间，有的考试会用一些“特殊”手段，让考试成绩有所提高。这个是否属实，我不能百分之百确定，不过有次在考试的时候，他坐我旁边，的确问过我某一题选什么的，我看了看他，然后继续答题了。

（同学C最后因为成绩不错，最后保送本校，读博士了）

其实，我和这三位，都是很好的朋友，他们都不是有啥坏点子的人，大家都过着各自不同的生活，呵呵。好久没见他们，还是有些想念的。

浮躁

我觉得，类似这种“基于演示的开发”的出现，跟学生没太大关系，并且学生是受害者。大家从小接受的教育就是倾向于“随大流”或者“什么专业赚钱多就选什么”，很少有人因为这是自己的兴趣爱好而选择自己的专业的（至少我看我们学校本专业的是这个情况），既然学得不是自己感兴趣的东西，就没什么动力去深入挖掘其中的奥秘，需要交什么作业，随便糊弄个就完了，只要能在学校这个“system”里面玩转就行了。接着大家有的毕业去工作，有的留校当老师，优良的“传统”就在职场和校园里面一代代传下去了……

出现了这种现象，到底是什么原因呢？我想“浮躁”这个词可以概括，社会很浮躁、学校很浮躁、学生们也难免浮躁。算了，还是不说什么抱怨了，太多的抱怨是没有用的。还是大家各自努力吧，沉下心来做好身边的事情，每个人都少点浮躁，多点执着！

—EOF—

用上Wordpress之后，总体感觉还是很不错的，安装、设置、撰写文章都很方便，但仍然有几点不足：

1. 许多功能都需要插件支持，比如代码语法高亮，首页截取文章摘要
2. 图片和文章的存储方式，图片需要单独找图床、或者上传到服务器，而文章又是保存 mysql数据库中的
3. 数据备份比较麻烦，每次都得使用插件或者人工备份数据

因此决定将博客迁移到github上面，即免费又能使用Jekyll这种静态博客，不需要配置DB、使用git发布、markdown语法。简单、方便、 很极客！

建立github.io初始环境

首先，你需要一个github帐号，然后使用JekyllBootstrap建立一个初始化的环境，参照教程一步一步来，环境很快就可以搞定。你就可以在USERNAME.github.io上面看到环境了

PS: 教程上面说需要建立的是USERNAME.github.com的repository，需要改为USERNAME.github.io才可以

备份Wordpress数据

迁移之前，先备份下数据，如果是使用VPN的话，SSH登录到服务器上，备份数据库

mysqldump -u root -p -h localhost BLOG_TABLE > BLOG_TABLE.sql

另外一些静态文件，比如图片什么的，也备份一份

选择迁移工具

迁移工具方面，基本上是基于下面两种方式：

1. 使用WordPress导出的xml文件，导出md文档
2. 连接WordPress的Mysql数据库导出md文档

Jekyll有自带的jekyll-import工具，很想使用官方的迁移工具，但我一直“未遂”，说是无法load到jekyll-import模块……

另外，Jekyll官网上还推荐了三个第三方的工具：

1. Exitwp
2. A great article ， 其实是一篇详细的迁移教程
3. wpXml2Jekyll

第二个太过详细，第三个只能运行在Windows下，所以看来只能选择第一个工具了。

导出WordPress XML文件

在WordPress的export.php页面上可以轻松导出XML文件。但这一步遇到一个小插曲：blog上面太多spam评论了，结果也会一并export出来，这些spam 评论会导致后面工具导出markdown文档失败。因为blog上面真实的评论并不多，所以就考 虑把评论都删除，网上查了资料，只需要将WordPress Mysql表中的wp_comments表删除即可

DROP TABLE wp_comments;

使用exitwp

这个工具带有鲜明的“反WordPress”风格，使用起来还是比较简单的，按照项目首页的 README操作即可，你的WordPress文章就变成一个个markdown文档了！

不过使用途中发现有几个问题：

1. 在Mac上使用pip进行依赖安装后，那些依赖的库还是会import失败（是我打开方式不对吗……），还是得自己将一个个依赖下载后安装
2. Exitwp虽然支持下载图片，但是文章中的图片链接却没有换过来
3. 导出后的md文档，对于正文中的特殊字符没有做处理，比如*，会导致jekyll build失败，需要手动修改
4. 由于系统编码原因，会导致使用exitwp以及jekyll失败，参考这篇文章 ，需要在/etc/profile添加export LANG=zh_CN.UTF-8以及export LC_ALL=zh_CN.UTF-8

发布！

发布之前，现在本地使用jekyll server或者rake --preview在本地预览，没问题就可以发布了。

好了，下面将生成的markdown文档以及图片，push到你的github空间即可！Just enjoy it! :)

最后，在使用markdown编写中文文章时，发现jekyll默认的markdown引擎对于中文支持不 是很好，对于对于全部为中文的列表对完全失效，需要将markdown引擎改为rdiscount ，在_config.yaml中添加：

markdown: rdiscount

就可以了。

最近抽时间把Go语言看了一下，把Go playground玩了一遍，把官方文档上的Effective Go也学习了一番。把一些重点或者说自己觉得比较有特点的地方记录下来，用作备忘和分享。

未使用的package或者变量是编译错误

这相当于就在代码层面对开发人员进行了规范，不像C++等其它语言，你多include一个.h文件，或者声明了一个变量但没有使用，这对你编译程序都不会有任何影响，挺多会打些编译warning。这样很容易造成程序编译了没有使用的库和变量，使程序变得臃肿。

变量的可见性有变量名决定

一个package中的变量名如果首字母是大写，则对于package外部是可见的，反之则不可见。Go里面没有public, private这样的关键字（至少我目前没看到），直接约定首字母大写的变量是public的，不是大写的是private的，简便并且规范。

函数可以返回多值

像Python一样，Go的函数可以返回多个值，这样就很方便的把正常情况下需要返回的数据以及发生错误时error一并返回了。

关键字defer——return之前执行

Go里面可以将语句前声明defer关键字，表示目前先不执行这条语句，等待函数return前再执行。这实在是太方便了！特别是对于一些需要管理资源的场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Contents returns the file's contents as a string.
func Contents(filename string) (string, error) {
    f, err := os.Open(filename)
    if err != nil {
        return "", err
    }
    defer f.Close()  // f.Close will run when we're finished.

    var result []byte
    buf := make([]byte, 100)
    for {
        n, err := f.Read(buf[0:])
        result = append(result, buf[0:n]...) // append is discussed later.
        if err != nil {
            if err == io.EOF {
                break
            }
            return "", err  // f will be closed if we return here.
        }
    }
    return string(result), nil // f will be closed if we return here.
}

试想一下，在C++中，如果想要在每个分支都能释放资源，就得采用1）goto或do-while，例如以下代码，或者 2）scoped pointer。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

int f1(const char* fname) {
    int ret = 0;
    FILE* fp = fopen(fname, "r");
    if ( NULL == fp ) {
        return -1;
    }
    if (....) {
        ret = 1;
        goto FINISH;
    } else if (....) {
        ret = 2;
        goto FINISH;
    }

FINISH:
    fclose(fp);
    return ret;
}

int f2(const char* fname) {
    int ret = 0;
    FILE* fp = fopen(fname, "r");
    if ( NULL == fp ) {
        return -1;
    }
    do {
        if (....) {
            ret = 1;
            break;
        } else if (....) {
            ret = 2;
            break;
        }
    } while(0);

    fclose(fp);
    return ret;
}

new & make

Go语言中的new和C++中的不太一样，它只负责分配一段全为'\0'的内存，不会进行任何其它初始化，需要你自己再做一些工作。 而make关键字是用来新建slice, map, channel这三中类型的，因为它们内部必须做一些特殊的初始化才能使用。

结构体可以直接print

默认情况下，struct就可以直接打印出来，而且还会打印出每个字段的名称和值。这个对于开发人员排查问题，也是极其方便的。

1
2
3
4
5
6
7
8
9

type T struct {
    a int
    b float64
    c string
}
t := &T{ 7, -2.35, "abc\tdef" }
fmt.Printf("%v\n", t)
fmt.Printf("%+v\n", t)
fmt.Printf("%#v\n", t)

会打印出

&{7 -2.35 abc   def}
&{a:7 b:-2.35 c:abc     def}
&main.T{a:7, b:-2.35, c:"abc\tdef"}

当然，你也可以定义某个类型T的String()方法，用来改变输出的字符串，就像Python中实现__str__方法一样。

接口“嵌入”

如果想使用某套接口，在C++中一般都是将满足这套接口的实例作为某个类的成员，再调用这个成员的接口。在Go中，可以在某个接口里面直接“嵌入”其它已经实现的接口，比如需要一个ReadWriter接口，里面有Read()和Write()，但是已经有一个接口Reader里面有Read()，一个接口Writer里面有Write()，就直接使用以下代码就可以了，这样Read()和Writer()就是ReadWriter接口的方法了。

1
2
3
4
5
6
7
8
9
10
11
12
13

type Reader interface {
    Read(p []byte) (n int, err error)
}

type Writer interface {
    Write(p []byte) (n int, err error)
}

// ReadWriter is the interface that combines the Reader and Writer interfaces.
type ReadWriter interface {
    Reader
    Writer
}

goroutine && channel

goroutine以及channel可以说是Go语言最重要的特性了。goroutine有一个简单的思想，它就是一个通其它goroutine运行在同一份内存空间的函数。而channel顾名思义，就是一个管道，任何数据可以通过管道进行传输，可以往channel里面放数据，可以从channel里面获取数据。goroutine和channel的配合使用，很好的解释了Go语言“Do not communicate by sharing memory; instead, share memory by communicating”的思想，还有一个很好的例子在这里，这里例子同时也讲解了并发（concurrency）和并行（parallelism）之间的关系和区别。

我觉得，并发是一种工作方式，它把一个整体的复杂的任务分解为小型的逻辑简单的任务；而并行就是真是的同时在做许多事情。就那例子中的任务来说，把一堆书送到另一端的火堆烧掉。如果是并行的话，就是原来是一个人“拿书-运书-烧书”，现在同时有多个人“拿书-运书-烧书”。如果是并发的话：，就是把任务可以分解为：1）一个人把一部分书从书堆中放到车子上；2）一个人把装有书的车子推到火堆旁；3）一个人把火堆旁的书烧掉。每个人各司其职，只需要从一个源头（channel或者其它地方）获取原始数据，自己进行简单的加工，然后堆到另外一边（另一个channel），自己不用管其他人是怎么工作、或者什么时候工作的，只需要把自己分内的事情完成就OK了。Divide and conquer真是一种简单精妙的思想！

好了，暂时就先整理到这里吧~

参考资料：

• Effetive Go
• Concurrency is not Parallelism
• Go Playground

—EOF—

较早之前，一个模块的reload程序出现过这样一个问题：模块会定期检查一份文件是否被更新，如果被更新了，就reload；但是，如果文件正在被更新（没有写完）并且模块正好检测到更新，模块就会reload到一份不全的文件，导致数据异常。当时的解决方案是：使用一个done文件，推送文件的脚本在完成数据更新后，touch一下done，模块检测done文件的更新来判断是否reload。

最近这个事情又被同们事提起，不过稍微扩展了下，问题变成了：有没有一种机制，能让许多并行的脚本能串行进行一系列操作。比如多个脚本对文件进行依次读写，以免产生脏数据。无疑，如果脚本如果shell中有一种“锁”的机制，就可以解决这个问题。原来只使用过API级别的锁，脚本中的锁还真没用过。其实，如果要在shell脚本实现锁，需要满足两个条件：

1. 一个全局可见的状态
2. 一种“检测 + 加锁”的原子操作

大家可能会想到使用一个文件来当做锁，如果有这个文件，就表示某个脚本正在操作，其它脚本等待；如果没有这个文件，我就touch这个文件，然后开始我的操作。但是，“检测文件”和“新建文件”不是原子操作，所以是无法保证串行的。

google了一下，还是有几种满足条件的方案的。

文件夹锁

检测文件和新建文件无法做到原子性，但是mkdir操作，却能做到原子地检测文件夹和创建文件夹，有点儿意思！所以，当脚本想对于竞争数据进行操作，就mkdir某个文件夹，根据返回码得知申请所是否成功，申请成功、完成操作之后再rm -rf就可以实现了。例如这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#!/bin/sh

if [ $# -ne 2 ]
then
    exit 1
else
    NUM="$1"
    SLEEP_TIME="$2"
fi

OUT_FILE="test.out"
LOCK_FILE="lock.file"

while :
do
    mkdir ${LOCK_FILE}
    if [ $? -ne 0 ]
    then
        continue
    fi
    for ((i=0; i<10; i++))
    do
        echo "${NUM} is working in $i step!" >> ${OUT_FILE}
    done
    sleep ${SLEEP_TIME}
    rm -rf ${LOCK_FILE}
done

lockfile命令

原来直接就有个专门用于文件锁的命令，这个命令比mkdir更强大，可以设置申请文件锁的等待时长、重拾次数、锁的过期时间。但是，在写测试代码的时候，却发现只会有一个脚本一直获取到文件锁，其它脚本都处于申请锁等待并超时的状态，难道我参数用的不对？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#!/bin/sh

if [ $# -ne 2 ]
then
    exit 1
else
    NUM="$1"
    SLEEP_TIME="$2"
fi

OUT_FILE="test.out"
LOCK_FILE="lock.file"

while :
do
    echo "${NUM} try to get lockfile" >> ${OUT_FILE}
    lockfile  ${LOCK_FILE}
    if [ $? -ne 0 ]
    then
        echo "${NUM} wait lock failed" >> ${OUT_FILE}
        continue
    fi
    echo "${NUM} got lockfile" >> ${OUT_FILE}
    for ((i=0; i<10; i++))
    do
        echo "${NUM} is working in $i step!" >> ${OUT_FILE}
    done
    sleep ${SLEEP_TIME}
    echo "${NUM} delete lockfile" >> ${OUT_FILE}
    rm -rf ${LOCK_FILE}
done

exit 0

设置noclobber + 重定向文件

shell中有一个参数叫noclobber，设置了这个参数后，当脚本试图重定向文件时，如果发现改文件已经存在，重定向就会失败。这种方法自己没尝试过，下面是从网上抄来的code example：

1
2
3
4
5
6
7
8

if ( set -o noclobber; echo "locked" > "$lockfile") 2> /dev/null; then
  trap 'rm -f "$lockfile"; exit $?' INT TERM EXIT
  echo "Locking succeeded" >&2
  rm -f "$lockfile"
else
  echo "Lock failed - exit" >&2
  exit 1
fi

看来在脚本中使用文件锁，还是比较方便的。不过，在我看来在脚本中使用文件锁，有个致命弱点：操作系统不会禁止其它进程对作为锁的文件（或者文件夹）进行操作。相当于一个脚本已经申请到了文件锁并正在操作，但是其它进程完全可以不受限制的删除这个文件锁，这样就会使得期间其它脚本能够成功申请到文件锁。或者一些脚本使用文件锁对竞争资源进行操作，但其它脚本直接操作竞争资源，这种情况也是无法避免的。使用文件锁，完全靠自觉！

另外，文件锁也没有提供像共享锁、排它锁这样的高级功能，这也是文件锁的短板。

参考资料：

http://en.wikipedia.org/wiki/File_locking

Lock your script (against parallel run)

—EOF—

链表，应该是每一个学编程的人都会接触到的经典数据结构，大部分计算机专业的同学至少在上学期间也实现过单向、双向链表。在我的印象里，链表一般都是这么表示的：

struct LinkNode
{
    LinkNode* prev;
    LinkNode* next;
    int my_data1;
    double my_data2;
    //...
};

class LinkList
{
    LinkNode root;
    //...
};

或者，我们就干脆直接是用std::list<T>。无论是哪一种，它都是将使用的数据“嵌入”到链表的节点中，或者说是节点包在数据之外。这种实现也是教科书里面讲到的那个实现，也是我之前知道的唯一的实现方式。

前段时间看网上的几篇博客（Tips of Linux C programming，Avoiding game crashes related to linked lists），发现原来还有另外一种更优雅的链表实现——intrusive list。Linux kernel，以及许多底层软件（另外还有游戏星际争霸）的开发中，都是使用intrusive list进行链表操作的。

所谓intrusive list，就是指不像上面说的那样将链表节点包在数据外面，而是将链表节点包在数据里面。例如下面这样：

struct list_node_t
{
    list_node_t* prev;
    list_node_t* next;
};

struct MyClass
{
    int data;
    list_node_t node;
};

这样做，是为了让节点和数据在一个数据结构中。因为许多场景下，链表包含的数据是指针（考虑到数据拷贝构造的代价，以及一份数据被多个链表共享的情况），例如std::list<MyClass*>。使用intrusive list实现，就可以省去了”节点 –> 数据指针 –> 数据”的二次查找。找到intrusive list中的一个节点后，就可以立即找到这个节点对应的数据，即我知道一个list_node_t的地址，我改如何找到这个list_node_t对应的MyClass的data呢？这里用到了一段很优美的宏：

#define GET_ENTRY(ptr, type, member)\
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

第一眼肯定觉得晕，不急，我们一步一步来。首先看参数：

• ptr: list_node_t的地址

• type: 包含这个list_node_t的类型，对应上面的例子，就是Myclass

• member：这个list_node_t类型变量在MyClass中的变量名，需要这个得到改变量的offset

首先看

(&((type *)0)->member)

这个的意思是：如果有个type类型的变量，它的地址是0，那type类型中的member变量的地址是多少，其实就是这个member变量距离所属的type类型变量的偏移量。

然后是

((char *)(ptr)-(unsigned long)(&((type *)0)->member))

这就很清楚了，知道了偏移量，我又知道了真正的member变量的地址（ptr），用ptr的地址减去ptr的偏移量，就得到了ptr所在的type变量的地址了，然后就可以获取type变量上的数据了。

自己简单实现了intrusive list，再和std::list做一个简单的性能测试，对一个int数据的链表插入，结果是：std::list push_back的操作操作时间基本上都在intrusive list的2倍以上！这么看来，intrusive list的优势还是挺明显的。

QuXiaos-MacBook-Pro:intrusive_list quxiao$ ./a.out 1000
std_list: 0.129 ms
intrusive_list: 0.059 ms
QuXiaos-MacBook-Pro:intrusive_list quxiao$ ./a.out 10000
std_list: 1.297 ms
intrusive_list: 0.550 ms
QuXiaos-MacBook-Pro:intrusive_list quxiao$ ./a.out 100000
std_list: 11.961 ms
intrusive_list: 4.901 ms
QuXiaos-MacBook-Pro:intrusive_list quxiao$ ./a.out 1000000
std_list: 116.855 ms
intrusive_list: 53.086 ms
QuXiaos-MacBook-Pro:intrusive_list quxiao$ ./a.out 10000000
std_list: 1061.955 ms
intrusive_list: 544.419 ms

intrusive list的实现以及测试的代码如下：

#include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    #include <list>
    
    struct list_node_t
    {
        list_node_t* prev;
        list_node_t* next;
    };
    
    struct MyClass
    {
        int data;
        list_node_t node;
    };
    
    void _list_add(list_node_t* cur, list_node_t* prev, list_node_t* next)
    {
        prev->next = cur;
        next->prev = cur;
        cur->prev = prev;
        cur->next = next;
    }
    
    void list_add_head(list_node_t* cur, list_node_t* head)
    {
        _list_add(cur, head, head->next);
    }
    
    void list_add_tail(list_node_t* cur, list_node_t* head)
    {
        _list_add(cur, head->prev, head);
    }
    
    void list_del(list_node_t* cur)
    {
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;
        cur->prev = cur->next = NULL;
    }
    
    #define GET_ENTRY(ptr, type, member)\
        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
    
    #define INIT_NODE(ptr)\
        (ptr)->next = (ptr)->prev = ptr;
    
    #define list_for_each(pos, head) \
            for (pos = (head)->next; pos != (head); \
                            pos = pos->next)
    
    #define list_for_each_safe(pos, n, head) \
            for (pos = (head)->next, n = pos->next; pos != (head); \
                        pos = n, n = pos->next)
    
    void test_std_list(int run_num)
    {
        int t1 = clock();
        std::list<int> std_list;
        for (int i = 0; i < run_num; i ++)
        {
            std_list.push_back(i);
        }
    
        printf("std_list: %.3lf ms\n", double(clock() - t1) / CLOCKS_PER_SEC * 1000);
    }
    
    void test_intrusive_list(int run_num)
    {
        int t1 = clock();
        list_node_t list_head;
        INIT_NODE(&list_head);
    
        for (int i = 0; i < run_num; i ++)
        {
            MyClass* c = (MyClass*) malloc(sizeof(MyClass));
            c->data = i;
            list_add_tail(&c->node, &list_head);
        }
        printf("intrusive_list: %.3lf ms\n", double(clock() - t1) / CLOCKS_PER_SEC * 1000);
    }
    
    int main(int argc, char** argv)
    {
        if ( argc != 2 )
        {
            fprintf(stderr, "argc is not 2");
            return -1;
        }
        int run_num = atoi(argv[1]);
        if ( 0 == run_num )
        {
            fprintf(stderr, "argv[%s] is not num", argv[1]);
            return -1;
        }
    
        test_std_list(run_num);
        test_intrusive_list(run_num);
    
        return 0;
    }

另外，intrusive list还有几个特点，比如：

• 移植性好，不像数据包在链表里面的实现，要么每种链表类型都写重复的代码，要么就使用template，但只能在C++中使用

• 容易使用，你需要使用哪种类型的列表，就在这种类型中添加节点即可

• 可以方便实现一份数据被多个链表共享的情况，有几个链表，就在类型下添加几个节点变量即可，多个链表直接不会互相干扰

要不是看了那几篇博客，我对链表的认识还停留在教科书上，好歹也看了几本数据结构的书，其中不乏经典书籍，但从没有听说过intrusive list这种实现，看来很多知识，并不是光靠看书就能获取的。

参考材料：

• Strategy: Stop Using Linked-Lists

• Avoiding game crashes related to linked lists

• Tips of Linux C programming

• Linux Kernel Linked List Explained

—EOF—

Memcached中有以下几类线程：

• 主线程
• 工作线程
• 维护线程

主线程，又可以叫分发线程，除了完成程序的各种参数、以及其他线程的初始化以外，还会listen端口，新建连接，并且将该连接分发到其他的工作线程。

工作线程，大部分实际的工作都是他们干的，包括读取请求的协议内容、解析、进行具体存、取、更新、删除kv的操作，最后返回结果。

另外，还有一个维护线程，它的工作就是在需要的时候（存放的item大于总量的2/3）对hash表进行扩展。

Memcached处理请求时，采用的是单进程多线程的Master-Worker模型，通过libevent这个事件响应库来实现的。

首先来看一下主线程和工作线程之间是怎么交互的吧：

工作线程在初始化的时候，会建立一个pipe（管道），两端分别为：notify_receive_fd，以及notify_send_fd：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

for (i = 0; i < nthreads; i++) {
    int fds[2];
    if (pipe(fds)) {
        perror("Can't create notify pipe");
        exit(1);
    }

    threads[i].notify_receive_fd = fds[0];
    threads[i].notify_send_fd = fds[1];

    setup_thread(&threads[i]);
    /* Reserve three fds for the libevent base, and two for the pipe */
    stats.reserved_fds += 5;
}

也就是说当其他线程向notify_send_fd文件描述符写内容的时候，notify_receive_fd就可以接受到。

接着，就用到了libevent的API：

1
2
3
4
5
6
7
8
9
10
11

me->base = event_init();

/* Listen for notifications from other threads */
event_set(&me->notify_event, me->notify_receive_fd,
          EV_READ | EV_PERSIST, thread_libevent_process, me);
event_base_set(me->base, &me->notify_event);

if (event_add(&me->notify_event, 0) == -1) {
    fprintf(stderr, "Can't monitor libevent notify pipe\n");
    exit(1);
}

每个工作线程都新建一个libevent实例(me->base)，并且将notify_event绑定在这个实例上。

notify_event什么时候触发？ 当notify_receive_fd有内容的时候被触发。

触发了执行什么函数？ 执行thread_libevent_process (me)函数。

那在哪个地方会写notify_send_fd呢？ 在主线程将新建的连接分发给工作时，就会向某个线程的notify_send_fd写一个空的字符串用来唤醒这个线程。下面的代码一目了然：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void dispatch_conn_new(int sfd, enum conn_states init_state, int event_flags,
                       int read_buffer_size, enum network_transport transport) {
    CQ_ITEM *item = cqi_new();
    /*这就是所谓的round robin*/
    int tid = (last_thread + 1) % settings.num_threads;

    LIBEVENT_THREAD *thread = threads + tid;

    last_thread = tid;

    item->sfd = sfd;
    /* ... */

    cq_push(thread->new_conn_queue, item);

    if (write(thread->notify_send_fd, "", 1) != 1) {
        perror("Writing to thread notify pipe");
    }
}

首先来看看主线程，当他把其他工作线程、维护线程启起来之后，就开始侦听socket端口了（可以在memcached的源码中看出tcp和udp在处理逻辑上有很多不同的地方，但我不知道为什么不一样，就只看了处理tcp部分的代码，看来改补一补网络通信的知识了……），主要逻辑在server_sockets函数中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

if (IS_UDP(transport)) {
    int c;

    for (c = 0; c < settings.num_threads_per_udp; c++) {
        /* this is guaranteed to hit all threads because we round-robin */
        dispatch_conn_new(sfd, conn_read, EV_READ | EV_PERSIST,
                          UDP_READ_BUFFER_SIZE, transport);
    }
} else {
    if (!(listen_conn_add = conn_new(sfd, conn_listening,
                                     EV_READ | EV_PERSIST, 1,
                                     transport, main_base))) {
        fprintf(stderr, "failed to create listening connection\n");
        exit(EXIT_FAILURE);
    }
    listen_conn_add->next = listen_conn;
    listen_conn = listen_conn_add;
}

conn_new函数建立了连接之后，将socket文件描述符于event_handler函数绑定，当有socket请求过来的时候，就执行event_handler。在event_handler中，就是直接调用drive_machine这个大大的状态转移函数，一次连接的所有状态就都在这个函数里面处理了。

主线程首先达到drive_machine中的conn_listenning状态，然后通过dispatch_conn_new将这次的连接分配给某个工作线程，工作线程再经历其他的状态，完成一次请求。

drive_machine的具体逻辑比较复杂，这里就不讲了。

好，最后简单回顾下这个工作流程：

1. 主线程接受到memcached客户端的请求（是在哪儿一直接收请求的？）
2. 主线程通过round robin找到一个工作线程
3. 主线程将创建的连接push到工作线程的连接队列中，然后唤醒这个工作线程
4. 工作线程被唤醒后，从自己的线程队列中取出一个连接
5. 解析请求、对hash表进行相应的操作，写入返回

整体看下来，感觉memcached的源码并没有什么高深的算法，用的都是很朴素的链表、底层的网络通信、线程间互斥、字符串解析等等，感觉除了网络通信比较繁琐以外，其他的地方都是一个刚毕业的计算机专业的学生可以也应该掌握的。通过对一些简单、实用的东西进行有效的组合，就可以获取一个功能更强大的合成体。

—EOF—

入职一年多，在大公司里面学到了不少东西，比如学习了模块的开发流程，了解了公司的许多业务系统、模块，也体会到了不少工作中的“狼性”。但是工作的这一年多，尤其是最近这段时间，也感受到了大公司的一些“病”，今天来吐槽一下。（可能并不一定就是病，也可能和自身的理解有关，我这里只是罗列一下，仅代表个人观点）

会议太多

周一到周五，几乎每隔一天就要开上一次会，会议时间有长有短，短的15分钟，长的要开上一下午。虽然大部分的会议时间并不算很长，但也严重打断了我们RD的思路。经常是问题想了一半，然后被拉过去开会，开完会再试图把上下文切换回来，结果花费很长时间，说不定中间再被一个事情打断，那整个下午（或者上午）就算是废了。

大多数的会议，内容就是在过进度，PM这周做了哪些事，RD开发到什么进度了。这种事情大家每天写在一个公共的地方（比如日报、周报系统），让大家都能看到也就行了，不必每次都把所有相关人员聚到一个专门的会议室。大家来会议室，也都是带着自己的笔记本电脑，做自己的事情。做自己事情的效率、以及开会的效率都很低。

项目太多

公司大了，不管旧的项目维护，还是新的项目开发，都渐渐多了起来。这样一来，一个人所涉及到的项目也就多了起来。作为一个RD，经常需要维护A项目的升级、排查B项目的bug、再进行C项目的开发。你的C项目开发正进入状态的时候，让你再弄一下啊项目A和B，换做谁效率都高不了。对于QA，可能更悲剧，公司QA人手本来就少，结果项目、模块越来越多，QA经常一个项目接着一个项目进行测试，之前我甚至看到过一个QA的签名是“同时测10个模块……”，这么赶，测试case就不一定想得很周全了，线上出现问题的概率也会越来越大。

人员比例失调

不知为何，公司里面，PM（产品经理）：RD：QA差不多是3：2：1 这么个奇怪的比例，按我的理解，PM：RD：QA应该是1：2：2.5才比较合理，RD和QA，都算是开发，具体什么比例其实可以比较灵活；至于PM，应该保持少而精，1~2个人就能撑起一个规模不小的项目。对于目前公司PM的人数，我觉得是太多了。经常1个RD需要接口5~6个PM，别说是5、6个PM，就算是2、3个PM同一天有事联系你，也够RD同学喝一壶的，要是5、6个PM每周“均匀”地“骚扰”你，你也别干什么事了。

而且，许多PM同学也都是新人，经验明显不足，本来PM应该是给项目规划好一个大的方向，协调各方、共同朝这个方面努力的。结果许多新的PM是在一边参与项目，一边学习，能不添乱就已经很好了。许多PM，连基本的处理数据的能力都欠缺。经常是，PM有一个数据的需求，RD在服务器上运算好了，PM不会登录服务器，需要RD线下或者邮件提供，有的甚至一定要Excel格式的才行。数据里面多了一列、多了个逗号啥的，PM就不会处理了，需要RD调整一下格式再提供……

不过话说回来，还是有些PM是比较给力的，文档写得明确、数据也能自己处理，有的更给力的直接对RD说，“把mysql的账号密码告诉我，我自己跑sql”，对于RD来说，遇到这种PM真是件令人愉快的事情！

KPI

这个算是老生长谈了，每半年或者一年，大家都需要回顾一下过去，并对自己所做的事情打个分，还要展望一下未来，对于半年甚至一年之后的事情，做一下规划。回顾下过来也就算了，这是有必要的。对下一个半年进行规划，这就有点勉为其难的。比如项目刚刚开展实验，还不知道效果怎么样，如何确定半年里面对这个项目做规划，或者说半年里面，这个项目做不做还要打上一个问号呢。

另外，不同职位上的同学对于KPI的理解和要求不一致，也会导致许多问题。比如对于一个商业产品，PM的KPI会是指这个产品给公司带来了多少收益、新增了多少客户；而对于我们RD同学，我们KPI的定义除了收益之外，还有这个产品中的系统的稳定性、能够承受的性能指标，还有比如采用了什么新的技术，使得系统扩展性更好、同时减少人力的投入等等这些。

这样一来，双方为了达到各自的KPI，所采取的行为可能就是相悖的。比如对于一个新的商品产品，PM想到的往往是接几个大客户、大单子，这样一下子PM的KPI就很容易达标了。而如果是这样的话，对于RD来说，所需要做的工作可能就是：开发一个能够满足功能的系统、修改下配置、上线这几家客户。这对于RD来说，意义很小。

RD的想法一般是接入许多中小客户，使得大规模的客户能在系统中运转起来，产生规模效应，RD在这个过程中就可以依据线上的效果，对系统进行迭代的升级，以提高这个产品的整体收益。不过整个过程肯定是要花上不短的时间的，PM可能对于这个时间就不能接受了，毕竟接大单子一下子就有不小的收益，还体现了PM的工作能力，PM何乐而不为呢。

不过，KPI这种事，就像是高考一样，虽然有各种各样的弊端，不过对于一个有上万乃至十几万人的公司来说，可能已经算是最公平的方法了，谁让我们在一个大公司呢，呵呵。

—EOF—–

作为一名RD，作为一名后端RD，每天大部分的工作都是在终端上面完成的，除了在vim上面编写代码，也需要分析日志、数据，定时跑一些任务，因此各种shell、各种脚本语言也是不少用。罗列些自己平时工作中用到查看、处理文本的命令：

查看日志

平常查看模块打印的日志，肯定是必需的，比如需要知道一个模块重启后运行是否正常，需要查看请求返回的一些字段。日志比较小的话（100Mb以内），可以直接用vim打开，否则会把服务器内存全部吃掉，甚至把服务器搞挂。。。

文件太大的话，可以用less或者more命令打开，这样不会把整个文件都load到内存，然后再使用“/”或者”?“向后或者向前查找需要的字符串

有时只需要看看文件的头尾几行，看看日志的格式如何，用head以及tail就可以，特别，如果需要实时查看日志，则可以使用tail -f。

过滤日志

有时只需要获取日志的某些行，比如查找哪些行包含”FATAL”，就可以用

grep "FATAL" xxx.log

如果先是想看看有没有这类日志存在，就用管道结合wc -l

grep "FATAL" xxx.log | wc -l

也可以结合之前的less、head、tail查看部分日志

grep "FATAL" xxx.log | less

如果是想获取日志中的某些字段，可以使用cut命令进行分割

假设有如下日志：

1 2 3 4 5

11 12 13 14 15

获取第三列，用cat xxx.log | cut -d'\t' -f3，就可以得到

3

13

有时候，日志比较复杂，比如：

a=1,b=2,c=3

比如还是获取第三列，则可以：

cat xxx.log | cut -d',' -f3 | cut -d'=' -f2

过滤日志，也可以使用awk，但感觉如何不是对于日志的数据进行计算，只用awk进行过滤，未免有些大材小用了，呵呵。

计算日志字段

好，这个时候awk就可以排上用场了，它不但能对字段进行过滤、累加、对日志按类似C语言printf()的格式进行输出，还可以进行dict运算。比如有一份日志保存着每次请求的query字段：

htc

iphone4s

htc

sumsung

xiaomi

我需要知道每个query的频次，用几行python应该也能很快搞定，不过用awk，仅需用一行：

cat xxx.log | awk '{dict[$1]++;} END{for(i in dict){printf "query:[%s] pv:[%d]\n", i, dict[i];}}'

query:[xiaomi] pv:[1]

query:[sumsung] pv:[1]

query:[htc] pv:[2]

query:[iphone4s] pv:[1]

遍历文件

有时候需要依次对一些文件进行相同的处理，如果只是想遍历文件一个文件夹下面的某些文件，可以直接

for file in ./*.log; do echo "$file"; done

./zhixin_stat.log ./zhixin_stat.py.log

有时候需要构造一些序列，一般情况，用类似C语言的for循环，比如：

for ((i=0; i<=10; i++)); do echo 201304$i; done

2013040 2013041 2013042 2013043 2013044 2013045 2013046 2013047 2013048 2013049 20130410

但是可以发现，生成的序列宽度是不一样的，就需要用到seq命令了，它可能生成固定宽度的序列：

for i in `seq -w 1 10`; do echo 201304$i; done

20130401 20130402 20130403 20130404 20130405 20130406 20130407 20130408 20130409 20130410

用python进行排序

统计数据，难免需要对某几个维度进行分析，在python中进行排序，无非就是对于一个list进行排序，list中的元素一般为某个class或者一个dict。

对于排序class，需要定义’<‘, ’>‘, ’<=‘, ’>=‘, ’==‘, ’!=‘六种比较行为，就好像C++中的operator重载一样。具体Python doc中这篇HowTo讲解的很清楚，这里不再赘述了。

对于dict进行排序，如果需要按照dict的某个key进行排序，则可以这么写：

from operator import itemgetter
#按照name字段进行排序  
newlist = sorted(list_to_be_sorted, key=itemgetter('name'))

用python发送邮件

好了，文本统计完了，生成了一份统计报表，这时候可能就需要我们通过邮件的形式发送给同事看。用crontab每天凌晨开始抓数据、跑统计、然后把统计数据邮件给大家，显得专业！

发送邮件的功能，可以用python + sendmail实现：

from os import path
import datetime
import time
import sys
import subprocess
import smtplib
from email.mime.text import MIMEText
from email.mime.multipart import MIMEMultipart
from email.mime.application import MIMEApplication

sender = 'quxiao@somewhere.com'
receiver = 'someone@somewhere.com'

def main(date):
    EmailBody = 'blablabla'
    msg = MIMEMultipart()
    msg['Subject'] = 'some subject'
    msg['From'] = sender
    msg['To'] = receiver
    msg.attach(MIMEText(EmailBody,'html','GB18030'))
    #send
    proc = subprocess.Popen(['/usr/lib/sendmail','-t'],stdin = subprocess.PIPE)
    proc.stdin.write(str(msg))
    proc.stdin.close()

—EOF—

item是memcached操作的最小单位，一个item包括以下数据：

• struct item 本身大小
• key (uint8_t)
• suffix (uint8_t)，内容是" %d %d\r\n", flag, nbytes-2
• value
• CAS（optional, uint64_t）

(参考do_item_alloc && item_make_header)

与item相关的操作有以下几种

分配item

流程如下：

1. 确定item大小——ntotal
2. 找到合适的slab
3. 看该slab的（LRU）tails中是否有item
   • 如果tails没有，在该slab上申请ntotal大小的内存
   • 如果a) tails上面有item，并且b)其引用计数（refcount）为0，c)item是过期的（time和exptime），那么
     • 重新计算这个slab上面分配的总item大小，
     • 更新关联数组（do_item_unlink_noblock），就是链表的删除节点操作。
     • （注意：_hashitem_before()函数中，使用了&引用操作）
   • 如果slab上面试图分配但是分配不到，并且最tails上的item没有过期（expire）
     • 如果不允许将item给evict，return NULL
     • 否则，a) 只好把这个tails上的item给evict掉; b) 重新计算这个slab上面分配的总item大小; c) 删除关联数组中的该item节点
4. 初始化item各个字段

 free item

1. 当一个item的引用计数为0时，就将这个item“释放”（其实没有真正的释放）
2. 计算item的大小ntotal
3. 判断是在哪个slab_class上
4. 在该slab_class上，释放ntotal大小的空间（之前的slab上释放空间的操作）

hashtable && heads && tails

当对item进行创建、删除等操作的时候，除了在slab上进行申请、释放空间之外，还需要更新以下数据：

• item的time和flag
• 全局stats
• primary_hashtable
• 与item对应的slab的heads和tails数组

其中，

time就是当前创建时间，flag表示item目前的状态（TODO）

primary_hashtable是一个item**结构

primary_hashtable的大小是2 ^ hashpower，hashpower默认大小为16

item与primary_hashtable的对应关系为：

hash_key(item) & (2^hashporwer - 1)

heads和tails数组用于记录每一个slab_class的item*的链表，用于进行LRU淘汰，所以说，memcached的LRU算法是每个slab_class独立的。

—EOF—

memcached的内存结构中，内存被分为一个一个的页（slab），每一个slab会被分到不同的slab_class。不同的slab_class，申请的item大小就不一样。

slab_class所对应的数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

typedef struct {

    //当前slab_class的最大item大小
    unsigned int size;      /* sizes of items */
    //当前slab_class每一个slab的item数
    unsigned int perslab;   /* how many items per slab */
    //被释放过的item的list
    void **slots;           /* list of item ptrs */
    //free list大小
    unsigned int sl_total;  /* size of previous array */
    //free list下标 
    unsigned int sl_curr;   /* first free slot */
    //最近申请的page(slab)的指针
    void *end_page_ptr;         /* pointer to next free item at end of page, or 0 */
    //最近申请的page(slab)所剩的item个数
    unsigned int end_page_free; /* number of items remaining at end of last alloced page */
    //当前slab_class申请了多少slab(page)
    unsigned int slabs;     /* how many slabs were allocated for this class */
    //申请的slab的指针数组
    void **slab_list;       /* array of slab pointers */
    unsigned int list_size; /* size of prev array */
    //没用到？
    unsigned int killing;  /* index+1 of dying slab, or zero if none */
    size_t requested; /* The number of requested bytes */

} slabclass_t;

slab初始化

memcached的slab初始化比较简单，主要是设定一些字段的大小，逻辑如下：

下标i从0开始遍历每一个slab class：

• 对齐当前slab class的size，使其是CHUNK_ALIGN_BYTES字节对齐的。
• 设置slabclass[i] 为size
• 设置当前slab class中，每一页能存放的iterm数据slabclass[i].perslab
• 更新size为下一个slab class的size
• 设置最大的一个slab class，其中size = setting.item_size_max, perslab = 1

 slab分配内存

• 如果是采用系统的malloc，就是直接申请；
• 如果是预先申请了所有的内存的话，依次通过以下手段获取内存：
  • 之前被“free”掉的item的地址会被标记在freelist中，如果freelist中有，则直接从freelist中拿；
  • 如果最近申请过的页中还有剩余空间，则从页的末尾申请item
  • 申请一个新的page

释放slab上的item空间

• 如果是系统分配，free指针，mem_malloc –= size；
• 否则，将地址设置到free_list末尾，如果free_list满了，double一下长度