Антон Коновалов – «RoaringBitmap: что это такое и как мы это используем»

Transcript

1. Ozon Tech 2023
   RoaringBitmap: что это такое
   и как мы это используем
   Антон Коновалов, руководитель отдела «Сегменты
   и триггерные коммуникации»
   

   View Slide

2. Что такое битмапы
   1
   

   View Slide

3. Какие свойства? Где используют?
   Bitmap, bitset, bit-array
   3
   Index 0 1 2 3 4 5 6 7 . . . N
   Bitmap 0 1 0 1 0 0 1 . . . 1
   N
   существует
   в этом наборе
   2
   не существует
   в этом наборе
   

   View Slide

4. 4
   Почему это быстро?
   Храня наборы целых чисел в таком
   представлении, bitmap могут использовать
   преимущества чрезвычайно быстрых
   инструкций CPU
   • bitwise-AND
   • bitwise-OR
   • SIMD
   

   View Slide

5. Маски
   5
   

   View Slide

6. При решении каких задач
   мы используем bitmap в отделе
   «Сегменты и триггерные коммуникации»?
   2
   

   View Slide

7. Построение сегментов и сегментирование
   Сегменты
   7
   

   View Slide

8. Визуализация сегментов
   Сегменты
   8
   

   View Slide

9. Конструктор рассылок по аудиториям и аналитика по результатам
   Коммуникации
   9
   

   View Slide

10. Конструктор рассылок по аудиториям и аналитика по результатам
    Коммуникации
    10
    

    View Slide

11. Как написать свой
    маленький Bitset
    на Gо?
    11
    

    View Slide

12. RoaringBitmap
    3
    

    View Slide

13. Сжатые Bitmap. Могут быть в сотни раз быстрее
    RoaringBitmap
    13
    0х0000 0х0001 0х0001
    0
    62
    124
    186
    248
    310
    …
    61 938
    [0,99]
    [101,99]
    [300,99]
    1
    0
    1
    0
    1
    0
    …
    0
    16-bit values + pointers to container
    1000 sorted 16-bit values (2000 B)
    216 bits (8kB)
    3 х 2 B = 6 B
    Three pairs of 16-bit
    values, indicating
    intervals [0,99], [101,
    200], [300,399]; pairs
    are sorted for fast
    random access
    array container
    (1000 values)
    run container
    (3 runs)
    bitset container
    (215 values)
    

    View Slide

14. На сегменте 100_000_000 пользователей
    Посчитаем размер
    14
    Bitset
    1. Структура хранения:
    []uint64
    2. Размер сета:
    100_000_000 / 64 = 1_562_500
    3. 1_562_500 * 8 bytes = 12.5Mb
    RoaringBitmap
    1. Зависит от случая,
    посмотрим в коде J
    

    View Slide

15. [email protected]
    Спасибо за внимание
    Антон Коновалов, руководитель отдела
    «Сегменты и триггерные коммуникации»
    

    View Slide