Count-Min Sketch: Оцінювання Частот Без Зберігання Всього

Чому Точне Підрахунок Не Виправляє Ситуацію на Великих Масштабах

Точний підрахунок кількості разів, коли кожен елемент з'являється в потоці, здається простим: зберігати хеш-мапінг від елемента до кількості та збільшувати відповідний запис при кожному входженні. Проблема полягає у пам’яті. Якщо потік містить сотні мільйонів унікальних елементів, наприклад, унікальні IP-адреси, які звертаються до сервера, унікальні пошукові запити або унікальні ідентифікатори продуктів у роздрібному продажу, хеш-мапінг сам по собі стає достатньо великим, щоб зберігати кожен унікальний ключ, а також додатковий простір для покажчиків, бачків та ланцюгів зіткнення. У багатьох реальних системах кількість унікальних елементів не обмежена або невідома заздалегідь, і потік ніколи не припиняється, тому немає моменту, коли можна було б просто зупинити розширення карти. Ще гірше, багато застосунків лише потребують приблизних відповідей: чи є ця IP-адреса важким користувачем, чи цей запит особливо популярний, чи цей продукт тренд? Для цих питань марно витрачати гігабайти оперативної пам’яті, щоб отримати абсолютно точний підрахунок, коли трохи розмита відповідь, обчислена за допомогою кількох кілобайтів, буде достатньо. Ця прогалина заповнює Count-Min Sketch. Він відмовляється від точності в обмін на фіксований, регульований бюджет пам’яті, який не збільшується з кількістю унікальних елементів, а лише залежить від бажаного рівня точності та довірчого інтервалу, що робить його практичним для потоків фактично необмежених розмірів і кардинальності.

Структура: Мережа Лічильників та Кілька Функцій Хешування

Count-Min Sketch, по суті, є двовимірний масив лічильників з d рядків і w стовпців, усі початково встановлені на нуль. Кожен рядок має свою незалежну функцію хешування, яка відображає будь-який прихідний елемент в один із w стовпців у цьому рядку. Важливо зазначити, що рядки не представляють різні предмети або різні часові періоди; вони паралельні та незалежні погляди на одному й тому ж потоці даних, кожен з яких використовує різну функцію хешування для розсіювання елементів по своїх стовпцях. Оскільки функції хешування є незалежними, елемент, який випадково зіштовхується з іншим елементом у функції хешування одного рядка, дуже ймовірно, не зіштовхнеться з цим самим елементом у функції хешування іншого рядка. Ця надлишковість – це вся суть структури: жоден окремий рядок не може бути довіряний наодинці, оскільки зіткнення збільшує значення лічильників у ньому, але об'єднання інформації з усіх d рядків дозволяє схецету скасувати більшість цього шуму. Розмір сітки, тобто кількість рядків і стовпців, визначається наперед залежно від допустимої похибки та бажаної впевненості, що похибка залишатиметься в межах цього обмеження, а також цей розмір не змінюється незалежно від кількості унікальних елементів, які згодом протікають через потік.

Оновлення Схеми: Хешування, Потім Збільшення Лічильника

Обробка нової появи елемента є надзвичайно дешевою. Для кожної з d рядків елемент проходить через функцію хешування цього рядка для обчислення індексу стовпця, і лічильник, що знаходиться в цьому рядку та стовпці, збільшується на одиницю. Це відбувається один раз на рядок, тому окреме оновлення торкається точно d лічильників загалом, незалежно від кількості різних елементів у потоці або розміру сітки. Немає пошуку існуючого запису, не потрібне розширення, немає ланцюгових структур, і навіть не потрібно знати, чи бачили елемент раніше. Два повністю різні елементи можуть, і часто будуть, потрапляти в один і той же стовпець у заданому рядку лише через випадкове хешування, і коли це відбувається, їхні лічильники змішуються разом в цій клітинці. Це очікується та допускається, тому що схема розроблена таким чином, що навіть якщо окремі клітинки забруднені зіткненнями з інших елементів, комбінація всіх рядків під час запиту все ще може відновити щільну та надійну оцінку. Вартість операції оновлення залишається постійною протягом усього життєвого циклу потоку, що і робить структуру придатною для високопродуктивних, реального часу середовищ, де кожін подію потрібно обробити за фіксованого, невеликого часу.

Отримання даних з креслення: Чому мінімум є правильною відповіддю

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

Обмін Пам’яттю на Точність та Його Застосування

Точність Count-Min Sketch безпосередньо визначається його розмірами. Збільшення кількості стовпців, w, розподіляє елементи більш тонко по кожній рядку, зменшуючи ймовірність зіткнення двох елементів і, відповідно, скорочуючи типову кількість перерахувань. Збільшення кількості рядків, d, додає більше незалежних можливостей знайти рядок, де певний елемент уникнув серйозного зіткнення, що підвищує впевненість у тому, що мінімальне значення, яке повертається, близьке до справжнього. Подвоєння будь-якого з цих розмірів приблизно подвоює використання пам’яті, але дає відповідне покращення точності або рівня впевненості, надаючи інженерам простий регулятор для торгівлі між використанням пам'яті та точністю на основі того, що може витримати їх застосування. У практиці ця структура постійно зустрічається в системах, які повинні дешево підсумовувати величезні потоки даних. Оператори мереж використовують її для моніторингу трафіку та виявлення «тягарів» – IP-адрес або з’єднань, що споживають непропорційно великий пропускну здатність, без утримання стану окремих потоків для кожної адреси. Оптимізатори запитів до баз даних використовують схеми, побудовані над стовпцями таблиць, щоб оцінити, скільки рядків відповідає фільтру або з’єднанню, що допомагає вибрати план виконання без сканування всієї таблиці. Платформи для аналізу потокових даних використовують її для відповіді на запитання, такі як які події, користувачі чи хештеги є трендами в режимі реального часу, обробляючи мільйони подій за секунду, зберігаючи при цьому використання пам’яті стабільним і передбачуваним.

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

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

Усе, що вище, працює прямо у вашому браузері — відкрийте Count-Min Sketch: Estimating Frequencies Without Storing Everything і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.