今天把这两货放在一起来看看，因为Redis是把数据都放在了内存里，所以涉及到内存的占用，基本就是能省则省，对于一些小容量的redis对象来说，redis底层会选择一些压缩数据结构而不是大容量的结构来存储他们,今天要写的就属于这种类型。分别是Intset和ziplist.
先来看看intset吧，顾名思义，这玩意就是一个整数集合，用来实现少量整数的集合。下面是它的类型定义。
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
intset是一种具有一致类型数据的set，它里面的数据可以是int_16 int_32 int_64 的，为了区分他们，需要一个encoding来记录contents数组里面存放的是何种数据。
当我们需要放入的数据超出了当前set的encoding所能表示的范围，那么我们就需要对intset进行升级，也就是upgrade方法
哦对了，下面的代码里会出现一个定义在endianconv中的反转字节函数。它是这么定义的。以intrev32ifbe为例。
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是一种压缩型的列表，它记录尾部，从尾到头来遍历整个list。
非空 ziplist 示例图
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
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 节点的前面都带有一个 header ，这个 header 包含两部分信息：
*
* 1)前置节点的长度，在程序从后向前遍历时使用。
*
* 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 的结尾标识
看到这么多的格式，是不是要崩溃了。。。其实我的感觉也是差不多的，为了省内存，这也是没有办法的事情。说了这么多，当前面的结点长度改变时，有时还会发生更蛋疼的事情，那就是前面结点的长度超过我之前记录的一个字节所能容纳的范围了，于是我就是变成四个字节了，这可没那么轻松，又得重新分配内存了，最糟糕的事情是一个结点的更新如同蝴蝶效应一般，造成了之后的结点的长度都超出了一个字节所能表示（255字节）的范围，那么我得连锁更新，不过，从概率学的角度来说，那并不是很容易发生。
写到这里，我也觉得很蛋疼，但是没有办法作为一种跑在内存里吃内存的NOSQL，为了省内存，redis也是拼了。
