Redis之整数集合intset
intset是Redis集合的底層實現(xiàn)之一,當(dāng)存儲整數(shù)集合并且數(shù)據(jù)量較小的情況下Redis會使用intset作為set的底層實現(xiàn)。當(dāng)數(shù)據(jù)量較大或者集合元素為字符串時則會使用dict實現(xiàn)set。
intset將整數(shù)元素按順序存儲在數(shù)組里,并通過二分法降低查找元素的時間復(fù)雜度。數(shù)據(jù)量大時,依賴于“查找”的命令(如SISMEMBER)就會由于O(logn)的時間復(fù)雜度而遇到一定的瓶頸,所以數(shù)據(jù)量大時會用dict來代替intset。但是intset的優(yōu)勢就在于比dict更省內(nèi)存,而且數(shù)據(jù)量小的時候O(logn)未必會慢于O(1)的hash function。這也是intset存在的原因。
intset結(jié)構(gòu)體聲明
typedef struct intset {uint32_t encoding; //intset的類型編碼uint32_t length; //成員元素的個數(shù)int8_t contents[];//用來存儲成員的柔性數(shù)組 }需要注意contents數(shù)組成員被聲明為int8_t類型并不表示contents里存的是int8_t類型的成員,這個類型聲明對于contents來說可以認(rèn)為是毫無意義的,因為intset成員是什么類型完全取決于encoding變量的值。encoding提供下面三種值:
#define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t))如果intset的encoding為INTSET_ENC_INT16,則contents的每個成員的“邏輯類型”都為int16_t。
雖然每個成員的“實際類型”是int8_t,無法直接通過contents[x]取出索引為x的成員元素,但是intset.c里提供了些函數(shù),可以按照不同的encoding方式設(shè)置/取出contents的成員。(用指針設(shè)置,memcpy取出)
由于這種方法在內(nèi)存上暴力地賦值與取值,所以希望元素在不同機器上存儲的字節(jié)序一致,但是不同處理器 在內(nèi)存中存放數(shù)據(jù)的方式不一定相同,主要分為大端字節(jié)序和小端字節(jié)序。 大小端字節(jié)序自己網(wǎng)上搜索資料進行學(xué)習(xí)。
如果老老實實通過contents[x]的方式賦值取值,我們就不需要考慮這個字節(jié)序的問題,但是intset根據(jù)encoding的值指定元素的地址偏移,暴力地對內(nèi)存進行操作。若數(shù)據(jù)被截斷了,則大端機器和小端機器會表現(xiàn)出不統(tǒng)一的狀況。為了避免這種情況發(fā)生,intset不管在什么機器上都按照同一種字節(jié)序(小端)在內(nèi)存中存intset的成員變量。
redis源碼中使用了比較暴力的方式進行大小端的轉(zhuǎn)換:以64位的轉(zhuǎn)換為例.
/* variants of the function doing the actual convertion only if the target* host is big endian */ #if (BYTE_ORDER == LITTLE_ENDIAN) #define memrev16ifbe(p) #define memrev32ifbe(p) #define memrev64ifbe(p) #define intrev16ifbe(v) (v) #define intrev32ifbe(v) (v) #define intrev64ifbe(v) (v) #else #define memrev16ifbe(p) memrev16(p) #define memrev32ifbe(p) memrev32(p) #define memrev64ifbe(p) memrev64(p) #define intrev16ifbe(v) intrev16(v) #define intrev32ifbe(v) intrev32(v) #define intrev64ifbe(v) intrev64(v) #endif//翻轉(zhuǎn) void memrev64(void *p) {unsigned char *x = p, t;t = x[0];x[0] = x[7];x[7] = t;t = x[1];x[1] = x[6];x[6] = t;t = x[2];x[2] = x[5];x[5] = t;t = x[3];x[3] = x[4];x[4] = t; } uint64_t intrev64(uint64_t v) {memrev64(&v);return v; }intset基本操作
底層賦值/取值操作
通過_intsetSet和_intsetGet這兩個工具函數(shù),可以根據(jù)intset的encoding 讀/寫contents里索引為pos的值。這是后續(xù)intset操作的基礎(chǔ)。
/* Set the value at pos, using the configured encoding. */ //按照intset的encoding設(shè)置指定位置pos的值 static void _intsetSet(intset *is, int pos, int64_t value) {uint32_t encoding = intrev32ifbe(is->encoding);if (encoding == INTSET_ENC_INT64) {((int64_t*)is->contents)[pos] = value;//大端機器在設(shè)置contents時將數(shù)據(jù)按字節(jié)翻轉(zhuǎn),按照小端序存儲memrev64ifbe(((int64_t*)is->contents)+pos);} else if (encoding == INTSET_ENC_INT32) {((int32_t*)is->contents)[pos] = value;memrev32ifbe(((int32_t*)is->contents)+pos);} else {((int16_t*)is->contents)[pos] = value;memrev16ifbe(((int16_t*)is->contents)+pos);} } /* Return the value at pos, using the configured encoding. */ //按照intset的encoding取出指定位置pos的值 //不對pos進行越界判斷,可能會導(dǎo)致undefined behavior static int64_t _intsetGet(intset *is, int pos) {return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding)); } /* Return the value at pos, given an encoding. */ //以enc為編碼取出整數(shù)集合is在pos索引上的值 //不對pos進行越界判斷,可能會導(dǎo)致undefined behavior static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {int64_t v64;int32_t v32;int16_t v16;if (enc == INTSET_ENC_INT64) {//將contents在pos位置的值賦給v64//不能直接寫contents[pos]的原因是contents時int8_t類型的,contents[pos]表示是以sizeof(int8_t)為單位移動的指針,而實際的編碼是INTSET_ENC_INT64,先將contents指針的類型變?yōu)閕nt64_t*memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));//大端機器在取出contents時將原本按照小端序存儲的數(shù)據(jù)按字節(jié)翻轉(zhuǎn),讀出正確的值memrev64ifbe(&v64);return v64;} else if (enc == INTSET_ENC_INT32) {memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));memrev32ifbe(&v32);return v32;} else {memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));memrev16ifbe(&v16);return v16;} }創(chuàng)建一個空intset
空intset的默認(rèn)encoding是INTSET_ENC_INT16,contents每個成員的邏輯類型是int16_t(雖然還沒有成員)
/* Create an empty intset. */ intset *intsetNew(void) {intset *is = zmalloc(sizeof(intset));is->encoding = intrev32ifbe(INTSET_ENC_INT16);is->length = 0;return is; }查詢一個成員
前面說了intset是將元素按大小順序存儲在contents數(shù)組里,所以在插入新元素之前,必須通過二分法找到合理的插入位置,這由intsetSearch(intset?is, int64_t value, uint32_t?pos)函數(shù)實現(xiàn)。
它的作用是在整數(shù)集合里用二分法找到value的位置,并把位置寫給pos參數(shù),函數(shù)返回1;若沒找到,則寫給pos的是能被插入的value的位置(intset按順序存儲),函數(shù)返回0。
使用二分法的查找方法還是比較快速的找到對應(yīng)的值的,上面寫的方式在數(shù)據(jù)量比較大時,可能會存在越界的可能,可以改為下面的方式:
while (max >= min) {mid = min + (max - min)/2;........ }原因是:max + min可能就越界了。
插入一個成員
插入一個值為value的成員時,會做以下判斷邏輯:
- 計算value的encoding
- 若value的encoding大于要插入的intset的encoding,則調(diào)用intsetUpgradeAndAdd直接升級intset的encoding并插入到首部或者尾部。
- 若value的encoding小于要插入的intset的encoding,則不需要升級intset的encoding,調(diào)用intsetSearch找到合適的插入位置,再將該位置到contents尾部的數(shù)據(jù)全部右移一格,最后將value插入到pos。
移除一個成員
不同于插入一個成員,移除一個成員時不會改變intset的encoding,盡管移除這個成員之后所有成員的encoding都小于所在intset的encoding。
/* Delete integer from intset */ intset *intsetRemove(intset *is, int64_t value, int *success) {uint8_t valenc = _intsetValueEncoding(value);uint32_t pos;if (success) *success = 0;//valenc不可能大于當(dāng)前編碼,否則value一定不在該intset中if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {uint32_t len = intrev32ifbe(is->length);/* We know we can delete */if (success) *success = 1;/* Overwrite value with tail and update length */if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);is = intsetResize(is,len-1);//減小內(nèi)存分配is->length = intrev32ifbe(len-1);//size-1}return is; }總結(jié)
通過intset底層實現(xiàn)我們可以發(fā)現(xiàn):基于順序存儲的整數(shù)集合 執(zhí)行一些需要用到查詢的命令時 其時間復(fù)雜度不會是文檔里注明O(1),例如:SADD、SREM 操作一個成員時,時間復(fù)雜度會是O(logn)。所以當(dāng)整數(shù)集合數(shù)據(jù)量變大的時候,redis會用dict作為集合的底層實現(xiàn),將SADD、SREM、SISMEMBER這些命令的時間復(fù)雜度降至O(1),當(dāng)然,這會比intset消耗更多內(nèi)存。
總結(jié)
以上是生活随笔為你收集整理的Redis之整数集合intset的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 人人开源中invalid Code
- 下一篇: socket api中send()和re