«Может показаться, что я ничего не делаю. Но на самом деле, на клеточном уровне, я очень занят»
Автор неизвестен

В 21 веке построение программ все чаще напоминает конструктор Lego. Этот подход подразумевает, что многие «кубики» придуманы до нас. Собственно их элементарность обманчиво подсказывает, что ресурс улучшений за многие годы здесь практически исчерпан и нам остается использовать то, что есть. Но, как не странно, по аналогии с биологией, элементарные «клетки» порой скрывают самые сложные и продуманные алгоритмы и именно здесь заключены все самые интересные баталии. В этом смысле программисты по многогранности индустрии, чем-то напоминают медиков. Здесь есть свои терапевты, ветеринары, хирурги и есть вот те ребята, которые на несколько строк кода могут потратить несколько месяцев работы.

«В компании Google, прямо сейчас, пока я говорю, в нашем парке серверов, 1% всех CPU занимаются вычислениями внутри хештаблиц. Пока я говорю, более 8% всей оперативной памяти серверов занимают хештаблицы. И это только то, что относится к С++, я не знаю ситуации по Java»
Matt Kulukundis, CppCon 2017

В свое время мне пришла в голову интересная идея о том, как можно размещать две sparse страницы на одном участке памяти попутно кодируя сами значения ключей в контейнере через переходы (jumps). Идея эта казалась достаточно интересной и свежей, а ее проверка занимала всего несколько десятков строк кода, поэтому в ближайший вечер преодолело любопытство узнать, во сколько же можно сжать таким способом страницы памяти. Надо сказать, что это было только начало и со временем все вылилось в проверку огромного количества гипотез, замеров, версий. В текущей версии достаточно сложно разглядеть очертания той первоначальной «идеальной» модели. В такой задаче, как и в типичной инженерной задач, очень важно найти баланс. Сложно найти тот простой универсальный механизм, который прямо как затвор автомата, в грязи, воде и на жаре будет одинаково хорошо работать.

«Сделать простое иногда во много раз труднее, чем сложное»
Михаил Калашников

Идея создать Trie, который будет работать быстрее Хештаблиц, не нова. В 2001 году Дуглас Баскинс описал принцип работы Judy Array. Идея показалась настолько интересной, что в компании Hewlett Packard выделили целую группу инженеров для этого проекта. Хорошо оптимизированное Trie скорей напоминает маленькую операционную систему. Здесь своя собственная реализация менеджера памяти, целый список алгоритмов сжатия и балансировки узлов, своя маленькая экосистема для управления микромиром в контейнере. В ввиду сложности реализации, таких проектов в открытом доступе совсем мало. В открытых репозиториях практически абсолютное большинство реализаций Trie насчитывает всего несколько сотен строк кода (JudyArray от HP около 20К, HArray около 8К LOC прим.). Те реализации которые есть, скорей носят академический характер, или созданы для решения специфических задач для работы с текстом. О Trie врядли спросят у Вас на собеседовании, такие Key/Value контейнеры не включают в стандартные библиотеки популярных языков программирования. И нужно сказать, совершенно зря. Уже при первом рассмотрении, приходит понимание, что хорошо оптимизированное Trie может работать быстрее хештаблиц, при этом по функциональности будучи даже богаче, чем бинарные деревья.

Поиск информации, одна из фундаментальных задач вычислительной техники. Собственно сразу после того как комьютеры научили что-то считать и хранить информацию, появилась потребность в эффективном поиске. За все время было предложено всего три основных концепта для организации быстрого поиска. Бинарные деревья — способ организации контейнера при котором ключи для поиска должна быть строго отсортированы. Хештаблицы – адресс значения получаем через обработку ключа хешфункцией. И Trie – где ключ сам по себе кодирует путь к значению. В литературе можно найти подробнее, как работают эти алгоритмы. Например здесь есть графическое описание чем эти подходы отличаются друг от друга
Но мало сказано, чем же Trie более интересен именно с точки зрения построения универсального Key/Value контейнера.

