Quel est le principe sous-jacent de Redis

Objet principal Redis

Dans Redis, il existe un "objet principal"appelé redisObject, qui est utilisé pour représenter toutes les clés et valeurs. La structure redisObject est utilisée pour représenter cinq types de données : String, Hash, List, Set, et tapez ZSet.

Le code source de redisObject est en redis.h, écrit en langage C Si vous êtes intéressé, vous pouvez le vérifier par vous-même. Concernant redisObject, j'ai fait un dessin ici, qui montre que la structure de redisObject est la suivante. suit :

In redisObject In "le type indique à quel type de données il appartient, et l'encodage indique comment les données sont stockées" , qui est la structure de données sous-jacente du type de données implémenté. Par conséquent, cet article présente spécifiquement la partie correspondante du codage.

Alors, que signifient les types de stockage dans l'encodage ? La signification représentée par le type de données spécifique est celle indiquée dans la figure ci-dessous :

Vous pourriez encore vous sentir confus après avoir lu cette image. Pas de panique, nous allons donner une introduction détaillée aux cinq structures de données. Cette image vous permet uniquement de trouver les types de stockage correspondant à chaque structure de données, et d'avoir probablement une impression dans votre esprit.

Pour donner un exemple simple, vous définissez une clé de chaîne 234 dans Redis, puis vérifiez le type de stockage de cette chaîne et vous verrez qu'il s'agit d'un type int qui utilise le type de stockage embstr. comme suit Montré :

String type

String est le type de données le plus basique de Redis. L'introduction ci-dessus mentionne également que Redis est développé en langage C. Cependant, il existe des différences évidentes entre les types de chaînes dans Redis et les types de chaînes en langage C.

Il existe trois façons de stocker une structure de données de type String : int, raw et embstr. Alors, quelles sont les différences entre ces trois méthodes de stockage ?

int

Redis stipule que si la "valeur entière" stockée, telle que l'ensemble numéro 123, sera stockée en utilisant la méthode de stockage int, qui sera stockée dans le "attribut ptr" de redisObject Enregistrez cette valeur .

SDS

Si la "chaîne stockée est une valeur de chaîne et que la longueur est supérieure à 32 octets", elle sera stockée en utilisant SDS (chaîne dynamique simple) et l'encodage est défini sur brut si ; "La longueur de la chaîne est inférieure ou égale à 32 octets" changera l'encodage en embstr pour enregistrer la chaîne.

SDS s'appelle "Simple Dynamic String". Il y a trois attributs définis dans SDS dans le code source Redis : int len, int free et char buf[].

len enregistre la longueur de la chaîne, free représente le nombre d'octets inutilisés dans le tableau buf et le tableau buf stocke chaque élément de caractère de la chaîne.

Ainsi, lorsque vous stockez une chaîne Hello dans Redsi, selon la description du code source Redis, vous pouvez dessiner le diagramme de structure redisObject sous forme de SDS comme indiqué ci-dessous :

Comparaison entre les chaînes du langage SDS et C

Redis a certainement ses propres avantages dans l'utilisation de SDS comme type de stockage de chaînes. Par rapport aux chaînes en langage C, SDS a sa propre conception et optimisation pour les chaînes en langage C. Les avantages spécifiques sont les suivants :

(1) La chaîne en langage C n'enregistre pas sa propre longueur, donc "Chaque fois que la longueur de la chaîne est obtenue, elle sera parcourue et la complexité temporelle est O(n)", lors de l'obtention de la chaîne dans Redis. Il suffit de lire la valeur de len, et la complexité temporelle devient O(1).

(2) Lors de la concaténation de deux chaînes en "langage c", si un espace mémoire d'une longueur suffisante n'est pas alloué, "un débordement de tampon se produira" et "SDS" utilisera d'abord l'attribut len ​​Déterminez si l'espace répond aux exigences. Si l'espace n'est pas suffisant, l'espace correspondant sera agrandi, donc "il n'y aura pas de débordement de tampon".

(3) SDS propose également deux stratégies : "Pré-allocation d'espace" et "Libération d'espace paresseuse". Lors de l'allocation d'espace pour une chaîne, allouez plus d'espace que l'espace réel, ce qui peut "réduire le nombre de réallocations de mémoire causées par l'exécution continue de la croissance de chaîne" .

Lorsque la chaîne est raccourcie, SDS ne récupérera pas immédiatement l'espace inutilisé, mais enregistrera l'espace inutilisé via l'attribut free et le libérera lorsqu'il sera utilisé ultérieurement.

Le principe spécifique de pré-allocation d'espace est le suivant : "Lorsque la longueur len de la chaîne modifiée est inférieure à 1 Mo, un espace de même longueur que len sera pré-alloué, c'est-à-dire len=free ; si len est supérieur supérieur à 1 Mo, l'espace alloué gratuitement sera de 1 Mo".

(4) SDS est binaire-safe En plus de stocker des chaînes, il peut également stocker des fichiers binaires (tels que des données binaires d'images, d'audios, de vidéos, etc.) tandis que les chaînes en langage C se terminent par une chaîne vide. les images contiennent des terminateurs et ne sont donc pas sécurisées en termes binaires.

Afin de faciliter la compréhension, nous avons créé un tableau comparant les chaînes en langage C et SDS, comme indiqué ci-dessous :

Chaîne en langage C SDS La complexité temporelle pour obtenir la longueur est O(n) Obtenez le length La complexité temporelle est O(1).Ce n'est pas sûr pour les binaires.Il ne peut sauvegarder que des chaînes et peut également sauvegarder des données binaires. Augmenter la chaîne n fois entraînera inévitablement n fois l'allocation de mémoire. augmentez le nombre d'allocations de mémoire de la chaîne.

