redis的底層原理是什麼

Redis核心物件

在Redis中有一個「核心的物件」叫做redisObject ，是用來表示所有的key和value的，用redisObject結構體來表示String、 Hash、List、Set、ZSet五種資料類型。

redisObject的原始碼在redis.h中，使用c語言寫的，感興趣的可以自行查看，關於redisObject我這裡畫了一張圖，表示redisObject的結構如下所示：

在redisObject中“type表示屬於哪種資料類型，encoding表示該資料的儲存方式”，也就是底層的實現的該資料類型的數據結構。因此這篇文章具體介紹的也是encoding對應的部分。

那麼encoding中的儲存類型又分別表示什麼意思呢？具體資料型態所表示的意義，如下圖：

可能看完這張圖，還是覺得一臉懵。不慌，會進行五種資料結構的詳細介紹，這張圖只是讓你找到每種中資料結構對應的儲存類型有哪些，大概腦子裡有個印象。

舉一個簡單的例子，你在Redis中設定一個字串key 234，然後查看這個字串的儲存類型就會看到為int類型，非整數型的使用的是embstr儲存類型，具體操作如下圖所示：

String類型

#String是Redis最基本的資料類型，上面的簡介也說到Redis是用c語言開發的。但是Redis中的字串和c語言中的字串類型卻是有明顯的區別。

There are three ways to store data structure of type String: int, raw, and embstr.。那麼這三種儲存方式有什麼差別呢？

int

Redis中規定假如儲存的是「整數型值」，例如set num 123這樣的類型，就會使用int的儲存方式進行存儲，在redisObject的“ptr屬性”中就會儲存該值。

SDS

假如儲存的「字串是一個字串值且長度大於32個位元組」就會使用SDS（​​simple dynamic string）方式進行存儲，並且encoding設定為raw；如果是“字串長度小於等於32個位元組”就會將encoding改為embstr來保存字串。

SDS稱為「簡單動態字串」，對於SDS中的定義在Redis的原始碼中有的三個屬性int len、int free、char buf[]。

len保存了字串的長度，free表示buf數組中未使用的位元組數量，buf數組則是保存字串的每個字元元素。

因此當你在Redsi中儲存一個字串Hello時，根據Redis的原始碼的描述可以畫出SDS的形式的redisObject結構圖如下圖所示：

SDS與c語言字串對比

Redis使用SDS作為儲存字串的類型肯定是有自己的優勢，SDS與c語言的字串相比，SDS對c語言的字串做了自己的設計和最佳化，具體優勢有以下幾點：

（1）c語言中的字串並不會記錄自己的長度，因此「每次取得字串的長度都會遍歷得到，時間的複雜度是O(n)”，而Redis中取得字串只要讀取len的值就可，時間複雜度變成O(1)。

（2）「c語言」中兩個字串拼接，若是沒有分配足夠長度的記憶體空間就「會出現緩衝區溢位的狀況」 ；而「SDS」會先根據len屬性判斷空間是否滿足要求，若是空間不夠，就會進行對應的空間擴展，所以「不會出現緩衝區溢位的狀況」。

（3）SDS也提供「空間預先分配」和「惰性空間釋放」兩種策略。在為字串分配空間時，分配的空間比實際上要多，這樣就能「減少連續的執行字串成長帶來記憶體重新分配的次數」。

當字串被縮短的時候，SDS也不會立即回收不適用的空間，而是透過free屬性將不使用的空間記錄下來，等後面使用的時候再釋放。

具體的空間預先分配原則是：「當修改字串後的長度len小於1MB，就會預先分配和len一樣長度的空間，即len=free；若是len大於1MB， free分配的空間大小就為1MB”。

（4）SDS是二進位安全的，除了可以儲存字串以外還可以儲存二進位檔案（如圖片、音頻，視訊等檔案的二進位資料）；而c語言中的字串是以空字串作為結束符，有些圖片中含有結束符，因此不是二進位安全的。

為了方便易懂，做了一個c語言的字串和SDS進行比較的表格，如下所示：

c語言字串 SDS  取得長度的時間複雜度為O(n) 取得長度的時間複雜度為O(1) 不是二進位安全的是二進位安全的只能保存字串還可以保存二進位資料n次成長字串必然會帶來n次的記憶體分配n次成長字串記憶體分配的次數

