Slim - în mod surprinzător, tipuri de date eficiente în spațiu în Golang

eficient

Slim este o colecție de tipuri de date surprinzător de eficiente din punct de vedere spațial, cu API-uri de serializare corespunzătoare pentru a le păstra pe disc sau pentru transport.

Pe măsură ce datele de pe internet continuă să crească exponențial, decalajul de capacitate dintre memorie și disc devine mai mare.

De cele mai multe ori, datele în sine nu trebuie încărcate în memoria principală scumpă. Doar informațiile mult mai importante, WHERE-A-DATA-IS, merită un loc în memoria principală.

Aceasta este ceea ce face Slim, păstrează cât mai puține informații în memoria principală, ca un indice minimizat de cantitate imensă de date externe.

SlimIndex: este o structură de index comună, construită deasupra SlimTrie .

SlimTrie este structura subiacentă a datelor de index, dezvoltată din trie.

Caracteristici:

Minimizat: 11 biți pe cheie(mult mai puțin decât un pointer pe 64 de biți !).

Grajd: consumul de memorie este stabil în diferite scenarii. Cel mai rău caz converge la consumul mediu strâns. A se vedea etalonul.

Chei lungi: Poti avea FOARTE taste lungi (16K octeți), fără risipă de memorie (și bani). Nu vă pierdeți viața scriind o altă compresie de prefix:). (aws-s3 limitează lungimea cheii la 1024 octeți). Consumul de memorie se referă numai la numărul de taste, nu la lungimea cheii.

Ordonat: la fel ca btree, cheile sunt stocate. Scanarea intervalului va fi gata în 0.6.0 .

Rapid:

100 ns pe Get (). Complexitatea timpului pentru un get este O (log (n) + k); n: număr de chei; k: lungimea cheii .

Gata pentru transport: un singur proto.Marshal () este tot ce este necesar pentru a serializa, transporta sau persista pe disc etc.

Design cuplat slab: logica indexului și stocarea datelor sunt complet separate. Bucată de tort folosind SlimTrie pentru a indexa date imense.

Biți/cheie: memorie sau spațiu pe disc în biți o cheie consumată în medie. Nu se schimbă când lungimea cheii (k) devine mai mare!

Timp (în nano secunde) petrecut pe un Get () cu golang-map, SlimTrie, array și btree de google.

  • De 3,3 ori mai rapid decât arborele.
  • De 2,3 ori mai rapid decât căutarea binară.

Timp (în nano secunde) petrecut pe un Get () cu număr de chei diferite (n) și lungimea cheii (k):

Rată fals pozitivă

Filtrul Bloom necesită aproximativ 9 biți/cheie pentru a arhiva mai puțin de 1% FPR.

API-urile SlimTrie sunt stabile și au fost utilizate într-un mediu de producție.

Între timp ne concentrăm pe optimizarea utilizării memoriei și a performanței interogării.

Structura internă a datelor este promisă că va fi compatibilă înapoi pentru totdeauna. Nicio problemă de migrare a datelor!

  • Interogare după interval
  • 2019-09-18 v0.5.10 Reduceți rata falsului pozitiv la mai puțin de 0,05%
  • 2019-06-03 v0.5.9 Etalon mare set de chei
  • 29.05.2019 v0.5.6 Suportă până la 2 miliarde de taste
  • 18.05.2019 v0.5.4 Reduceți utilizarea memoriei de la 40 la 14 biți/cheie
  • 2019-04-20 v0.4.3 Indicele intervalului: multe taste împart un singur element index
  • 2019-04-18 v0.4.1 Suport de asamblare
  • 2019-03-08 v0.1.0 SlimIndex SlimTrie

Chei index, obțineți după cheie

Indexează intervalele de taste, obține după cheie

Creați un element de index pentru fiecare 4 (sau mai multe după cum doriți) taste.

Permiteți mai multor chei adiacente să partajeze un singur element de index reduce mult costul memoriei dacă există o cantitate mare de chei în datele externe. Cum ar fi indexarea a miliarde de obiecte 4KB pe un disc de 4 TB (deoarece un IO de disc costă 20 ms fie pentru citirea 4KB, fie pentru citirea 1 MB).

Instalare

Toate pachetele de dependență sunt incluse în furnizor/dir.

Condiții prealabile

Pentru utilizatori (cine ar dori să construiască lucruri interesante cu slim):

Nimic.

Pentru colaboratori (cine ar dori să facă slim mai bine):

  • dep: pentru gestionarea dependenței.
  • protobuf: pentru recompilarea fișierului * .proto dacă se schimbă structura de date pe disc.

Pe alte platforme puteți citi mai multe: dep-install, protoc-install.

Cine folosește slim

Feedback și contribuții

Feedback-ul și contribuțiile sunt foarte apreciate.

În această etapă, întreținătorii sunt cei mai interesați de feedback-ul axat pe:

  • Aveți un scenariu din viața reală care suportă bine sau nu suportă deloc?
  • Oricare dintre API-urile îți îndeplinesc bine nevoile?

Spuneți-ne prin depunerea unui număr, descrierea a ceea ce ați făcut sau ați dorit să faceți, ce vă așteptați să se întâmple și ce s-a întâmplat de fapt:

Sau alt tip de problemă.

  • 刘保海mareșalarea
  • 吴义 谱matrice
  • 张炎 泼design slimtrie
  • 李文博trie-comprimare, trie-căutare
  • 李树龙mareșalarea

Vezi și lista contribuitorilor care au participat la acest proiect.

Acest proiect este licențiat sub licența MIT - consultați fișierul LICENȚĂ pentru detalii.

Despre

Trie surprinzător de eficient în spațiu în Golang (11 biți/cheie; 100 ns/get).