Colectii Voldemort: Itereaza un magazin cheie-valoare

Unul dintre numeroasele proiecte pe care LinkedIn le-a contribuit la open source este Project Voldemort, un sistem de stocare distribuit cheie-valoare. Am avut privilegiul de a contribui la proiect implementand o mica biblioteca de colectii deasupra Voldemort. Sursa este disponibila pe github-ul Voldemort.

O parte a provocarii in crearea de aplicatii deasupra unui magazin de valori-cheie este lipsa API-urilor de nivel superior pentru a interactiona cu datele in alte moduri decat ca harta. Aceasta a fost o provocare speciala cand am vrut sa convertim actualizarile noastre de retea (de exemplu, actualizarile de stare pe care le afisam pe pagina principala) dintr-o baza de date relationala in Voldemort. In exemplele care urmeaza, folosesc aceste actualizari de retea ca o ilustrare simplificata a modului in care facem acest lucru.

DB traditional

Intr-un sistem traditional de gestionare a bazelor de date relationale (RDBMS), aveti un tabel pentru utilizatori si un tabel pentru actualizari. O cheie straina reprezinta relatia unu-la-multi dintre utilizatori si actualizari. Obtinerea actualizarilor unui utilizator este la fel de simpla ca efectuarea unei interogari SQL precum „SELECT * FROM updates WHERE updates.user_id = users.user_id”. Problema cu un RDBMS traditional este ca scalarea devine mai dificila pe masura ce depasiti capacitatile unei singure masini.

O abordare tipica

O modalitate de a stoca date secventiale intr-un depozit cheie-valoare este prin crearea unui index secundar simplu pentru a stoca lista de elemente ID. In exemplul de mai jos, aveti un magazin numit index care pastreaza o harta de la un singur utilizator la o lista a actualizarilor sale. Un al doilea magazin, actualizari , pastreaza o harta de la update_id la datele reale continute in actualizare (de exemplu, „Alfred a distribuit aceasta postare interesanta de pe blog”).

Indice secundar simplu care stocheaza o lista de

indexuri de elemente : user_id => [update_id]

updates : update_id => update_data

Problema cu aceasta abordare este ca, daca un utilizator este foarte activ, lista ID-urilor de actualizare poate creste infinit pana la o dimensiune imposibil de gestionat. Lucrul cu o lista de aceasta dimensiune ar genera acces excesiv la disc si ar creste traficul de retea.

Folosirea unui index paginat

O modalitate alternativa de a face acest lucru este utilizarea unui index secundar paginat cu un fel de cheie bazata cronologic. In acest fel, limitam numarul de intrari continute in fiecare lista pe luna. In exemplul urmator, indexul acum stocheaza o combinatie intre user_id si luna. In acest fel, puteti face o interogare precum „ce actualizari a facut Bruce in luna mai?”

Index secundar paginat dupa

index lunar : user_id, month => [update_id]

actualizari : update_id => update_data

Aceasta cheie bazata cronologic este excelenta daca rata elementelor de intrare va ramane constanta in timp – va puteti configura cheile astfel incat indexul sa ramana o dimensiune usor de gestionat. In caz contrar, este greu sa configurati acest numar. Daca stocati prea putine elemente intr-o pagina, riscati sa solicitati prea multe operatii get () pentru a opera asupra elementelor. Daca exista prea multe elemente intr-o pagina, aveti acelasi risc de a creste accesul la disc si latenta retelei.

Colectia VStack

Pentru a rezolva aceste probleme, structurile de date VStack si VLinkedPagedList din biblioteca de colectii Voldemort contribu fac acest tip de acces la date mai natural si mai eficient.

