Гучні Біти: Стиснений Бітсет, Який Живить Пошукові Двигуни

Розбиття Діапазону Цілих Чисел на Частини

Розумний Біт починається з простої ідеї, запозиченої від того, як комп'ютери вже представляють числа. Будь-яке 32-бітне непідписане ціле число може бути розділене на дві 16-бітні половини: верхню та нижню. Верхні 16 біт можуть мати будь-які з 65 536 різних значень, тому їх використовують для вибору, до якої групи контейнерів належить число. Нижні 16 біт, які також можуть мати 65 536 різних значень, описують положення цього числа всередині свого блоку. Іншими словами, весь діапазон з більш ніж чотирьох мільярдів 32-бітних цілих чисел розділений на 65 536 контейнерів, кожен з яких відповідає точно 65 536 можливим значенням. Важливо, що блок створюється та зберігається лише тоді, коли принаймні одне число, яке належить до нього (тобто нижні 16 біти), насправді присутнє в наборі. Якщо ваші дані використовують лише цілі числа менше ста тисяч, то лише перші два блоки ніколи не повинні існувати, і всі інші блоки споживають нульовий об'єм пам’яті. Ця ленива, за запитом виділення блоків пам’яті, є одним із основних джерел ефективності Roaring Bitmap: вона ніколи не нараховує витрати на пам’ять для діапазонів чисел, які повністю порожні. Всередині кожного активного блоку числа, які належать до нього (тобто нижні 16 біти), потрібно зберігати якось, і цей формат зберігання вибирається незалежно для кожного окремого блоку. Ця двошарова структура, розріджений верхній рівень ідентифікаторів блоків у поєднанні з незалежно оптимізованими контейнерами нижче, дозволяє Roaring Bitmap плавно адаптуватися до дуже різних розподілів чисел, від кількох розкиданих ідентифікаторів до майже безперервних діапазонів, що охоплюють мільйони значень, все в одній єдиній структурі.

Три Типи Контейнерів для Трьох Видів Даних

Всередині кожного фрагменту Roaring Bitmap підтримує контейнер, який зберігає шістнадцять найнижчих бітів кожної знахідки, і обирає між трьома форматами контейнерів на основі того, скільки значень фактично міститься в ньому. Перший – це контейнер масиву, який використовується, коли фрагмент розріджений, зазвичай містить не більше приблизно чотирьох тисяч значень. Він просто перераховує найнижчі біти у відсоркованому порядку, кожен з яких зберігається компактно. Другий – це контейнер-бітова мапа, який використовується, коли фрагмент щільний. Він виділяє фіксований блок восьми тисяч дев’ятисот двадцять вісім байт, по одному біту для кожного можливого значення в фрагменті, і просто перемикає біти на або з вимкненого стану. Коли фрагмент містить більше кількох тисяч значень, бітова мапа стає більш компактною, ніж відсортований список окремих чисел, оскільки вартість зберігання кожного значення в контейнері масиву починає перевищувати фіксовану вартість одного біта на кожне можливе положення. Третій – це контейнер з узагальненням довжини пробілів, який використовується, коли фрагмент містить довгі безперервні ділянки послідовних цілих чисел. Замість зберігання кожного значення в пробілі окремо, він зберігає лише початкове значення та довжину кожного пробілу. Таким чином, фрагмент, що представляє, наприклад, десять тисяч послідовних ідентифікаторів документів, може бути описаний лише однією маленькою парою чисел замість десяти тисячі окремих записів. Roaring Bitmap постійно оцінює та динамічно перетворює між будь-який із цих трьох форматів, який би займав найменше місця для фактичного вмісту фрагменту, тому структура ніколи не платить за невиправдану вартість, коли дешевший формат може зробити те саме.

Чому адаптивні контейнери перевершують прості бітмапи та масиви

Мотивація для цього трьохстороннього адаптивного дизайну стає очевидною, коли ви враховуєте можливі збої двох простіших альтернатив, які він замінює. Простий, незрощений бітмап по всій тридцятидворатковій діапазоні потребував би п’ятьсот дванадцять мегабайт лише для існування, незалежно від того, скільки чисел містить набір або десять мільйонів, оскільки кожне можливе значення вимагає зарезервованого біта, незалежно від того, чи використовується воно чи ні. Це величезний, часто неможливий, фіксований витратний бюджет для представлення розріджених наборів даних, які надзвичайно поширені в реальних робочих навантаженнях, таких як відповідність пошуковим запитам із вузьким фільтром. З іншого боку, простий відсортований масив або хеш-набір уникає цього фіксованого витратного бюджету та зберігає лише числа, які насправді присутні, але платить іншу ціну, коли набір стає великим або коли потрібно об’єднати кілька наборів. Обчислення перетину або об’єднання двох великих відсортованих масивів зазвичай потребує порівняння та злиття елементів один за одним, операція, вартість якої зростає зі збільшенням загальної кількості елементів, а хеш-набори погіршують ситуацію, відмовляючись від відсортованого порядку, який робить швидке злиття можливим у першому місці. Roaring Bitmap обходить обидві проблеми, ніколи не застосовуючи єдину стратегію впродовж всього діапазону. Розріджені регіони простору чисел обробляються компактним контейнером масиву, тому немає відходів пам’яті на порожнечі. Щільні регіони обробляються безпосереднім контейнером бітмапу, щоб уникнути надмірної витрати ресурсів на елемент за елементом. Регіони з довгими послідовними пробілами, які є поширеними в робочих навантаженнях, таких як часові ідентифікатори або безперервні діапазони рядків, обробляються контейнером зі стисненням довжини пробілу, який може представляти мільйони значень у невеликій фіксованій кількості місця. Оскільки вибір робиться незалежно для кожного блоку, одне Roaring Bitmap одночасно може містити деякі блоки, які майже порожні, деякі, що майже повні, і деякі довгі безперервні проміжки, кожен з яких зберігається у форматі, який найкраще підходить для нього, без будь-якої глобальної компромісної складності.

