要设计一个内存型数据库需要考虑哪些?
0)终端连接
1)存储的数据结构(需要支持多样的数据类型、数据结构)
哈希表
Hash冲突:Key的Hash值冲突,导致一个桶挂了多个元素,Hash表退化成了链表,查找耗时。
rehash:为了解决Hash冲突的问题,需要rehash操作,增加现有的Hash桶数量。
渐进式Rehash:每操作一次迁移一个Entry,避免rehash造成的阻塞。
双向链表
整数数组
压缩队列
类似于一个数组,数组中的每一个元素都对应保存一个数据。
压缩列表表头有三个字段zlbytes 列表长度, zltail 列表尾部偏移量, zllen 列表中entry的个数, 压缩列表再表尾还有一个zlend,表示列表结束。
跳表
加速队列和数组的访问。
简单动态字符串
byte 1字节
boolean 1字节
char 2字节,只要是字符无论是英文还是汉字,都占2个字节。
short 2字节
int 4字节
long 8字节
float 4字节
double 8字节
整数数组和压缩列表再查找时间复杂度方面并没有很大的优势,为什么Redis还会把他们作为底层数据结构?
1)内存利用率方面:数组和压缩列表都是非常紧凑的数据结构,它比链表占用的内存更少。
Redis是内存数据库,大量数据存储到内存中,此时需要做尽可能的优化,提高内存的利用率。
2)数组对CPU高速缓存支持更友好,所以Redis再设计师,集合数据元素较少情况下,默认采用内存紧凑排列的方式存储,同时利用CPU高速缓存不会降低访问速度。
当数据元素超过设定阈值后看,避免时间复杂度太高,转为Hash和跳表数据结构存储,保证查询效率。
数组对CPU缓存友好的原因是,CPU预读取一个CacheLine大小的数据,数组数据排列紧凑,相同大小空间保存的元素更多,访问下一个元素时、恰好已经在CPU缓存中了,如果是随机访问,就不能充分利用CPU缓存。
2)对数据的加工和操作
单个元素的查找、修改、删除对于Redis来讲会非常快(在没有Hash冲突的情况下)
LLEN、SCARD等操作时间复杂度为O(1), 集合类型采用压缩列表,双向链表,整数数组等数据结构时,这些结构中专门记录了元素的个数统计,因此可以高效的完成相关操作。
HGETALL、SMEMBERS、LRANGE、ZRANGE等复杂度为O(N)的操作要避免,使用HSCAN、SSCAN、ZSCAN来替代,SCAN操作实现了渐进式便利,每次只返回优先数量的数据。
3)数据的安全性:
1)数据的备份:
实时备份:
对数据进行操作后记录操作日志
定时备份
2)数据的恢复
4)服务的高可用
主从模式
5)服务的监控、故障恢复以及通知
哨兵模式
哨兵集群
6)数据分片
纵向扩展:扩大服务器的内存,但是当存储数据内容较多,需要RDS备份时,会影响到Redis的使用性能。
横向扩展
数据结构
高性能IO模型
多路复用
命令解析
命令处理
数据安全
AOF AppendOnlyFile
记录每一条日志
日志压缩