ClawHub的技术分享

引言本篇文章来了解一下Redis内存淘汰机制与过期策略,这是两个独立的内容，内存淘汰机制只有在redis中内存大于 server.maxmemory时触发。过期策略在操作key-val对时候检测，如果过期就进行相应的处理。 1、内存淘汰机制先看内存淘汰机制，在执行任何命令之前都会检测，内存超过限制时触发：redis.c 12345678910111213141516171819202122int processCommand(redisClient *c) { //略.... /* Handle the maxmemory directive. * * First we try to free some memory if possible (if there are volatile * keys in the dataset). If there are not the only thing we can do * is returning an error. */ // 如果设置了最大内存，那么检查内存是否超过限制，并做相应的操 ...

引言经过前几个文章的学习，大概了解了redis中用到的主要的数据结构：简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表。但是我们使用的时候并没有直接使用这些数据结构，而是基于这个封装出string、list、hash、set、zset五种对象类型。 1、redis对象的数据结构123456789101112typedef struct redisObject { // 类型 unsigned type:4; // 编码 unsigned encoding:4; // 对象最后一次被访问的时间 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */ // 引用计数 int refcount; // 指向实际值的指针 void *ptr;} robj; 1.1、encoding通过编码方式encoding来确定*ptr所指向的数据结构是什么。 1.2、refcount对象数据结构中的引用计数refcount有两个作 ...

引言redis中的hash,list,zset在数据量小的时候都使用压缩列表ziplist。这些对应关系在redis源码的onject.c中可以看出来。等最后写对象总结的时候再好好看看。 Ziplist 是为了尽可能地节约内存而设计的特殊编码双端链表。 结构抄一段源码中别人放的注释： 12345678910111213141516171819202122232425262728293031323334/* 空白 ziplist 示例图area |<---- ziplist header ---->|<-- end -->|size 4 bytes 4 bytes 2 bytes 1 byte +---------+--------+-------+-----------+component | zlbytes | zltail | zllen | zlend | | | | | |value | ...

1、intset数据结构整数集合intset用来实现集合键，当数据量小，并且都是整数的时候才使用，数据结构比较简单： 1234567891011121314typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[];} intset; intset 底层本质是一个有序的、不重复的、整型的数组，支持不同类型整数。 看一下查找算法： 123456789101112131415161718/* Determine whether a value belongs to this set * * 检查给定值 value 是否集合中的元素。 * * 是返回 1 ，不是返回 0 。 * * T = O(log N) */uint8_t intsetFind(intset *is, int64_t value) { // 计算 value 的编码 uint8 ...

引言 跳跃表(skip list) 可以媲美平衡树(AVL Tree)，是一种 插入/删除/搜索 都是 O(logN) 的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树，如 redis, leveldb 等。 在redis中，有序集合键与集群节点中用到跳跃表。 1、数据结构跳跃表的数据结构有两部分组成：zskiplistNode和zskiplist,位于redis.h源码中。 1.1、跳跃表节点zskiplistNode12345678910111213141516171819/* ZSETs use a specialized version of Skiplists *//* * 跳跃表节点 */typedef struct zskiplistNode { // 成员对象 robj *obj; // 分值 double score; // 后退指针 struct zskiplistNode *backward; // 层 struct zskipli ...

引言字典dict相当于java中的HashMap，用来实现redis数据库和redis的hash类型value。 1、数据结构字典数据结构分为三部分，字典dict、哈希表dictht、节点dictEntry。一个dict包含两个dictht，一个dictht有多个dictEntry,每个dictEntry代表key-val。 1.1、节点dictEntry123456789101112131415/* * 哈希表节点 */typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next;} dictEntry; 和java中的java.util.HashMap.Node差不多： 1234567static class Node<K,V> im ...

1、数据结构1234567891011121314151617181920212223242526272829303132/* * 双端链表结构 */typedef struct list { // 表头节点 listNode *head; // 表尾节点 listNode *tail; // 节点值复制函数 void *(*dup)(void *ptr); // 节点值释放函数 void (*free)(void *ptr); // 节点值对比函数 int (*match)(void *ptr, void *key); // 链表所包含的节点数量 unsigned long len;} list;/* * 双端链表节点 */typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value;} ...

1、数据结构1234567891011/* * 保存字符串对象的结构 */struct sdshdr { // buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 数据空间 char buf[];}; 2、新建sds12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758/* * 根据给定的初始化字符串 init 和字符串长度 initlen * 创建一个新的 sds * * 参数 * init ：初始化字符串指针 * initlen ：初始化字符串的长度 * * 返回值 * sds ：创建成功返回 sdshdr 相对应的 sds * 创建失败返回 NULL * * 复杂度 * T = O(N) *//* Create a new sds string with the content speci ...

引言Redis中每个键值对都是由对象组成: 键总是一个字符串对象（string） 值可以是字符串对象（string）、列表对象（list）、哈希对象（hash）、集合对象（set）、有序集合对象（zset）。 1、介绍redis官方网站中对其数据类型的简单介绍:An introduction to Redis data types and abstractions摘抄一段关于redis key的介绍： Redis keysRedis keys are binary safe, this means that you can use any binary sequence as a key, from a string like “foo” to the content of a JPEG file. The empty string is also a valid key.A few other rules about keys: Very long keys are not a good idea. For instance a key of 1024 bytes is a ...

引言一直在使用redis,但是却没有系统的了解过它的底层实现，准备边学习边记录，深入了解redis。打算分析以下几个方面： redis的基本类型及底层原理与java对比，每种数据类型的使用场景 redis底层对象 key的一致性Hash算法 单线程的redis“快” redis的过期策略以及内存淘汰机制 redis分布式锁原理 redis备份方式 多机环境下主从赋值、哨兵、集群的优缺点 哨兵机制与选举算法 集群机制的分片原理 缓存的key并发竞争问题 缓存和数据库双写一致性问题 缓存雪崩问题 缓存击穿问题 这只是暂时列举出来，最后有可能删减。 1、前期准备1.1、带注释的源码redis-3.0-annotated 1.2、相关资料《Redis设计与实现》PDF链接：https://pan.baidu.com/s/190tZRsOQpGCqs57BGL-cXA 密码：i94A 参考的博客文章将在每一篇文章下方给出。