Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Ingénierie de la performance au sein des mégado...

Ingénierie de la performance au sein des mégadonnées

Les index logiciels accélèrent les applications en intelligence d'affaire, en apprentissage machine et en science des données. Ils déterminent souvent la performance des applications portant sur les mégadonnées. Les index efficaces améliorent non seulement la latence et le débit, mais aussi la consommation d'énergie. Plusieurs index font une utilisation parcimonieuse de la mémoire vive afin que les données critiques demeurent près du processeur. Il est aussi souhaitable de travailler directement sur les données compressées afin d'éviter une étape de décodage supplémentaire.
(1) Nous nous intéressons aux index bitmap. Nous les trouvons dans une vaste gamme de systèmes :
Oracle, Hive, Spark, Druid, Kylin, Lucene, Elastic, Git... Ils sont une composante de systèmes, tels que Wikipedia ou GitHub, dont dépendent des millions d'utilisateurs à tous les jours. Nous
présenterons certains progrès récents ayant trait à l'optimisation des index bitmap, tels qu'ils sont utilisés au sein des systèmes actuels. Nous montrons par des exemples comment multiplier la
performance de ces index dans certains cas sur les processeurs bénéficiant d'instructions SIMD (instruction unique, données multiples) avancées.
(2) Nous ciblons aussi les listes d'entiers que l'on trouve au sein des arbres B+, dans les indexes inversés et les index bitmap compressés. Nous donnons un exemple récent de technique de compression (Stream VByte) d’entiers qui permet de décoder des milliards d’entiers compressés par seconde.

Daniel Lemire

March 06, 2018
Tweet

More Decks by Daniel Lemire

Other Decks in Technology

