程序員的成長之路

互聯(lián)網(wǎng)/程序員/技術/資料共享?

來自：https://github.com/CyC2018/CS-Notes

• 一、概述

• 二、數(shù)據(jù)類型

• STRING

• LIST

• SET

• HASH

• ZSET

• 三、數(shù)據(jù)結(jié)構

• 字典

• 跳躍表

• 四、使用場景

• 計數(shù)器

• 緩存

• 查找表

• 消息隊列

• 會話緩存

• 分布式鎖實現(xiàn)

• 其它

• 五、Redis 與 Memcached

• 數(shù)據(jù)類型

• 數(shù)據(jù)持久化

• 分布式

• 內(nèi)存管理機制

• 六、鍵的過期時間

• 七、數(shù)據(jù)淘汰策略

• 八、持久化

• RDB 持久化

• AOF 持久化

• 九、事務

• 十、事件

• 文件事件

• 時間事件

• 事件的調(diào)度與執(zhí)行

• 十一、復制

• 連接過程

• 主從鏈

• 十二、Sentinel

• 十三、分片

• 十四、一個簡單的論壇系統(tǒng)分析

• 文章信息

• 點贊功能

• 對文章進行排序

• 參考資料

一、概述

二、數(shù)據(jù)類型

What Redis data structures look like

STRING

> set hello world
OK
> get hello
"world"
> del hello
(integer) 1
> get hello
(nil)

LIST

> rpush list-key item
(integer) 1
> rpush list-key item2
(integer) 2
> rpush list-key item
(integer) 3

> lrange list-key 0 -1
1) "item"
2) "item2"
3) "item"

> lindex list-key 1
"item2"

> lpop list-key
"item"

> lrange list-key 0 -1
1) "item2"
2) "item"

SET

> sadd set-key item
(integer) 1
> sadd set-key item2
(integer) 1
> sadd set-key item3
(integer) 1
> sadd set-key item
(integer) 0

> smembers set-key
1) "item"
2) "item2"
3) "item3"

> sismember set-key item4
(integer) 0
> sismember set-key item
(integer) 1

> srem set-key item2
(integer) 1
> srem set-key item2
(integer) 0

> smembers set-key
1) "item"
2) "item3"

HASH

> hset hash-key sub-key1 value1
(integer) 1
> hset hash-key sub-key2 value2
(integer) 1
> hset hash-key sub-key1 value1
(integer) 0

> hgetall hash-key
1) "sub-key1"
2) "value1"
3) "sub-key2"
4) "value2"

> hdel hash-key sub-key2
(integer) 1
> hdel hash-key sub-key2
(integer) 0

> hget hash-key sub-key1
"value1"

> hgetall hash-key
1) "sub-key1"
2) "value1"

ZSET

> zadd zset-key 728 member1
(integer) 1
> zadd zset-key 982 member0
(integer) 1
> zadd zset-key 982 member0
(integer) 0

> zrange zset-key 0 -1 withscores
1) "member1"
2) "728"
3) "member0"
4) "982"

> zrangebyscore zset-key 0 800 withscores
1) "member1"
2) "728"

> zrem zset-key member1
(integer) 1
> zrem zset-key member1
(integer) 0

> zrange zset-key 0 -1 withscores
1) "member0"
2) "982"

三、數(shù)據(jù)結(jié)構

