Джуді Арей: Адаптивна Трійка з Урахуванням Кэша

Фундамент з 256-Стрічковою Трійкою

Джуді-масив фундаментально є *цифровою трійкою*, також відомою як трихорід, побудований поверх необроблених байтів ключа, а не на основі порівнянь між повними ключами. Для 32-бітного цілочисельного ключа трійка має до чотирьох рівнів, кожен для одного байта, і на кожному рівні вузол може розгалужуватися до 256 напрямків, оскільки байт містить 256 різних значень. Переміщення від кореня до листка, отже, займає обмежену кількість кроків, не більше чотирьох для 32-бітного ключа або восьми для 64-бітного ключа, повністю незалежно від того, скільки ключів насправді зберігається в масиві. Це критична структурна відмінність від порівняльних дерев, таких як червоно-чорні дерева або B-дерева, де довжина шляху зростає з *логарифмом* кількості ключів. У Джуді-масиві довжина шляху визначається шириною ключа, а не кількістю записів, тому вартість пошуку не погіршується зі збільшенням масиву. Найпростіше реалізувати 256-стрічкову розгалуження на кожному рівні - це простий масив з 256 покажчиків на вузол. Це швидко, один доступ до пам'яті за індексом на рівні, але це також надзвичайно неефективно: вузол із лише двома або трьома дітьми все одно резервує слоти для 256, витрачаючи кілобайти пам’яті на невелику кількість реальних записів. Оскільки Джуді-масиви спеціально розроблені для обробки *рідкісних* просторів ключів, таких як набір кількох тисяч 64-бітових ідентифікаторів, розсіяних по величезному діапазону, цей найпростіший макет повністю знищить мету. Структура, призначена для економії пам’яті, не повинна одночасно виділяти ресурси для найбільш щільного випадку на кожному вузлі. Ця напруга, бажаючи *O(1)* швидкості прямого індексування на рівні та слідкувати за слідом пам'яті структури, яка платить лише за існуючих дітей, є точно тим, що мотивує основне рішення Джуді щодо дизайну. Замість вибору одного формату вузла та прийняття його компромісу скрізь, структура дозволяє кожному вузлу незалежно обирати свій формат, щоб відповідати фактичній кількості дітей нижче нього. Вузол біля кореня, який може мати сотні нащадків, може собі дозволити велике щільне представлення. Вузол глибоко в розрідженому гілку, який може мати лише одного або двох дітей, використовує мінімальний формат, який коштує майже нічого. Ця адаптивність вузла до вузла, застосована рекурсивно по всій трійці, є механізмом, що досліджується в наступній секції.

Адаптивні представлення вузлів: Список, Бітова карта та Повний масив

Серце Judy array — це невелика родина представлень вузлів, кожне з яких оптимізовано для різних популяцій. Реалізація автоматично перетворює вузол з одного представлення в інше при додаванні або видаленні дітей. Хоча точні порогові значення та формати варіюються між Judy1, JudyL і JudySL, основна стратегія єдина і може бути зрозуміла як три основні рівні. *Лінійні вузли списку* використовуються, коли вузол має лише невелику кількість дітей, зазвичай менше приблизно півтора десятка. У цьому вузол зберігає відсортований масив ключових байтів та відповідних йому покажчиків на дітей, а пошук дитини передбачає короткий лінійний або бінарний пошук замість прямого індексування. Це свідомо просто: з такою малою кількістю елементів компактний список перевершує розріджену бітову карту або масив на 256 записів по всіх осях, враховуючи пам'ять та швидкість, оскільки весь список поміщається в одну або дві кеш-лінії. *Бітові вузли* беруть верх, коли кількість дітей перевищує комфортний діапазон списку, але все ще не досягають повної щільності. Замість зберігання ключових байтів явно, бітовий вузол використовує 256-бітний вектор (32 байти) з одним бітом, встановленим для кожного байта, що має дитину, а також стислий масив покажчиків лише для тих дітей, які дійсно існують. Знаходження дитини полягає у перевірці одного біта та підрахунку кількості встановлених бітів перед ним, щоб знайти індекс покажчика в стислому масиві – *підрахунок популяції*. Це представлення набагато щільніше за список, коли присутня десятків кількість дітей, але водночас уникає виділення місця для відсутніх дітей. *Повні масивні вузли* використовуються, коли більшість або всі 256 можливих байтових значень дійсно приводять до дитини. Тут Judy повертається до наївного прямого індексованого масиву з 256 покажчиків, оскільки при цій щільності накладні витрати на підрахунок популяції бітової карти більше не виправдовуються, а одноразове завантаження за індексом є найшвидшим і найбільш ефективним з точки зору пам'яті варіантом. При додаванні та видаленні дітей поширюється по популяціях, Judy прозоро змінює представлення вузла, щоб структура в цілому завжди використовувала формат, який є локально доречним, ніколи не платячи щільно за розрідженість або розріджено за щільність.”]} 1/17 2/17 3/17 4/17 5/17 6/17 7/17 8/17 9/17 10/17 11/17 12/17 13/17 14/17 15/17 16/17 17/17 18/17 19/17 20/17 21/17 22/17 23/17 24/17 25/17 26/17 27/17 28/17 29/17 30/17 31/17 32/17 33/17 34/17 35/17 36/17 37/17 38/17 39/17 40/17 41/17 42/17 43/17 44/17 45/17 46/17 47/17 48/17 49/17 50/17 51/17 52/17 53/17 54/17 55/17 56/17 57/17 58/17 59/17 60/17 61/17 62/17 63/17 64/17 65/17 66/17 67/17 68/17 69/17 70/17 71/17 72/17 73/17 74/17 75/17 76/17 77/17 78/17 79/17 80/17 81/17 82/17 83/17 84/17 85/17 86/17 87/17 88/17 89/17 90/17 91/17 92/17 93/17 94/17 95/17 96/17 97/17 98/17 99/17 100/17 101/17 102/17 103/17 104/17 105/17 106/17 107/17 108/17 109/17 110/17 111/17 112/17 113/17 114/17 115/17 116/17 117/17 118/17 119/17 120/17 121/17 122/17 123/17 124/17 125/17 126/17 127/17 128/17 129/17 130/17 131/17 132/17 133/17 134/17 135/17 136/17 137/17 138/17 139/17 140/17 141/17 142/17 143/17 144/17 145/17 146/17 147/17 148/17 149/17 150/17 151/17 152/17 153/17 154/17 155/17 156/17 157/17 158/17 159/17 160/17 161/17 162/17 163/17 164/17 165/17 166/17 167/17 168/17 169/17 170/17 171/17 172/17 173/17 174/17 175/17 176/17 177/17 178/17 179/17 180/17 181/17 182/17 183/17 184/17 185/17 186/17 187/17 188/17 189/17 190/17 191/17 192/17 193/17 194/17 195/17 196/17 197/17 198/17 199/17 200/17

