Una dintre marile provocări pentru mine ca dezvoltator de software este citirea codului altor persoane. Pentru această postare, am citit o bucată interesantă de cod C pe care nu o știam înainte și sunt pe cale să ți-o prezint. Codul despre care voi vorbi face parte din Redis baza de date și poate fi găsit aici.

Redis este o bază de date cheie-valoare. Fiecare intrare din baza de date este o mapare de la o cheie la o valoare. Valorile pot avea mai multe tipuri. Există numere întregi, liste, tabele hash și multe altele. În culise, baza de date în sine este, de asemenea, un tabel hash. În această postare, vom explora comanda SCAN în Redis.

Cum functioneaza functia Redis Hash Table Scan
De © Utilizator: Colin / Wikimedia Commons, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=30343877

Redis SCAN

SCAN este o comandă de iterație bazată pe cursor, care permite unui client să treacă peste toate elementele dintr-un tabel. Acest scaner bazat pe cursor acceptă un număr întreg cursor la fiecare apel și revine un lot de articole si valoarea cursorului pentru a fi utilizat în următorul apel către SCAN. Valoarea inițială a cursorului este 0, iar când SCAN returnează 0 ca următoare valoare a cursorului, înseamnă că scanarea este efectuată și toate elementele au fost văzute de client.

Comanda SCAN are câteva proprietăți interesante:

  1. Acesta garantează că toate articolele prezente în tabel vor fi returnate cel puțin o dată.
  2. Este Fara stare. Tabelul nu salvează date despre scanerele sale active. Aceasta înseamnă, de asemenea, că scanările nu blochează baza de date.
  3. Este rezistent la redimensionarea tabelului. Pentru a menține timpul de acces O (1), tabelele hash susțin un anumit factor de încărcare. Factorul de încărcare măsoară cât de „plină” este masa la un moment dat. Când factorul de încărcare devine prea mare sau prea mic, tabelul este redimensionat. SCAN își va menține garanțiile chiar dacă este apelat în timp ce tabelul este redimensionat.

Implementare

SCAN este implementat în dict.c, în funcție dictScan(). Aceasta este semnătura funcției și menaj suplimentar:

unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       dictScanBucketFunction* bucketfn,
                       void *privdata)
{
    dictht *t0, *t1;
    const dictEntry *de, *next;
    unsigned long m0, m1;

    if (dictSize(d) == 0) return 0;
    // ...

Lucruri demne de remarcat:

  • Funcția acceptă 5 parametri: dict *d, dicționarul de scanat, unsigned long v, cursorul și alți 3 parametri în care vom intra mai târziu.
  • Funcția returnează valoarea cursorului care va fi utilizată în următorul apel la această funcție. Dacă funcția returnează 0, înseamnă că scanarea este terminată.
  • if (dictSize(d) == 0) return 0;. Când dicționarul este gol, funcția returnează 0 pentru a indica faptul că scanarea a fost efectuată.

1. Scanare normală

Următorul cod scanează o grămadă de elemente:

if (!dictIsRehashing(d)) {
    t0 = &(d->ht[0]);
    m0 = t0->sizemask;

    /* Emit entries at cursor */
    if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
    de = t0->table[v & m0];
    while (de) {
        next = de->next;
        fn(privdata, de);
        de = next;
    }
    
    /* Set unmasked bits so incrementing the reversed cursor
     * operates on the masked bits */
    v |= ~m0;

    /* Increment the reverse cursor */
    v = rev(v);
    v++;
    v = rev(v);
    
} else {
    // ...

Să trecem peste ea pas cu pas. Să începem cu prima linie de mai jos:

if (!dictIsRehashing(d)) {
    t0 = &(d->ht[0]);
    m0 = t0->sizemask;

Rehashing este procesul de împrăștiere uniformă a elementelor pe o masă după ce a fost redimensionat. Tabelul de hash dict.c reface incremental, ceea ce înseamnă că nu reface întreaga masă simultan, ci încetul cu încetul. Fiecare operație efectuată pe masă, cum ar fi adăugarea, ștergerea, găsirea, efectuează, de asemenea, un pas de rehașurare. Acest lucru permite menținerea mesei disponibile pentru operațiuni în timpul rehahing. Datorită modului în care rehashing este implementat, funcția funcționează diferit în timpul rehahing. Vom începe prin a ne uita la ceea ce se întâmplă atunci când masa nu se reface.

Un indicator către tabelul hash este salvat în variabila locală t0, si este masca de marime este salvat în m0. Masca de dimensiuni: tabelele hash dict.c sunt întotdeauna 2^n in marime. Pentru o dimensiune de masă dată, masca de dimensiuni este 2^n-1, care este un număr binar cu n biți mai puțin semnificativi setați la 1. De exemplu, pentru n=4; 2^n-1 = 00001111. Pentru o cheie dată, locația sa în tabelul hash va fi ultima n bucăți de hash a cheii. Vom vedea acest lucru în acțiune într-un pic.

Utilizează tabelul de hash dict.c adresare deschisă. Fiecare intrare din tabel este o listă legată de elemente cu valoare hash conflictuală. Aceasta se numește a găleată. În următoarea parte, a găleată de elemente este scanat:

/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
    next = de->next;
    fn(privdata, de);
    de = next;
}

Rețineți utilizarea fișierului masca de marime: t0->table[v & m0]. v ar putea fi în afara intervalului indexabil al tablouluie. v & m0 folosește masca de dimensiuni pentru a păstra doar lascifre tn ofv și produce un index valid în tabel.

S-ar putea să fi ghicit până acum ce bucketfn este pentru. bucketfn este furnizat de apelant și se aplică fiecărei găleți de elemente. De asemenea, este trecut privdata, care sunt date arbitrare transmise către dictScan() de către apelant. În mod similar, fn se aplică la toate intrările din cupă unul câte unul. Rețineți că o găleată poate fi goală, caz în care valoarea sa este NULL.

OK, așa că am repetat peste o găleată de elemente. Ce urmeaza? Vom returna valoarea cursorului pentru următorul apel către dictScan(). Acest lucru se face prin incrementarea cursorului curent v, dar cu o întorsătură! Cursorul este mai întâi inversat, apoi incrementat și apoi inversat din nou:

    /* Set unmasked bits so incrementing the reversed cursor
     * operates on the masked bits */
    v |= ~m0;
    /* Increment the reverse cursor */
    v = rev(v);
    v++;
    v = rev(v);

Primul, v |= ~m0 setează toți biții care nu sunt mascați în v la 1. Efectul este acela la inversare v și incrementând, acești biți vor fi efectiv ignorați. Atunci, v este inversat, incrementat și inversat din nou. Să vedem un exemplu:

Table size = 16 (n = 4, m0 = 16-1 = 00001111)
v = 00001000 (Current cursor)
v |= ~m0;    // v == 11111000  (~m0 = 11110000)
v = rev(v);  // v == 00011111
v++;         // v == 00100000
v = rev(v);  // v == 00000100

După această magie de biți, v este returnat.

De ce este inversat cursorul înainte de a fi incrementat? Tabelul ar putea crește între iterații. Acest lucru garantează că cursorul rămâne valabil. Când masa crește, se adaugă biți suplimentari la masca sa de dimensiuni din stânga. Prin incrementarea numărului inversat, putem extinde indicii tabelului mai mic în cel mai mare.

De exemplu: Să presupunem că dimensiunea vechiului tabel era de 16 (masca de dimensiune 00001111) și cursorul a fost 00001000. Când masa crește la 32 de elemente, masca sa de dimensiuni va fi 00011111. Toate elementele anterioare din 00001000 slotul va fi mapat la oricare 00001000sau 00011000 în noul tabel. Aceste cursoare sunt compatibile atât cu tabele mai mici, cât și cu cele mai mari!

2. Scanare în timpul repasării mesei

Ultima parte pe care trebuie să o înțelegem este modul în care funcționează scanarea în timp ce tabelul se reface. Reconsiderare incrementală este implementat în dict.c având două tabele active în același timp. Un al doilea tabel este creat atunci când tabelul hash este redimensionat. Elementele noi sunt adăugate la noul tabel. La fiecare pas de rehash, elementele din tabelul vechi sunt mutate în tabelul nou. Când vechea masă devine goală este eliminată.

Atunci când efectuați o scanare, atât tabelele vechi, cât și cele noi sunt scanate pentru elemente, începând de la mai mici masa. După scanarea elementelor din tabelul mai mic, fișierul elemente complementare de la masa mai mare sunt scanate. Astfel toate elementele acoperite de cursor v sunt scanate. Să vedem cum arată asta. Acesta este întregul fragment de cod, îl vom descompune mai jos:

    } else {  // dictIsRehashing(d)
        t0 = &d->ht[0];
        t1 = &d->ht[1];

        /* Make sure t0 is the smaller and t1 is the bigger table */
        if (t0->size > t1->size) {
            t0 = &d->ht[1];
            t1 = &d->ht[0];
        }

        m0 = t0->sizemask;
        m1 = t1->sizemask;

        /* Emit entries at cursor */
        if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
        de = t0->table[v & m0];
        while (de) {
            next = de->next;
            fn(privdata, de);
            de = next;
        }

        /* Iterate over indices in larger table that are the expansion
         * of the index pointed to by the cursor in the smaller table */
        do {
            /* Emit entries at cursor */
            if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
            de = t1->table[v & m1];
            while (de) {
                next = de->next;
                fn(privdata, de);
                de = next;
            }

            /* Increment the reverse cursor not covered by the smaller mask.*/
            v |= ~m1;
            v = rev(v);
            v++;
            v = rev(v);

            /* Continue while bits covered by mask difference is non-zero */
        } while (v & (m0 ^ m1));
    }

Pentru inceput, t0 și t1 sunt folosite pentru a stoca mesele mai mici și respectiv mai mari, cu m0 și m1 măștile de dimensiuni pentru fiecare. Apoi, tabelul mai mic este scanat, așa cum am văzut mai devreme.

Apoi, cursorul este folosit pentru indexarea în tabelul mai mare, folosind masca de dimensiuni mai mari m1: de = t1->table[v & m1]. În bucla interioară, cursorul este incrementat pentru a acoperi toate extinderile indexului tabelului mai mic.

De exemplu, dacă indicele cupei din tabelul mai mic a fost 0100, iar tabelul mai mare este de două ori mai mare, indicii acoperiți în această buclă vor fi 00100 și 10100. Starea do-while împiedică creșterea cursorului dincolo de intervalul acoperit de cupa mesei mici: while (v & (m0 ^ m1));. Vă voi lăsa să înțelegeți acest ultim pic 🙂

Asta e! Am acoperit întreaga funcție de scanare a tabelului hash. Singura piesă care lipsește este implementarea rev(v), care este o funcție generală pentru a inversa biții dintr-un număr. Implementarea utilizată în dict.c este deosebit de interesantă deoarece atinge un timp de rulare O (log n). S-ar putea să îl acoper într-o postare viitoare.

Mulțumesc pentru lectură! Multe mulțumiri lui Dvir Volk pentru inspirație și sprijin! Mulțumesc lui Jason Li pentru feedback-ul său care m-a ajutat să corectez o eroare în postare.