Vue d'ensemble

Redis repose sur un petit ensemble de structures élémentaires implémentées en C. Les cinq types exposés au client (chaînes, listes, ensembles, etc.) sont matérialisés par une ou plusieurs de ces structures : chaîne dynamique simple (SDS), liste chaînée, dictionnaire, skip list, ensemble d'entiers et liste compressée. L'encodage réel d'une clé peut être consulté avec la commande OBJECT ENCODING <clé>.

Chaîne dynamique simple (SDS)

Redis ne se sert pas des chaînes C terminées par un octet nul. Il utilise une structure de chaîne dont la longueur et l'espace réservé sont stockés explicitement.

typedef struct sds_string {
    size_t used;      /* nombre d'octets occupés */
    size_t reserved;  /* octets libres après used */
    char   payload[]; /* données terminées par '\0' */
} sds_string;

Ce modèle offre plusieurs avantages :

• Longueur en O(1) : used donne directement la taille logique, sans parcours.
• Protection contre le débordement : toute modification redimensionne d'abord le tampon si nécessaire.
• Réduction des réallocations : Redis alloue à l'avance un peu d'espace supplémentaire lors d'une extension et reporte la libération lors d'une réduction.
• Sécurité binaire : la fin de la chaîne est repérée par used, non par un octet nul, ce qui permet de stocker des données brutes.
• Compatibilité partielle : le champ payload reste terminé par '\0', donc certains appels de la libc restent utilisables.

Liste chaînée

Redis fournit sa propre liste doublement chaînée. Chaque nœud est indépendant et la structure de liste maintient des pointeurs vers les extrémités ainsi qu'un compteur.

typedef struct list_node {
    struct list_node *prev;
    struct list_node *next;
    void             *value;
} list_node;

typedef struct linked_list {
    list_node        *first;
    list_node        *last;
    unsigned long    count;
    void *(*copy)(void *ptr);
    void  (*release)(void *ptr);
    int   (*compare)(void *a, void *b);
} linked_list;

Cette liste est bidirectionnellle, non circulaire et polymorphe : elle accepte n'importe quel type de valeur grâce aux fonctions fournies par l'utilisateur de la structure.

Dictionnaire (table de hachage)

Le dictionnaire est au cœur de Redis, notamment pour représenter l'espace de clés. Il s'agit d'une table de hachage avec chaînage pour la résolution des collisions.

typedef struct hash_entry {
    void *key;
    union {
        void     *ptr;
        uint64_t u64;
        int64_t  s64;
    } value;
    struct hash_entry *next;
} hash_entry;

typedef struct hash_table {
    hash_entry   **slots;
    unsigned long capacity;
    unsigned long mask;
    unsigned long count;
} hash_table;

La structure de dictionnaire maintient deux tables, l'une servant lors du rehashing.

typedef struct dict {
    hash_table ht[2];
    long       rehash_index; /* -1 si aucun rehash actif */
} dict;

Le calcul d'index s'effectue par un ET avec le masque : index = hash & mask. Les collisions sont gérées par chaînage en tête de liste. Quand le facteur de charge devient trop élevé, Redis procède à un rehash : il alloue une nouvelle table, y réinsère toutes les entrées, puis échange les tables.

Pour éviter un pic de latence, le rehash se fait de manière progressive. À chaque opération de lecture ou d'écriture, une petite portion des entrées est migrée. Durant cette phase, les recherches portent d'abord sur la table source, puis sur la destination, tandis que les insertions se font uniquement dans la nouvelle table.

Skip list

La skip list est une structure probabiliste permettant des recherches, insertions et suppressions efficaces. Elle sert principalement pour les ensembles et plages ordonnés.

typedef struct skiplist_node {
    struct level {
        struct skiplist_node *forward;
        unsigned int          span;
    } levels[];
    struct skiplist_node *backward;
    double                score;
    robj                 *member;
} skiplist_node;

typedef struct skiplist {
    skiplist_node *head;
    skiplist_node *tail;
    unsigned long  size;
    int            max_height;
} skiplist;

Chaque niveau contient un pointeur vers un nœud ultérieur et un écart indiquant le nombre de nœuds sautés. Tous les nœuds possèdent un pointeur arrière. Les nœuds sont triés par score, le champ member étant un pointeur vers un objet SDS.

Ensemble d'entiers

Lorsqu'un ensemble ne contient que quelques entiers, Redis peut utiliser un intset, une structure compacte et continue.

typedef struct intset {
    uint32_t encoding;
    uint32_t count;
    int8_t   payload[];
} intset;

L'encodage détermine si les éléments sont stockés en int16_t, int32_t ou int64_t. Si l'insertion d'un entier plus grand que le format courant est requise, Redis effectue une montée en gamme de tout le tableau. Cette opération augmente la flexibilité et économise la mémoire tant que seuls des petits entiers sont présents. Aucune descente d'encodage n'est effectuée.

Liste compressée (ziplist)

La ziplist est une structure séquentielle et contiguë conçue pour minimiser l'empreinte mémoire. Chaque entrée se compose de trois parties :

• prevlen : longueur de l'entrée précédente, encodée sur 1 ou 5 octets.
• encoding : type et taille de la charge utile.
• content : octets du littéral ou de l'entier.

La connaissance de prevlen permet de remonter d'un nœud à l'autre dans le bloc continu. Un changement de taille d'entrée peut provoquer une mise à jour en cascade si le champ prevlen d'un nœud doit passer de 1 à 5 octets et que cette augmentation dépasse elle-même la limite du nœud suivant. Ce scénario reste rare en pratique.

Récapitulatif des fondations

Les six structures précédentes forment la base sur laquelle reposent les types de haut niveau de Redis. L'utilisation finale d'une structure pour un type donné dépend du contenu et des commandes employées ; la commande OBJECT ENCODING permet de découvrir l'implantation sous-jacente d'une clé.