开发者学堂课程【第八届大学生创新创业大赛阿里命题数据库命题解析：内存数据库容量极致优化赛题解析】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1045/detail/15281
内存数据库容量极致优化赛题解析
内容介绍：
一、云原生内存数据库 Tair 介绍
二、命题解析和常见优化方式介绍
三、Redis 开发简介
由云原生内存数据库 Tair 带来的问题，提升内存数据引擎资源使用率。后续内容将分为以下三个部分，首先我会介绍云原生内存数据库 Tair，之后将解析命题并介绍常见的内存数据库能量优化方式，为了降低大家参与问题的难度，最后会对 redis 代码进行简要介绍。
一、云原生内存数据库 Tair 介绍
云原生内存数据库Tair是阿里云推出的支持高并发的云原生内存数据库，完全兼容right数据结构和api，支持主从与集群架构，采用多种存储器直应对不同数据温度场景，并提供全球多活、数据闪回和丰富的数字模型等特性，致力于帮助用户构建在线实时场景，可以有效支持游戏，电商、政务的多种多样的应用场景，同时还通过DTS等服务提供了与多种数据库和计算系统进行数据互通的能力。
Tair团队在内存数据库里面有多年的探索和积累，最早可追溯到2009年4月。Tair1.0诞生，并被应用于淘宝核心系统，在同年的11月正式开始支撑双11的超大流量场景。其后的几年里Tair不断扩充能力，推出了面向不同场景的LDB、RDB等引擎，Fastdump系统，2014年5月Tair推出云上缓存产品OCS，成为阿里云初始的基础产品之一，服务云上Memcache用户，2015年3月跳推出阿里云KVStore即云数据库Redis版，Tair由此开始进入云时代。2019年4月KVStore团队在Redis开源社区贡献排名前三，并在Redis Conf 2019上发表了公开演讲。2019年11月发布Tair3.0即云数据库Redis企业版，包括性能增强型，2020年2月在存储顶会FAST20上发表了内存引擎论文《HotRing:A Hotspot-Aware In-Memory Key-Value Store》。2020年9月数据持久化不依赖传统磁盘，保证每个操作持久化的同时提供近乎Redis社区版的吞吐和延时，极大提升业务数据可靠性。·持久内存型:基于Intel傲腾傲腾持久内存，为您提供大容量、兼容Redis的内存数据库产品。单实例成本对比Redis社区版最高可降低30%，且容量存储型:基于云盘ESSD研发，兼容Redis核心数据结构与接口，可提供大容量、低成本、强持久化的数据库服务。2022年5月论文《Tair-PMem:AFully Durable Non-Volatile Memory Database》被数据库顶会VLDB收录。
二、命题解析和常见优化方式介绍
本命题的命题背景内内存数据库是以内存为主要介质的数据库管理系统，其特点是吞吐高、延迟低。同时由于内存介质本身容量小和价格高的限制，相对来说存放的数据量比较小，以上限制导致大部分用户只能在内存数据库中存放热点和高频数据，而无法满足新型场景下，对于容量吞吐延迟延迟的高需求。新型场景主要是指将服务所需的数据全部放置在内存数据库中，提供稳定的高吞吐数据服务，满足用户的实时查询和数据分析需求，同时通过持久内存等新硬件以较低的技能开销保证用户数据的可靠性，使得用户可以将内存数据库作为主数据库，而不再需要为了数据可靠性引入其他系统，这将大幅简化用户系统架构，降低开发和运维成本。为了更好的满足以上需求，阿里云原生内存数据库Tair完全兼容Redis的基础上，一方面通过引入持久内存、超高数云盘等进一步提供更大容量的服务，同时自研引擎上从数据结构，运行时数据，备份开销，内存碎片等角度进一步优化MemoryFootprint以提高资源利用率。本命题的内题内容为以开源Redis为原型一同探索在性能稳定的同时如何进一步提升内存数据库的内存利用率，鼓励从各种维度探索和创新。
下面将介绍一些常见的内存容量优化方式，有以下三个方面，第一个方面是结构优化，通过对内存数据库中各类数据结构进行调用，节约内存数据库容量，其中主要分为两个部分，存储结构和索引结构。存储结构主要指存储数据的各类结构，对这类结构可以通过更加紧凑的数据排出方式来降低容量开销，但紧缩的排布往往也会同时增加查询和更新的性能开销，如ziplist在查询时需要扫描多条数据，修改时需要移动控制其他不相关的数据，如何在节约空间的同时控制紧凑排布对数据的影响？是一个可以探索的方向，索引结构主要指内存数据库中的各类索引，主要优化方式有减少不必要的指针等。
第二个方面是数据压缩，其中主要手段有压缩用户数据和数据去重。由于用户存储在内存数据库的数据往往是具有可压缩性的，所以压缩用户数据可以节约内存数据库的容量，这里需要考虑压缩算法、粒度以及参数的选择，更进一步，由于用户的数据特征是多种多样的，用户数据特征甚至是多变的，需要内存数据库能够自动识别特征，并对压缩算法和参数进行动态的调整。压缩词典的构建也是一个需要解决的问题，OLTP内存数据库的数据往往不以页面为单位进行组织，数据相对分散，这给构造词典带来额外的难度，另外，词典的构造频率和时机也需要精确的控制，以平衡词典构建的性能消耗和实时性。对于部分数据重复较多的场景，数据去重也是一个有效的优化方式，比如Redis中的常见字符串使用，如何高效的查找重复的数据是制定方案的难点。
第三个方面是减少额外开销，一是减少运行时开销，主要是各类数据和buffer，二是减少备份时快照的开销，比如Redis在fork后cow的开销，三是减少数据结构的额外开销，比如Redis在主索引在rehash时会同时存在两个hashtable，增加了索引的开销，四是减少内存碎片，在这个方向上，jemalloc等分配器已经做了一些工作，结合内存数据库的分配特征，可以对内存值概率进行进一步的优化，还有一些在OLTP内存数据库中运用较少的优化方式没有详细介绍，比如列式存储。以上只是主要的内存数据库容量优化方式，也期待大家能够找到更多更有效的优化方式。
三、Redis 开发简介
首先会对Redis执行流程进行简单介绍，Redis在Linux上默认基于epoll实现事件循环，请求处理辑作为回调注册进循环中。回调函数为readQueryFromClient，大部分情况为逐层调
用:readQueryFromClient:从网络读取数据到对应client的buffer中 processInputBuffer:对请求进行解析，构造出命令参数等对象。 processCommandAndResetClient:封装请求调用和后续流程 processCommand:该函数较为复杂，有鉴权、查找命令处理函数等，逻辑较为繁杂 call:调用命令处理函数和生成同步日志。
后来将对 Redis 数据结构进行简单介绍，这张 PPT 上的图是Redis各个结构的关联关系，从左至右是从 RedisDB 到最后的 key 和 value，可以参考这张图来理解Redis主要的索引数据结构。此处以String对象为例，Redis支持多DB所以会有多个redisDB结构，每个DB中有两个主要的索引，分布负责Key到Value和Key到过期信息的映射索引通过Hash表实现，通过链表法解决冲突。每个Hash桶含有一个指针指向冲突链，冲突链中每一个entry有三个指针(分别指向Key，Value 和下一个entry) Value 均为 robj 结构，用于支持多种类型的数据结构。到 robj 为止是通用的结构，之后的结构各个类型会有所不同。
下面将对比两个Redis中的经典数据结构，Redis使用Hashtable作为其主要的索引结构，对应结构体类型dict，dict中主要有以下变量:，dictType类似虚表，用于支持KV释放等行为的自定义，dictht是hash表的抽象，其中包含指向hashtable的指针，hashtable大小， hashtable中的key数量等统计信息，为了支持rehash，所以有两个dictht。在正常运行时只有一个dictht中包含 hashtable当通过rehash进行hashtable的扩缩容时，会在另外一个dictht中创建出新的hashtable，并将数据从原有hashtable移动到新的hashtable中(所以在rehash时会产生额外的空间消耗)，hashtable就是由dictEntry指针构成的数组，每个指针代表一个hash桶，指向相应的冲突链。冲突链由dictEntry构成，其中存储指向key，value和下一个entry的指针，Dict结构在Redis中使用频率很高，主索引和Hash类型等均使用了Dict结构。
Dict结构：
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx=-1*/unsigned long iterators; /* number of iterators currently running * dict;/* This is our hash table structure. Every dictionary has two of this as we* implement incremental rehashing, for the old to the new table.*/
itypedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;}
dictht;
typedef struct dictentry {
void *key;
union {
void *val;
vint64_t u64;
int64_t s64;
double d;
} v;
struct dictentry *next;
dictentry；
Ziplist 是 Redis 中典型的紧凑数据结构，通过连续排布 KV 减少指针等带来的空间开销，还通过数值类型的变长编码来进一步压缩空间。查询时需要扫描多个KV以定位到所需数据。结构头部会存储ziplist的字节长度(zlbytes)，尾部元素相对起始地址的偏移量(zltail)，元素个数(zllen)。之后是存储的各个元素(entry)。最后在整个ziplist 末尾会有一个终止元素(zlend)。
ziplist中的entry实际包含三部分:前一个entry的长度(prevlen)，编码(encoding)，实际内容(data)。其中前一个entry的长度是为了加速反向遍历。Dict结构不论是hashtable和冲突链中都需通过指针来关联各个对象。而ziplist由于是连续排布数据并不需要额外的指针，这节约了内存空间。但ziplist的连续排布也导致对entry的更新操作往往需要移动其他entry。比如删除某个处于ziplist中间的entry时，需要将之后的entry都往前移动，而移动后又有可能导致占用空间变小，需要进行空间的重新分配。插入操作也存在类似情况。这也导致ziplist结构的插入删除性能往往低于Dict结构。Redis中采用类似优化方式的还有intset。通过上述两个结构的介绍，可以看出在性能和内存容量上是有一定的取舍空间的，主要难度在于如何在保证性能紧密的情况下尽可能的节约内存空间。
最后介绍一下对Redis代码进行修改编译和测试的方法。首先是代码结构的介绍，主要代码均在主要代码均在src下，其中几个主要文件为:server.h:Redis的主头文件，大部分函数和结构的声明，server.c:Redis进程的初始化逻辑和命令表redisCommandTable等，network.c:网络IO相关函数，db.c:通用命令处理逻辑和相关函数，t*.c:各数据类型命令处理逻辑。编译和测试均使用make即可，更多信息可参考
https://github.com/redis/redis/blob/unstable/README.md，
为了方便大家对内存消耗进行分析，这里也介绍一下内存容量监控和限制:MemoryCgroup是Linux上常用的内存用量统计和限制方式，其中的memoryusage_in_bytes提供了进程使用内存总量的统计。利用其中的memorylimit_in_bytes可以限制进程使用的内存总量，具体使用方式可参考
https://www.kenel.org/doc/html/latest/admin guide/cgroup-v1/memory.html
这里也还有一些额外的文档和学习资料，供大家查阅，主要包括
1.Tair帮助文档:https://help.aliyun.com/document detail/145957.html
2.Tair产品入口:https://www.aliyun.com/database/redistair
3.Tair性能白皮书:https://help.aliyun.com/document detail/188009.html