Hashtable Эта структура проектировалась для очень быстрого поиска ключа, собственно, жертвуя всем остальным. Во главе угла лежит хешфункция, от качества работы которой зависит почти все. Впрочем, вы можете выбрать отличную хешфункцию, которая на тестовых данных даст практически равномерное распределение, но всеравно не контролируете ситуацию на все 100%. Возможно в реальной работе, на новых данных, ваша хешфункция выродится в близкий к worst case случай. В этом случае супер быстрый поиск превратится в чтото вроде full scan и O(N) вместо O(1). Еще одна проблема, чем больше данных, тем больше коллизий. На больших обьемах данных коллизии наростают как снежный ком и в какойто момент, прийдется перестроить всю хештаблицу целиком. Это событие называется Stop World event и означает что вы не можете для вызывающего кода гарантировать близкую к константной latency. Также, большое количество данных повлечет за собой нелинейное черезмерное потребление памяти, многие ячейки внутри хештаблицы будут пусты, а сами ключи будут хранится в buckets в несжатом виде. Не существует эффективного способа искать по диапазону или по шаблону ключа в контейнере. Даже если ключи отличаются всего одним последним битом, вероятность что они окажутся рядом в структуре в одном и томже bucket стремится к нулю. Для процессора, если вы работаете с каким нибудь природным набором данных где сами по себе ключи похожи друг на друга (URL, FilePath, Words и др.), зачастую это будет означать cache miss, что также не прибавляет быстродействия. Но даже если у вас идеальная хешфункция, в контейнере всего несколько ключей и вообще нет коллизий, при вставке и поиске сам ключ вы сканируете как минимум дважды. Первый раз пропуская через хешфункцию и второй раз, когда пришли по адрессу, перепроверяя что найденный ключ действительно тот, что требуется. Почти всех этих недостатков лишена Trie, но о ней подробнее ниже.

Binary Tree Неким золотым стандартом, особенно если говорить о базах данных, является разные вариации бинарного поиска. Чаще всего встречаются две модификации. Red Black Tree — бинарный поиск с эффективной балансировкой дерева и B+ модификация, если нужна дополнительно работа с диском. Бинарный поиск лишен многих недостатков хештаблиц. Выбор хешфункции не нужен, потребление памяти практически линейно, вставки и поиск за предсказуемое время, обычно O(log(n)). Возможность искать по диапазону ключей и задавать тип сортировки данных. Но сама по себе скорость поиска достаточно низкая. В контейнере где около 1 млн ключей, ключ будет найден примерно за 20 seek times. При этом, если в идеальной хештаблице без коллизий мы говорили о сканировании ключа дважды, то здесь ключ может сканироваться десятки раз, на каждом этапе где нам нужно сравнивать ключи между собой на больше-меньше-равно. В целом, бинарное дерево работает действительно хорошо, но, к сожалению, не на плоской модели памяти. Каждый раз, когда нам нужно вставить новый ключ, мы его вставляем где-то в середину, чтобы сохранить порядок сортировки. Из-за этого достаточно сложные алгоритмы балансировки, из-за этого — оставленные spaces в extends, чтобы избежать перемещение старых данных при каждой вставке.

Trie Здесь мы возвращаемся к нашей “темной лошадке” и первое о чем нужно сказать, Trie всегда сканирует ключ один раз. По сути это означает, что именно Trie, хотябы теоретически, может работать быстрее чем хештаблицы и уж тем более чем бинарные деревья. Отсюда выходит еще одно интересное свойство — чем длинее ключи, тем больше разница в скорости работы между хештаблицами и Trie в пользу последнего. Кроме того, эта структура очень дружелюбно работает с кешами процессора, поскольку во-первых, похожие ключи лежат рядом в памяти, во-вторых, чаще всего такие ключи используют общие сегменты памяти и при следующей вставке или поиске, вероятно, часть ключа окажется уже загруженной в L1/L2 кеши процессора. Если ключи имеют похожую природу, вроде URL, структура более экономно расходует память за счет префиксного сжатия. Такие ключи также будут более эффективно сканироваться по диапазону. Бинарное дерево каждый ключ будет читать от начала до конца, в то время как Trie, будет сканировать только “хвосты” ключей. Очевидно что Trie лучше работает на плоской модели памяти, поскольку не требует постоянной балансировки в отличии от бинарных деревьев и при этом не требует полного перестроения дерева на больших обьемах данных в отличии от хештаблиц. Здесь нет Stop World события.

Какие же недостатки? Первое — не смотря на разные методики сжатия узлов, вроде Patricia, эта структура очень любит long jumps. Если данные мы храним на HDD, где seek time очень дорогая операция, то хештаблица будет работать значительно быстрее. Ведь не смотря на то, что она сканирует ключ дважды и более раз, seek time у нее будет всего один — спозиционироваться на нужный bucket, в то время как у Trie таких seek times будет несколько, хоть и в среднем меньше, чем в бинарном (классическом) дереве. Также, сканирование ключей рандомной природы по диапазону, в бинарном дереве будет значительно эффективней потому что, опять же, много jumps при сканировании поддерева. Еще в недостатки можно записать сложность реализации такой структуры и невозможность задать кастомную сортировку ключей, хотя это справедливо не для всех реализаций, например в HArray задать кастомную сортировку ключей всеже можно.

