做门户网站要多少钱,建设银行官网电话,网络开发部是做什么的,滁州市南谯区建设局网站后端需要知道的关于redis的事#xff0c;基本都在这里了。
此文后续会改为粉丝可见#xff0c;所以喜欢的请提前关注。
你的点赞和评论是我创作的最大动力#xff0c;谢谢。
1、入门
Redis是一款基于键值对的NoSQL数据库#xff0c;它的值支持多种数据结构#xff1a;…后端需要知道的关于redis的事基本都在这里了。
此文后续会改为粉丝可见所以喜欢的请提前关注。
你的点赞和评论是我创作的最大动力谢谢。
1、入门
Redis是一款基于键值对的NoSQL数据库它的值支持多种数据结构 字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。 • Redis将所有的数据都存放在内存中所以它的读写性能十分惊人用作数据库缓存和消息代理。
Redis具有内置的复制Lua脚本LRU逐出事务和不同级别的磁盘持久性并通过Redis Sentinel和Redis Cluster自动分区提供了高可用性。 • Redis典型的应用场景包括缓存、排行榜、计数器、社交网络、消息队列等
1.1NoSql入门概述
1单机Mysql的美好时代
瓶颈 数据库总大小一台机器硬盘内存放不下数据的索引B tree一个机器的运行内存放不下访问量读写混合一个实例不能承受2Memcached缓存 MySql 垂直拆分
通过缓存来缓解数据库的压力优化数据库的结构和索引
垂直拆分指的是分成多个数据库存储数据如卖家库与买家库 3MySql主从复制读写分离
主从复制主库来一条数据从库立刻插入一条。读写分离读取从库Master写主库Slave4分表分库水平拆分MySql集群
主库的写压力出现瓶颈行锁InnoDB取代表锁MyISAM分库根据业务相关紧耦合在同一个库对不同的数据读写进行分库如注册信息等不常改动的冷库与购物信息等热门库分开分表切割表数据例如90W条数据id 1-30W的放在A库30W-60W的放在B库60W-90W的放在C库MySql扩展的瓶颈
大数据下IO压力大表结构更改困难
常用的Nosql
Redis memcache Mongdb 以上几种Nosql 请到各自的官网上下载并参考使用
Nosql 的核心功能点
KV(存储) Cache(缓存) Persistence(持久化) ……
1.2redis的介绍和特点: 问题 传统数据库持久化存储数据。 solr索引库:大量的数据的检索。 在实际开发中高并发环境下不同的用户会需要相同的数据。因为每次请求 在后台我们都会创建一个线程来处理这样造成同样的数据从数据库中查询了N次。 而数据库的查询本身是操作效率低频率高也不好。 总而言之一个网站总归是有大量的数据是用户共享的但是如果每个用户都去数据库查询 效率就太低了。 解决 将用户共享数据缓存到服务器的内存中。 特点 1、基于键值对 2、非关系型(redis) 关系型数据库:存储了数据以及数据之间的关系,oracle,mysql 非关系型数据库:存储了数据,redis,mdb. 3、数据存储在内存中服务器关闭后持久化到硬盘中 4、支持主从同步 实现了缓存数据和项目的解耦。 redis存储的数据特点 大量数据 用户共享数据 数据不经常修改。 查询数据 redis的应用场景 网站高并发的主页数据 网站数据的排名 消息订阅 1.3redis——数据结构和对象的使用介绍
redis官网
微软写的windows下的redis 我们下载第一个
额案后基本一路默认就行了
安装后服务自动启动以后也不用自动启动。 出现这个表示我们连接上了。 redis命令参考链接
1.3.1String
数据结构
struct sdshdr{//记录buf数组中已使用字节的数量int len;//记录buf数组中未使用的数量int free;//字节数组用于保存字符串char buf[];
}
常见操作
127.0.0.1:6379 set hello world
OK
127.0.0.1:6379 get hello
world
127.0.0.1:6379 del hello
(integer) 1
127.0.0.1:6379 get hello
(nil)
127.0.0.1:6379
应用场景
String是最常用的一种数据类型普通的key/value存储都可以归为此类value其实不仅是String也可以是数字比如想知道什么时候封锁一个IP地址访问超过几次。INCRBY命令让这些变得很容易通过原子递增保持计数。
1.3.2LIST
数据结构
typedef struct listNode{//前置节点struct listNode *prev;//后置节点struct listNode *next;//节点的值struct value;
}
常见操作 lpush list-key item
(integer) 1lpush list-key item2
(integer) 2rpush list-key item3
(integer) 3rpush list-key item
(integer) 4lrange list-key 0 -1
1) item2
2) item
3) item3
4) itemlindex list-key 2
item3lpop list-key
item2lrange list-key 0 -1
1) item
2) item3
3) item
应用场景
Redis list的应用场景非常多也是Redis最重要的数据结构之一。 我们可以轻松地实现最新消息排行等功能。 Lists的另一个应用就是消息队列可以利用Lists的PUSH操作将任务存在Lists中然后工作线程再用POP操作将任务取出进行执行。
1.3.3HASH
数据结构
dictht是一个散列表结构使用拉链法保存哈希冲突的dictEntry。
typedef struct dictht{//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码用于计算索引值unsigned long sizemask;//该哈希表已有节点的数量unsigned long used;
}typedef struct dictEntry{//键void *key;//值union{void *val;uint64_tu64;int64_ts64;}struct dictEntry *next;
}
Redis的字典dict中包含两个哈希表dictht这是为了方便进行rehash操作。在扩容时将其中一个dictht上的键值对rehash到另一个dictht上面完成之后释放空间并交换两个dictht的角色。
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;
rehash操作并不是一次性完成、而是采用渐进式方式目的是为了避免一次性执行过多的rehash操作给服务器带来负担。
渐进式rehash通过记录dict的rehashidx完成它从0开始然后没执行一次rehash例如在一次 rehash 中要把 dict[0] rehash 到 dict[1]这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上dict[0] 的 table[rehashidx] 指向 null并令 rehashidx。
在 rehash 期间每次对字典执行添加、删除、查找或者更新操作时都会执行一次渐进式 rehash。
采用渐进式rehash会导致字典中的数据分散在两个dictht中因此对字典的操作也会在两个哈希表上进行。 例如查找时先从ht[0]查找没有再查找ht[1]添加时直接添加到ht[1]中。
常见操作 hset hash-key sub-key1 value1
(integer) 1hset hash-key sub-key2 value2
(integer) 1hset hash-key sub-key1 value1
(integer) 0hgetall hash-key
1) sub-key1
2) value1
3) sub-key2
4) value2hdel hash-key sub-key2
(integer) 1hdel hash-key sub-key2
(integer) 0hget hash-key sub-key1
value1hgetall hash-key
1) sub-key1
2) value1
1.3.4SET
常见操作 sadd set-key item
(integer) 1sadd set-key item2
(integer) 1sadd set-key item3
(integer) 1sadd set-key item
(integer) 0smembers set-key
1) item2
2) item
3) item3sismember set-key item4
(integer) 0sismember set-key item
(integer) 1srem set-key item
(integer) 1srem set-key item
(integer) 0smembers set-key
1) item2
2) item3
应用场景
Redis为集合提供了求交集、并集、差集等操作故可以用来求共同好友等操作。
1.3.5ZSET
数据结构
typedef struct zskiplistNode{//后退指针struct zskiplistNode *backward;//分值double score;//成员对象robj *obj;//层struct zskiplistLever{//前进指针struct zskiplistNode *forward;//跨度unsigned int span;}lever[];}typedef struct zskiplist{//表头节点跟表尾结点struct zskiplistNode *header, *tail;//表中节点的数量unsigned long length;//表中层数最大的节点的层数int lever;}
跳跃表基于多指针有序链实现可以看作多个有序链表。
与红黑树等平衡树相比跳跃表具有以下优点
插入速度非常快速因为不需要进行旋转等操作来维持平衡性。更容易实现。支持无锁操作。
常见操作 zadd zset-key 728 member1
(integer) 1zadd zset-key 982 member0
(integer) 1zadd zset-key 982 member0
(integer) 0zrange zset-key 0 -1
1) member1
2) member0zrange zset-key 0 -1 withscores
1) member1
2) 728
3) member0
4) 982zrangebyscore zset-key 0 800 withscores
1) member1
2) 728zrem zset-key member1
(integer) 1zrem zset-key member1
(integer) 0zrange zset-key 0 -1 withscores
1) member0
2) 982
应用场景
以某个条件为权重比如按顶的次数排序 ZREVRANGE命令可以用来按照得分来获取前100名的用户ZRANK可以用来获取用户排名非常直接而且操作容易。 Redis sorted set的使用场景与set类似区别是set不是自动有序的而sorted set可以通过用户额外提供一个优先级(score)的参数来为成员排序并且是插入有序的即自动排序。 redis命令参考链接
1.4Spring整合Redis
引入依赖 - spring-boot-starter-data-redis dependencygroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-data-redis/artifactId/dependency
配置Redis - 配置数据库参数
# RedisProperties
spring.redis.database11#第11个库这个随便
spring.redis.hostlocalhost
spring.redis.port6379#端口 - 编写配置类构造RedisTemplate
这个springboot已经帮我们配了但是默认object我想改成string
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.serializer.RedisSerializer;Configuration
public class RedisConfig {Beanpublic RedisTemplateString, Object redisTemplate(RedisConnectionFactory factory) {RedisTemplateString, Object template new RedisTemplate();template.setConnectionFactory(factory);// 设置key的序列化方式template.setKeySerializer(RedisSerializer.string());// 设置value的序列化方式template.setValueSerializer(RedisSerializer.json());// 设置hash的key的序列化方式template.setHashKeySerializer(RedisSerializer.string());// 设置hash的value的序列化方式template.setHashValueSerializer(RedisSerializer.json());template.afterPropertiesSet();return template;}}
访问Redis - redisTemplate.opsForValue() - redisTemplate.opsForHash() - redisTemplate.opsForList() - redisTemplate.opsForSet() - redisTemplate.opsForZSet()
RunWith(SpringRunner.class)
SpringBootTest
ContextConfiguration(classes CommunityApplication.class)
public class RedisTests {Autowiredprivate RedisTemplate redisTemplate;Testpublic void testStrings() {String redisKey test:count;redisTemplate.opsForValue().set(redisKey, 1);System.out.println(redisTemplate.opsForValue().get(redisKey));System.out.println(redisTemplate.opsForValue().increment(redisKey));System.out.println(redisTemplate.opsForValue().decrement(redisKey));}Testpublic void testHashes() {String redisKey test:user;redisTemplate.opsForHash().put(redisKey, id, 1);redisTemplate.opsForHash().put(redisKey, username, zhangsan);System.out.println(redisTemplate.opsForHash().get(redisKey, id));System.out.println(redisTemplate.opsForHash().get(redisKey, username));}Testpublic void testLists() {String redisKey test:ids;redisTemplate.opsForList().leftPush(redisKey, 101);redisTemplate.opsForList().leftPush(redisKey, 102);redisTemplate.opsForList().leftPush(redisKey, 103);System.out.println(redisTemplate.opsForList().size(redisKey));System.out.println(redisTemplate.opsForList().index(redisKey, 0));System.out.println(redisTemplate.opsForList().range(redisKey, 0, 2));System.out.println(redisTemplate.opsForList().leftPop(redisKey));System.out.println(redisTemplate.opsForList().leftPop(redisKey));System.out.println(redisTemplate.opsForList().leftPop(redisKey));}Testpublic void testSets() {String redisKey test:teachers;redisTemplate.opsForSet().add(redisKey, 刘备, 关羽, 张飞, 赵云, 诸葛亮);System.out.println(redisTemplate.opsForSet().size(redisKey));System.out.println(redisTemplate.opsForSet().pop(redisKey));System.out.println(redisTemplate.opsForSet().members(redisKey));}Testpublic void testSortedSets() {String redisKey test:students;redisTemplate.opsForZSet().add(redisKey, 唐僧, 80);redisTemplate.opsForZSet().add(redisKey, 悟空, 90);redisTemplate.opsForZSet().add(redisKey, 八戒, 50);redisTemplate.opsForZSet().add(redisKey, 沙僧, 70);redisTemplate.opsForZSet().add(redisKey, 白龙马, 60);System.out.println(redisTemplate.opsForZSet().zCard(redisKey));System.out.println(redisTemplate.opsForZSet().score(redisKey, 八戒));System.out.println(redisTemplate.opsForZSet().reverseRank(redisKey, 八戒));System.out.println(redisTemplate.opsForZSet().reverseRange(redisKey, 0, 2));}Testpublic void testKeys() {redisTemplate.delete(test:user);System.out.println(redisTemplate.hasKey(test:user));redisTemplate.expire(test:students, 10, TimeUnit.SECONDS);}
}
这样还是稍微有点麻烦我们其实可以绑定key // 多次访问同一个keyTestpublic void testBoundOperations() {String redisKey test:count;BoundValueOperations operations redisTemplate.boundValueOps(redisKey);operations.increment();operations.increment();operations.increment();operations.increment();operations.increment();System.out.println(operations.get());}
2、数据结构原理总结
这部分在我看来是最有意思的我们有必要了解底层数据结构的实现这也是我最感兴趣的。
比如你知道redis中的字符串怎么实现的吗为什么这么实现
你知道redis压缩列表是什么算法吗
你知道redis为什么抛弃了红黑树反而采用了跳表这种新的数据结构吗
你知道hyperloglog为什么用如此小的空间就可以有这么好的统计性能和准确性吗
你知道布隆过滤器为什么这么有效吗有没有数学证明过
你是否还能很快写出来快排或者不断优化性能的排序是不是只会调库了甚至库函数怎么实现的都不知道真的就是快排
包括数据库持久化处理事件、客户端服务端、事务的实现、发布和订阅等功能的实现也需要了解。 2.1数据结构和对象的实现
1 字符串
redis并未使用传统的c语言字符串表示它自己构建了一种简单的动态字符串抽象类型。
在redis里c语言字符串只会作为字符串字面量出现用在无需修改的地方。
当需要一个可以被修改的字符串时redis就会使用自己实现的SDSsimple dynamic string。比如在redis数据库里包含字符串的键值对底层都是SDS实现的不止如此SDS还被用作缓冲区buffer比如AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区。
下面来具体看一下sds的实现
struct sdshdr
{int len;//buf已使用字节数量保存的字符串长度int free;//未使用的字节数量char buf[];//用来保存字符串的字节数组
};
sds遵循c中字符串以\0结尾的惯例这一字节的空间不算在len之内。
这样的好处是我们可以直接重用c中的一部分函数。比如printf sds相对c的改进 获取长度c字符串并不记录自身长度所以获取长度只能遍历一遍字符串redis直接读取len即可。 缓冲区安全c字符串容易造成缓冲区溢出比如程序员没有分配足够的空间就执行拼接操作。而redis会先检查sds的空间是否满足所需要求如果不满足会自动扩充。 内存分配由于c不记录字符串长度对于包含了n个字符的字符串底层总是一个长度n1的数组每一次长度变化总是要对这个数组进行一次内存重新分配的操作。因为内存分配涉及复杂算法并且可能需要执行系统调用所以它通常是比较耗时的操作。 redis内存分配
1、空间预分配如果修改后大小小于1MB程序分配和len大小一样的未使用空间如果修改后大于1MB程序分配 1MB的未使用空间。修改长度时检查够的话就直接使用未使用空间不用再分配。
2、惰性空间释放字符串缩短时不需要释放空间用free记录即可留作以后使用。 二进制安全
c字符串除了末尾外不能包含空字符否则程序读到空字符会误以为是结尾这就限制了c字符串只能保存文本二进制文件就不能保存了。
而redis字符串都是二进制安全的因为有len来记录长度。
2 链表
作为一种常用数据结构链表内置在很多高级语言中因为c并没有所以redis实现了自己的链表。
链表在redis也有一定的应用比如列表键的底层实现之一就是链表。当列表键包含大量元素或者元素都是很长的字符串时
发布与订阅、慢查询、监视器等功能也用到了链表。
具体实现
//redis的节点使用了双向链表结构
typedef struct listNode {// 前置节点struct listNode *prev;// 后置节点struct listNode *next;// 节点的值void *value;
} listNode;
//其实学过数据结构的应该都实现过
typedef struct list {// 表头节点listNode *head;// 表尾节点listNode *tail;// 链表所包含的节点数量unsigned long len;// 节点值复制函数void *(*dup)(void *ptr);// 节点值释放函数void (*free)(void *ptr);// 节点值对比函数int (*match)(void *ptr, void *key);
} list;
总结一下redis链表特性
双端、无环、带长度记录、
多态使用 void* 指针来保存节点值 可以通过 dup 、 free 、 match 为节点值设置类型特定函数 可以保存不同类型的值。
3字典
其实字典这种数据结构也内置在很多高级语言中但是c语言没有所以redis自己实现了。
应用也比较广泛比如redis的数据库就是字典实现的。不仅如此当一个哈希键包含的键值对比较多或者都是很长的字符串redis就会用字典作为哈希键的底层实现。
来看看具体是实现
//redis的字典使用哈希表作为底层实现
typedef struct dictht {// 哈希表数组dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩码用于计算索引值// 总是等于 size - 1unsigned long sizemask;// 该哈希表已有节点的数量unsigned long used;} dictht;
table 是一个数组 数组中的每个元素都是一个指向dictEntry 结构的指针 每个 dictEntry 结构保存着一个键值对。 图为一个大小为4的空哈希表。
我们接着就来看dictEntry的实现
typedef struct dictEntry {// 键void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 指向下个哈希表节点形成链表struct dictEntry *next;
} dictEntry;
v可以是一个指针 或者是一个 uint64_t 整数 又或者是一个 int64_t 整数。
next就是解决键冲突问题的冲突了就挂后面这个学过数据结构的应该都知道吧不说了。 下面我们来说字典是怎么实现的了。
typedef struct dict {// 类型特定函数dictType *type;// 私有数据void *privdata;// 哈希表dictht ht[2];// rehash 索引int rehashidx; //* rehashing not in progress if rehashidx -1
} dict;
type 和 privdata 是对不同类型的键值对 为创建多态字典而设置的
type 指向 dictType 每个 dictType 保存了用于操作特定类型键值对的函数 可以为用途不同的字典设置不同的类型特定函数。
而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。
而dictType就暂时不展示了不重要而且字有点多。。。还是讲有意思的东西吧 rehash重新散列
随着我们不断的操作哈希表保存的键值可能会增多或者减少为了让哈希表的负载因子维持在合理的范围内有时需要对哈希表进行合理的扩展或者收缩。 一般情况下 字典只使用 ht[0] 哈希表 ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
redis字典哈希rehash的步骤如下
1为ht[1]分配合理空间如果是扩展操作大小为第一个大于等于ht[0]*used*2的2的n次幂。 如果是收缩操作大小为第一个大于等于ht[0]*used的2的n次幂。
2将ht[0]中的数据rehash到ht[1]上。
3释放ht[0]将ht[1]设置为ht[0]ht[1]创建空表为下次做准备。 渐进rehash
数据量特别大时rehash可能对服务器造成影响。为了避免服务器不是一次性rehash的而是分多次。
我们维持一个变量rehashidx设置为0代表rehash开始然后开始rehash在这期间每个对字典的操作程序都会把索引rehashidx上的数据移动到ht[1]。
随着操作不断执行最终我们会完成rehash设置rehashidx为-1.
需要注意rehash过程中每一次增删改查也是在两个表进行的。
4整数集合
整数集合intset是 Redis 用于保存整数值的集合抽象数据结构 可以保存 int16_t 、 int32_t 、 int64_t 的整数值 并且保证集合中不会出现重复元素。
实现较为简单
typedef struct intset {// 编码方式uint32_t encoding;// 集合包含的元素数量uint32_t length;// 保存元素的数组int8_t contents[];
} intset;
各个项在数组中从小到大有序地排列 并且数组中不包含任何重复项。
虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值
如果 encoding 属性的值为 INTSET_ENC_INT16 那么 contents 就是一个 int16_t 类型的数组 数组里的每个项都是一个 int16_t 类型的整数值 最小值为 -32,768 最大值为 32,767 。
如果 encoding 属性的值为 INTSET_ENC_INT32 那么 contents 就是一个 int32_t 类型的数组 数组里的每个项都是一个 int32_t 类型的整数值 最小值为 -2,147,483,648 最大值为 2,147,483,647 。
如果 encoding 属性的值为 INTSET_ENC_INT64 那么 contents 就是一个 int64_t 类型的数组 数组里的每个项都是一个 int64_t 类型的整数值 最小值为 -9,223,372,036,854,775,808 最大值为 9,223,372,036,854,775,807 。 升级
c语言是静态类型语言不允许不同类型保存在一个数组。这样第一灵活性较差第二有时会用掉不必要的内存
比如用long long储存1
为了提高整数集合的灵活性和节约内存我们引入升级策略。
当我们要将一个新元素添加到集合里 并且新元素类型比集合现有元素的类型都要长时 集合需要先进行升级。
分为三步进行
根据新元素的类型 扩展整数集合底层数组的空间大小 并为新元素分配空间。将底层数组现有的所有元素都转换成与新元素相同的类型 并将类型转换后的元素放置到正确的位上将新元素添加到底层数组里面。
因为每次添加新元素都可能会引起升级 每次升级都要对已有元素类型转换 所以添加新元素的时间复杂度为 O(N) 。
因为引发升级的新元素比原数据都长所以要么他是最大的要么他是最小的。我们把它放在开头或结尾即可。 降级
略略略不管你们信不信整数集合不支持降级操作。。我也不知道为啥
5压缩列表
压缩列表是列表键和哈希键的底层实现之一。
当一个列表键只包含少量列表项并且列表项都是小整数或者短字符串redis就会用压缩列表做列表键底层实现。
压缩列表是 Redis 为了节约内存而开发的 由一系列特殊编码的连续内存块组成的顺序型sequential数据结构。
一个压缩列表可以包含任意多个节点entry 每个节点可以保存一个字节数组或者一个整数值。
具体实现 具体说一下entry
由三个部分组成
1、previous_entry_length:记录上一个节点的长度这样我们就可以从最后一路遍历到开头。
2、encoding记录了content所保存的数据类型和长度。具体编码不写了不重要
3、content保存节点值可以是字节数组或整数。具体怎么压缩的等我搞明白再补 连锁更新
前面说过 每个节点的 previous_entry_length 属性都记录了前一个节点的长度
如果前一节点的长度 254 KB 那么 previous_entry_length 需要用 1 字节长的空间如果前一节点的长度254 KB 那么 previous_entry_length 需要用 5 字节长的空间
现在 考虑这样一种情况 在一个压缩列表中 有多个连续的、长度介于 250 字节到 253 字节之间的节点 这时 如果我们将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点。。。。
然后脑补一下就会导致连锁扩大每个节点的空间对吧e(i)因为e(i-1)的扩大而扩大i1也是如此以此类推。。。 删除节点同样会导致连锁更新。
这个事情只是想说明一个问题插入删除操作的最坏时间复杂度其实是o(n*n)因为每更新一个节点都要o(n)。
但是也不用太过担心因为这种特殊情况并不多见这些命令的平均复杂度依旧是o(n)。 2.2 跳表专栏
2.2.1跳表是啥
为什么选择了跳表而不是红黑树
跳表是个啥东西请看这个文章。
我们知道节点插入时随机出一个层数仅仅依靠一个简单的随机数操作而构建出来的多层链表结构能保证它有一个良好的查找性能吗为了回答这个疑问我们需要分析skiplist的统计性能。
在分析之前我们还需要着重指出的是执行插入操作时计算随机数的过程是一个很关键的过程它对skiplist的统计特性有着很重要的影响。这并不是一个普通的服从均匀分布的随机数它的计算过程如下
首先每个节点肯定都有第1层指针每个节点都在第1层链表里。如果一个节点有第i层(i1)指针即节点已经在第1层到第i层链表中那么它有第(i1)层指针的概率为p。节点最大的层数不允许超过一个最大值记为MaxLevel。
这个计算随机层数的伪码如下所示
randomLevel()
level : 1
// random()返回一个[0...1)的随机数
while random() p and level MaxLevel do
level : level 1
return levelrandomLevel()的伪码中包含两个参数一个是p一个是MaxLevel。在Redis的skiplist实现中这两个参数的取值为
p 1/4
MaxLevel 32
2.2.2skiplist的算法性能分析
在这一部分我们来简单分析一下skiplist的时间复杂度和空间复杂度以便对于skiplist的性能有一个直观的了解。如果你不是特别偏执于算法的性能分析那么可以暂时跳过这一小节的内容。
我们先来计算一下每个节点所包含的平均指针数目概率期望。节点包含的指针数目相当于这个算法在空间上的额外开销(overhead)可以用来度量空间复杂度。
根据前面randomLevel()的伪码我们很容易看出产生越高的节点层数概率越低。定量的分析如下
节点层数至少为1。而大于1的节点层数满足一个概率分布。节点层数恰好等于1的概率为1-p。节点层数大于等于2的概率为p而节点层数恰好等于2的概率为p(1-p)。节点层数大于等于3的概率为p^2而节点层数恰好等于3的概率为p^2(1-p)。节点层数大于等于4的概率为p^3而节点层数恰好等于4的概率为p^3(1-p)。......
因此一个节点的平均层数也即包含的平均指针数目计算如下 现在很容易计算出
当p1/2时每个节点所包含的平均指针数目为2当p1/4时每个节点所包含的平均指针数目为1.33。这也是Redis里的skiplist实现在空间上的开销。
接下来为了分析时间复杂度我们计算一下skiplist的平均查找长度。查找长度指的是查找路径上跨越的跳数而查找过程中的比较次数就等于查找长度加1。以前面图中标出的查找23的查找路径为例从左上角的头结点开始一直到结点22查找长度为6。
为了计算查找长度这里我们需要利用一点小技巧。我们注意到每个节点插入的时候它的层数是由随机函数randomLevel()计算出来的而且随机的计算不依赖于其它节点每次插入过程都是完全独立的。所以从统计上来说一个skiplist结构的形成与节点的插入顺序无关。
这样的话为了计算查找长度我们可以将查找过程倒过来看从右下方第1层上最后到达的那个节点开始沿着查找路径向左向上回溯类似于爬楼梯的过程。我们假设当回溯到某个节点的时候它才被插入这虽然相当于改变了节点的插入顺序但从统计上不影响整个skiplist的形成结构。
现在假设我们从一个层数为i的节点x出发需要向左向上攀爬k层。这时我们有两种可能
如果节点x有第(i1)层指针那么我们需要向上走。这种情况概率为p。如果节点x没有第(i1)层指针那么我们需要向左走。这种情况概率为(1-p)。用C(k)表示向上攀爬k个层级所需要走过的平均查找路径长度概率期望那么
C(0)0
C(k)(1-p)×(上图中情况b的查找长度) p×(上图中情况c的查找长度)
代入得到一个差分方程并化简
C(k)(1-p)(C(k)1) p(C(k-1)1)
C(k)1/pC(k-1)
C(k)k/p
这个结果的意思是我们每爬升1个层级需要在查找路径上走1/p步。而我们总共需要攀爬的层级数等于整个skiplist的总层数-1。
那么接下来我们需要分析一下当skiplist中有n个节点的时候它的总层数的概率均值是多少。这个问题直观上比较好理解。根据节点的层数随机算法容易得出
第1层链表固定有n个节点第2层链表平均有n*p个节点第3层链表平均有n*p^2个节点...
所以从第1层到最高层各层链表的平均节点数是一个指数递减的等比数列。容易推算出总层数的均值为log1/pn而最高层的平均节点数为1/p。
综上粗略来计算的话平均查找长度约等于
C(log1/pn-1)(log1/pn-1)/p
即平均时间复杂度为O(log n)。
当然这里的时间复杂度分析还是比较粗略的。比如沿着查找路径向左向上回溯的时候可能先到达左侧头结点然后沿头结点一路向上还可能先到达最高层的节点然后沿着最高层链表一路向左。但这些细节不影响平均时间复杂度的最后结果。另外这里给出的时间复杂度只是一个概率平均值但实际上计算一个精细的概率分布也是有可能的。
详情还请参见William Pugh的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。
2.2.3skiplist与平衡树、哈希表的比较
skiplist和各种平衡树如AVL、红黑树等的元素是有序排列的而哈希表不是有序的。因此在哈希表上只能做单个key的查找不适宜做范围查找。所谓范围查找指的是查找那些大小在指定的两个值之间的所有节点。在做范围查找的时候平衡树比skiplist操作要复杂。在平衡树上我们找到指定范围的小值之后还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单只需要在找到小值之后对第1层链表进行若干步的遍历就可以实现。平衡树的插入和删除操作可能引发子树的调整逻辑复杂而skiplist的插入和删除只需要修改相邻节点的指针操作简单又快速。从内存占用上来说skiplist比平衡树更灵活一些。一般来说平衡树每个节点包含2个指针分别指向左右子树而skiplist每个节点包含的指针数目平均为1/(1-p)具体取决于参数p的大小。如果像Redis里的实现一样取p1/4那么平均每个节点包含1.33个指针比平衡树更有优势。查找单个keyskiplist和平衡树的时间复杂度都为O(log n)大体相当而哈希表在保持较低的哈希值冲突概率的前提下查找时间复杂度接近O(1)性能更高一些。所以我们平常使用的各种Map或dictionary结构大都是基于哈希表实现的。从算法实现难度上来比较skiplist比平衡树要简单得多。
2.2.4Redis中的skiplist和经典有何不同
分数(score)允许重复即skiplist的key允许重复。这在最开始介绍的经典skiplist中是不允许的。在比较时不仅比较分数相当于skiplist的key还比较数据本身。在Redis的skiplist实现中数据本身的内容唯一标识这份数据而不是由key来唯一标识。另外当多个元素分数相同的时候还需要根据数据内容来进字典排序。第1层链表不是一个单向链表而是一个双向链表。这是为了方便以倒序方式获取一个范围内的元素。在skiplist中可以很方便地计算出每个元素的排名(rank)。
2.2.5作者的话
最后我们看看对于这个问题Redis的作者 antirez 是怎么说的
There are a few reasons:
1) They are not very memory intensive. Its up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
有几个原因
1它们的记忆力不是很强。基本上由你决定。更改有关节点具有给定数量级别的概率的参数将使内存密集度低于btree。
2排序集通常是许多Zrange或Zrevrange操作的目标即作为链表遍历跳过列表。通过此操作跳过列表的缓存区域性至少与其他类型的平衡树一样好。
3它们易于实现、调试等。例如由于跳过列表的简单性我收到了一个补丁已经在redis master中其中包含在ologn中实现zrank的扩展跳过列表。它只需要对代码稍作修改。
2.3HyperLogLog 专栏
HyperLogLog 是一种概率数据结构用来估算数据的基数。数据集可以是网站访客的 IP 地址E-mail 邮箱或者用户 ID。
基数就是指一个集合中不同值的数目比如 a, b, c, d 的基数就是 4a, b, c, d, a 的基数还是 4。虽然 a 出现两次只会被计算一次。
使用 Redis 统计集合的基数一般有三种方法分别是使用 Redis 的 HashMapBitMap 和 HyperLogLog。前两个数据结构在集合的数量级增长时所消耗的内存会大大增加但是 HyperLogLog 则不会。
Redis 的 HyperLogLog 通过牺牲准确率来减少内存空间的消耗只需要12K内存在标准误差0.81%的前提下能够统计2^64个数据。所以 HyperLogLog 是否适合在比如统计日活月活此类的对精度要不不高的场景。
这是一个很惊人的结果以如此小的内存来记录如此大数量级的数据基数。下面我们就带大家来深入了解一下 HyperLogLog 的使用基础原理源码实现和具体的试验数据分析。
2.3.1HyperLogLog 在 Redis 中的使用
Redis 提供了 PFADD 、 PFCOUNT 和 PFMERGE 三个命令来供用户使用 HyperLogLog。
PFADD 用于向 HyperLogLog 添加元素。 PFADD visitors alice bob carol(integer) 1 PFCOUNT visitors(integer) 3
如果 HyperLogLog 估计的近似基数在 PFADD 命令执行之后出现了变化 那么命令返回 1 否则返回 0 。 如果命令执行时给定的键不存在 那么程序将先创建一个空的 HyperLogLog 结构 然后再执行命令。
PFCOUNT 命令会给出 HyperLogLog 包含的近似基数。在计算出基数后 PFCOUNT 会将值存储在 HyperLogLog 中进行缓存知道下次 PFADD 执行成功前就都不需要再次进行基数的计算。
PFMERGE 将多个 HyperLogLog 合并为一个 HyperLogLog 合并后的 HyperLogLog 的基数接近于所有输入 HyperLogLog 的并集基数。 PFADD customers alice dan(integer) 1 PFMERGE everyone visitors customersOK PFCOUNT everyone(integer) 4
2.3.2内存消耗对比实验
我们下面就来通过实验真实对比一下下面三种数据结构的内存消耗HashMap、BitMap 和 HyperLogLog。
我们首先使用 Lua 脚本向 Redis 对应的数据结构中插入一定数量的数然后执行 bgsave 命令最后使用 redis-rdb-tools 的 rdb 的命令查看各个键所占的内存大小。
下面是 Lua 的脚本
local key KEYS[1]local size tonumber(ARGV[1])local method tonumber(ARGV[2])for i1,size,1 doif (method 0)thenredis.call(hset,key,i,1)elseif (method 1)thenredis.call(pfadd,key, i)elseredis.call(setbit, key, i, 1)endend
我们在通过 redis-cli 的 script load 命令将 Lua 脚本加载到 Redis 中然后使用 evalsha 命令分别向 HashMap、HyperLogLog 和 BitMap 三种数据结构中插入了一千万个数然后使用 rdb 命令查看各个结构内存消耗。
我们进行了两轮实验分别插入一万数字和一千万数字三种数据结构消耗的内存统计如下所示。 从表中可以明显看出一万数量级时 BitMap 消耗内存最小 一千万数量级时 HyperLogLog 消耗内存最小但是总体来看HyperLogLog 消耗的内存都是 14392 字节可见 HyperLogLog 在内存消耗方面有自己的独到之处。
2.3.3基本原理
HyperLogLog 是一种概率数据结构它使用概率算法来统计集合的近似基数。而它算法的最本源则是伯努利过程。
伯努利过程就是一个抛硬币实验的过程。抛一枚正常硬币落地可能是正面也可能是反面二者的概率都是 1/2 。伯努利过程就是一直抛硬币直到落地时出现正面位置并记录下抛掷次数k。比如说抛一次硬币就出现正面了此时 k 为 1; 第一次抛硬币是反面则继续抛直到第三次才出现正面此时 k 为 3。
对于 n 次伯努利过程我们会得到 n 个出现正面的投掷次数值 k1, k2 ... kn , 其中这里的最大值是k_max。
根据一顿数学推导我们可以得出一个结论 2^{k_ max} 来作为n的估计值。也就是说你可以根据最大投掷次数近似的推算出进行了几次伯努利过程。 下面我们就来讲解一下 HyperLogLog 是如何模拟伯努利过程并最终统计集合基数的。
HyperLogLog 在添加元素时会通过Hash函数将元素转为64位比特串例如输入5便转为101(省略前面的0下同)。这些比特串就类似于一次抛硬币的伯努利过程。比特串中0 代表了抛硬币落地是反面1 代表抛硬币落地是正面如果一个数据最终被转化了 10010000那么从低位往高位看我们可以认为这串比特串可以代表一次伯努利过程首次出现 1 的位数为5就是抛了5次才出现正面。
所以 HyperLogLog 的基本思想是利用集合中数字的比特串第一个 1 出现位置的最大值来预估整体基数但是这种预估方法存在较大误差为了改善误差情况HyperLogLog中引入分桶平均的概念计算 m 个桶的调和平均值。 Redis 中 HyperLogLog 一共分了 2^14 个桶也就是 16384 个桶。每个桶中是一个 6 bit 的数组。
HyperLogLog 将上文所说的 64 位比特串的低 14 位单独拿出它的值就对应桶的序号然后将剩下 50 位中第一次出现 1 的位置值设置到桶中。50位中出现1的位置值最大为50所以每个桶中的 6 位数组正好可以表示该值。
在设置前要设置进桶的值是否大于桶中的旧值如果大于才进行设置否则不进行设置。
此时为了性能考虑是不会去统计当前的基数的而是将 HyperLogLog 头的 card 属性中的标志位置为 1表示下次进行 pfcount 操作的时候当前的缓存值已经失效了需要重新统计缓存值。在后面 pfcount 流程的时候发现这个标记为失效就会去重新统计新的基数放入基数缓存。
在计算近似基数时就分别计算每个桶中的值带入到上文的 DV 公式中进行调和平均和结果修正就能得到估算的基数值。
2.3.4HyperLogLog 具体对象
我们首先来看一下 HyperLogLog 对象的定义
struct hllhdr {char magic[4]; /* 魔法值 HYLL */uint8_t encoding; /* 密集结构或者稀疏结构 HLL_DENSE or HLL_SPARSE. */uint8_t notused[3]; /* 保留位, 全为0. */uint8_t card[8]; /* 基数大小的缓存 */uint8_t registers[]; /* 数据字节数组 */};
HyperLogLog 对象中的 registers 数组就是桶它有两种存储结构分别为密集存储结构和稀疏存储结构两种结构只涉及存储和桶的表现形式从中我们可以看到 Redis 对节省内存极致地追求。
我们先看相对简单的密集存储结构它也是十分的简单明了既然要有 2^14 个 6 bit的桶那么我就真使用足够多的 uint8_t 字节去表示只是此时会涉及到字节位置和桶的转换因为字节有 8 位而桶只需要 6 位。
所以我们需要将桶的序号转换成对应的字节偏移量 offsetbytes 和其内部的位数偏移量 offsetbits。需要注意的是小端字节序高位在右侧需要进行倒转。
当 offset_bits 小于等于2时说明一个桶就在该字节内只需要进行倒转就能得到桶的值。 offset_bits 大于 2 则说明一个桶分布在两个字节内此时需要将两个字节的内容都进行倒置然后再进行拼接得到桶的值。
Redis 为了方便表达稀疏存储它将上面三种字节表示形式分别赋予了一条指令。 ZERO : 一字节表示连续多少个桶计数为0前两位为标志00后6位表示有多少个桶最大为64。 XZERO : 两个字节表示连续多少个桶计数为0前两位为标志01后14位表示有多少个桶最大为16384。 VAL : 一字节表示连续多少个桶的计数为多少前一位为标志1四位表示连桶内计数所以最大表示桶的计数为32。后两位表示连续多少个桶。 Redis从稀疏存储转换到密集存储的条件是 任意一个计数值从 32 变成 33因为 VAL 指令已经无法容纳它能表示的计数值最大为 32 稀疏存储占用的总字节数超过 3000 字节这个阈值可以通过 hllsparsemax_bytes 参数进行调整。
2.4LRU专栏
2.4.1LRU介绍和代码实现
LRU全称是Least Recently Used即最近最久未使用的意思。
LRU算法的设计原则是如果一个数据在最近一段时间没有被访问到那么在将来它被访问的可能性也很小。也就是说当限定的空间已存满数据时应当把最久没有被访问到的数据淘汰。这一段是找的让大家理解一下什么是LRU。 说一下我们什么时候见到过LRU其实老师们肯定都给大家举过这么个例子你在图书馆你把书架子里的书拿到桌子上。。但是桌子是有限的你有时候不得不把一些书放回去。这就相当于内存和硬盘。这个例子都说过吧
LRU就是记录你最长时间没看过的书就把它放回去。在cache那里见过吧 然后最近在研究redis又看到了这个LRU所以就想写一下吧。
题目设计一个结构这个结构可以查询K-V但是容量有限当存不下的时候就要把用的年代最久远的那个东西扔掉。
其实思路很简单我们维护一个双向链表即可get也就是使用了我们就把把它提到最安全的位置。新来的KV就依次放即可。
我们就先写这个双向链表结构
先写节点结构 public static class NodeV {public V value;public NodeV last;//前public NodeV next;//后public Node(V value) {this.value value;}}
然后写双向链表结构 我们没必要把链表操作都写了分析一下我们只有三个操作
1、加节点
2、使用了某个节点就把它调到尾代表优先级最高
3、把优先级最低的移除也就是去头部
不会的翻我之前的链表操作都有写 public static class NodeDoubleLinkedListV {private NodeV head;//头private NodeV tail;//尾public NodeDoubleLinkedList() {this.head null;this.tail null;}public void addNode(NodeV newNode) {if (newNode null) {return;}if (this.head null) {//头空this.head newNode;this.tail newNode;} else {//头不空this.tail.next newNode;newNode.last this.tail;//注意让本节点前指针指向旧尾this.tail newNode;//指向新尾}}
/*某个点移到最后*/public void moveNodeToTail(NodeV node) {if (this.tail node) {//是尾return;}if (this.head node) {//是头this.head node.next;this.head.last null;} else {//中间node.last.next node.next;node.next.last node.last;}node.last this.tail;node.next null;this.tail.next node;this.tail node;}
/*删除第一个*/public NodeV removeHead() {if (this.head null) {return null;}NodeV res this.head;if (this.head this.tail) {//就一个this.head null;this.tail null;} else {this.head res.next;res.next null;this.head.last null;}return res;}}
链表操作封装完了就要实现这个结构了。
具体思路代码注释 public static class MyCacheK, V {//为了kv or vk都能查private HashMapK, NodeV keyNodeMap;private HashMapNodeV, K nodeKeyMap;//用来做优先级private NodeDoubleLinkedListV nodeList;private int capacity;//容量public MyCache(int capacity) {if (capacity 1) {//你容量连1都不给捣乱呢throw new RuntimeException(should be more than 0.);}this.keyNodeMap new HashMapK, NodeV();this.nodeKeyMap new HashMapNodeV, K();this.nodeList new NodeDoubleLinkedListV();this.capacity capacity;}public V get(K key) {if (this.keyNodeMap.containsKey(key)) {NodeV res this.keyNodeMap.get(key);this.nodeList.moveNodeToTail(res);//使用过了就放到尾部return res.value;}return null;}public void set(K key, V value) {if (this.keyNodeMap.containsKey(key)) {NodeV node this.keyNodeMap.get(key);node.value value;//放新vthis.nodeList.moveNodeToTail(node);//我们认为放入旧key也是使用过} else {NodeV newNode new NodeV(value);this.keyNodeMap.put(key, newNode);this.nodeKeyMap.put(newNode, key);this.nodeList.addNode(newNode);//加进去if (this.keyNodeMap.size() this.capacity 1) {this.removeMostUnusedCache();//放不下就去掉优先级最低的}}}private void removeMostUnusedCache() {//删除头NodeV removeNode this.nodeList.removeHead();K removeKey this.nodeKeyMap.get(removeNode);//删除掉两个map中的记录this.nodeKeyMap.remove(removeNode);this.keyNodeMap.remove(removeKey);}} 2.4.2Redis中的LRU算法改进
redis通常使用缓存是使用一种固定最大内存的使用。当数据达到可使用的最大固定内存时我们需要通过移除老数据来获取空间。redis作为缓存是否有效的重要标志是如何寻找一种好的策略删除即将需要使用的数据是一种糟糕的策略而删除那些很少再次请求的数据则是一种好的策略。 在其他的缓存组件还有个命中率仅仅表示读请求的比例。访问一个缓存中的keys通常不是分布式的。然而访问经常变化这意味着不经常访问相反有些keys一旦不流行可能会转向最经常访问的keys。 因此通常一个缓存系统应该尽可能保留那些未来最有可能被访问的keys。针对keys淘汰的策略是那些未来极少可能被访问的数据应该被移除。 但有一个问题redis和其他缓存系统不能够预测未来。
LRU算法
缓存系统不能预测未来原因是那些很少再次被访问的key也很有可能最近访问相当频繁。如果经常被访问的模式不会突然改变那么这是一种很有效的策略。然而“最近经常被访问”似乎更隐晦地标明一种 理念。这种算法被称为LRU算法。最近访问频繁的key相比访问少的key有更高的可能性。 举个例子这里有4个不同访问周期的key每一个“~”字符代表一秒结尾的“|”表示当前时刻。
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|
A key每5秒请求一次B周期是2秒C、D都是10秒。 访问频率最高的是B因为它的空闲时间最短这意味着B是4个key中未来最有可能被访问的key。 同样的A和C目前的空闲时间是2s和6s也能很好地反映它们本身的周期。然而你可以看到不够严谨D的访问周期是10秒但它却是4个key中最近被访问的。 当然在一个很长的运行周期中LRU算法能工作得很好。通常有一个更高访问频率的key当然有一个更低的空闲周期。LRU算法淘汰最少被访问key那些有最大空闲周期的key。实现上也相当容易只需要额外跟踪最近被访问的key即可有时甚至都需要把所有我们想要淘汰的对象放到一个链表中当一个对象访问就移除链表头部元素当我们要淘汰元素是就直接淘汰链表尾部开始。
redis中的LRU:起因
最初redis不支持LRU算法。当内存有效性成为一个必须被解决的问题时后来才加上了。通过修改redis对象结构在每个key对象增加24bit的空间。没有额外的空间使用链表把所有对象放到一个链表中大指针因此需要实现得更加有效不能因为key淘汰算法而让整个服务改动太大。 24bits的对象已经足够去存储当前的unxi时间戳。这个表现被称为“LRU 时钟”key元数据经常被更新所以它是一个有效的算法。 然后有另一个更加复杂的问题需要解决如何选择访问间隔最长的key然后淘汰它。 redis内部采用一个庞大的hash table来保存添加另外一个数据结构存储时间间隔显然不是一个好的选择。然而我们希望能达到一个LRU本身是一个近似的通过LRU算法本身来实现。
redis原始的淘汰算法简单实现**当需要淘汰一个key时随机选择3个key淘汰其中间隔时间最长的key。**基本上我们随机选择key淘汰key效果很好。后来随机3个key改成一个配置项N随机key。但把默认值提高改成5个后效果大大提高。考虑到它的效果你根本不用修改他。
然而你可能会想这个算法如何有效执行你可以看到我们如何捣毁了很多有趣的数据。也许简单的N key我们会遇到很多好的决策但是当我们淘汰最好的下一个周期又开始抓。
验证规则第一条用肉眼观察你的算法
其中有一个观点已经应用到Redis 3.0正式版中了。在redis2.8中一个LRU缓存经常被使用在多个环境用户关于淘汰的没有抱怨太多但是很明显我可以提高它通过不仅仅是增加额外的空间还有额外的CPU时间。 然而为了提高某项功能你必须观察它。有多个不同的方式去观察LRU算法。你可以通过写工具观察例如模拟不同的工作负载、校验命中率和失误率。 程序非常简单增加一些指定的keys然后频繁地访问这些keys以至于每一个key都有一个下降的空闲时间。最终超过50%的keys被增加一半的老key需要被淘汰。 一个完美理想的LRU实现应该是没有最新加的key被淘汰而是淘汰最初的50%的老key。
规则二不要丢弃重要信息
借助最新的可视化工具我可以在尝试新的方法观察和测试几分钟。使用redis最明显有效的提高算法就是积累对立的垃圾信息在一个淘汰池中。 基本上当N keys算法被采用时通常会分配一个很大的线程pool默认为16key这个池按照空闲时间排序所以只有当有一个大于池中的一个或者池为空的时候最新的key只会进入到这个池中。 同时一个新的redis-cli模式去测量LRU算法也增加了(看这个-lru-test选项)。 还有另外一个方式去检验LRU算法的好坏通过一个幂等访问模式。这个工具通常校验用一个不同的测试新算法工作工作效果好于真实世界负载。它也同样使用流水线和每秒打印访问日志因此可以被使用不用为了基准不同的思想至少可以校验和观察明显的速度回归。
规则三、最少使用原则LFU算法 一切源于一个开放性问题但你有多个redis 3.2数据库时而淘汰算法只能在本机选择。因此假如你全部空闲小的key都是DB0号机器空闲时间长的key都是1号机器redis每台机器都会淘汰各自的key。一个更好的选择当然是先淘汰DB1最后再淘汰DB0。 当redis被当作缓存使用时很少有情况被分成不同的db上这不是一个好的处理方式。然而这也是我为什么我再一次修改淘汰代码的原因。最终我能够修改缓存池包括数据库id使用单缓存池为多个db代替多缓存池。这种实现很麻烦但是通过优化和修改代码最终它比普通实现要快到20%。 然而这时候我对这个redis缓存淘汰算法的好奇心又被点燃。我想要提升它。我花费了几天想要提高LRU算法实现或许可以使用更大的缓存池通过历史时间选择最合适被淘汰的key 经过一段时间通过优化我的工具我理解到LRU算法受限于数据库中的数据样本有时可能相反的场景效果非常好因此要想提高非常非常难。实际上能通过展示不同算法的图片上看这有点非常明显每个周期10个keys几乎和理论的LRU算法表现一致。 当原始算法很难提高时我开始测试新的算法。 如果我们倒回到博客开始我们说过LRU实际上有点严格。哪些key需要我们真正想要保留将来有最大可能被访问最频繁被访问而不是最近被访问的key。 淘汰最少被访问的key算法成为LFULeast Frequently Used将来要被淘汰腾出新空间给新key。 理论上LFU的思想相当简单只需要给每个key加一个访问计数器。每次访问就自增1所以也就很容易知道哪些key被访问更频繁。 当然LFU也会带起其他问题不单单是针对redis对于LFU实现 1、不能使用“移除顶部元素”的方式keys必须要根据访问计数器进行排序。每访问一次就得遍历所有key找出访问次数最少的key。 2、LFU不能仅仅是只增加每一访问的计数器。正如我们所讲的访问模式改变随时变化因此一个有高访问次数的key后面很可能没有人继续访问它因此我们的算法必须要适应超时的情况。 在redis中第一个问题很好解决我们可以在LRU的方式一样随机在缓存池中选举淘汰其中某项。第二个问题redis还是存在因此一般对于LFU的思想必须使用一些方式进行减少或者定期把访问计数器减半。
24位的LFU实现
LFU有它本身的实现在redis中我们使用自己的24bit来记录LRU。 为了实现LFU仅仅需要在每个对象额外新增24bit 1、一部分用于保存访问计数器 2、足够用于决定什么时候将计数器减半的信息
我的解决方法是把24bit分成两列
16bits8bitslast decr timeLOG_C
16位记录最后一次减半时间那样redis知道上一次减半时间另外8bit作为访问计数器。 你可能会想8位的计数器很快就会溢出是的相对于简单计数器我采用逻辑计数器。逻辑计数器的实现
uint8_t LFULogIncr(uint8_t counter) {if (counter 255) return 255;double r (double)rand()/RAND_MAX;double baseval counter - LFU_INIT_VAL;if (baseval 0) baseval 0;double p 1.0/(baseval*server.lfu_log_factor1);if (r p) counter;return counter;}
基本上计数器的较大者更小的可能计数器会增加上面的代码计算p位于0~1之间但计数器增长时会越来越小位于0-1的随机数r只会但满足rp时计数器才会加一。 你可以配置计数器增长的速率如果使用默认配置会发生
100次访问后计数器101000次访问是是1810万次访问是142100万次访问后达到255并不在继续增长
下面让我们看看计数器如果进行衰减。16位的被储存为unix时间戳保留到分钟级别redis会随机扫描key填充到缓存池中如果最后一个下降的时间大于N分钟前可配置化如果计数器的值很大就减半或者对于值小的就直接简单减半。 这里又衍生出另外一个问题就是新进来的key是需要有机会被保留的。由于LFU新增是得分都是0非常容易被选举替换掉。在redis中开始默认值为5。这个初始值是根据增长数据和减半算法来估算的。模拟显示得分小于5的key是首选。
代码和性能
上面描述的算法已经提交到一个非稳定版的redis分支上。我最初的测试显示它在幂等模式下优于LRU算法测试情况是每个key使用用相同数量的内存然而真实世界的访问可能会有很大不同。时间和空间都可能改变得很不同所以我会很开心去学习观察现实世界中LFU的性能如何两种方式在redis实现中对性能的改变。 因此新增了一个OBJECT FREQ子命令用于报告给定key的访问计数器不仅仅能有效提观察一个计数器而且还能调试LFU实现中的bug。 注意运行中切换LRU和LFU刚开始会随机淘汰一些key随着24bit不能匹配上然而慢慢会适应。 还有几种改进实现的可能。Ben Manes发给我这篇感兴趣的文章描述了一种叫TinyLRU算法。链接
这篇文章包含一个非常厉害的观点相比于记录当前对象的访问频率让我们概率性地记录全部对象的访问频率看到了这种方式我们甚至可以拒绝新key同样我们相信这些key很可能得到很少的访问所以一点也不需要淘汰如果淘汰一个key意味着降低命中/未命中率。 我的感觉这种技术虽然很感兴趣GET/SET LFU缓存但不适用与redis性质的数据服务器用户期望keys被创建后至少存在几毫秒。拒绝key的创建似乎在redis上就是一种错误。 然而redis保留了LFU信息当一个key被覆盖时举个例子
SET oldkey some_new_value
24位的LFU计数器会从老的key复制到新对象中。
新的redis淘汰算法不稳定版本还有以下几个好消息 1、跨DB策略。在过去的redis只是基于本地的选举现在修复为所有策略不仅仅是LRU。 2、易变ttl策略。基于key预期淘汰存活时间如今就像其他策略中的使用缓存池。 3、在缓存池中重用了sds对象性能更好。
这篇博客比我预期要长但是我希望它反映出一个见解在创新和对于已经存在的事物实现上一种解决方案去解决一个特定问题一个基础工具。由开发人员以正确的方式使用它。许多redis的用户把redis作为一个缓存的解决方案因此提高淘汰策略这一块经常一次又一次被拿出来探讨。
2.6对象
刚写了redis主要的数据结构
动态字符串、双端链表、字典、压缩列表、整数集合、跳表等
redis肯定不能直接使用这些数据结构来实现数据库它用这些数据库建立了一个对象系统包含
字符串对象、列表对象、哈希对象、集合对象、有序集合对象
我们可以针对不同的使用场景为对象设置多种分不同的数据结构实现从而优化对象在不同场景下的效率。
1键值对
对于redis的键值对来说key只有字符串类型而v可以是各种类型
我们习惯把“这个键所对应的值是一个列表”表达为这是一个“列表键。
TYPE 命令的实现方式也与此类似 当我们对一个数据库键执行 TYPE 命令时 命令返回的结果为数据库键对应的值对象的类型 而不是键对象的类型
# 键为字符串对象值为列表对象redis RPUSH numbers 1 3 5
(integer) 6redis TYPE numbers
list
2对象
我们看一下redis对象的组成
typedef struct redisObject {// 类型unsigned type:4;// 编码unsigned encoding:4;// 指向底层实现数据结构的指针void *ptr;// ...
} robj;
通过 encoding 属性来设定对象所使用的编码 而不是为特定类型的对象关联一种固定的编码 极大地提升了 Redis 的灵活性和效率 因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码 从而优化对象在某一场景下的效率。
字符串对象
字符串对象的编码可以是 int 、 raw 或者 embstr 。
如果一个字符串对象保存的是整数值 并且这个整数值可以用 long 类型来表示 那么字符串对象会将整数值保存在字符串对象结构的 ptr属性里面将 void* 转换成 long 并将字符串对象的编码设置为 int 。
如果字符串对象保存的是一个字符串值 并且这个字符串值的长度大于 39 字节 那么字符串对象将使用一个简单动态字符串SDS来保存这个字符串值 并将对象的编码设置为 raw 。
如果字符串对象保存的是一个字符串值 并且这个字符串值的长度小于等于 39 字节 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。
embstr 编码是专门用于保存短字符串的一种优化编码方式 这种编码和 raw 编码一样 都使用 redisObject 结构和 sdshdr 结构来表示字符串对象但 raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间 空间中依次包含 redisObject 和 sdshdr 两个结构。 embstr 编码有以下好处
embstr 编码创建删除字符串对象只需操作一次内存因为数据都保存在一块连续的内存 所以这种编码的字符串对象比 raw 编码字符串对象能更好地利用缓存带来的优势。
3列表对象
列表对象的编码可以是 ziplist 或者 linkedlist 。
当列表对象可以同时满足以下两个条件时 列表对象使用 ziplist 编码
列表对象保存的所有字符串元素的长度都小于 64 字节列表对象保存的元素数量小于 512 个
不能满足这两个条件的列表对象需要使用 linkedlist 编码。
4哈希对象
哈希对象的编码可以是 ziplist 或者 hashtable 。
当哈希对象可以同时满足以下两个条件时 哈希对象使用 ziplist 编码
哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节哈希对象保存的键值对数量小于 512 个
不能满足这两个条件的哈希对象需要使用 hashtable 编码。
5集合对象
集合对象的编码可以是 intset 或者 hashtable 。
当集合对象可以同时满足以下两个条件时 对象使用 intset 编码
集合对象保存的所有元素都是整数值集合对象保存的元素数量不超过 512 个
不能满足这两个条件的集合对象需要使用 hashtable 编码。
6有序集合对象
有序集合的编码可以是 ziplist 或者 skiplist 。
当有序集合对象可以同时满足以下两个条件时 对象使用 ziplist 编码
有序集合保存的元素数量小于 128 个有序集合保存的所有元素成员的长度都小于 64 字节
不能满足以上两个条件的有序集合对象将使用 skiplist 编码。
这里多说两句各个语言的对象其实都差不多底层实现也就那几个比如java中的容器c的STL。java的hashset就是一个哈希而已hashmap就是k带了一个v而”有序的“Treemap使用了红黑树这种有平衡性的搜索二叉树。
redis的有序集合并没有再采取hash红黑树的操作而是把平衡树换成了跳表实际上性能真的没差多少甚至有时比红黑树有优势比如跳表的性能较为平均红黑树攒了很多次不平衡要调整可能会带来资源需求的一个高峰再加上跳表实现简单的优点红黑树真的没什么优势。
并且就算是真的想用一种带平衡性的搜索树现在竞赛也是用的华人之光发明的SB树。
有序集合的优点就是它的有序操作比如拿最大最小值红黑树时间o(logN),而哈希表只能一个一个遍历。缺点在于插入一个值的时间也是o(logN),跳表也是。而哈希表插入数是o(1).
要了解底层和这些优缺点