字典

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

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

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;

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    int empty_visits = n * 10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while (n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long) d->rehashidx);
        while (d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while (de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

跳躍表

• 插入速度非常快速，因為不需要進行旋轉(zhuǎn)等操作來維護平衡性；

• 更容易實現(xiàn)；

• 支持無鎖操作。

四、使用場景

計數(shù)器

緩存

查找表

消息隊列

會話緩存

分布式鎖實現(xiàn)

其它

五、Redis 與 Memcached

數(shù)據(jù)類型

數(shù)據(jù)持久化

分布式

內(nèi)存管理機制

• 在 Redis 中，并不是所有數(shù)據(jù)都一直存儲在內(nèi)存中，可以將一些很久沒用的 value 交換到磁盤，而 Memcached 的數(shù)據(jù)則會一直在內(nèi)存中。

• Memcached 將內(nèi)存分割成特定長度的塊來存儲數(shù)據(jù)，以完全解決內(nèi)存碎片的問題。但是這種方式會使得內(nèi)存的利用率不高，例如塊的大小為 128 bytes，只存儲 100 bytes 的數(shù)據(jù)，那么剩下的 28 bytes 就浪費掉了。

六、鍵的過期時間

七、數(shù)據(jù)淘汰策略

八、持久化

RDB 持久化

AOF 持久化

• always 選項會嚴重減低服務器的性能；

• everysec 選項比較合適，可以保證系統(tǒng)崩潰時只會丟失一秒左右的數(shù)據(jù)，并且 Redis 每秒執(zhí)行一次同步對服務器性能幾乎沒有任何影響；

• no 選項并不能給服務器性能帶來多大的提升，而且也會增加系統(tǒng)崩潰時數(shù)據(jù)丟失的數(shù)量。

九、事務

十、事件

文件事件

時間事件

• 定時事件：是讓一段程序在指定的時間之內(nèi)執(zhí)行一次；

• 周期性事件：是讓一段程序每隔指定時間就執(zhí)行一次。

事件的調(diào)度與執(zhí)行

def aeProcessEvents():
    # 獲取到達時間離當前時間最接近的時間事件
    time_event = aeSearchNearestTimer()
    # 計算最接近的時間事件距離到達還有多少毫秒
    remaind_ms = time_event.when - unix_ts_now()
    # 如果事件已到達，那么 remaind_ms 的值可能為負數(shù)，將它設為 0
    if remaind_ms < 0:
        remaind_ms = 0
    # 根據(jù) remaind_ms 的值，創(chuàng)建 timeval
    timeval = create_timeval_with_ms(remaind_ms)
    # 阻塞并等待文件事件產(chǎn)生，最大阻塞時間由傳入的 timeval 決定
    aeApiPoll(timeval)
    # 處理所有已產(chǎn)生的文件事件
    procesFileEvents()
    # 處理所有已到達的時間事件
    processTimeEvents()

def main():
    # 初始化服務器
    init_server()
    # 一直處理事件，直到服務器關閉為止
    while server_is_not_shutdown():
        aeProcessEvents()
    # 服務器關閉，執(zhí)行清理操作
    clean_server()

十一、復制

連接過程

1. 主服務器創(chuàng)建快照文件，發(fā)送給從服務器，并在發(fā)送期間使用緩沖區(qū)記錄執(zhí)行的寫命令。快照文件發(fā)送完畢之后，開始向從服務器發(fā)送存儲在緩沖區(qū)中的寫命令；

2. 從服務器丟棄所有舊數(shù)據(jù)，載入主服務器發(fā)來的快照文件，之后從服務器開始接受主服務器發(fā)來的寫命令；

3. 主服務器每執(zhí)行一次寫命令，就向從服務器發(fā)送相同的寫命令。

主從鏈

十二、Sentinel

十三、分片

• 最簡單的方式是范圍分片，例如用戶 id 從 0~1000 的存儲到實例 R0 中，用戶 id 從 1001~2000 的存儲到實例 R1 中，等等。但是這樣需要維護一張映射范圍表，維護操作代價很高。

• 還有一種方式是哈希分片，使用 CRC32 哈希函數(shù)將鍵轉(zhuǎn)換為一個數(shù)字，再對實例數(shù)量求模就能知道應該存儲的實例。

• 客戶端分片：客戶端使用一致性哈希等算法決定鍵應當分布到哪個節(jié)點。

• 代理分片：將客戶端請求發(fā)送到代理上，由代理轉(zhuǎn)發(fā)請求到正確的節(jié)點上。

• 服務器分片：Redis Cluster。

十四、一個簡單的論壇系統(tǒng)分析

• 可以發(fā)布文章；

• 可以對文章進行點贊；

• 在首頁可以按文章的發(fā)布時間或者文章的點贊數(shù)進行排序顯示。

文章信息

點贊功能

對文章進行排序

參考資料

• Carlson J L. Redis in Action[J]. Media.johnwiley.com.au, 2013.

• 黃健宏. Redis 設計與實現(xiàn) [M]. 機械工業(yè)出版社, 2014.

• REDIS IN ACTION

• Skip Lists: Done Right

• 論述 Redis 和 Memcached 的差異

• Redis 3.0 中文版- 分片

• Redis 應用場景

• Using Redis as an LRU cache

推薦閱讀：

【98期】面試官：給我說說你對Java GC機制的理解？

【97期】一網(wǎng)打盡面試中常被問及的8種數(shù)據(jù)結(jié)構

【96期】盤點那些關于Nginx的常考面試題

微信掃描二維碼，關注我的公眾號

朕已閱?