摘要.
一. 问题出发点
需要储存 15 亿级 dives_id+500 位标签数据 的标签系统数据，并实现 200 毫秒内的高并发查询 200 毫秒不是还需要给其他处理留出时间，所以需要将查询时间压缩到 30 毫秒甚至更少，并且要承受住高并发处理。
二. 数据库选择
已 redis 为基础进行优化分析
redis 基础，redis 属于内存储存，所以使用成本很大，但是查询效率十分高，单机就可以支持 10 万 qps 的并发量处理，当然需要增加 redis service 节点
所以大数据 redis 可以支持特定场景下的高并发大数据处理查询 达到高速查询的效果
那么就要想办法优化 redis 存储结构，从以下几个点出发
1. 从 key 的存储格式入手
2. 从 redis 的 key value 储存结构入手
3. 从统一格式减少数据碎片入手
4. 从减少查询次数入手
三. 优化
基础优化 key 储存结构
疑问：redis 是怎么快速从大数据量中查询到 key 的
原文资料：https://blog.csdn.net/agangdi/article/details/21567199
key 的储存结构
1、redis 中的每一个数据库，都由一个 redisDb 的结构存储。其中，redisDb.id 存储着 redis 数据库以整数表示的号码。redisDb.dict 存储着该库所有的键值对数据。redisDb.expires 保存着每一个键的过期时间。
2、当 redis 服务器初始化时，会预先分配 16 个数据库（该数量可以通过配置文件配置），所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中。当我们选择数据库 select number 时，程序直接通过 redisServer.db[number] 来切换数据库。有时候当程序需要知道自己是在哪个数据库时，直接读取 redisDb.id 即可。
3、既然我们知道一个数据库的所有键值都存储在 redisDb.dict 中，那么我们要知道如果找到 key 的位置，就有必要了解一下 dict 的结构了：
typedef struct dict {// 特定于类型的处理函数 dictType *type;
// 类型处理函数的私有数据 void *privdata;
// 哈希表（2 个）dictht ht[2];
// 记录 rehash 进度的标志，值为 - 1 表示 rehash 未进行 int rehashidx;
// 当前正在运作的安全迭代器数量 int iterators;
} dict;
由上述的结构可以看出，redis 的字典使用哈希表作为其底层实现。dict 类型使用的两个指向哈希表的指针，其中 0 号哈希表（ht[0]）主要用于存储数据库的所有键值，而 1 号哈希表主要用于程序对 0 号哈希表进行 rehash 时使用，rehash 一般是在添加新值时会触发，这里不做过多的赘述。所以 redis 中查找一个 key，其实就是对进行该 dict 结构中的 ht[0] 进行查找操作。
4、既然是哈希，那么我们知道就会有哈希碰撞，那么当多个键哈希之后为同一个值怎么办呢？redis 采取链表的方式来存储多个哈希碰撞的键。也就是说，当根据 key 的哈希值找到该列表后，如果列表的长度大于 1，那么我们需要遍历该链表来找到我们所查找的 key。当然，一般情况下链表长度都为是 1，所以时间复杂度可看作 o(1)。
当 redis 拿到一个 key 时，如果找到该 key 的位置。
了解了上述知识之后，我们就可以来分析 redis 如果在内存找到一个 key 了。
1、当拿到一个 key 后， redis 先判断当前库的 0 号哈希表是否为空，即：if (dict->ht[0].size == 0)。如果为 true 直接返回 NULL。
2、判断该 0 号哈希表是否需要 rehash，因为如果在进行 rehash，那么两个表中者有可能存储该 key。如果正在进行 rehash，将调用一次_dictRehashStep 方法，_dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash，这里不作赘述。
3、计算哈希表，根据当前字典与 key 进行哈希值的计算。
4、根据哈希值与当前字典计算哈希表的索引值。
5、根据索引值在哈希表中取出链表，遍历该链表找到 key 的位置。一般情况，该链表长度为 1。
6、当 ht[0] 查找完了之后，再进行了次 rehash 判断，如果未在 rehashing，则直接结束，否则对 ht[1]重复 345 步骤。
我们的重点是了解到了 redis key 的储存形式，那么根据上述所说，以此来推论
1. 当 redis 每保存一个 key 那么会储存一个完整的 dict，当 key 值越多的时候，hash 表也会膨胀，储存空间也会增大，
2. 如果当 key 值过大会造成 hash 碰撞链表增长，那么需要去遍历链表增加时间复杂度变为 o(n) < 当然也不是完全的 o(n) 但是会有复杂度膨胀 > 所以当 key 值数量十分多的时候越多查询效率会相对降低虽然降低的不大
综上所述我们要想办法优化 key 值的数量
但是因为标签系统 key 值是 32 位 MD5 的设备号，所以都是一一对应的，单纯的 key 数量是无法减少的, 如果减少会造成投放不准确。所以我们只能通过储存格式入手
redis 储存格式 key 值没有变化，那么我们想办法从 value 值入手想办法减少 key 值
redis value 值储存格式 String、Hash 、List 、 Set 、 Ordered Set
redis 基础数据结构
hash 结构的 k-k-v 格式有可能能符合减少 k 值的需求，那么来看一下 hash 结构得储存结构
资料连接:https://www.cnblogs.com/weknow619/p/10464139.html
typedef struct dict { // 类型特定函数 dictType *type;
// 私有数据 void *privdata;
// 哈希表 dictht ht[2];
// rehash 索引 // 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量 int iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
// 哈希表数组 dictEntry **table;
// 哈希表大小 unsigned long size;
// 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量 unsigned long used;
} dictht;
typedef struct dictEntry {
void *key;
union {void *val;uint64_t u64;int64_t s64;} v;
// 指向下个哈希表节点，形成链表 struct dictEntry *next;
} dictEntry;
typedef struct dictType {
// 计算哈希值的函数 unsigned int (*hashFunction)(const void *key);
// 复制键的函数 void *(*keyDup)(void *privdata, const void *key);
// 复制值的函数 void *(*valDup)(void *privdata, const void *obj);
// 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 销毁键的函数 void (*keyDestructor)(void *privdata, void *key);
// 销毁值的函数 void (*valDestructor)(void *privdata, void *obj);
} dictType;
上面源码可以简化成如下结构：
虽然看到 hash 结构里面的底层代码的 dict 和 key 值里面的 dict 结构是一样的，但其实 redis 底层会将 hashtable（哈希表）压缩为 ziplist（压缩列表）的结构，可以大大节省存储空间，经过实验，ziplist 储存和 hash 表储存储存效率超过 7 倍 当储存数量越多储存节省空间也会相应增加
简单理解下 ziplist:
资料链接：https://blog.csdn.net/yellowriver007/article/details/79021049
Hash 对象只有同时满足下面两个条件时，才会使用 ziplist（压缩列表）：
1. 哈希中元素数量小于 512 个；
2. 哈希中所有键值对的键和值字符串长度都小于 64 字节。
所以我们要在之后的处理注意 Hash 值的要求否则所有的工作就都打水漂了
当然我们可以修改 list-max-ziplist-value 与 hash-max-ziplist-entries 来使用不同的阈值。
具体源码：https://blog.csdn.net/m0_37343985/article/details/83715138
再加上 hash 结构的 value 值可以实现 o(1) 的复杂度
至此大概确定了优化思路, 以 key-hashmap 结构保存数据，降低 key 值储存空间，空值 value 值长度，控制 key 下 hashmap 数量
那么第一个问题，怎么减少 key 值数量
最直接的办法是切割，但是安卓和 ios 的设备 id 分别是 idfa，imei 长度不一致所以，切割后第一 切割长度不好统一，第二长度不一会更容易造成 redis 产生内存碎片（内存碎片会单独写）
所以需要通过 MD5 哈希化设备号为 32 位
然后讲前 22 位切割作为 key-map 的 key 值，后 10 位作为 field
当我们的数据量十分庞大的时候前 22 位数据会出现重复项，这个时候 map 值会增加，由于切割的长度做了控制，当前 20 亿数据的量级不用担心元素数量大于 512 位，经过实验其实平均保存数量只有 20 到 30 之间，最大数量也只有 80 多一点所以其实还可以继续降低 key 值长度以此来达到优化存储空间的问题
当然根据上文所述查询效率其实并没有降低，由于实验区别十分小在这也就不对比了
至此 key 值优化搞定，下面优化 value 值
value 值优化：
优化存储空间，第一反应是字节储存，并且因为 map 中 value 默认值位 64 位所以最好在这个区间内
那么将 500 个标签压缩在 64 个字节中并且因为 500 个标签属于离散数据，那么第一反应是 one-host 编码，但是 one-host 编码会导致数据长短不一 500 个标签全部都需要控制在 64 位中不太好实现
所以选择 bitmap 数据格式，将每一个标签标记为是否属实，属实为 1，不属实为 0
简单计算下 1 个字节可以存储 8 位 64 位就是 512 个标签 大于 500 个标签也就是意味着用 63 位就可以存储下所有的标签数据
简单描述 bitmap 数据结构
资料：http://www.luyixian.cn/news_show_23323.aspx
32 位计算机下存储一个 int a=1 在内存中占 32bit 位, 但是我们的数据全部都是 0，1 结构这样储存空间会十分浪费，其实开辟一个 byte 空间就可以存储 8bit 的数据，那么将所以的 byte 作为数组储存，比如需要存储 50 个数据那么只需要保存一个 7 个 byte 的数组就可以保存下这些数据总耗费空间位 56bit 这个空间，即使多出来的 6 位置为 0 也可以大大节省存储空间，毕竟两个 int 就已经占了 64bit 位的空间了。
优点： 运算效率高，不需要进行比较和移位； 占用内存少，比如 N=10000000；只需占用内存为 N/8=1250000Byte=1.25M。
而且这种数据在进行单条数据筛选的时候可以根据位置进行位运算处理大大提高查询效率,
当需要判断某一用户是否和某个标签匹配的时候只需要根据设备 id 取出 value 值然后进行指定位的比较就可以在接近 O(1) 的时间复杂度下实现，达到告诉处理反馈
至此全部的优化逻辑
key 的存储格式：key-hashmap 储存
value 的储存格式：bitmap 数据结构
统一数据格式格式：md5 哈希化为 32 位，切割为两半 22 位和 10 位组合作为 key 和 field
降低时间复杂度：O(1) 复杂度，redis 一次操作查询次数只为 1 次 标签对比次数也为 1
平均查询处理时间 30 毫秒左右。
单节点 7200mb 50 个 redis 节点，总内存 175gb 使用内存 130gb
内存碎片
资料：https://www.jianshu.com/p/cf803e9c38e9?from=timeline&isappinstalled=0
redis 的内存状态 info memory
redis 的内存状态
内存碎片计算公式
内存碎片率 1.24 还算比较健康
ratio 指数 > 1 表明有内存碎片，越大表明越多，<1 表明正在使用虚拟内存，虚拟内存其实就是硬盘，性能比内存低得多，这是应该增强机器的内存以提高性能。一般来说，mem_fragmentation_ratio 的数值在 1 ~ 1.5 之间是比较健康的
----------------------------------------------------- 分割线 ---------------------------------------
产生原因
可以这样认为，redis 产生内存碎片有两个原因，A：redis 自身的内存分配器。B：修改 cache 的值，且修改后的 value 与原来 value 的大小差异较大。
进程需要用内存的话，会先通过 OS 向 device 申请，然后才能够使用。一般进程在不需要使用的时候，会释放掉这部分内存并返回给 device。但是 redis 作者可能为了更高的性能，所以在 redis 中实现了自己的内存分配器来管理内存，不会马上返还内存，不用每次都向 OS 申请了，从而实现高性能。
但是，在内存分配器的那张图片我们知道，redis 的每个 k-v 对初始化的内存大小是最适合的，当这个 value 改变的并且原来内存大小不适用的时候，就需要重新分配内存了。（但是 value 存比原来小不知道会不会产生碎片）。重新分配之后，就会有一部分内存 redis 无法正常回收，一直占用着。
1、重启 redis 服务，简单粗暴。2、redis4.0 以上可以使用新增指令来手动回收内存碎片，配置监控使用性能更佳。
资料链接：https://my.oschina.net/watliu/blog/1620666
3. 修改内存分配器。Redis 支持 glibc’s malloc、jemalloc11、tcmalloc 几种不同的内存分配器，每个分配器在内存分配和碎片上都有不同的实现。不建议普通管理员修改 Redis 默认内存分配器，因为这需要完全理解这几种内存分配器的差异，也要重新编译 Redis https://www.jianshu.com/p/a7cdbb1d7ae1 https://www.jianshu.com/p/a7cdbb1d7ae1