Analyse du code source et de la conception de redis - - 7. Liste rapide

Redis Liste rapide

1. Introduction

Nous avons déjà décrit la structure de la liste liée et la structure de la liste compressée,Ce sont les implémentations sous - jacentes des touches de liste,Mais l'espace supplémentaire de la liste est un peu élevé,Parce queprevEtnextLe pointeur prendra une partie de l'espace（64Occupation du système bit8 + 8 = 16Octets）.Et chaque noeud de la liste est attribué individuellement à la mémoire,Peut aggraver la fragmentation de la mémoire.

Donc, dansredis-3.2Début de la version,RedisUtiliserquicklistEn tant qu'implémentation sous - jacente de la clé de liste.

2. quicklistRéalisation

quicklistEn fait, oui.zipListEtlinkedListUn mélange de,Il metzipListMettez - le surlinkedListDans chaque noeud, Réaliser un stockage compact .

2.1 quicklistStructure de l'en - tête

typedef struct quicklist {
    
    // Pointe vers la tête.(À gauche.)quicklistPointeur de noeud
    quicklistNode *head;

    // Pointe vers la queue(À droite)quicklistPointeur de noeud
    quicklistNode *tail;

    // ziplistCompteur de noeuds
    unsigned long count;

    // quicklistCompteur de noeuds
    unsigned int len;

    // EnregistrerziplistTaille,Configuration du profil,Pourcentage16bits
    int fill : 16;

    //  Degré de compression du noeud ,Configuration du profil,Pourcentage16bits,0Indique qu'il n'y a pas de compression
    unsigned int compress : 16;
} quicklist;

Parmi euxfillEtcompress Les propriétés sont configurables ,Inredis.confDans le document.

• fill Configuration correspondant à la propriété ：list-max-ziplist-size -2
  • Quand le nombre est négatif , Signifie ce qui suit ：
    • -1Représente chaquequicklistNodeNodeziplist La taille des octets ne peut pas dépasser 4kb.
    • -2Représente chaquequicklistNodeNodeziplist La taille des octets ne peut pas dépasser 8kb（Par défaut）.
    • -3Représente chaquequicklistNodeNodeziplist La taille des octets ne peut pas dépasser 16kb.
    • -4Représente chaquequicklistNodeNodeziplist La taille des octets ne peut pas dépasser 32kb.
    • -5Représente chaquequicklistNodeNodeziplist La taille des octets ne peut pas dépasser 64kb.
  • Quand le nombre est positif , Signifie ce qui suit ：
    • Représentationziplist La structure peut contenir entryNombre maximum de,Max.2 ^ 15.
  • compress Configuration correspondant à la propriété ：list-compress-depth 0
  • 0Indique qu'il n'y a pas de compression（Par défaut）.
  • 1Représentationquicklist Les deux extrémités de la liste ont 1Noeuds non compressés,Compression des noeuds au milieu.
  • 2Représentationquicklist Les deux extrémités de la liste ont 2Noeuds non compressés,Compression des noeuds au milieu.
  • 3Représentationquicklist Les deux extrémités de la liste ont 3Noeuds non compressés,Compression des noeuds au milieu.
  • Max.2 ^ 16.

2.2 quicklistStructure des noeuds

typedef struct quicklistNode {
    
    struct quicklistNode *prev;     //Pointeur de noeud avant
    struct quicklistNode *next;     //Pointeur de noeud suivant

    //  Pointez vers un ziplistStructure, Définir le paramètre de données compressées pour pointer vers quicklistLZFStructure
    unsigned char *zl;

    // Liste compresséeziplistLongueur totale
    unsigned int sz;

    // ziplistNombre de noeuds dans,Pourcentage16 bitsLongueur
    unsigned int count : 16;

    //  Indique si LZFAlgorithme de COMPRESSION COMPRESSION COMPRESSIONquicklistNoeud,1 Indique que ,2Indique l'adoption,Pourcentage2 bitsLongueur
    unsigned int encoding : 2;

    // Représente unquicklistNodeSi le noeud adopteziplistLa structure stocke les données,2Indique l'adoption,1 Indique que ,Par défaut2,Pourcentage2bitsLongueur
    unsigned int container : 2;

    // Marquagequicklist Compressé ou non ,Pourcentage1bitLongueur
    // SirecompressPour1,Attendez d'être comprimé à nouveau
    unsigned int recompress : 1;

    // À utiliser lors des essais
    unsigned int attempted_compress : 1;

    // Extension supplémentaire,Pourcentage10bitsLongueur
    unsigned int extra : 10;
} quicklistNode;

2.3 Compriméziplist

typedef struct quicklistLZF {
    
    // Indique queLZFAlgorithme compresséziplistTaille
    unsigned int sz;

    //  Enregistrer la compression ziplistTableau de,Tableau flexible
    char compressed[];
} quicklistLZF;

2.4 quicklistEntry

// GestionquicklistMoyennequicklistNodeDans les noeudsziplistStructure de l'information
typedef struct quicklistEntry {
    
	// Pointer versquicklistPointeur vers
    const quicklist *quicklist;
    // Pointer versquicklistNodePointeur de noeud
    quicklistNode *node;
    // Pointer vers le courantziplistPointeur de structure 
    unsigned char *zi;
     // Pointer vers le courantziplistLa chaîne de la structurevlaueMembres 
    unsigned char *value;
    // Pointer vers le courantziplist Entier de la structure valueMembres 
    long long longval;            
    // Enregistrer le courantziplist Taille de la structure en octets 
    unsigned int sz;
    //  Enregistrer la relative ziplistOffset of
    int offset;
} quicklistEntry;

3. Opérations courantes

3.1 Insérer

quicklist Vous pouvez choisir d'insérer à la tête ou à la queue ,CorrespondantAPI- Oui.quicklistPushHeadEtquicklistPushTail：

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    
	//  Adresse du noeud d'en - tête de sauvegarde 
    quicklistNode *orig_head = quicklist->head;

    // SiziplistPeut être inséréentryNoeud
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
    
        quicklist->head->zl =
        	// NoeudpushÀ la tête
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        // Mise à jourquicklistNodeEnregistrementziplistTaillesz
        quicklistNodeUpdateSz(quicklist->head);
    } else {
    
    	//  Si vous ne pouvez pas insérer entryNode toziplist
    	// Créer un nouveauquicklistNodeNoeud
        quicklistNode *node = quicklistCreateNode();

        //Oui.entryNoeudpush Au nouveau quicklistNodeDans les noeuds
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

		// Mise à jourziplistTaillesz
        quicklistNodeUpdateSz(node);
        //  Insérer le noeud nouvellement créé avant le noeud d'en - tête 
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    // Mise à jourquicklistNodeCompteur
    quicklist->count++;
    // Mise à jourentryCompteur
    quicklist->head->count++;
    //  Si vous changez le pointeur du noeud de tête, retournez 1,Sinon, retournez à0
    return (orig_head != quicklist->head);
}

int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
    
    quicklistNode *orig_tail = quicklist->tail;

    // SiziplistPeut être inséréentryNoeud
    if (likely(
            _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
    
        quicklist->tail->zl =
       		// NoeudpushÀ la queue
            ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);
        // Mise à jourquicklistNodeEnregistrementziplistTaillesz
        quicklistNodeUpdateSz(quicklist->tail);
    } else {
    
    	// Créer un nouveauquicklistNodeNoeud
        quicklistNode *node = quicklistCreateNode();

        // Oui.entryNoeudpush Au nouveau quicklistNodeDans les noeuds
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);

		// Mise à jourziplistTaillesz
        quicklistNodeUpdateSz(node);
        //  Après avoir inséré le noeud nouvellement créé dans le noeud de queue 
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
    }
    // Mise à jourquicklistNodeCompteur
    quicklist->count++;
    // Mise à jourentryCompteur
    quicklist->tail->count++;
    //  Si vous changez le pointeur du noeud de queue, retournez 1,Sinon, retournez à0
    return (orig_tail != quicklist->tail);
}

Références：

《RedisConception et mise en œuvre》

RedisAnalyse du code source et commentaires