1. Redis 與Memcached 的對比

1.1 數(shù)據(jù)Eviction

• 作用是刪除舊數(shù)據(jù)來釋放空間.
• Memcached 適用LRU(Least Recently Used) 來任意地騰出新數(shù)據(jù)需要的空間.
• Redis ?適用惰性+定期策略來獲取更好的控制.
  • 定時(shí)刪除. 使用定時(shí)器對內(nèi)存友好但是CPU不友好.
  • 惰性刪除. 僅當(dāng)取key時(shí)才進(jìn)行刪除. 對CPU友好.
  • 定期刪除. 難點(diǎn)是確定刪除操作執(zhí)行的時(shí)長和頻率.

1.2 存儲的對象

• Memcached 中的key 要小于250B, value 要小于1MB. 且僅支持String 類型.
• Redis 中的key 和value 的最大尺寸都是512MB. 支持六種數(shù)據(jù)類型.

2. Redis 的數(shù)據(jù)類型

2.1 簡單動(dòng)態(tài)字符串(SDS: Simple Dynamic String)

• C字符串只用在只讀的地方.
  • 獲取長度復(fù)雜度為O(N).
  • 不記錄長度導(dǎo)致很容易造成buffer overflow.
    • 典型的場景: strcat(s1,s2).
• SDS 結(jié)構(gòu)體
  struct sdshdr = len + free + char[] buf;
  • 解決了C字符串的問題:
    • 獲取字符串長度的復(fù)雜度為O(1).
    • 自動(dòng)擴(kuò)展的空間分配策略, 杜絕了發(fā)生buffer overflow的可能性.
  • 減少修改字符串時(shí)帶來的內(nèi)存重新分配次數(shù).
    • 空間預(yù)分配.
      • 修改后,若SDS的長度小于1M, 那么free=len; 若大于1M, 那么free=1M.
      • 將連續(xù)增長N次字符串所需的內(nèi)存重新分配次數(shù)減少為最多N次.
    • 惰性空間釋放.
      • 優(yōu)化SDS縮短操作. 使用free 記錄縮短的字節(jié).
      • 在有需要時(shí),可以真正地釋放free空間.
  • 二進(jìn)制安全(char[]).
    • 可以保存任意格式的二進(jìn)制數(shù)據(jù).
    • C字符串必須符合某種編碼,以\0結(jié)尾, 所以只能保存文本.
  • 兼容部分C字符串函數(shù)
    • 因?yàn)橐診0為結(jié)尾.可以應(yīng)用諸如strcasecmp,strcat 字符串的操作.

2.2 鏈表

typeof struct listNode { prev, next, value};
typeof struct list{ head, tail, len, dup, free, match};

• 特性:
  • 高效的節(jié)點(diǎn)重排, 順序性的節(jié)點(diǎn)訪問方式.
  • 雙端,無環(huán),多態(tài).
  • 將一組value綁定到single key上.
  • 雙向鏈表,支持反向查找和遍歷.
• 適用場景:
  • 顯式最新項(xiàng)目列表: 維持newest 100用戶/新聞.
  • shared queue.
  • twitter的關(guān)注列表,粉絲列表.
  • 消息隊(duì)列.

2.3 字典

dictEntry{ key, union{void*,int64_t,uint64_t} next};
dictht{ *table, size, sizemask, used};
dict{ type, privatedata, ht[2],trehashidx};

• 實(shí)現(xiàn)細(xì)節(jié)
  • type為類型特定函數(shù)(不同用途的字典有不同的特定函數(shù)).
  • ht[1]僅在做過rehash后才會有值.

• 哈希算法.
  • 先hashFunction(key)計(jì)算出hash值, 然后根據(jù)hash值和sizemask計(jì)算出在table中的索引值.
• 解決key collision.
  • 將hash值相同的多個(gè)key(使用next)鏈接成表.
• rehash. 當(dāng)負(fù)載因子大于1時(shí)自動(dòng)擴(kuò)展,小于0.1時(shí)自動(dòng)收縮.
  • load_factor = ht[0].used/ht[0].size.
  • 過程: 為ht[1]進(jìn)行空間分配 -> 將h[0]上的鍵值對rehash后保存到ht[1]上 -> 釋放ht[0] -> 交換ht[1/0].
• 漸進(jìn)式rehash.
  • 在數(shù)據(jù)量大時(shí),避免rehash對服務(wù)器性能造成影響.
  • 在rehash期間, 每次對字典的更新操作時(shí), 順帶將rehashidx上的鍵值對rehash至ht[1]. 直至完成為-1.

2.4 跳躍表

  zskiplist{ header, tail, level, length}. 
  zskiplistNode{ level[], backward, score,obj}

• 實(shí)現(xiàn)細(xì)節(jié)
  • level不含header的層高, 等于前進(jìn)指針 + 跨度.
    • 遍歷時(shí),會沿著前進(jìn)指針進(jìn)行.
    • 當(dāng)創(chuàng)建節(jié)點(diǎn)時(shí),根據(jù)power law(越大的樹出現(xiàn)的概率越小),隨機(jī)生成1~32j的level值.
    • 跨度用以計(jì)算rank. 在查找節(jié)點(diǎn)時(shí),將訪問過的層跨度累加就是rank.
  • backward 用于反項(xiàng)遍歷時(shí), 指向前一個(gè)節(jié)點(diǎn).
    • 當(dāng)只有一個(gè)時(shí), 只能后退至前一個(gè).
  • 節(jié)點(diǎn)按照score從小到大排列.
    • 相同score的多個(gè)節(jié)點(diǎn), 以obj的字典序從小到大排序.

2.4 Set

• 無重復(fù)的List.

• 內(nèi)部實(shí)現(xiàn): value=null的HashMap. 通過計(jì)算hash來快速排重.
• 適用場景:
  • 跟蹤friends/tags. 提供了判斷某成員是否在set內(nèi)的接口.
  • 所有粉絲,關(guān)注人的集合.交集,并集,差集,來實(shí)現(xiàn)共同關(guān)注,共同愛好.

2.5 Sorted Set

• 內(nèi)部實(shí)現(xiàn): HashMap(成員到score的映射)和SkipList(所有成員,獲得較高的查找效率).
  • 每個(gè)value關(guān)聯(lián)score字段,并使用score進(jìn)行sort.
• 插入有序,自動(dòng)排序.
• ?適用場景:
  • score來跟蹤時(shí)間序列,基于game score來rank player.
  • 高分跟蹤.
  • 帶權(quán)重的隊(duì)列.

2.6 整數(shù)集合

  inset{ encoding, length, contents[]};

• 實(shí)現(xiàn)細(xì)節(jié)
  • encoding指定int16/32/64.
  • contents中值以從小到大排列, 且無重復(fù).

• 升級: 添加的新元素超出現(xiàn)有encoding的max時(shí).
  • 首先會擴(kuò)充contents的空間.
  • 優(yōu)勢: 提升靈活性, 節(jié)省內(nèi)存.
  • 同時(shí),不支持降級.
  • 升級后, 編碼會一直保持在升級后的狀態(tài).