$30 off During Our Annual Pro Sale. View Details »

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

Ozon Tech
September 22, 2023

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

Ozon Tech

September 22, 2023
Tweet

More Decks by Ozon Tech

Other Decks in Technology

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