Redisソース--省メモリ大法--intsetとziplist

7522 ワード

今日はこの2つの商品を一緒に見てみましょう.Redisはデータをメモリに入れているので、メモリの占有量に関連しています.基本的には省則省で、小容量のredisオブジェクトにとって、redisの下層は大容量の構造ではなく圧縮データ構造を選択して保存します.今日書くのはこのようなタイプです.それぞれInsetとziplistです.
まずintsetを見てみましょう.その名の通り、これは少量の整数の集合を実現するための整数集合です.次に、そのタイプ定義を示します.

typedef struct intset {
 
    //     
    uint32_t encoding;

    //          
    uint32_t length;

    //        
    int8_t contents[];

} intset;

intsetは一貫したタイプのデータを持つsetであり、その中のデータはint_であることができる.16 int_32 int_64は、それらを区別するために、contents配列に格納されているデータを記録するためにencodingが必要である.現在のsetのencodingで表される範囲を超えたデータを入れる必要がある場合は、intsetをアップグレードする必要があります.つまりupgradeメソッドです.はい、次のコードにはendianconvで定義された反転バイト関数が表示されます.このように定義されています.intrev 32 ifbeを例に挙げます.

uint32_t intrev32(uint32_t v) {
    memrev32(&v);
    return v;
}

void memrev32(void *p) {
    unsigned char *x = p, t;

    t = x[0];
    x[0] = x[3];
    x[3] = t;
    t = x[1];
    x[1] = x[2];
    x[2] = t;
}

なぜこの関数を使うのかについては、注釈ではこう述べています.Redis tries to encode everything as little endian (but a few things that need

to be backward compatible are still in big endian) because most of the

production environments are little endian, and we have a lot of conversions

in a few places because ziplists, intsets, zipmaps, need to be endian-neutral

even in memory, since they are serialied on RDB files directly with a single

write(2) without other additional steps. 簡単に言えば、redisのRDB持続化方式ではziplists、intsetsなどが直接ファイルに書き込まれるため、メモリにはサイズ端中性(endian-neutral)であることが要求され、大部分の環境は小端法であるため、これらの圧縮されたデータ構造では、redisは常に小端法でバイトを格納し、大端法の機械にとって正しい数を得るには、端変換が必要である.なお、反転はパラメータとしてスタックに入力されたバイトのみであり、構造体自体のバイトについては変化しない.

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    
    //        
    uint8_t curenc = intrev32ifbe(is->encoding);

    //          
    uint8_t newenc = _intsetValueEncoding(value);

    //          
    int length = intrev32ifbe(is->length);

    //    value   ，                     
    //   ，   value                    
    //    value             ，            
    //   ，value                  
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    //          
    is->encoding = intrev32ifbe(newenc);
    //         （     ）      
    // T = O(N)
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    //            ，            
    //                    
    //           ，                         
    //                 ，               
    //     ，      curenc        ，          ：
    // | x | y | z | 
    //              ，       （   ？         ）：
    // | x | y | z | ? |   ?   |   ?   |
    //            ，      ：
    // | x | y | z | ? |   z   |   ?   |
    // | x | y |   y   |   z   |   ?   |
    // |   x   |   y   |   z   |   ?   |
    //   ，              ？        ：
    // |   x   |   y   |   z   |  new  |
    //                       ，    prepend == 0
    //                （prepend == 1），       ：
    // | x | y | z | ? |   ?   |   ?   |
    // | x | y | z | ? |   ?   |   z   |
    // | x | y | z | ? |   y   |   z   |
    // | x | y |   x   |   y   |   z   |
    //       ，    | x | y |          
    // |  new  |   x   |   y   |   z   |
    // T = O(N)
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    //     ，   prepend                  
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);

    //            
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);

    return is;
}

ここでのupgradeAndAddは長いように見えますが、実は値によって最初に置くか最後に置くか(setは秩序化されているため)、プロセス全体がデータを再移動する必要があるため、複雑度はO(N)であるべきで、この複雑度は小さい時にしか受け入れられません.幸いなことに、私たちはもともとメモリの使用をできるだけ減らす必要があります.これはtime space trade offと見なすことができます.残りの方法もあまり悪くないので、その上でsetに対して挿入、検索、削除を行います.次はziplistを見てもいいです.よく似ています.ziplistは圧縮型のリストで、末尾を記録し、末尾からリスト全体を巡回します.

   ziplist    

area        ||||

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL

各ziplistノードの前にヘッダーがあります.このヘッダーには2つの情報が含まれています.

 *
 * 1)       ，            。
 *
 * 2)               。

前置長については,メモリを節約するために2つのコードを用いた.

 *
 * 1)             254   ，        1            。
 *
 * 2)               254   ，        5            ：
 *    a)   1           254 ，         5        。
 *    b)     4                  。

  ，          ，      ：

1)             ，
 *          header    2                   ，
 *                      。
 *
 * |00pppppp| - 1 byte
 *      String value with length less than or equal to 63 bytes (6 bits).
 *                  63   。
 * |01pppppp|qqqqqqqq| - 2 bytes
 *      String value with length less than or equal to 16383 bytes (14 bits).
 *                  16383   。
 * |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
 *      String value with length greater than or equal to 16384 bytes.
 *                  16384   。
 *
 * 2)            ，
 *          header    2         1 ，
 *           2                  。
 *
 * |11000000| - 1 byte
 *      Integer encoded as int16_t (2 bytes).
 *            int16_t      ，    2   。
 * |11010000| - 1 byte
 *      Integer encoded as int32_t (4 bytes).
 *            int32_t      ，    4   。
 * |11100000| - 1 byte
 *      Integer encoded as int64_t (8 bytes).
 *            int64_t      ，    8   。
 * |11110000| - 1 byte
 *      Integer encoded as 24 bit signed (3 bytes).
 *            24  （3   ）    。
 * |11111110| - 1 byte
 *      Integer encoded as 8 bit signed (1 byte).
 *            8  （1   ）    。
 * |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer.
 *      Unsigned integer from 0 to 12. The encoded value is actually from
 *      1 to 13 because 0000 and 1111 can not be used, so 1 should be
 *      subtracted from the encoded 4 bit value to obtain the right value.
 *              0   12         。
 *         0000   1111      ，          1   13 。
 *             4       ，      1 ，         。
 *         ，       0001 = 1 ，           1 - 1 = 0 。
 * |11111111| - End of ziplist.
 *      ziplist

こんなにたくさんのフォーマットを見て、崩壊するのではないでしょうか...実は私の感覚もあまり悪くなくて、メモリを節約するために、これも仕方がないことです.こんなにたくさん言って、前のノードの長さが変わると、もっと卵が痛いことがあります.それは前のノードの長さが私が前に記録した1バイトの許容範囲を超えていることです.そこで私は4バイトになりました.これはそんなに楽ではありません.メモリを再割り当てなければなりません.最悪のことは、1つのノードの更新が蝶の効果のように、その後のノードの長さが1バイトで表す(255バイト)の範囲を超えているため、連鎖更新をしなければなりませんが、確率学的には起こりにくいわけではありません.ここまで書くと、私も卵が痛いと思いますが、メモリの中でメモリを食べているNOSQLとしては仕方がありません.メモリを節約するために、redisも必死です.

asp.Netプロファイルの読み取り方法

Asp.NetエクスポートExcel