Transcript

  1. Redécouvrir Unix Plusieurs composantes spécialisées et réutilisables: Calcite : SQL

    + optimisation Hadoop etc. "Make your own database from parts" 3
  2. Ensembles Un concept fondamental (ensemble de documents, d'enregistrements) → Pour

    la performance, on utilise des ensemble d'entiers (identifiants). → Souvent des entiers à 32 bits suffise (identifiants locaux). 4
  3. tests : x ∈ S? intersections : S ∩ S

    unions : S ∪ S differences : S ∖ S Jaccard/Tanimoto : ∣S ∩ S ∣/∣S ∪ S ∣ iteration: f o r x i n S d o p r i n t ( x ) 2 1 2 1 2 1 1 1 1 2 5
  4. Mise en oeuvre tableaux triés ( s t d :

    : v e c t o r < u i n t 3 2 _ t > ) tables de hachage ( j a v a . u t i l . H a s h S e t < I n t e g e r > , s t d : : u n o r d e r e d _ s e t < u i n t 3 2 _ t > ) … bitmap ( j a v a . u t i l . B i t S e t ) bitmap compressé 6
  5. Tableaux w h i l e ( l o w

    < = h i g h ) { i n t m I = ( l o w + h i g h ) > > > 1 ; i n t m = a r r a y . g e t ( m I ) ; i f ( m < k e y ) { l o w = m I + 1 ; } e l s e i f ( m > k e y ) { h i g h = m I - 1 ; } e l s e { r e t u r n m I ; } } r e t u r n - ( l o w + 1 ) ; 7
  6. table de hachage valeur x stockée à l'index h(x) accès

    aléatoire à une valeur rapide accès ordonné pénible 8
  7. accès ordonné pénible [15, 3, 0, 6, 11, 4, 5,

    9, 12, 13, 8, 2, 1, 14, 10, 7] [15, 3, 0, 6, 11, 4, 5, 9, 12, 13, 8, 2, 1, 14, 10, 7] [15, 3, 0, 6, 11, 4, 5, 9, 12, 13, 8, 2, 1, 14, 10, 7] [15, 3, 0, 6, 11, 4, 5, 9, 12, 13, 8, 2, 1, 14, 10, 7] [15, 3, 0, 6, 11, 4, 5, 9, 12, 13, 8, 2, 1, 14, 10, 7] [15, 3, 0, 6, 11, 4, 5, 9, 12, 13, 8, 2, 1, 14, 10, 7] (Robin Hood, sondage linéaire, fonction de mixage MurmurHash3) 9
  8. Opérations ensemblistes sur les tables de hachage h 1 <

    - h a s h s e t h 2 < - h a s h s e t . . . f o r ( x i n h 1 ) { i n s e r t x i n h 2 / / é c h e c ( m é m o i r e t a m p o n ) } 10
  9. Faire "crasher" Swift v a r S 1 = S

    e t < I n t > ( 1 . . . s i z e ) v a r S 2 = S e t < I n t > ( ) f o r i i n S 1 { S 2 . i n s e r t ( i ) } 11
  10. Quelques chiffres: une demi‑heure pour 64M taille temps (s) 1M

    0.8 8M 22 64M 1400 Maps and sets can have quadratic‑time performance https://lemire.me/blog/2017/01/30/maps‑and‑sets‑can‑have‑ quadratic‑time‑performance/ Rust hash iteration+reinsertion https://accidentallyquadratic.tumblr.com/post/153545455987/ru st‑hash‑iteration‑reinsertion 12
  11. 13

  12. Les bitmaps ou bitsets Façon efficace de représenter les ensembles

    d'entiers. Par ex., 0, 1, 3, 4 devient 0 b 1 1 0 1 1 ou "27". {0} → 0 b 0 0 0 0 1 {0, 3} → 0 b 0 1 0 0 1 {0, 3, 4} → 0 b 1 1 0 0 1 {0, 1, 3, 4} → 0 b 1 1 0 1 1 14
  13. Manipuler un bitmap Processeur 64 bits. Étant donné x ,

    l'index du mot est x / 6 4 et l'index du bit est x % 6 4 . a d d ( x ) { a r r a y [ x / 6 4 ] | = ( 1 < < ( x % 6 4 ) ) } 15
  14. Est‑ce que c'est rapide? i n d e x =

    x / 6 4 - > u n s h i f t m a s k = 1 < < ( x % 6 4 ) - > u n s h i f t a r r a y [ i n d e x ] | - m a s k - > u n O R a v e c l a m é m o i r e Un bit par ≈ 1.65 cycles à cause de la superscalarité 16
  15. Parallélisme des bits Intersection entre {0, 1, 3} et {1,

    3} équivaut à une seule opération AND entre 0 b 1 0 1 1 et 0 b 1 0 1 0 . Résultat est 0 b 1 0 1 0 ou {1, 3}. Aucun embranchement! 17
  16. Les bitmaps bénéficient des mots étendus SIMD: Single Intruction Multiple

    Data SSE (Pentium 4), ARM NEON 128 bits AVX/AVX2 (256 bits) AVX‑512 (512 bits) AVX‑512 est maintenant disponible (par ex. chez Dell!) avec les processors ayant une microarchitecture Skylake‑X. 18
  17. Similarité ensembliste avec les bitmaps Jaccard/Tanimoto : ∣S ∩ S

    ∣/∣S ∪ S ∣ devient 1.15 cycles par paire de mots (64‑bit) Wojciech Muła, Nathan Kurz, Daniel Lemire Faster Population Counts Using AVX2 Instructions Computer Journal 61 (1), 2018 (adopté par clang) 1 1 1 2 ∣B OR B ∣ 1 2 ∣B AND B ∣ 1 2 19
  18. Les bitsets peuvent être gourmants {1, 32000, 64000} : 1000

    octets pour 3 nombres On utilise donc la compression! 20
  19. Qu'est‑ce qu'on entend par compression? Modèle conventionnel: compresse, stocke, décompresse,

    traite; RAM → CPU → RAM → CPU Modèle performant: compresse, stocke, traite sans décompression; RAM → CPU 21
  20. Git (GitHub) utilise EWAH Codage par plage Exemple: 000000001111111100 est

    00000000 − 11111111 − 00 On peut coder les longues séquences de 1 ou de 0 de manière concise. https://github.com/git/git/blob/master/ewah/bitmap.c 22
  21. [EWAH in Git] has already saved our users roughly a

    century of waiting for their fetches to complete (and the equivalent amount of CPU time in our fileservers). http://githubengineering.com/counting‑objects/ 23
  22. Après une comparaison exhaustive des techniques de compressions par plage

    sur les bitmaps, Guzun et al. (ICDE 2014) en arrive à la conclusion... EWAH offers the best query time for all distributions. 24
  23. Complexité Intersection : O(∣S ∣ + ∣S ∣) ou O(min(∣S

    ∣, ∣S ∣)) Union en place (S ← S ∪ S ): O(∣S ∣ + ∣S ∣) ou O(∣S ∣) 1 2 1 2 2 1 2 1 2 2 25
  24. Roaring Bitmaps http://roaringbitmap.org/ Apache Lucene, Solr et Elasticsearch, Metamarkets’ Druid,

    Apache Spark, Apache Hive, Apache Tez, Netflix Atlas, LinkedIn Pinot, InfluxDB, Pilosa, Microsoft Visual Studio Team Services (VSTS), Couchbase's Bleve, Intel’s Optimized Analytics Package (OAP), Apache Hivemall, eBay’s Apache Kylin. Mise en oeuvre en Java, C, Go (interopérable) Point départ: thèse de S. Chambi (UQAM), co‑dirigée avec Robert Godin Roaring bitmaps 26
  25. Modèle hybride Décompose l'espace 32 bits en des sous‑espaces de

    16 bits. Au sein du sous‑espace de 16 bits, utilisons la meilleure structure (contenant): tableau trié ({1,20,144}) bitset (0b10000101011) plages ([0,10],[15,20]) C'est Roaring! Travaux similaires: O'Neil's RIDBit + BitMagic Roaring bitmaps 27
  26. Roaring Tous les contenants ont 8 kB ou moins (mémoire

    cache du processeur) On prédit le type de structure à la volée pendant les calculs Par ex. quand un tableau devient trop volumineux, on passe au bitset L'union de deux grands tableaux est prédite comme étant un bitset... Des dizaines d'heuristiques... réseaux de tri, etc. Roaring bitmaps 29
  27. Use Roaring for bitmap compression whenever possible. Do not use

    other bitmap compression methods (Wang et al., SIGMOD 2017) kudos for making something that makes my software run 5x faster (Charles Parker, BigML) Roaring bitmaps 30
  28. Unions de 200 éléments taille en bits par éléments :

    bitset tableau hachage Roaring census1881 524 32 195 15.1 weather 15.3 32 195 5.38 cycles par valeur par éléments : bitset tableau hachage Roaring census1881 9.85 542 1010 2.6 weather 0.35 94 237 0.16 Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience Volume 48, Issue 4 April 2018 https://arxiv.org/abs/1709.07821 Roaring bitmaps 31
  29. Compression d'entiers Technique "standard" : VByte, VarInt, VInt Utilisation de

    1, 2, 3, 4, ... octets per entiers Utilise un bit par octet pour indique longueur des entiers en octets Lucene, Protocol Buffers, etc. 32 : 00100000 128 : 10000000 + 00000001 Compression d'entiers 32
  30. varint‑GB de Google VByte: un embranchement par entier varint‑GB: un

    embranchemement par bloc de 4 entiers chaque bloc de 4 entiers est précédé d'un octet 'descriptif' Exige de modifier le format (pas compatible avec VByte) Compression d'entiers 33
  31. Accélération par vectorisation Stepanov (inventeur du STL en C++) travaillant

    pour Amazon a proposé varint‑G8IU Stocke autant d'entiers que possible par blocs de 8 octets Utilise la vectorisation (SIMD) Exige de modifier le format (pas compatible avec VByte) P rotégé par un brevet SIMD‑Based Decoding of Posting Lists, CIKM 2011 https://stepanovpapers.com/SIMD_Decoding_TR.pdf Compression d'entiers 35
  32. Observations de Stepanov et al. (partie 1) Incapable de vectoriser

    VByte (original) Compression d'entiers 37
  33. Accélérer VByte (sans changer le format) C'est possible nonobstant l'échec

    de Stepanov et al. Décodeur avec SIMD: Masked VByte Travaux réalisés avec Indeed.com (en production) Jeff Plaisance, Nathan Kurz, Daniel Lemire, Vectorized VByte Decoding, International Symposium on Web Algorithms 2015, 2015. Compression d'entiers 38
  34. Observations de Stepanov et al. (partie 2) Possible de vectoriser

    le varint‑GB de Google, mais moins performant que varint‑G8IU Compression d'entiers 40
  35. Stream VByte Reprend l'idée du varint‑GB de Google Mais au

    lieu de mélanger les octets descriptifs avec le reste des données... On sépare les octets descriptifs du reste Daniel Lemire, Nathan Kurz, Christoph Rupp Stream VByte: Faster Byte‑Oriented Integer Compression Information Processing Letters 130, 2018 Compression d'entiers 41
  36. Stream VByte est utilisé par... Redis (au sein de RediSearch)

    https://redislabs.com upscaledb https://upscaledb.com Trinity https://github.com/phaistos‑networks/Trinity Compression d'entiers 46
  37. As you can see, Stream VByte is over 30% faster

    than the second fastest, (...) This is quite an impressive improvement in terms of query execution time, which is almost entirely dominated by postings list access time (i.e integers decoding speed). https://medium.com/@markpapadakis/trinity‑updates‑and‑ integer‑codes‑benchmarks‑6a4fa2eb3fd1 Compression d'entiers 47
  38. Pour en savoir plus... Blogue (2 fois/semaine) : https://lemire.me/blog/ GitHub:

    https://github.com/lemire Page personnelle : https://lemire.me/fr/ CRSNG : F aster C ompressed I ndexes O n N ext‑ G eneration H ardware (2017‑2022) Twitter @lemire @lemire 48