chaomai's Odyssey

redis dict

chaomai published on 2019-12-03 included in Redis

结构

dict使用链地址法解决冲突，size为$2^n$，sizemask = size - 1，用于计算key所属的bucket上，避免了mod，还便于处理scan时发生rehash的情况。每个dict有两个dictht，多个出来的一个用于rehash。

redis list

chaomai published on 2019-12-02 included in Redis

结构

reids的list采用的是双向链表的实现，未使用dummy node。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;

特点

双端
无环
有头尾指针
有长度计数器
多态（使用void*来保存节点值，并提供free，dup，match来处理节点）

redis sds

chaomai published on 2019-11-26 included in Redis

结构

sds主要由len，alloc和buf构成。其中buf是柔性数组，分配sds的时候，这个结构体会作为header。

 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
typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

// 如果没有packed，那么sizeof(sdshdr32) =
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
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[];
};

为sds分配空间，initlen是字符串的长度，1是末尾的’\0’。

go踩坑合集

chaomai published on 2019-09-20 included in Golang

RWMutex RLock重入导致死锁

RWMutex，即读写锁，可以被多个的reader或一个writer获取使用。

死锁例子

在使用RWMutex的时候，同一个reader是不应该连续调用Rlock多次的，这样做不但没有意义，还有可能导致死锁，具体代码如下：

python multiprocessing.Queue模块源码阅读

chaomai published on 2019-09-10 included in Python

之前有记录过python Queue的使用，以及multiprocessing.Process模块。现在看看multiprocessing.Queue的具体工作方式（本文基于Python 3.7.4）。

multiprocessing.Queue定义在queues.py中，除此之外还定义了SimpleQueue和JoinableQueue，是FIFO队列。

python multiprocessing.Process模块源码阅读

chaomai published on 2019-09-09 included in Python

之前有记录过python进程间通信的几个方式，现在来看看这个模块的具体的是怎样工作的（本文基于Python 3.7.4）。

multiprocessing.Process典型的使用方式为，

1
2
3
4
5
6
7
8
import multiprocessing

def f(name):
    print('hello', name)

p = multiprocessing.Process(target=f, args=('world',))
p.start()
p.join()

以这段代码为例，看看进程的执行过程。