Application de type String

Cela dit, je pense que beaucoup de gens peuvent dire qu'ils maîtrisent déjà le type String de Redis, mais pour une compétence purement théorique, le La théorie doit encore être appliquée dans la pratique. Comme mentionné ci-dessus, String peut être utilisé pour stocker des images. Prenons maintenant le stockage d'images comme une implémentation de cas.

(1) Tout d'abord, vous devez encoder l'image téléchargée. Voici une classe d'outils pour traiter l'image en codage Base64. Le code d'implémentation spécifique est le suivant :

/**  * 将图片内容处理成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 );

Copiez le code

(2) La deuxième étape. est Stocker le format de chaîne de l'image traitée dans Redis. Le code implémenté est le suivant :  

/**  * 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中取出即可。  }

Cela réalise le stockage binaire de l'image. Bien entendu, l'application de la structure de données de type String inclut également le comptage conventionnel : "Statistiques Nombre de. Weibo, statistiques du nombre de fans", etc.

Type de hachage

Il existe deux façons d'implémenter des objets Hash : ziplist et hashtable La méthode de stockage de la table de hachage est de type String, et la valeur est également stockée sous forme de valeur clé.

La couche inférieure du type de dictionnaire est implémentée par hashtable. Comprendre le principe de mise en œuvre sous-jacent du dictionnaire signifie comprendre le principe de mise en œuvre de la table de hachage. Le principe de mise en œuvre de la table de hachage peut être comparé au principe sous-jacent de HashMap.

Dictionnaire

Les deux calculeront l'indice du tableau via la clé lorsqu'ils seront ajoutés. La différence est que la méthode de calcul est différente, alors que dans la table de hachage, après avoir calculé la valeur de hachage, elle doit également le faire. utilisez sizemask. Les attributs et les hachages obtiennent à nouveau les indices du tableau.

Nous savons que le plus gros problème avec les tables de hachage sont les conflits de hachage. Afin de résoudre les conflits de hachage, si différentes clés de la table de hachage obtiennent le même index par calcul, une liste chaînée unidirectionnelle ("Méthode d'adresse de chaîne") sera formé, comme le montre la figure ci-dessous. Représentation :

rehash

Dans l'implémentation sous-jacente du dictionnaire, l'objet valeur est stocké dans chaque objet dictEntry lorsque les paires clé-valeur sont stockées dans la table de hachage. continue à augmenter ou à diminuer, la table de hachage doit être modifiée. Une expansion ou une contraction.

Tout comme HashMap, l'opération de répétition sera également effectuée ici, c'est-à-dire l'arrangement de répétition. Comme le montre la figure ci-dessus, ht[0] et ht[1] sont deux objets ci-dessous, nous nous concentrerons sur le rôle de leurs attributs.

Il y a quatre attributs dans la définition de la structure de la table de hachage : dictEntry **table, taille longue non signée, taille longue non signéemasque, longue non signée utilisée, qui signifient respectivement "tableau de table de hachage, taille de table de hachage, utilisé pour le calcul La valeur d'index est toujours égal à la taille-1 et au nombre de nœuds dans la table de hachage.".

ht[0] est utilisé pour stocker initialement des données Lorsqu'une expansion ou une contraction est requise, la taille de ht[0] détermine la taille de ht[1], et toutes les paires clé-valeur dans ht[0] ce seront. ressassé dans ht[1].

Opération d'expansion : la taille étendue de ht[1] est la première puissance entière de 2 qui est le double de la valeur actuelle de ht[0].used ; Opération de réduction : la première puissance entière de ht[0].used est supérieure. supérieur ou égal à une puissance entière de 2.

Lorsque toutes les paires clé-valeur sur ht[0] sont rehachées vers ht[1], toutes les valeurs d'indice du tableau seront recalculées lorsque la migration des données est terminée, ht[0] sera publié, puis ht [. 1] est remplacé par ht[0] et ht[1] est nouvellement créé pour préparer la prochaine expansion et contraction.

Rehachage progressif

Si la quantité de données est très importante pendant le processus de rehachage, Redis ne réussira pas à rehacher toutes les données en même temps, ce qui entraînera l'arrêt du service externe de Redis. Afin de gérer cette situation, Redis adopte en interne . « Répétition progressive » « .

Redis divise toutes les opérations de rehash en plusieurs étapes jusqu'à ce que toutes les opérations de rehash soient terminées. L'implémentation spécifique est liée à l'attribut rehashindex dans l'objet, "Si rehashindex est exprimé comme -1, cela signifie qu'il n'y a pas d'opération de rehash".

Lorsque l'opération de rehachage démarre, la valeur sera modifiée à 0. Au cours du processus de rehachage progressif"La mise à jour, la suppression et la requête seront effectuées à la fois dans ht[0] et ht[1]", par exemple, mettez d'abord à jour une valeur. Mettez à jour ht[0] puis ht[1].

La nouvelle opération est directement ajoutée à la table ht[1], et ht[0] n'ajoutera aucune donnée. Cela garantit que "ht[0] ne fera que diminuer mais pas augmenter, jusqu'à ce qu'elle change au dernier moment. . dans une table vide", et l'opération de répétition est terminée.

Ce qui précède est le principe d'implémentation de la table de hachage sous-jacente du dictionnaire. Après avoir parlé du principe d'implémentation de la table de hachage, jetons un coup d'œil aux deux méthodes de stockage de la structure des données de hachage"ziplist (liste compressée)"

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>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="https://img.php.cn/upload/article/000/887/227/168511087742882.jpg" alt="Quel est le principe sous-jacent de 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>应用场景</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对象的列表进行返回。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!