1. Введение
Пролистал официальный аккаунт и уже почти два месяца серьезно не писал статьи.За это время был в основном занят реваншем мидлвера Али, плюс поездка команды какое-то время назад, поэтому задержался с написанием резюме матча-реванша до сих пор. Сначала опубликуйте результаты:
Прежде всего, давайте поговорим об этой теме.Предыстория темы рематча — RocketMQ, который реализует механизм постоянного хранения сообщений в процессе и требует следующих функций:
- 发送消息功能
- 根据一定的条件做查询或聚合计算，包括
A. 查询一定时间窗口内的消息
B. 对一定时间窗口内的消息属性某个字段求平均
Пример: t означает время, временное окно [1000, 1002] означает: t>=1000 & t
Для уровня интерфейса сообщение включает два поля: одно — бизнес-поле a, другое — отметку времени, а также тело сообщения в виде массива байтов. Фактический формат хранения определяется пользователем, если может быть реализован соответствующий интерфейс чтения и записи.
Отправьте сообщение следующим образом (не обращайте внимания на тело сообщения):
消息1，消息属性{"a":1,"t":1001}
消息2，消息属性{"a":2,"t":1002}
消息3，消息属性{"a":3,"t":1003}
Запрос выглядит следующим образом:
示例1-
输入：时间窗口[1001，9999]，对a求平均
输出：2, 即：(1+2+3)/3=2
示例2-
输入：时间窗口[1002，9999]，求符合的消息
输出：{"a":1,"t":1002},{"a":3,"t":1003}
示例3-
输入：时间窗口[1000，9999]&（a>=2），对a求平均
输出：2 (去除小数位)
Общая тема относительно проста, в основном необходимо ввести 2 миллиарда данных, а затем запросить разные данные в соответствии с различными требованиями. Баллы делятся на 3 этапа: этап отправки, этап сообщения агрегации запроса, этап среднего запроса:
-
Этап отправки: предполагается, что количество отправленных сообщений равно N1, а время отправки всех сообщений равно T1; имеется несколько потоков отправки, а атрибуты сообщения: a (случайное целое число), t (аналоговое значение входной отметки времени, которое не имеет ничего общего с фактической меткой времени, в порядке возрастания внутри потока).Общий размер сообщения составляет 50 байт, количество сообщений составляет около 2 миллиардов, а общий объем данных составляет около 100 ГБ.
-
Стадия сообщения агрегации запросов: имеется несколько запросов, общее количество сообщений равно N2, а время всего запроса равно T2; возвращаются сообщения с условиями t и a в качестве условий и возвращаются сообщения в порядке возрастания t
-
Средняя стадия запроса: имеется несколько запросов, общее количество сообщений равно N3, а время всех запросов равно T3; вернуть среднее значение a на основе t и a
Если все результаты запроса верны, окончательный результат будет N1/T1 + N2/T2 + N3/T3.
Прежде чем говорить о конкретном методе, давайте поговорим о мучительном опыте этого конкурса. Конкурс разделен на несколько этапов:
- Первый — простой этап, в начале все следовали общей идее (данные хранятся в файлах), а баллы были от 30 000 до 50 000. Но на момент первого места среднее количество запросов составляло 150 000, а общее количество — 160 000. Всем было интересно, какими же ухищрениями они пользуются, чтобы получить такой высокий балл, поэтому был второй этап конкурса.
- На втором этапе все в основном используют унифицированную процедуру для сжатия A и T в память, а затем фильтруют или накапливают некоторые блоки кеша для получения среднего.Наивысший балл на этом этапе достигает 2,6 миллиона. На данном этапе это в основном превратилось в соревнование по среднему расчету.
- Организатор увидел, что эта тенденция была нехорошей, поэтому они очистили список и обновили набор оценочных данных, чтобы сделать A более случайным и несжимаемым, чтобы баллы на трех этапах были как можно более равными.На этом этапе они в основном были в первой тройке.Когда игру можно было закончить гладко, другой большой босс поднял третий этап на высокий уровень, и таким образом дошел до четвертого этапа.
- На четвертом этапе, который является последней неделей конкурса, организатор снова опустошил список. На самом деле такой недели не было, но организатор принудительно задержал ее на неделю. За последнюю неделю все более-менее нашли некоторые первые.Трехэтапный метод быстрого расчета, хотя есть некоторые общие идеи, поскольку групповой тур не реализовал эту идею на последней неделе тура, окончательный рейтинг был 28-м.
2. Сжатие данных
Первоначальная идея первоначально думала, что эта игра была тестом ввода-вывода файла игры, но в конце концов обнаружила, что на самом деле это средний конкурс, основная идея состоит в том, чтобы сжать + кешировать, кешировать это продолжение не приземлился здесь много вещи не последний хороший разговор, так что на этот раз в основном о сжатии данных, поэтому заголовок также называется это.
Мы внимательно изучили конкурсные вопросы и обнаружили, что сообщение состоит из трех частей: одна представляет собой обычно упорядоченную букву t, другая представляет собой неправильную букву а и 34-байтовое тело. Общая практика состоит в том, чтобы хранить эти три части в файле, затем строить разреженный индекс, а затем запрашивать наши результаты.
Но это явно неэффективно.Все операции запроса должны проходить через ввод-вывод.Есть ли какой-нибудь способ максимально выполнить наш запрос в памяти? Конечно, для этого требуется наше сжатие.
2.1 Что такое сжатие
Сжатие - это механизм уменьшения размера компьютерных файлов с помощью определенного алгоритма. На самом деле сжатие использует только законы файловых данных для достижения своей цели. Например, строка «Чжан Чжан Чжан Чжан Чжан Чжан Сан», здесь одиннадцать символов, поэтому на самом деле мы можем сократить его до «десять листов и один три».Мы используем «десять листов» для замены 10 листов, «один три» для замены трех, и, наконец, мы используем четыре символа для представления нас. Строка состоит из одиннадцати символов, но если это строка "Чжао Цянь Сунь Ли", то нет правила, которому нужно следовать. Если используется стратегия сжатия, размер файла увеличивается.
2.2 Цифровое сжатие
В наших вопросах о соревнованиях и а, и тело нерегулярны. Если мы решим сжать их, цена будет относительно высокой. Наше t задано в вопросе в основном упорядоченным, и основной порядок также можно интерпретировать как каждый. Всегда будет закономерности между числами, поэтому мы можем сжать их цифровым способом. Мы знаем много часто используемых сжатий, таких как zip, rar и т. д., но эти алгоритмы сжатия не предназначены для сжатия наших чисел, если их использовать непосредственно в нашей сцене, то они будут менее эффективны.
Для обычных чисел существует много относительно хороших алгоритмов сжатия чисел с открытым исходным кодом, которые будут представлены один за другим ниже.
3. Алгоритм сжатия
3.1 zigzag
Алгоритм сжатия зигзаг широко используется, и он присутствует в Avro и Thrift, Он используется для цифрового сжатия при передаче данных, чтобы уменьшить объем передаваемых данных.
Чтобы хорошо проиллюстрировать идею зигзага, мы можем сначала взглянуть на наше целое число 1. Если мы имеем тип int, оно представлено на нашем компьютере как:
00000000_00000000_00000000_00000001
Видно, что у нас есть много бесполезных нулей, поэтому мы можем с помощью некоторых стратегий сжать 31 ведущий 0. Что, если это -1, потому что кодирование наших отрицательных чисел должно быть представлено в компьютерном дополнении, следующее:
11111111_11111111_11111111_11111111
Первым битом нашего дополнения является бит знака, если это отрицательное число, то оно обязательно будет 1. Эта 1, естественно, мешает нашему сжатию ведущего 0. Мы ставим 1 в конце нашего кода, а остальные числа сдвинут влево на 1. Бит, в целом, представляет собой циклический сдвиг влево на 1 бит, то будут следующие результаты:
11111111_11111111_11111111_11111111
После переезда я обнаружил, что он точно такой же, как и наш предыдущий, и его по-прежнему нельзя сжать, поэтому зигзаг провел еще одну оптимизацию, знаковый бит остается неизменным, а остальные позиции инвертированы, остальная логика такая же, как у выше, то получается:
00000000_00000000_00000000_00000001
Видно, что он заполнен ведущими нулями, но если присмотреться, разве это не двоичный код 1? Ты -1 стал этим, а что насчет 1? Точно так же наши положительные числа также должны выполнять ту же логику сдвига.Бит знака положительного числа равен 0, но биты данных не нужно инвертировать, поэтому кодирование 1:
00000000_00000000_00000000_00000010
Таким образом, начальный 0 может быть сжат, независимо от того, является ли он положительным или отрицательным числом, поэтому как сжать начальный 0. Ранее мы приводили пример сжатия строки. Мы можем использовать вспомогательную информацию для его представления. число Int, оно не будет превышать 32 бита, и мы можем использовать дополнительные 5 бит для представления фактической длины наших данных.Положительное число 1 выше на самом деле только две допустимые длины, поэтому на самом деле это 10, и мы можем использовать следующие данные для представления:
00010_10
При декодировании мы сначала читаем 5 цифр, здесь 2, что означает, что у нас еще есть 2 бита данных, и, наконец, читаем оставшиеся 2 цифры из 10, а затем поворачиваем вправо, чтобы получить наш окончательный результат.
В реальном зигзаге используется другой метод сжатия: 32-битное число разбивается на 7-битное представление, а если его недостаточно, добавляется 0:
0000000_0000000_0000000_0000000_0000010
Таким образом, у нас будет байт 5. В настоящее время все они имеют только биты 7, и есть еще один бит метки. Мы добавляем 0 ко всем байтам с действительными данными и добавляем 1 к последнему. Итак, результат
10000010
Zigzag больше подходит для небольших чисел, то есть там много ведущих нулей, но наши числа t относительно большие и имеют длинный тип, как с этим быть? Не забывайте, что у нас есть в основном упорядоченное правило, которое доказывает, что разница между нашими двумя последовательными t невелика, мы можем вычислить разницу между последовательными t, а затем сжать разницу таким образом. Сжатие разницы здесь более важно, и последующая деятельность в основном связана с ним.
3.2 винт, влонг компрессия
Учащиеся, знакомые с Hadoop или Lucene, могут иметь некоторое представление об этом. Его суть также заключается в сжатии переменной длины, что в основном совпадает с обработкой положительных чисел зигзагом. Поскольку vint не нужно учитывать отрицательные числа, нет нужно переместить бит знака. Принцип сжатия: 8 бит байта, последние 7 бит представляют фактическое значение, а первый бит указывает, есть ли другие байты позади. Запишите 266 в двоичной форме 00000000_00000000_00000001_00001010 и используйте vint для представления 00000010_10001010, это экономит два байта, а vint подходит для положительных чисел.Конечно, во многих случаях наши числа являются положительными числами, которые можно выбирать в соответствии с реальной сценой.
3.3 delta-of-delta
Фейсбук с открытым исходным кодомberingeiбаза данных временных рядов.beringeiБаза данных, используемая для решения внутренних требований к хранению данных мониторинга и запросам, характеризуется высокой скоростью чтения и записи. Наш вопрос на этот раз в основном похож на базу данных временных рядов, поэтомуberingeiИдеологический принцип быстрого чтения и скорости письма можно хорошо использовать для нашего конкурса.
ЗнатьberingeiПочему скорость быстрая, тогда я должен сказать, что его алгоритм сжатия дельта-дельта, что такое дельта-дельта? Мы ввели дельта-алгоритм выше.Даже если мы используем сжатие, если наши данные относительно велики, степень сжатия определенно не будет особенно идеальной, поэтому мы можем использовать нашу дельту для оптимизации здесь.
| t | delta |
|---|---|
| 1100 | 0 |
| 1160 | 60 |
| 1121 | 61 |
| 1178 | 57 |
Как уже упоминалось в таблице выше, мы можем сжать исходные данные с Delta, то есть изменение наших данных непосредственно на 0, 60, 61, 57. Вообще говоря, эта оптимизация в основном удовлетворена, но мы можем быть дополнительно оптимизированы, мы хранить разницу между дельтой и дельтой, которая будет дополнительно сжата,
| t | delta | delta-of-delta |
|---|---|---|
| 1100 | 0 | 0 |
| 1160 | 60 | 60 |
| 1121 | 61 | 1 |
| 1178 | 57 | -4 |
Таким образом, мы будем 61, 57, только 1 и -4 могут быть сжаты и выражены, так что наша степень сжатия будет еще больше улучшена. В этом конкурсе мы выбрали этот алгоритм сжатия, который может сжимать 2 миллиарда временных меток с 15G до примерно 300-400M, а также некоторые вспомогательные индексы для бинарного поиска.Общее использование менее 800M может сжимать временные метки в память, а скорость запроса составляет тоже достаточно быстро.
3.4 XOR + DFCM
существуетberingeiВ базе данных временных рядов для сжатия времени используется дельта-дельта-дельта, а для сжатия числовых значений используется другой метод: XOR, который в основном является неправильным для числовых значений, поэтому значение разности не используется для сжатия. вместо этого используйте XOR:
| value | шестнадцатеричный | XOR результат |
|---|---|---|
| 15.5 | 0x402F000000000000 | 0 |
| 14.0625 | 0x402C200000000000 | 0x0003200000000000 |
| 3.25 | 0x400A000000000000 | 0x0026200000000000 |
| 8.625 | 0x4021400000000000 | 0x002b400000000000 |
Видно, что после XOR мы также можем получить немного меньшее значение, такую как дельта, но это значение все еще выглядит очень большим, и скорость сжатия не чувствует себя очень высокой, не волнуйтесь, мы представили сжатие, ведущее 0 ранее, Из вышеперечисленных данных мы можем обнаружить, что количество трейлинга 0s, кажется, больше, здесь мы можем сжать ведущую 0 и трейлинг 0 вместе. Он разделен на три части в DFCM:
- Ведущие нули: количество ненулевых значений до XOR
- Завершающие нули: количество нулей после ненулевого значения после XOR
- Значимые биты: количество ненулевых символов в середине.
После разделения частей правила кодирования следующие:
- Первые данные не сжаты для восстановления
- Затем оцените биты управления:
- Если XOR равен 0, сохраните 1 бит-0
- Если XOR не равен 0, первый бит управляющего бита устанавливается в 1, а второй бит и последующие данные вычисляются следующим образом:
- Значимые биты попадают в область значимых битов предыдущего XOR, второй бит управляющего бита равен 1, а следующий является значением XOR.
- В противном случае второй бит управляющего бита равен 0. Затем сохраните: 5 бит: номер начального бита; 6 бит: номер значимого бита; затем поместите значение
| value | XOR сжатый результат | XOR результат |
|---|---|---|
| 15.5 | без сжатия | 0 |
| 14.0625 | 13 бит (бит управления заголовком) + 5 бит (фактическое значение) | 0x0003200000000000 |
| 3.25 | 13 бит (бит управления головкой) + 10 бит (фактическое значение) | 0x0026200000000000 |
| 8.625 | 2 бита (биты управления заголовком) + 10 бит (фактическое значение) | 0x002b400000000000 |
Этот подход намного быстрее, чем gzip, rar и т. д.
Однако в этом конкурсе он малоэффективен, поэтому в итоге не был выбран.
3.5 snappy
Snappy по своей природе не является специальным алгоритмом цифрового сжатия. Мы можем использовать его для сжатия наших сообщений. Snappy используется во многих сценариях Google, таких как BigTable, MapReduce, rpc и так далее.
Snappy имеет более высокую скорость сжатия/распаковки, чем некоторые алгоритмы сжатия, такие как gzip и zip, но его размер сжатия не такой маленький, как у других алгоритмов. В матче-реванше для сжатия сообщений в начале использовался Snappy.Скорость записи однажды достигла 8500, а степень сжатия была около 40%.Однако в конце спрашивающий обновил данные сообщения, так что Snappy не смог сжать наше сообщение. Честно говоря, человек, который задал вопрос, немного собака. Я попросил его перед тем, чтобы спросить, можно ли сжать сообщение, и это общий алгоритм. Через несколько дней этот человек напрямую превратил сообщение в несжимаемые данные. , В реальной сцене snappy должен иметь возможность исправить Данные сжаты, но это изменение не соответствует нашей реальной сцене.
3.6 RoaringBitmap
RoaringBitmap — один из алгоритмов сжатия, которые я исследовал в самом начале. Хотя его нельзя использовать в нашей сцене, его мощность огромна, если использовать его в правильной сцене. Используется множество замечательных фреймворков: Spark, Hive, Tez и т. д.
Каждый контактирует с Bitmap при чистке теста, и данные записываются через Bit.Например, ваши данные имеют все типы int, только 32-кратные битовые записи, используемые в 2, могут сэкономить память в 32 раза, но Bitmap имеет вопрос, если ваши данные малы, но поскольку вы используете биты от 2 до 32 раз, будет много отходов BIT, поэтому появляется RoaringBitmap.
Roaringbitmap — это ультратрадиционный сжатый BitMap. Его скорость в сотни раз выше, чем у несжатого BitMap, и его основная идея состоит в том, чтобы сжать бит, бит которого равен 0. Конкретные детали можно найти в Интернете самостоятельно, и здесь они не будут подробно объясняться.
Roraingbitmap не только обладает характеристиками сжатого размера, но и имеет высокую скорость для объединения и пересечения нескольких Roraingbitmaps.RoaringBitmap можно использовать как инвертированный индекс.Если у нас большая таблица пользователей, если в ней есть пол пользователя , Мы знаем, что не рекомендуется индексировать поле с низкой степенью дискриминации, например, пол пользователя, потому что это очень расточительно, но если мы используем Roraingbitmap, мы можем это сделать.Мы создаем два Roraingbitmap, один используется для хранить пол мужской, Один используется для хранения пола женщины. Данные в Roraingbitmap - это идентификатор пользователя, и мы можем построить на нем индекс. Если в этой таблице есть другие поля, которые не являются сильно дискриминационными, то также можно создать Roraingbitmap. Если нам нужно запросить эти поля с низкой дискриминацией, мы можем запросить через объединение и пересечение Roraingbitmap.
4. Резюме
Хотя результаты на этот раз не были идеальными, я научился многим навыкам сжатия в соревновании. Я чувствую, что это самый большой выигрыш в этом соревновании. Я поделюсь им с вами здесь и надеюсь, что вы сможете использовать его в соответствующих сценариях. в будущем. Еще одно понимание заключается в том, что в такого рода соревнованиях изменения слишком велики, и данные будут изменены и переоценены в любое время, поэтому, когда у вас будет возможность прийти снова в следующий раз, не торопитесь делать это. этого почти достаточно, чтобы сделать это за 2 недели до крайнего срока. За этот конкурс я хотел бы поблагодарить брата Хуэйвэя, Киртио и Пу Цзя, к.к., и Лао Вана из Meituan.Все они очень помогли мне в конкурсе.
Если вы считаете, что эта статья полезна для вас, то ваше внимание и пересылка - самая большая поддержка для меня, O(∩_∩)O: