本文从网络模型,数据结构和内存管理,持久化和多机协作四个角度对复述的设计思路进行分析。
一。网络模型
复述是典型的基于反应堆的事件驱动模型,单进程单线程、高效的框架总是类似的。网络模型与spp的异步模型几乎一致。
复述,流程上整体分为接受请求处理器,响应处理器和应答处理器三个同步模块,每一个请求都是要经历这三个部分。
复述,集成了libevent/epoll/kqueue/选择等多种事件管理机制,可以根据操作系统版本自由选择合适的管理机制,其中libevent是最优选择的机制。
复述的网络模型有着所有事件驱动模型的优点,高效低耗。但是面对耗时较长的操作的时候,同样无法处理请求,只能等到事件处理完毕才能响应。所以了解清楚网络模型有助于在业务中扬长避短,减少长耗时的请求,尽可能多一些简单的短耗时请求发挥异步模型的最大的威力。
二。数据结构和内存管理
1。字符串
1.1内存管理方式
动态内存管理方式,动态方式最大的好处就是能够较为充分的利用内存空间,减少内存碎片化,与此同时带来的劣势就是容易引起频繁的内存抖动,通常采用“空间预分配”和“惰性空间释放”两种优化策略来减少内存抖动,复述,也不例外。
每次修改字符串内容时,首先检查内存空间是否符合要求,否则就扩大2倍或者按M增长,减少字符串内容时,内存并不会立刻回收,而是按需回收。
关于内存管理的优化,最基本的出发点就是浪费一点空间还是牺牲一些时间的权衡,像STL, tcmalloc, protobuf3竞技场的机制等采用的核心思路都是“预分配迟回收”,复述,也是一样的。
1.2二进制安全
判断字符串结束与否的标识是兰字段,而不是C语言的' \ 0 ',因此是二进制安全的。
放心的将pb序列化后的二进制字符串存入复述。
简而言之,通过复述的简单封装,复述的字符串的操作更加方便,性能更友好,并且屏蔽了C语言字符串的一些需要用户关心的问题。
2。字典(哈希)
字典的底层一定是散列,涉及到散列一定会涉及到哈希算法,冲突的解决方法和哈希表扩容和缩容。
2.1哈希算法
复述,使用的就是常用的Murmurhash3, Murmurhash算法能够给出在任意输入序列下的散列分布性,并且计算速度很快。之前做共享内存的本地缓存的需求时也正是利用了Murmurhash的优势,解决了原有结构的哈希函数散列分布性差的问题。
2.2哈希冲突解决方法
链地址法解决哈希冲突,通用解决方案没什么特殊的。多说一句,如果选用链地址解决冲突,那么势必要有一个散列性非常好的哈希函数,否则散列的性能将会大大折扣.Redis选用了Murmurhash,所以可以放心大胆的采用链地址方案。
3。整数集合
变长整数存储,整数分为16/32/64三个变长尺度,根据存入的数据所属的类型,进行规划。
每次插入新元素都有可能导致尺度升级(例如由16位涨到32位),因此插入整数的时间复杂度为O (n)。这里也是一个权衡,内存空间和时间的一个折中,尽可能节省内存。
4。跳跃表
复述的skilplist和普通的skiplist没什么不同,都是冗余数据实现的从粗到细的多层次链表,复述中应用跳表的地方不多,常见的就是有序集合。
5 .链表
复述的链表是双向非循环链表,拥有表头和表尾指针,对于首尾的操作时间复杂度是O(1),查找时间复杂度O (n),插入时间复杂度O (1)。
三.AOF和RDB持久化
AOF持久化日志,RDB持久化实体数据,AOF优先级大于RDB。
1. aof持久化
机制:通过定时事件将aof缓冲区内的数据定时写到磁盘上。
2. aof重写
为了减少AOF大小,复述,提供了AOF重写功能,这个重写功能做的工作就是创建一个新AOF文件代替老的AOF,并且这个新的AOF文件没有一条冗余指令。(例如对列表先插入A/B/C,后删除B/C,再插入D共6条指令,最终状态为A/D,只需1条指令就可以)
实现原理就是读现有数据库的状态,根据状态反推指令,跟之前的AOF无关。同样,为了避免长时间耗时,重写工作放在子进程进行。
3. rdb持久化
保存和BGSAVE两个命令都是用于生成RDB文件,区别在于BGSAVE会叉出一个子进程单独进行,不影响复述,处理正常请求。定时和定次数后进行持久化操作。
