Самый быстрый Индиан: Key/Value контейнер на базе Trie

    image

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

    В 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 с множеством оптимизаций. Реализация получилась достаточно сложной, но на мой взгляд, достаточно эффективной, что подтверждается бенчмарками. Вариант этот не окончательный, есть еще много идей для улучшений. К тому же, старая версия работала в раза полтора быстрее, но после добавления новой функциональности существенно замедлилась и с этим тоже стоит разобраться.

    Кроме базовой функциональности, реализовано честное удаление. Честное, это когда ключи не “обнуляются” а честно демонтируются шаг за шагом высвобождая постепенно память. В сценариях массивного добавления и удаления ключей, структура работает в режиме “безотходного производства”, части старых “отмерших” ключей используются для построения новых. Если количество удалений превышает количество добавлений новых ключей, то в какойто момент структура может отдавать “лишние” страницы памяти операционной системе, попутно дефрагментируя свои собственные используемые страницы. Также реализованы всевозможные обходы по дереву, поиск по шаблону ключа, сохранение на диск, возможность переопределения сортировки ключей в контейнере и другая функциональность.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 19

      +3
      Когда-то просматривал ваш проект… заметил странный код и как-то забыл об этом спросить.
      HArray\HArray_insert.cpp — 576
      else //key is exists, update
      {
      	pContentPage->pContent[contentIndex] = pContentPage->pContent[contentIndex];
      
      	return 0;
      }
      

      Это не опечатка?
        0

        Да, опечатка, обязательно исправлю. Спасибо за внимательность, порой самые очевидные ошибки сложнее всего заметить.

          +3
          Поскольку проект под лицензией MIT, можно попробовать прогнать статический анализатор PVS-Studio, может ещё какие нибудь недочеты можно будет устранить.
            +1
            Можно конечно, наверняка от этого была бы польза. Но самые сложные баги что я здесь ловил, были алгоритмические. Обычно дело обстояло так, на вставке 345123 ключа, что-то идет не так, но баг никак себя не проявляет и структура умудряется безошибочно вставить еще несколько сотен тысяч ключей после чего необьяснимо крашится в каком нибудь проприетарном коде. Такие баги пришлось ловить, написав отдельную функциональность которая тщательно проверяет Healthy всей памяти после вставки каждого ключа, чтобы засечь баг как можно раньше. Для структуры, которая кодирует данные чуть менее чем полностью через GoTo по другому не получается. На сейчас, в основных кейсах, структура достаточно стабильно работает под Linux и Windows, на х64/x32 платформах. В одном из тестов удалось вставить даже около 1 млрд ключей и ничего не рассыпалось.
              0
              Простите, не можете ли объяснить, каким образом содержание или количество данных влияют на надежность?

              Мне казалось, что если алгоритм верен (и железо надёжно) — то неважно, сколько данных хранится — 1000 записей или миллиард, а судя по вашему комментарию получаются что это лотерея, и не факт что при 10 миллиардах записей ничего не «рассыпется».
                +2
                Далеко не все алгоритмы. Хештаблицы построены на вероятностной модели. Такая модель подразумевает, что распределение по слотам идет достаточно равномерно без сильных перекосов. Но большие данные сами по себе подразумевают что может быть любой сценарий. В одних buckets будет всего несколько ключей, а в других 100500. И дальше все зависит предусмотрено ли это разработчиками. Плохое качество хешфункции и(или) большие данные могут «подвесить» или «развалить» практически любую хештаблицу.
                  0
                  Да, на больших объемах могут вылезти ошибки или недостатки проектирования, но при чем тут надежность? Небалансирующееся дерево может выродится в список, но работать то оно не перестанет, просто будет тормозом.
                  Если у Вас там вероятны проезды по памяти, то напишите приличные тесты и гоняйте их под {l,m}san.
                    0
                    С семейством Binary Tree да. Это одна из причин, почему именно это семейство поисковых алгоритмов используется в базах данных. Хорошее предсказуемое поведение как по скорости работы так и по потреблению памяти в независимости от объемов данных, хотя тут тоже есть ньюансы. Пост выше касался хештаблиц и разных гибридных алгоритмов, которые используют вероятностную модель. С ними не все так однозначно.
        0
        Спасибо большое за поднятие интересной темы. А вы не могли бы привести какие-нибудь детали реализации, в чем основная фишка или описать основные операции по шагам? Просто при прочтении, внимательном, не мог отделаться от мысли что вы описываете suffix-tree. Кода много, а по картинкам вообще ничего не понял, хотя, вроде немного в теме, про хеш-таблицы и деревья. Заранее извиняюсь, если туплю на пустом месте.
          0
          Спасибо за отзыв. Действительно, сейчас когда говорят о Trie, зачастую подразумевают тот-же Suffix-Tree, хотя это всего лишь один из подвидов применения Trie, где добавив все возможные суффиксы строк получаются доступными такие операции как — поиск подстроки, количество различных подстрок в строке и др. Как это работает достаточно хорошо описано в разных источниках, есть посты и на этом сайте. Однако область применения Trie, как и любого Key/Value контейнера, не ограничивается работой с текстом или алгоритмами архивирования. Если реализация не тривиальная, то работать такой контейнер может на уровне или быстрее хештаблиц при этом потребляя меньше памяти и предоставляя более широкую функциональность. В таком ключе статей мало, почему я и решил написать пост выше на хабре. Подробного описания алгоритмов для HArray пока что нет, но есть подобное описание для JudyArray. Как по мне, то эти документы как их не пиши, будут тяжелыми для восприятия, поэтому я больше склоняюсь к мысли просто записать несколько видео-лекций возле доски в будущем.
            0
            В принципе, описывать всю полную и законченную реализация не обязательно. Насколько мне удалось понять из вашего описания, вы применяете хитрую методику аллокации узлов которая сильно отличается от аллокации узлов в дереве. Вот про нее бы и хотелось услышать поподробнее. За счет чего появляется возможность оптимизации, ведь мы, по сути, пытаемся создать такие же разреженные массивы узлов как и в случае с деревьями?
              +1
              Тут конечно можно было бы написать длинный пост, с большим количеством технических деталей, как и что работает. Но самом деле, я бы смотрел глубже, вообще в суть Trie. А суть в том, что он на самом деле намного ближе к уже работающим механизмам в мире биологии, он сам по себе моделирует эволюционный процесс, где каждый из узлов усложняется только по мере необходимости. Поэтому он часто находит применения в таких неожиданных областях, как например анализ цепочек ДНК. Но это отступление, если вернуться почему Trie работает быстрее, то все сведется к тому, что он лучше работает с линейной памятью. Он просто линейно пишет свои узлы, шаг за шагом. Пишет эффективно, если ключи похожи, он использует одни и теже сегменты два и более раз, не пишет ничего дважды, не перемещает уже записанные сегменты, ничего не балансирует, ничего глобально не перестраивает на ходу. Если у него есть конфликт, ставит шунт, говорит здесь ветвление делаем джамп и снова линейно пишет. Вообщем суммируя, сам по себе алгоритм, кроме всех прочих достоинств, более дружелюбен к блоку предсказания процессора, к кешам процессора и к линейной модели памяти вообще. Но конечно, чтобы раскрыть весь его потенциал, нужно многие вещи делать вручную. Если напр. на каждой операции создания вызывать создание узла через оператор new, то никаких конечно профитов по скорости не будет.
                0
                А поясните пожалуйста вот это ваше высказывание:
                Вообщем суммируя, сам по себе алгоритм, кроме всех прочих достоинств, более дружелюбен к блоку предсказания процессора, к кешам процессора и к модели памяти вообще.
                Если даже предположить, что мы не используем new и сжимаем узлы, то возьмем, к примеру, текстовый ключ «veryveryverylongkey». Здесь я насчитал 19-ть рандомных переходов по памяти. Как это соотносится с вашим утверждением выше, что-то я туплю?
                  0
                  Если у вас всего один ключ veryveryverylongkey, то у вас самый простой примитив. Все что сделает Trie, просто запишет его в одну единственную область памяти как сплошной текст на максимальной скорости. Чуть сложнее будет если у вас будет еще один, похожий на этот ключ, тогда получится бранч на два ветвления Здесь есть обьяснение с картинками
                    0
                    Т.е. мы не сплитим ключ пока в этом нет необходимости. ОК, я вас понял. Эх, тогда все-таки придется читать оригиналы начиная с Judy Array и по списку. Жаль. Вы меня заинтриговали. Не часто на ровном месте открываешь давно известные идеи с новым неожиданным подходом.
                      0
                      Judy Array достаточно большой документ, там используется до десятка разных способов сжатия узлов. Если интересует только этот метод сжатия, то это Patricia или Compact Trie описан в вики, напр. здесь en.wikipedia.org/wiki/Radix_tree
          0
          GPL? жаль.
            0
            GPL? жаль.

            А в тексте readme: "The code is licensed under the MIT license, see the LICENSE file for details."
            Но ссылка на GPL. Чему верить?

              0
              А я и не заметил, спасибо, что обратили внимание. Да, жаль.

            Only users with full accounts can post comments. Log in, please.