Чому Усвідомлення Кэшу Незалежне Від Дизайну

Вибір правильного представлення для популяції вузла – це лише половина інженерної історії Джуді, інша половина полягає в тому, що кожне представлення свідомо проєктується та розміщується з урахуванням поведінки кэшу CPU, зазвичай загальнодоступного 64-байтового кэш-лінію, яка використовується на більшості процесорів епохи розробки Джуді. Траверс трійки, який асимптотично *O(1)* на рівні, все ще може бути повільним у практиці, якщо кожен доступ до вузла на рівні викликає пропуски кэшу, оскільки доступ до основної пам’яті може коштувати приблизно в сто разів більше циклів, ніж доступ, який потрапляє в кэш L1 або L2. Розробники Джуді розглядають мінімізацію пропусків кэшу на кожне запитування ключа як першочергову ціль, нарівні з мінімізацією розміру пам’яті, і формують формат списку, бітмапу та масиву вузлів таким чином, щоб один вузол або невелике постійне число таких вузлів зазвичай поміщалося в одну або дві кэш-лінії. Це має конкретні наслідки для реалізації. Бітмапове представлення з вектором на 256 біт складається з чотирьох 64-бітних слів, достатньо малим, щоб його можна було протестувати та порахувати популяцію за допомогою лише кількох інструкцій машини без розлиття по багатьох кэш-лініях. Компактні вузли списку підтримуються таким чином, щоб ключові байти та їхні покажчики на всю ноду часто жили в одній лінії, тому лінійний перегляд кількох записів коштує один пам’ятний доступ замість кількох. Джуді також використовує такі техніки, як зберігання вузьких фрагментів ключів безпосередньо замість повних покажчиків, де це можливо, та упаковка метаданих у невикористані біти вирівняних покажчиків, щоб вмістити більше корисної інформації в кожній отриманій кэш-лінії. Виграш полягає в тому, що хоча масив Джуді може здійснювати кілька доступу до вузлів для вирішення одного ключа, кожен доступ спроектований таким чином, щоб бути дешевим, часто це кешований послідовний або передбачуваний пам’ятний запис, а не непередбачувана погоня за покажчиком у холодну пам’ять. Це контрастує з наївними зв’язаними структурами, такими як незбалансовані бінарні пошукові дерева, де кожен рівень зазвичай означає непередбачуваний стрибок до нового виділення кучі. Саме ця комбінація структуровано обмеженої глибини трійки плюс кэш-орієнтовані внутрішні вузли дозволяє Джуді конкурувати з хеш-таблицями, які здійснюють лише один або два пам’ятні доступів в середньому, але розсіюють ці доступі непередбачувано по пам’яті, особливо коли хеш-таблиця збільшується завантаженням або її потрібно змінити розмір.

Відсортований порядок, запити діапазону та перебір у відсортованому порядку