JSON В преведущих примерах мы сравнивали особенности работы разных контейнеров по таким параметрам как скорость работы, память, возможность сканировать по диапазону ключей. Для большинства прикладных задач замена одной реализации контейнера на другую будет означать “бит оптимизацию”. В высоконагруженных проектах выиграш конечно будет существенно больше. Причем под высоконагруженными я подразумеваю не только сервера больших корпораций к которым очень много клиентских запросов. Например архивирование данных, графический рендеринг, индексирование контента — это все теже задачи где обычный key/value контейнер может работать внутри “движка” под нагрузкой в миллионы запросов в секунду. В таких сценариях скорость никогда не бывает лишней и оптимизация, условно, в два раза будет означать что 16 гб контента будет индексироваться не 4 часа, а всего 2. И всеже везде здесь у нас есть выбор. Мы можем использовать существующую реализацию key/value контейнера и особо не задумываться о деталях его работы. Однако существует целый класс задач, где использовать что-то кроме Trie совершенно нецелесообразно. Речь идет о целом ряде задач обработки текста, например принцип работы Suffix Tree. Также, как пример, Radix Tree нашел удачное применение внутри ядра Линукс и врядли мог бы быть заменен чем то еще. Все эти примеры хорошо описаны в разной литературе, поэтому я не буду останавливаться на них подробнее. Вместо этого приведу еще один интересный пример. Вообще в архитектуре приложений очень важно добиться единообразия. Так часто бывает, что правильно выбранная абстракция, шаблон, как по “лекалу” подходит для всего остального. Так вот JSON это естественный интуитивно понятный формат который таким же естественным интуитивно понятным способом может быть сохранен внутри Trie. Как это сделать? Достаточно просто, нужно всеголишь JSON “нарезать” на ключи, где Key — это путь к аттрибуту и его значение, а Value это номер документа. Таким образом вставка, обновление или удаление аттрибута в середине документа JSON будет означать не его полную перезапись, а всеголишь вставку, обновление или удаление ключей внутри контейнера. Поиск любого аттрибута или поиск по диапазону значений аттрибута будет означать всеголишь поиск ключей или сканирование поддерева внутри Trie, без десериализации всего документа. Все эти операции работают очень быстро. Извлечение из Key\Value контейнера ключа обычно стоит меньше сотни наносекунд. Кроме того Trie естественным образом сжимает JSON за счет инвертированого индекса. Дело в том, что если такие документы хранить как отдельные файлы, аттрибуты в них будут дублироваться. Но если они будут добавлены в Trie, то в Trie все аттрибуты будут представлены один раз в независимости от количества добавленных документов в контейнер. Этот подход чем-то напоминает подход, который используется в колоночных хранилищах данных, но на этот раз, он применяется для документоориентированных баз данных. В целом, тема эта заслуживает отдельной статьи.

«Теория без практики мертва и бесплодна, а практика без теории бесполезна и пагубна»
П. Л. Чебышев

Недавно в сеть, в открытый доступ, был выложен проект HArray, реализующий алгоритм работы Trie с множеством оптимизаций. Реализация получилась достаточно сложной, но на мой взгляд, достаточно эффективной, что подтверждается бенчмарками. Вариант этот не окончательный, есть еще много идей для улучшений. К тому же, старая версия работала в раза полтора быстрее, но после добавления новой функциональности существенно замедлилась и с этим тоже стоит разобраться.

Кроме базовой функциональности, реализовано честное удаление. Честное, это когда ключи не “обнуляются” а честно демонтируются шаг за шагом высвобождая постепенно память. В сценариях массивного добавления и удаления ключей, структура работает в режиме “безотходного производства”, части старых “отмерших” ключей используются для построения новых. Если количество удалений превышает количество добавлений новых ключей, то в какойто момент структура может отдавать “лишние” страницы памяти операционной системе, попутно дефрагментируя свои собственные используемые страницы. Также реализованы всевозможные обходы по дереву, поиск по шаблону ключа, сохранение на диск, возможность переопределения сортировки ключей в контейнере и другая функциональность.