Швидкі Операції з Набору Даних, Контейнер за Контейнером

Реальна вигода від цього дизайну проявляється, коли потрібно об'єднувати набори даних – операція, яку постійно виконують пошукові системи та бази даних, наприклад, перетин набору документів, що містять один пошуковий запит, з набором документів, що містять інший. Roaring Bitmap виконує операцію об'єднання, перетин або різницю шляхом проходження ідентифікаторів блоків обох бітмапів у відсоркованому порядку, подібно до злиття двох відсортованих списків, та обробки сумісних блоків разом. Якщо ідентифікатор блоку існує лише в одному з бітмапів, для об'єднання весь блок просто копіюється без змін, а для перетину він повністю пропускається, оскільки не може бути жодних відповідних значень в відсутньому блоці іншого бітмапу. Це само по собі усуває величезну кількість непотрібної роботи порівняно з підходом біт за бітом або елемент за елементом, оскільки цілих 65 536-значущих блоків вирішується одним порівнянням. Коли ідентифікатор блоку існує в обох бітмапах, два відповідні контейнери об'єднуються, а точний метод залежить від типів контейнерів, що беруть участь. Два контейнера типу бітмапу можна об'єднати за допомогою надзвичайно швидких інструкцій процесора, які працюють з багатьма бітами одночасно. Два контейнера типу масив можна об'єднати так само, як два відсортованих списки, в часі пропорційному їх сумарній величині. Контейнер з розширенням кількості пробілів можна об’єднати з іншим контейнером шляхом порівняння пробілів і діапазонів безпосередньо, часто торкаючись набагато менше окремих значень, ніж фактично представляє контейнер. Оскільки кожен формат контейнера зберігає вміст у передбачуваному та відсортованому внутрішньому порядку, ці злиття на рівні контейнерів ніколи не потребують повернення до повільного загального порівняння, а вартість операції відстежує справжню складність даних замість теоретичного розміру діапазону чисел. Це дозволяє системам, що обробляють мільярди ідентифікаторів, обчислювати перетини та об'єднання наборів даних за тисячі частки секунди.

Розумні Біти: Оптимізований Бітсет для Пошукових Дій

Розумні Біти вперше були описані у науковому дослідженні 2016 року та швидко перейшли від академічної концепції до практичного застосування в деяких із найбільш поширених систем даних у світі. Apache Lucene, пошукова бібліотека, яка лежить в основі Elasticsearch і Apache Solr, використовує структуру «Розумні Біти» для представлення списків публікацій, набір ідентифікаторів документів, пов’язаних із кожним індексованим терміном. Це дозволяє швидко об'єднувати результати запитів з кількох термінів, навіть якщо індекси містять сотні мільйонів документів. Apache Spark використовує «Розумні Біти» для відстеження, які розділи або рядки вже були оброблені під час великих розподілених обчислень, уникаючи проблеми пам’яті та навантаження при злитті списків. Аналітичні системи даних, такі як ClickHouse і Apache Druid, використовують їх для індексування бітмапів категоріальних стовпців, де запит може одночасно знайти всі рядки, що відповідають кільком умовам фільтрації, перетинаючи кілька таких бітмапів. У кожній з цих систем основна робота має однакову структуру: ідентифікатори приходять у величезному числовому діапазоні, їх розподіл непередбачуваний і може варіюватися від надзвичайно розрідженого до надзвичайно щільного, а система повинна швидко об'єднувати багато таких наборів під жорсткими обмеженнями затримки. Поєднання адаптивної стиснення на основі чанків та швидких операцій з об’єднанням контейнерних наборів «Розумні Біти» безпосередньо відповідає всім трьом вимогам одночасно, що пояснює, чому вони стали майже стандартом вибору, де потрібно ефективно індексувати, зберігати та поєднувати великі набори цілих чисел, а не нішевою технікою, обмеженою одним продуктом.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Roaring Bitmap: The Compressed Bitset That Powers Search Engines і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.