Redis是工作中很常用的，這里將比較普遍使用的結(jié)構(gòu)研究了下做個(gè)備忘。
hash
實(shí)現(xiàn)和dnspod的dataset半斤八兩，本質(zhì)上是個(gè)二維數(shù)組，通過(guò)將key哈希作為一維的下表，第二維的數(shù)組存相同哈希的元素，查找使用遍歷的方式，所以這里redis做了優(yōu)化，當(dāng)滿(mǎn)足條件的時(shí)候(數(shù)組數(shù)量太大)會(huì)進(jìn)行rehash，動(dòng)態(tài)擴(kuò)大桶的數(shù)量來(lái)減少最后一維遍歷的次數(shù).
函數(shù)名稱(chēng) | 作用 | 復(fù)雜度 |
dictCreate | 創(chuàng)建一個(gè)新字典 | O(1) |
dictResize | 重新規(guī)劃字典的大小 | O(1) |
dictExpand | 擴(kuò)展字典 | O(1) |
dictRehash | 對(duì)字典進(jìn)行N步漸進(jìn)式Rehash | O(N) |
_dictRehashStep | 對(duì)字典進(jìn)行1步嘗試Rehash | O(N) |
dictAdd | 添加一個(gè)元素 | O(1) |
dictReplace | 替換給定key的value值 | O(1) |
dictDelete | 刪除一個(gè)元素 | O(N) |
dictRelease | 釋放字典 | O(1) |
dictFind | 查找一個(gè)元素 | O(N) |
dictFetchValue | 通過(guò)key查找value | O(N) |
dictGetRandomKey | 隨機(jī)返回字典中一個(gè)元素 | O(1) |
字典結(jié)構(gòu)
typedef struct dict {
// 類(lèi)型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在運(yùn)行的安全迭代器的數(shù)量
int iterators; /* number of iterators currently running */
} dict;
這里哈希表有兩個(gè)，一般都用ht[0]，當(dāng)需要rehash的時(shí)候會(huì)創(chuàng)建一個(gè)比ht[0]大的 2 的 N 次方的ht[1]，然后漸進(jìn)式的將數(shù)據(jù)dictEntry移過(guò)去(除了定時(shí)的rehash，在每次操作哈希表時(shí)都會(huì)_dictRehashStep)，完成后將ht[1]替換ht[0]
zset
zset本質(zhì)就是list,只不過(guò)每個(gè)元素都有若干個(gè)指向后繼span長(zhǎng)的指針，這樣簡(jiǎn)單的設(shè)計(jì)大大提高了效率，使得可以比擬平衡二叉樹(shù)，查找、刪除、插入等操作都可以在對(duì)數(shù)期望時(shí)間內(nèi)完成，對(duì)比平衡樹(shù)，跳躍表的實(shí)現(xiàn)要簡(jiǎn)單直觀很多。
/* ZSETs use a specialized version of Skiplists */
/*
* 跳躍表節(jié)點(diǎn)
*/
typedef struct zskiplistNode {
// 成員對(duì)象
robj *obj;
// 分值
double score;
// 后退指針
struct zskiplistNode *backward;
// 層
struct zskiplistLevel {
// 前進(jìn)指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
/*
* 跳躍表
*/
typedef struct zskiplist {
// 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
struct zskiplistNode *header, *tail;
// 表中節(jié)點(diǎn)的數(shù)量
unsigned long length;
// 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
int level;
} zskiplist;
/*
* 有序集合
*/
typedef struct zset {
// 字典，鍵為成員，值為分值
// 用于支持 O(1) 復(fù)雜度的按成員取分值操作
dict *dict;
// 跳躍表，按分值排序成員
// 用于支持平均復(fù)雜度為 O(log N) 的按分值定位成員操作
// 以及范圍操作
zskiplist *zsl;
} zset;
雖然這種方式排序查找很快，但是修改的話(huà)就得多做些工作了
/* Delete an element with matching score/object from the skiplist.
*
* 從跳躍表 zsl 中刪除包含給定節(jié)點(diǎn) score 并且?guī)в兄付▽?duì)象 obj 的節(jié)點(diǎn)。
*
* T_wrost = O(N^2), T_avg = O(N log N)
*/
int zslDelete(zskiplist *zsl, double score, robj *obj)
intset
typedef struct intset {
uint32_t encoding; //所使用類(lèi)型的長(zhǎng)度，4\8\16
uint32_t length; //元素個(gè)數(shù)
int8_t contents[]; //保存元素的數(shù)組
} intset;
intset其實(shí)就是數(shù)組，有序、無(wú)重復(fù)地保存多個(gè)整數(shù)值，查找用的是二分查找 * T = O(log N)，添加的話(huà)在找到對(duì)應(yīng)的數(shù)組中應(yīng)該存在的位子后使用memmove向后移出空位填補(bǔ)(當(dāng)然需要先realloc預(yù)分配空間)，同理刪除也是用memmove向前移動(dòng)
set
當(dāng)使用整數(shù)時(shí)，使用intset，否則使用哈希表
其他的關(guān)于網(wǎng)絡(luò)事件處理，epoll，回調(diào)，拆包都和正常使用差不多，關(guān)于錯(cuò)誤處理EINTR(系統(tǒng)調(diào)用期間發(fā)生中斷)和EAGAIN 繼續(xù)重試而如果是EPOLLHUP或EPOLLERR則讓io該讀讀該寫(xiě)寫(xiě)，有錯(cuò)處理就是了。