Хешування досягає середнього постійного часу пошуку завдяки навмисному знищенню будь-якої взаємозв’язку між ключем і значенням та розташуванням у пам'яті. Хороша хеш-функція розкидає схожі ключі в непов’язані кошики. Саме тому хеш-таблиці неефективно відповідають на запити, такі як *знайти найменший ключ, більший за X* або *перебрати всі ключі між A і B у відсортованому порядку*, для цього потрібно було б сортувати весь таблицю з нуля. Judy array не сплачує таку ціну, оскільки це трійка, організована безпосередньо на основі байтових значень ключа, в тому ж структурі, що й відсортований представлення ключів. Оскільки кожен внутрішній вузол має дітей, незалежно від того, чи зберігаються вони у вигляді списку, бітмапу або повної масиву, завжди логічно відсортовані за байтовими значеннями, інверсний перебір трійки Judy відвідує ключі в строго зростаючому порядку безкоштовно, не потребуючи окремого сортування та жодних допоміжних метаданих для упорядкування. Це робить природними та ефективними операції, такі як *перший*, *останній*, *наступний* і *попередній*, переміщаючись убік і вниз по трійці відповідно до байтового порядку, закодованого в структурі вузла. Запити діапазону, які повертають усі ключі між двома межами, стають обмеженим ходом по трійці, який відвідує лише вузли та залишається всередині запитованого діапану, а не повним скануванням структури. Ця здатність до упорядкованого перебору – це не другорядна функція, прикріплена до Judy після того, як вона була створена; вона безпосередньо випливає з використання радіксальної трійки як базової структури, а не хеш-таблиці. Практичні наслідки значні для багатьох реальних робочих навантажень: структури індексів баз даних, таблиці маршрутизації IP, які потребують найдовшого префіксного збігу, та розріджені бітмапи або множини, які повинні підтримувати упорядковане перелічення або запити типу

, наступний біт після позиції N

, усі вони виграють від цієї властивості. Хеш-таблицю можна доповнити допоміжною відсортованою індексом для підтримки таких запитів, але це означає підтримку двох структур і оплату двох наборів витрат на пам’ять та оновлення. Judy надає доступ у порядку як вбудовану, практично безкоштовну властивість свого адаптивного дизайну трійки, один із найочевидніших способів, яким він займає точку проектування, до якої не досягають хеш-таблиці чи звичайні збалансовані дерева самостійно.

Торгові Дилеми проти Хеш-Таблиць та Дерев B

Масиви Джуді часто порівнюють із трьома альтернативами: хеш-таблиці, збалансовані бінарні пошукові дерева та дерева B, і цей порівняльний аналіз чітко визначає нішу, яку займає дизайн. У порівнянні з добре налаштованою хеш-таблицею, Джуді зазвичай досягає порівнянної або навіть кращої пропускної здатності пошуку для великих наборів даних, переважно завдяки компактним масивам вузлів, орієнтованих на кеш, які підтримують *робочий обсяг*, що торкається при кожному пошуку, і часто вже знаходяться в кеші, тоді як хеш-таблиці страждають від непередбачуваних промахів кешу на ланцюгах зіткнення або заходах відкритого адресування та повинні періодично платити дорогий повний перехешування при їхньому збільшенні. Використання пам’яті Джуді на кшталт ключа також часто нижче, ніж у хеш-таблиці, оскільки хеш-таблиці зазвичай повинні підтримувати коефіцієнт завантаження нижче певного порогу, зазвичай менше сімдесяти або вісімдесяти відсотків, щоб зберегти швидкість, марно витрачаючи залишок ємності, тоді як адаптивні представлення Джуді самостійно налаштовуються відповідно до фактичної кількості елементів, а не резервують зайву ємність. У порівнянні з класичними збалансованими бінарними пошуковими деревами, такими як дерева червоного-чорного кольору або AVL, Джуді вирішує питання швидкодії та використання пам’яті для великої кількості ключів, оскільки *O(log n)* порівняльна десцентна бінарного дерева включає багато непередбачуваних переслідувань покажчиків, одне на кожний порівняння, і навантаження на вузол для метаданих балансування, тоді як десцент Джуді обмежений шириною ключа та його вузли компактні та дружні до кешу. У порівнянні з деревами B, цей порівняльний аналіз ближчий, оскільки дерева B самі по собі були розроблені з урахуванням ефективності блоків або кеш-ліній, особливо для дискових сховищ. Джуді зазвичай випереджає в роботі над пам’яттю завдяки більш тонкому адаптуванню представлення вузла до фактичної щільності, ніж фіксована ширина розгалуження дерев B і уникає навантаження від порівнянь ключів, використовуючи безпосереднє індексування байтами замість цього. Однак торгуються реальні речі. Реалізація Джуді є значною, з багатьма типами вузлів, пороговими значеннями перетворення та уважним упаковкою бітів, що робить її набагато важче правильно реалізувати та підтримувати, ніж хеш-таблицю або дерево B, яке є однією з причин, чому якісні реалізації Джуді відносно рідкі порівняно з поширеними бібліотеками хеш-таблиць. Джуді також найкраще працює з цілими числами або ключами із фіксованою структурою, де розкладання байт-трієв є природним і потребує більшої уваги при застосуванні до ключів змінної довжини.

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

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

Усе, що вище, працює прямо у вашому браузері — відкрийте Judy Array: The Cache-Conscious Adaptive Trie і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.