company_banner

Judy-массивы в PHP

    В Badoo используется много сервисов на C и C++, большинство из которых работают с огромными объёмами данных. Как правило, сервисы выступают в роли «быстрого кэша» или «быстрой базы данных», т.е. совершают различные операции с массивами однотипных данных. Для быстрого доступа к данным мы давно и успешно используем Judy-массивы (англ. Judy arrays). Но однажды нам захотелось странного: обрабатывать большие массивы целых чисел на PHP, и мы сразу вспомнили про Judy.

    Немного истории

    Judy-массивы были изобретены Дугласом Баскинсом (англ. Douglas Baskins) в начале 2000-го года. Проект их разработки финансировался компанией HP, но примерно через два года был закрыт. За это время было выпущено четыре версии, причём разработка последней заняла больше года, и в ней разработчики смогли в два раза ускорить Judy, в два раза уменьшить потребление памяти, хоть и далось это нелёгкой ценой: объём кода вырос в 5 раз, а его сложность  ― на порядок.

    Алгоритм работы Judy-массивов запатентован, однако оригинальная реализация на C доступна на официальном сайте под лицензией LGPL.
    Проект назвали именем сестры Баскинса, потому что разработчики не смогли придумать варианта лучше.

    Массивы-деревья

    По правде говоря, Judy-массивы не являются собственно массивами. Judy ― это развитие trie, т.е. префиксного дерева, с использованием разных методик сжатия. Judy-массивы выгодно отличаются от C-массивов и стандартных реализаций хеш-массивов: разреженные Judy-массивы эффективно используют память и прекрасно масштабируются, при этом показывая сравнимую скорость чтения и записи (см. бенчмарки).
    Подробное описание алгоритма работы Judy вряд ли уместится в формат статьи для Хабра, поэтому мы просто оставим ссылки на официальную документацию: 1 и 2.

    Существует несколько типов Judy-массивов:
    • Judy1 ― битовый массив (bitmap), индексом является целое число (integer->bit);
    • JudyL ― массив c целым числом в качестве индекса (integer->integer/pointer);
    • JudySL ― массив указателей со строкой в качестве индекса (string->integer/pointer);
    • JudyHS ― массив указателей с набором байт в качестве индекса (array of bytes->integer/pointer).

    Массивы Judy не требуют инициализации, и пустой массив ― это простой NULL-указатель. Следствием этого является то, что Judy-массивы удобно вкладывать друг в друга. Настолько удобно, что JudySL и JudyHS ― это на самом деле вложенные массивы JudyL.

    Бенчмарки

    Встроенные массивы в PHP ― вещь универсальная и, как следствие, крайне неэффективная в некоторых случаях. Если сравнивать с Judy, то реализованы они довольно тривиально: это хеш-массивы с двусвязным списком внутри каждого элемента на случай коллизий хеша. Хранят PHP-массивы переменные PHP, т.е. указатели на структуры zval. В подавляющем большинстве случаев именно это от них и требуется, однако есть исключения.
    Чтобы продемонстрировать, почему мы решили использовать Judy, проведём сравнительное тестирование Judy и PHP-массивов. В качестве интерфейса к Judy из PHP используем модуль php-judy, в котором имплементирован класс Judy с реализацией интерфейса ArrayAccess. В тесте создадим массивы вида integer -> integer (array(), Judy::INT_TO_INT, Judy::INT_TO_MIXED) или integer->boolean (Judy::BITSET) и заполним их элементами с последовательными ключами.
    Для начала замерим скорость записи в массивы с помощью подобного кода:
    <?php
    $arr = array();
    for ($i = 0; $i < 10000000; $i++) {
      $arr[] = 1;
    }
    ?>
    

    image

    Интерактивный график см. здесь.
    Пики при записи array() вызваны удвоением размера массива и его перестроением при заполнении всех элементов хеша. Небольшие возвышенности на графиках Judy можно объяснить погрешностью измерений.
    Из графика видно, что разные виды Judy по скорости записи примерно равны встроенному массиву. Единственное исключение ― BITSET (Judy1), который чуть быстрее.

    Потом замерим скорость последовательного чтения из массивов:
    <?php
    /* …*/
    /* предварительно заполняем массив,  потом в цикле читаем все элементы */
    $arr = array();
    for ($i = 0; $i < 10000000; $i++) {
      $val = $arr[$i];
    }
    ?>
    

    image

    Интерактивный график см. здесь.
    Из графика видно, что при чтении Judy::BITSET и Judy::INT_TO_INT незначительно проигрывают встроенному массиву PHP. Это происходит потому, что в этих массивах хранятся биты и целые числа соответственно, а не переменные PHP (т.е. zval). Именно накладные расходы на создание и заполнение переменных и отнимают у нас выигрыш в производительности.
    С другой стороны, array() и Judy::INT_TO_MIXED хранят внутри как раз переменные PHP, и им не надо тратить время на их создание, поэтому они примерно равны по скорости.

    Наконец, замерим потребление памяти при заполнении массивов и получим следующий график:
    image

    Интерактивный график см. здесь.
    Как видно из графика, разница в потреблении памяти между PHP-массивами и Judy1/JudyL огромна, и для нас это является главным критерием в данном случае, т.к. мы вполне можем пожертвовать частью скорости при чтении из массива, получив взамен возможность работать с массивами гораздо большего размера, которые раньше вообще не умещались в оперативную память сервера.
    Таким образом, использование Judy-массивов в PHP оправдано при решении задач, связанных с обработкой больших массивов данных, особенно целых чисел и битов. С точки зрения скорости чтения и записи Judy-массивы не слишком отличаются от встроенных массивов, однако из-за отличий в имплементации они гораздо эффективнее используют память.
    Предваряя ваши вопросы, заметим, что, несмотря на свои явные преимущества, Judy-массивы вряд ли смогут заменить штатные массивы в PHP хотя бы потому, что последние могут одновременно содержать как целочисленные индексы, так и строчные, в то время как в Judy это реализуется с помощью двух разных типов массивов.
    Badoo
    351,00
    Big Dating
    Поделиться публикацией

    Комментарии 62

      +6
        +3
        видимо вы хотели подчеркнуть разницу между Judy на C и Judy на PHP… :)
        +1
        Очень интересно. Маленькое замечание — в графиках съелась легенда.
          +3
          Да, длинные строки там обрезались. Судя по всему, это фича Google Charts.
          Для этого есть ссылки на большие версии графиков.
          +2
          Добавьте, пожалуйста, в тест SplFixedArray. Или уже поздно?
            +1
            В SplFixedArray есть часть «fixed», которая делает их принципиально не подходящими под задачу «хранение больших массивов при минимуме памяти».
            Просто прогнать бенчмарки можно, но как вариант решения задачи они даже не рассматривались.
            +6
            Интересная у вас компания. Мне нравится то, что вы делаете.
              +1
              Спасибо! Нам тоже наша компания очень нравится :) И еще у нас полно вакансий.
              +3
              Буквально пару дней назад в php-judy были залиты улучшения по производительности (версия 0.1.6)
                +9
                Это наши патчи и мёржили.
                Поэтому и статью придержали немного, т.к. ждали мёржа и релиза новой версии.
                  +2
                  А, вот оно, что. Я на ник сразу внимание не обратил :-)
                  Я просто в твиттере мейнтейнера прочитал на днях «Got a bunch of great pull request from @_tony2001_». И тут вижу статью на Хабре. Думал совпадение.
                    +1
                    Очень сильно Вы верите в совпадения, мой друг. :)
                      0
                      лежит убитый анатолий три дырки в теле у него а рядом николай с трезубцем но это совпадение.
                  +8
                  Интересно узнать о задачах, под которые нужны массивы в миллионы элементов. Желательно с подробностями.
                    +7
                    select * from badoo.users
                      +4
                      $users = mysql_query('select * from badoo.users');
                      for ($user in $users) {
                          if ($user['login'] == $login && $user['password'] == md5($password)) {
                            //...
                          }
                      }
                      


                      так?
                        +11
                        как вы смогли вытащить у нас часть кода? =\
                          +2
                          Да еще и хеш без соли! Эх, баду-баду…
                          –12
                          Не мог оставить без внимания написанный код. Даже если вы написали его для демонстрации какого-то общего принципа, то делайте уж тогда это качественно.
                          1. Пора бы уже забыть про все функции начинающиеся на mysql_* (http://www.php.net/manual/ru/intro.mysql.php)
                          2. Даже в официальной документации php написано, что использовать md5 крайне не желательно, особенно для паролей! (http://www.php.net/manual/ru/faq.passwords.php#faq.passwords.fasthash)
                          Не забывайте, что ваш код читают сотни и потом некоторые начинают делать также.
                          Заранее извиняюсь за занудство.
                            +3
                            Ну, если что, то и цикл не for-in, а foreach-as.
                            Да и не foreach-as, а что-то там про while(mysql_fetch() !== null).
                            Ну как вспомнил, так вспомнил. Это всё дурное влияние питона :)

                            А если кто-то прочитает мой код и не поймёт шутки, и будет делать так же — ну, ссзб :)

                            И вообще, это был намёк, что выборка юзеров не является задачей. Это способ решения какой-то задачи, о которой изначально и было спрошено. Но намёк был слишком тонким, никто не понял. Со мной такое бывает.
                              0
                              почти все поняли, я думаю :)
                              –2
                              Ребят, за что минусуете? Если я что не так написал, аргументируйте и я заберу свои слова
                                +2
                                Я подозреваю, за капитанство.
                                  0
                                  Интересно получается :)
                                  То есть можно в примерах пользоваться mysql_ и md5, ведь всё равно все знают, что эти функции нельзя использовать.
                                  Хочу заметить, что я указал не на синтаксические ошибки, которые выдаст интерпретатор при первом же запуске, а на фундаментальные, которые неопытный человек не заметит.
                                    +3
                                    Нет, не поэтому.

                                    Оригинальный код nolar намеренно был глуп и с ошибками, чтобы подчеркнуть шутку symbix. Поэтому вы, де факто, пояснили шутку, которую, я подозреваю, большинство поняли сами.
                                      –4
                                      Да, вполне возможно
                                      +2
                                      В смысле, полный перебор логинов по базе не является ошибкой? Он не был упомянут.
                                0
                                > $users = mysql_query('select * from badoo.users');
                                это будут данные только с одного шарда, который содержит около 100К записей.
                                так-что в этом случае можно обойтись и простым массивом.
                                  0
                                  Но только это будет не просто массив на 100k записей, а массив из массивов по count(columns) — так что уже стоит попробовать judy. Но это всё так, just for fun, мы не такие задачи с помощью judy решаем.
                                  0
                                  Спасибо, настроение на остаток дня подняли =)
                                +3
                                Анализ статистических данных, пересчет/определение рейтингов пользователей например.
                                  0
                                  В какой-то момент для одной из бизнес задач нам потребовалась графовая база данных. Данные в неё нужно было как-то загружать, а при нашем масштабе данных было иногда мало, а иногда очень много, порядка озвученных 100k-1M. В основном это нужно было для того, чтобы не загружать в C-сервис уже имеющиеся в нём данные, потому каждая часть графа собиралась предварительно в PHP и в ней исключались дублирующиеся связи.
                                    0
                                    у моего друга, в проекте обсчета биллинга более 10 млн элементов — вылетело все по памятти.
                                    judy массивы здесь могли бы существенно помочь.
                                      0
                                      Честно говоря не знаю, как у нас биллинг считается, но в BI используют специализированные базы. Но после одного успешного применения judy уже разные команды начали думать как им это расширение может помочь.
                                        +1
                                        там где есть нагрузка — идет борьба за ресурсы
                                        там где есть объемы — идет борьба за ресурсы.
                                        все что сберегает ресурсы — может нам помочь :)

                                        так, что где есть нагрузка и объемы всегда найдет применение judy массивам
                                    0
                                    И все равно мне кажется, что такие вычисления стоит перенести на более производительные языки. Например D(имеет очень хороший фреймворк для веба)
                                      +2
                                      По-настоящему тяжелые вещи мы выносим в демоны на C/C++.
                                      Здесь как раз речь не о вычислениях, а о больших массивах данных, причем эти массивы грузятся в результате в один из демонов.
                                        +1
                                        А вы эти сишные демоны кластеризуете? Если да, то интересно как вы обеспечиваете консистентность данных в разных инстансах демона или как живете с неконсистентностью.
                                          +6
                                          Некоторые демоны шардируются по user_id, некоторые шардируются по странам. Многие из них реплицируют данные на другую площадку (у нас на данный момент по 1 площадке на каждом полушарии).

                                          В случае репликации консистентность опять же обеспечивается по-разному. В зависимости от типа хранимых данных. Например по времени. Типа «реплика, у тебя какое последнее время обновления? ну на тебе то что новее, теперь мы одинаковые». Это не 100% консистентность, но для наших задач ее хватает.
                                        +1
                                        Чуть выше Sannis ответил.
                                        +1
                                        Judy-массивы вряд ли смогут заменить штатные массивы в PHP

                                        Я бы заметил, что Judy массивы не сереализуются/десереализуются штатными методами что еще больше сужает сферу их применения из PHP.
                                          +3
                                          Будет надо — сделаем патч. Но пока я себе слабо представляю для чего нужна сериализация массива на миллионы элементов.
                                            +7
                                            в memcached положить! все, ухожу, ухожу
                                              0
                                              Лучше в redis.
                                                0
                                                положит в своп сервер твой редис…
                                                  +1
                                                  а что — редис у тебя не ложил сервер?
                                                    0
                                                    У меня, нет.
                                                0
                                                Ну на правах примера притянутого за уши — хранение редко изменяемых данных, в духе словарей, в той же shared memory с целью использования несколькими процессами. Хотя в сравнении с redis + igbinary выигрыш наверное будет не очень большой.
                                                  +2
                                                  В таком случае, вероятно, имеет смысл завести узкоспециализированного демона, который будет хранить именно Judy-массивы, а не инты в виде строк. Конечно, для общения с демоном так или иначе понадобится какой-то механизм сериализации для передачи данных по сети. У нас в качестве стандарта принято использовать Google Protocol Buffers. Но это не сериализация объекта, это протокол общения с демоном.
                                              +1
                                              Патентованность все-таки сильно смущает. Какая разница, реализация LGPL или нет.
                                                +1
                                                В айпаде патентованный прямоугольник не смущает? :)
                                                А LGPL или нет — разница большая. Авторы, конечно, могут сменить лицензию на свой код, но не задним числом. А значит, этот код всегда будет публично доступен под LGPL.
                                                  0
                                                  А зачем использовать-поддерживать патентованный алгоритм (и тратить на него силы — слать патчи, например), если если много непатентованных, которые ту же задачу решат?

                                                  Почему я думаю, что есть много других вариантов, которые бы работали так же эффективно (или еще эффективнее):

                                                  вот есть какие-то массивы цифр, которые сначала хранятся в хэш-таблице (что, понятное дело, плохо). Потом вы их начинаете хранить в Judy Array и они занимают меньше памяти. Если я правильно понял графики, то было 100М цифр, которые при 4байтных данных заняли бы в простом массиве 400М. Если данные случайные, то меньше 400М они занимать и не могут — но они занимают в двух из трех Judy-массивах меньше. Значит, у данных есть какая-то структура (ну, например, большинство записей — нули). А раз у данных есть структура, то есть и более эффективные способы их хранения, чем просто массив (ну, например, разряженные матрицы).

                                                  Вы про структуру ничего не рассказываете, и ни с чем другим, кроме array, не сравниваете (который, очевидно, ужасен для хранения цифр), поэтому красивые бенчмарки и графики довольно бессмысленными кажутся. Из них можно сделать вывод, что иногда Judy Array будут работать лучше array, вот и все — а это и так вполне очевидно, иначе зачем бы биндинги делали к ним, и т.д.
                                                    +3
                                                    Во-первых, я не совсем понимаю ваше отношение к патентованным алгоритмам.
                                                    То есть, да, софтварные патенты — зло и всё такое, я совершенно согласен. Но они сть и это факт. В данном случае человек запатентовал алгоритм и намеренно выложил его имплементацию в общий доступ, т.е. фактически защитил нас от патентных троллей. Не вижу в этом ничего плохого.

                                                    Во-вторых, расскажите плз про более эффективные алгоритмы, я совсем не против еще более улучшить и демона, и скрипты.
                                                    Задача такая: хранить много не очень больших (макс. десятки тысяч элементов) списков интов, по которым надо быстро проходить и по которым должны быть быстрые лукапы. Ну, и памяти они должны занимать минимум, конечно.
                                                    На данный момент это всё реализовано на Judy1.

                                                    В-третьих, да, вещи довольно очевидные, но я и не претендую на открытие Америки. С другой стороны, я уверен, что большинство про Judy не слышали и с удовольствием посмотрят на красивые диаграммки и узнают про новый инструмент.
                                                      0
                                                      Отношение такое: человек, запатентовавший алгоритм, может потенциально получить от этого выгоду, если алгоритм кто-то использует. Чтоб не поощрять патентование алгоритмов, лучше не использовать патентованные алгоритмы (и не пропогандировать их использование) — в этом случае у патентообладателя не будет возможности получить выгоду, и патентование оттого станет бессмысленным.

                                                      Про задачу — все еще не понял :) Есть N множеств чисел, в каждом множестве не более 100тыс элементов, и нужно понять, входит ли данное число в n-ное множество? Judy1 для этого хорош, это да. Можно еще какой-нибудь сжатый/разряженный bitarray найти, или двоичное дерево поиска использовать; если ошибки допустимы — можно использовать фильтр Блума (если недопустимы — то тоже можно, например, как «первый уровень», отсекать элементы, которых заведомо нет в множестве). Или задачу как-то переформулировать. Готового решения на php я в любом случае придумать не смогу, т.к. слабо в экосистеме разбираюсь.
                                                        +1
                                                        >Есть N множеств чисел, в каждом множестве не более 100тыс элементов,
                                                        >и нужно понять, входит ли данное число в n-ное множество?

                                                        Да, но еще надо проходить по этому множеству от начала до конца и чтобы это множество занимало минимум памяти.
                                                        Решение меня интересует не на PHP, конечно, а на С — мы же ищем более эффективный алгоритм, чем Judy.
                                                          +2
                                                          Потенциально может.

                                                          Но есть и другой вариант: запатентовать алгоритм для того, чтобы его не запатентовал кто-то другой, например, патентный тролль.

                                                          В комбинации с выкладыванием реализации в общий доступ вариант 2 более вероятен.
                                                  +1
                                                  А где примеры использования таких массивов?
                                                    +1
                                                    Все аналогично штатным массивам: $judy[] = $value; $value = $judy[0];
                                                    Только здесь жестко фиксирован тип индексов и значения элементов ограничены соотв-м типом.
                                                      0
                                                      Я всё понимаю. Но почему-то не увидел в топике самого простого: создания массива.
                                                        0
                                                          0
                                                          Я всё понимаю(почти) и всё уже нашёл. Просто, я не понимаю почему статья о Judy массивах не содержит примера кода использования Judy массива. При этом содержит пример использования нативного массива.
                                                    +1
                                                    Спасибо Тони 2001 за интересный рассказ о Judy массивах, а так же за его
                                                    интересное и полезное расширение, которое хорошо подойдет для расчетных задач (статистика и биллинг).

                                                    Непременно буду иметь его ввиду. Сам хотел сделать нечто подобное ;), даже это обсуждалось на Хабре более года назад в одной из тем про структуры данных, но просто не было подходящего проекта под эту задачу.

                                                    Лично я собирался использовать judy массивы в своих сишных проектах, по этому немного в теме,
                                                    но в конечном итоге стал использовать dict (libdict) и tokyocabinet в силу их более понятного АПИ, а так же решаемому объему задач (мне более 100 M элементов не надо).

                                                    Мы, все расчетные задачи выносим в бэдграунд, которые реализованы как сишные демоны. Да и пользователей у нас 25М, а не 100+М как в Баду…

                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                    Самое читаемое