VStack <K, E> implementeaza interfata Queue <E> si stocheaza elemente de tip E, identificate cu o cheie de tip K. Cheia reala din magazinul Voldemort este o inregistrare care contine atat valoarea lui K, cat si o numar intreg care identifica ID-ul nodului pentru nodul stivei. De exemplu, un teanc care reprezinta utilizatorul „Alfred” va avea noduri cu chei precum {“Alfred”, 0}, {“Alfred”, 1} si {“Alfred”, 2}. Valoarea din magazinul Voldemort este o inregistrare care contine valoarea reala din interiorul nodului, precum si numere intregi care identifica un pointer inainte si un pointer inapoi. Pointerii inainte si inapoi se refera la ID-ul nodului, asa cum s-a mentionat anterior in cheie.

In acest fel, putem folosi nodurile din depozitul de stive ca elemente ale unei liste dublu legate. Prima pagina incepe de la ID-ul „0”. Paginile anterioare si urmatoare sunt conectate prin ID-ul paginii in fiecare nod de lista. Un Iterator este furnizat pentru a permite accesul secvential pe toate nodurile. Pentru a-l readuce in exemplul actualizarilor de retea, K reprezinta ID-ul utilizatorului, iar E reprezinta ID-ul de actualizare. Folosirea acestuia este la fel de simpla ca si repetarea oricarei colectii Java standard.

VStack care sta la baza Voldemort stocheaza

stiva : user_id, page_id => update_id, next_page, previous_page

updates : update_id => update_data // iterand peste un VStack VStack <Integer, String> myUpdates = new VStack <Integer, String> (1337 / * exemplu userid * /, storeClient / * Voldemort StoreClient * /); pentru (String update: myUpdates) {System.out.println (update); }

Acest lucru ne atinge obiectivul de acces secvential la date, dar are inca doua dezavantaje. In primul rand, deoarece un element este stocat intr-un nod de lista separat, trebuie sa executam un apel Voldemort get () de fiecare data cand dorim sa vedem elementul urmator sau anterior. Acest lucru nu este practic pentru listele cu mai multe elemente ca dimensiune, in functie de cerintele de latenta ale aplicatiei. In al doilea rand, este foarte ineficient sa trebuiasca sa incepi de la cap sau coada pentru a ajunge la un element aflat in mijlocul listei.

VLinkedPagedLista pentru salvare

Pentru a aborda aceste probleme, am facut mai multe lucruri. In primul rand, in loc sa stocam un singur element in fiecare nod, stocam o lista de elemente intr-un singur nod VStack. Apoi, am construit un index secundar, numit page_index , deasupra acestuia. Acest index secundar asociaza un ID de nod cu cea mai mare valoare stocata in nod. Folosind aceste informatii, putem sari in mijlocul stivei prin cautare binara, in loc sa pornim de la cap sau coada. De asemenea, stocand o lista de elemente ordonate intr-un nod in loc de o singura actualizare, rareori trebuie sa lansam o alta operatiune get () pentru a recupera nodul urmator sau anterior.

Structura terminata este o lista VLinkedPagedList <I, LK extinde comparabil <LK>>. In contextul actualizarilor de retea, eu reprezinta ID-ul utilizatorului, iar LK reprezinta ID-ul de actualizare. Motivul pentru LK (inseamna „cheie liniara”) este ca trebuie sa fie comparabil pentru a oferi capacitatea de cautare. Acest lucru este util si pentru paginarea prin actualizarile unui utilizator.

VLinkedPagedList care sta la baza Voldemort stocheaza

page_index : user_id => [{page_id, last_update_id}]

stack : user_id, page_id => [update_id], next_page, previous_page

updates : update_id => update_data

Prin utilizarea acestor noi structuri de date, suntem capabili sa stocam orice set cronologic de elemente, indiferent daca provin din fluxul de actualizare al unui singur utilizator sau din postari intr-un grup de volum mare LinkedIn. In prezent, aceste structuri necesita cvorum strict in cazul in care sunt necesare + scrieri + obligatorii-citiri> factor de replicare. Lucrarile viitoare in acest sens pot fi realizate pentru a implementa un rezolvator de consistenta pentru a rezolva discrepantele la momentul citirii. De asemenea, mai multe structuri de date pot fi adaugate la aceasta biblioteca pentru a extinde in continuare utilitatea Voldemort in general.