String類型應用

說到這裡我相信很多人可以說已經精通Redis的String類型了，但是純理論的精通，理論還是得應用實踐，上面說到String可以用來儲存圖片，現在就以圖片儲存作為案例實現。

（1）先要把上傳得圖片編碼，這裡寫了一個工具類別把圖片處理成了Base64得編碼形式，具體得實現程式碼如下：

/**  * 将图片内容处理成Base64编码格式  * @param file  * @return  */  public static String encodeImg(MultipartFile file) {  byte[] imgBytes = null;  try {  imgBytes = file.getBytes();  } catch (IOException e) {  e.printStackTrace();  }  BASE64Encoder encoder = new BASE64Encoder();  return imgBytes==null?null:encoder.encode(imgBytes );

複製程式碼

（2）第二步就是把處理後的圖片字串格式儲存進Redis中，實作得程式碼如下： 

/**  * Redis存储图片  * @param file  * @return  */  public void uploadImageServiceImpl(MultipartFile image) {  String imgId = UUID.randomUUID().toString();  String imgStr= ImageUtils.encodeImg(image);  redisUtils.set(imgId , imgStr);  // 后续操作可以把imgId存进数据库对应的字段，如果需要从redis中取出，只要获取到这个字段后从redis中取出即可。  }

這樣就是實作了圖片得二進位存儲，當然String類型得資料結構得應用也還有常規計數：「統計微博數、統計粉絲數」等。

Hash型別

Hash物件的實作方式有兩種分別是ziplist、hashtable，其中hashtable的儲存方式key是String型別的，value也是以key value的形式儲存。

字典類型的底層就是hashtable實現的，明白了字典的底層實作原理也就是明白了hashtable的實作原理，hashtable的實作原理可以於HashMap的是底層原理相類比。

字典

兩者在新增時都會透過key計算出數組下標，不同的是計算法方式不同，HashMap中是以hash函數的方式，而hashtable中計算出hash值後，也要透過sizemask 屬性和雜湊值再次得到數組下標。

我們知道hash表最大的問題就是hash衝突，為了解決hash衝突，假如hashtable中不同的key透過計算得到同一個index，就會形成單向鍊錶（「鏈位址法」 ），如下圖所示：

rehash

#在字典的底層實作中，value物件以每一個dictEntry的物件進行存儲，當hash表中的存放的鍵值對不斷的增加或減少時，需要對hash表進行一個擴展或收縮。

就像HashMap一樣，這裡也會進行rehash操作，也就是重新散列排布。透過上圖可見，ht[0]和ht[1]是兩個對象，下面我們將重點放在它們的屬性的作用。

在hash表結構定義中有四個屬性分別是dictEntry **table、unsigned long size、unsigned long sizemask、unsigned long used，分別表示的含義就是“哈希表數組、hash表大小、用於計算索引值，總是等於size-1、hash表中已有的節點數」。

ht[0]是用來最開始儲存資料的，當要擴充或縮小時，ht[0]的大小就決定了ht[1]的大小，ht[0]中的所有的鍵值對就會重新散列到ht[1]。

擴展操作：ht[1]擴展的大小是比當前ht[0].used 值的二倍大的第一個2 的整數冪；收縮操作：ht[0].used 的第一個大於等於的2 的整數冪。

當ht[0]上的所有的鍵值對都rehash到ht[1]中，會重新計算所有的陣列下標值，當資料遷移完後ht[0]就會被釋放，然後將ht[1]改為ht[0]，並新建ht[1]，為下一次的擴展和收縮做準備。

漸進式rehash

假如在rehash的過程中資料量非常大，Redis不是一次把全部資料rehash成功，這樣會導致Redis對外服務停止，Redis內部為了處理這種情況採用「漸進式的rehash」。

Redis將所有的rehash的操作分成多步驟進行，直到都rehash完成，具體的實現與物件中的rehashindex屬性相關，「若是rehashindex 表示為-1表示沒有rehash操作」。

當rehash操作開始時會將值改成0，在漸進式rehash的過程「更新、刪除、查詢會在ht[0]和ht[1]中都會進行」，例如更新一個值先更新ht[0]，然後再更新ht[1]。

而新增操作直接就新增到ht[1]表中，ht[0]不會新增任何的數據，這樣保證“ht[0]只減不增，直到最後的某一個時刻變成空表”，這樣rehash操作完成。

上面就是字典的底層hashtable的實作原理，說完了hashtable的實作原理，我們再來看看Hash資料結構的兩一種儲存方式「ziplist（壓縮列表）」

#

ziplist

压缩列表（ziplist）是一组连续内存块组成的顺序的数据结构，压缩列表能够节省空间，压缩列表中使用多个节点来存储数据。

压缩列表是列表键和哈希键底层实现的原理之一，「压缩列表并不是以某种压缩算法进行压缩存储数据，而是它表示一组连续的内存空间的使用，节省空间」，压缩列表的内存结构图如下：

压缩列表中每一个节点表示的含义如下所示：

zlbytes：4个字节的大小，记录压缩列表占用内存的字节数。

1. zltail：4个字节大小，记录表尾节点距离起始地址的偏移量，用于快速定位到尾节点的地址。

2. zllen：2个字节的大小，记录压缩列表中的节点数。

3. entry：表示列表中的每一个节点。

4. zlend：表示压缩列表的特殊结束符号'0xFF'。

再压缩列表中每一个entry节点又有三部分组成，包括previous_entry_ength、encoding、content。

1. previous_entry_ength表示前一个节点entry的长度，可用于计算前一个节点的其实地址，因为他们的地址是连续的。

2. encoding：这里保存的是content的内容类型和长度。

3. content：content保存的是每一个节点的内容。

说到这里相信大家已经都hash这种数据结构已经非常了解，若是第一次接触Redis五种基本数据结构的底层实现的话，建议多看几遍，下面来说一说hash的应用场景。

应用场景

哈希表相对于String类型存储信息更加直观，擦欧总更加方便，经常会用来做用户数据的管理，存储用户的信息。

hash也可以用作高并发场景下使用Redis生成唯一的id。下面我们就以这两种场景用作案例编码实现。

存储用户数据

第一个场景比如我们要储存用户信息，一般使用用户的ID作为key值，保持唯一性，用户的其他信息（地址、年龄、生日、电话号码等）作为value值存储。

若是传统的实现就是将用户的信息封装成为一个对象，通过序列化存储数据，当需要获取用户信息的时候，就会通过反序列化得到用户信息。

但是这样必然会造成序列化和反序列化的性能的开销，并且若是只修改其中的一个属性值，就需要把整个对象序列化出来，操作的动作太大，造成不必要的性能开销。

若是使用Redis的hash来存储用户数据，就会将原来的value值又看成了一个k v形式的存储容器，这样就不会带来序列化的性能开销的问题。

分布式生成唯一ID

第二个场景就是生成分布式的唯一ID，这个场景下就是把redis封装成了一个工具类进行实现，实现的代码如下： 

// offset表示的是id的递增梯度值  public Long getId(String key,String hashKey,Long offset) throws BusinessException{  try {  if (null == offset) {  offset=1L;  }  // 生成唯一id  return redisUtil.increment(key, hashKey, offset);  } catch (Exception e) {  //若是出现异常就是用uuid来生成唯一的id值  int randNo=UUID.randomUUID().toString().hashCode();  if (randNo <h3 id="List类型">List类型</h3><p>在 Redis 3.2 之前的版本，Redis 的列表是通过结合使用 ziplist 和 linkedlist 实现的。在3.2之后的版本就是引入了quicklist。</p><p>ziplist压缩列表上面已经讲过了，我们来看看linkedlist和quicklist的结构是怎么样的。</p><p>Linkedlist有双向链接，和普通的链表一样，都由指向前后节点的指针构成。时间复杂度为O(1)的操作包括插入、修改和更新，而时间复杂度为O(n)的操作是查询。</p><p>linkedlist和quicklist的底层实现是采用链表进行实现，在c语言中并没有内置的链表这种数据结构，Redis实现了自己的链表结构。</p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/887/227/168511087742882.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="redis的底層原理是什麼"></p><p>Redis中链表的特性：</p><ol class=" list-paddingleft-2">
<li><p>每一个节点都有指向前一个节点和后一个节点的指针。</p></li>
<li><p>头节点和尾节点的prev和next指针指向为null，所以链表是无环的。</p></li>
<li><p>链表有自己长度的信息，获取长度的时间复杂度为O(1)。</p></li>
</ol><p>Redis中List的实现比较简单，下面我们就来看看它的应用场景。</p><h3 id="应用场景">应用场景</h3><p>Redis中的列表可以实现<strong>「阻塞队列」</strong>，结合lpush和brpop命令就可以实现。生产者使用lupsh从列表的左侧插入元素，消费者使用brpop命令从队列的右侧获取元素进行消费。</p><p>（1）首先配置redis的配置，为了方便我就直接放在application.yml配置文件中，实际中可以把redis的配置文件放在一个redis.properties文件单独放置，具体配置如下：</p><pre class="brush:php;toolbar:false">spring  redis:  host: 127.0.0.1  port: 6379  password: user  timeout: 0  database: 2  pool:  max-active: 100  max-idle: 10  min-idle: 0  max-wait: 100000

（2）第二步创建redis的配置类，叫做RedisConfig，并标注上@Configuration注解，表明他是一个配置类。

@Configuration  public class RedisConfiguration {  @Value("{spring.redis.port}")  private int port;  @Value("{spring.redis.pool.max-active}")  private int maxActive;  @Value("{spring.redis.pool.min-idle}")  private int minIdle;  @Value("{spring.redis.database}")  private int database;  @Value("${spring.redis.timeout}")  private int timeout;  @Bean  public JedisPoolConfig getRedisConfiguration(){  JedisPoolConfig jedisPoolConfig= new JedisPoolConfig();  jedisPoolConfig.setMaxTotal(maxActive);  jedisPoolConfig.setMaxIdle(maxIdle);  jedisPoolConfig.setMinIdle(minIdle);  jedisPoolConfig.setMaxWaitMillis(maxWait);  return jedisPoolConfig;  }  @Bean  public JedisConnectionFactory getConnectionFactory() {  JedisConnectionFactory factory = new JedisConnectionFactory();  factory.setHostName(host);  factory.setPort(port);  factory.setPassword(password);  factory.setDatabase(database);  JedisPoolConfig jedisPoolConfig= getRedisConfiguration();  factory.setPoolConfig(jedisPoolConfig);  return factory;  }   @Bean  public RedisTemplate, ?> getRedisTemplate() {  JedisConnectionFactory factory = getConnectionFactory();  RedisTemplate, ?> redisTemplate = new StringRedisTemplate(factory);  return redisTemplate;  }  }

（3）第三步就是创建Redis的工具类RedisUtil，自从学了面向对象后，就喜欢把一些通用的东西拆成工具类，好像一个一个零件，需要的时候，就把它组装起来。

@Component  public class RedisUtil {  @Autowired  private RedisTemplate<string> redisTemplate;  /**   存消息到消息队列中  @param key 键  @param value 值  @return  */  public boolean lPushMessage(String key, Object value) {  try {  redisTemplate.opsForList().leftPush(key, value);  return true;  } catch (Exception e) {  e.printStackTrace();  return false;  }  }   /**   从消息队列中弹出消息 - <rpop>  @param key 键  @return  */  public Object rPopMessage(String key) {  try {  return redisTemplate.opsForList().rightPop(key);  } catch (Exception e) {  e.printStackTrace();  return null;  }  }   /**   查看消息  @param key 键  @param start 开始  @param end 结束 0 到 -1代表所有值  复制代码@return  */  public List<object> getMessage(String key, long start, long end) {  try {  return redisTemplate.opsForList().range(key, start, end);  } catch (Exception e) {  e.printStackTrace();  return null;  }  }</object></rpop></string>

这样就完成了Redis消息队列工具类的创建，在后面的代码中就可以直接使用。

Set集合

Redis中列表和集合都可以用来存储字符串，但是「Set是不可重复的集合，而List列表可以存储相同的字符串」，Set集合是无序的这个和后面讲的ZSet有序集合相对。

Set的底层实现是「ht和intset」，ht（哈希表）前面已经详细了解过，下面我们来看看inset类型的存储结构。

inset也叫做整数集合，用于保存整数值的数据结构类型，它可以保存int16_t、int32_t 或者int64_t 的整数值。

在整数集合中，有三个属性值encoding、length、contents[]，分别表示编码方式、整数集合的长度、以及元素内容，length就是记录contents里面的大小。

在整数集合新增元素的时候，若是超出了原集合的长度大小，就会对集合进行升级，具体的升级过程如下：

1. 首先扩展底层数组的大小，并且数组的类型为新元素的类型。

2. 然后将原来的数组中的元素转为新元素的类型，并放到扩展后数组对应的位置。

3. 整数集合升级后就不会再降级，编码会一直保持升级后的状态。

应用场景

Set集合的应用场景可以用来「去重、抽奖、共同好友、二度好友」等业务类型。接下来模拟一个添加好友的案例实现：

@RequestMapping(value = "/addFriend", method = RequestMethod.POST)  public Long addFriend(User user, String friend) {  String currentKey = null;  // 判断是否是当前用户的好友  if (AppContext.getCurrentUser().getId().equals(user.getId)) {  currentKey = user.getId.toString();  }  //若是返回0则表示不是该用户好友  return currentKey==null?0l:setOperations.add(currentKey, friend);  }

假如两个用户A和B都是用上上面的这个接口添加了很多的自己的好友，那么有一个需求就是要实现获取A和B的共同好友，那么可以进行如下操作：

public Set intersectFriend(User userA, User userB) {  return setOperations.intersect(userA.getId.toString(), userB.getId.toString());  }

举一反三，还可以实现A用户自己的好友，或者B用户自己的好友等，都可以进行实现。

ZSet集合

ZSet是有序集合，从上面的图中可以看到ZSet的底层实现是ziplist和skiplist实现的，ziplist上面已经详细讲过，这里来讲解skiplist的结构实现。

skiplist也叫做「跳跃表」，跳跃表是一种有序的数据结构，它通过每一个节点维持多个指向其它节点的指针，从而达到快速访问的目的。

skiplist由如下几个特点：

1. 有很多层组成，由上到下节点数逐渐密集，最上层的节点最稀疏，跨度也最大。

2. 每一层都是一个有序链表，只扫包含两个节点，头节点和尾节点。

3. 每一层的每一个每一个节点都含有指向同一层下一个节点和下一层同一个位置节点的指针。

4. 如果一个节点在某一层出现，那么该以下的所有链表同一个位置都会出现该节点。

具体实现的结构图如下所示：

跳跃表的结构中包含指向头节点和尾节点的指针head和tail，能够快速进行定位。当在跳跃表中从尾向前遍历时，层数用 level 表示，跳跃表长度用 len 表示，同时也会使用后退指针 BW。

BW下面还有两个值分别表示分值（score）和成员对象（各个节点保存的成员对象）。

跳跃表的实现中，除了最底层的一层保存的是原始链表的完整数据，上层的节点数会越来越少，并且跨度会越来越大。

跳跃表的上面层就相当于索引层，都是为了找到最后的数据而服务的，数据量越大，条表所体现的查询的效率就越高，和平衡树的查询效率相差无几。

应用场景

因为ZSet是有序的集合，因此ZSet在实现排序类型的业务是比较常见的，比如在首页推荐10个最热门的帖子，也就是阅读量由高到低，排行榜的实现等业务。

下面就选用获取排行榜前前10名的选手作为案例实现，实现的代码如下所示：

@Autowired  private RedisTemplate redisTemplate;  /**  * 获取前10排名  * @return  */  public static List<levelvo> getZset(String key, long baseNum, LevelService levelService){  ZSetOperations<serializable> operations = redisTemplate.opsForZSet();  // 根据score分数值获取前10名的数据  Set<zsetoperations.typedtuple>> set = operations.reverseRangeWithScores(key,0,9);  List<levelvo> list= new ArrayList<levelvo>();  int i=1;  for (ZSetOperations.TypedTuple<object> o:set){  int uid = (int) o.getValue();  LevelCache levelCache = levelService.getLevelCache(uid);  LevelVO levelVO = levelCache.getLevelVO();  long score = (o.getScore().longValue() - baseNum + levelVO .getCtime())/CommonUtil.multiplier;  levelVO .setScore(score);  levelVO .setRank(i);  list.add( levelVO );  i++;  }  return list;  }</object></levelvo></levelvo></zsetoperations.typedtuple></serializable></levelvo>

以上的代码实现大致逻辑就是根据score分数值获取前10名的数据，然后封装成lawyerVO对象的列表进行返回。

以上是redis的底層原理是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！