предисловие
В этой статье в основном обсуждается распространенный метод временной метки или числового сжатия в базах данных временных рядов: алгоритм дельта-дельта, который может значительно снизить стоимость хранения данных и повысить производительность записи данных и запросов.
Временная метка дельта-дельта-сжатия упоминается в документе Facebook Gorilla, адрес документа:Уууу, лицо Ви полностью .org/PV в dB/Vol8/…Проект Prometheus TSDB также опирается на идеи, изложенные в статье Facebook Gorilla, которые могут обеспечить высокую степень сжатия данных временных рядов.
дельта-сжатие временных меток
Временные метки обычно хранятся в длинном виде, для чего требуется 8 байт дискового пространства. Самая простая оптимизация заключается в сохранении разницы временных меток, для чего требуется начальная временная метка и порог максимального диапазона дельты. Есть две общие идеи реализации:
- Сохраните разницу между двумя соседними метками времени Delta(n) = T(n) - T(n-1)
| Временная метка Unix | Delta |
|---|---|
| 1571889600000 | 0 |
| 1571889600010 | 10 |
| 1571889600025 | 15 |
| 1571889600030 | 5 |
| 1571889600040 | 10 |
- Сохраняет разницу от метки времени начала Delta(n) = T(n) - T(0)
| Временная метка Unix | Delta |
|---|---|
| 1571889600000 | 0 |
| 1571889600010 | 10 |
| 1571889600025 | 25 |
| 1571889600030 | 30 |
| 1571889600040 | 40 |
Предполагая, что метка времени начала равна 1571889600000, максимальное пороговое значение дельты составляет 3600 с, а для хранения значения каждой дельты требуется 13 бит. Следовательно, общее пространство, занимаемое приведенными выше данными временной метки, составляет 64 + 13 * 4 = 116 бит.
Преимущество идеи 2 заключается в том, что не нужно последовательно просматривать данные в блоке, но по сравнению с идеей 1 может потребоваться более частое изменение времени запуска и выбор подходящей схемы сжатия в соответствии с фактическими потребностями.
сжатие временных меток дельта-дельты
В Facebook Gorilla есть подробное объяснение того, как вычисляется дельта-дельта-кодирование.Ниже приведен отрывок из статьи.
Для данных за разные промежутки времени Facebook Gorilla предлагает более общее решение.
| D | идентификационный бит | Всего занимает бит |
|---|---|---|
| 0 | 0 | 1 |
| [-63,64] | 10 | 2 + 7 = 9 |
| [-255,256] | 110 | 3 + 9 = 12 |
| [-2047,2048] | 1110 | 4 + 12 = 16 |
| > 2048 | 1111 | 4 + 32 = 36 |
Тем не менее, через набор данных временных меток, чтобы интуитивно почувствовать эффект сжатия дельта-дельта-кодирования:
| Временная метка Unix | delta | delta-of-delta | Всего бит после сжатия |
|---|---|---|---|
| 1571889600000 | 0 | 0 | -- |
| 1571889600010 | 10 | 10 | 9 |
| 1571889600010 | 0 | -10 | 9 |
| 1571889600011 | 1 | 1 | 9 |
| 1571889600012 | 1 | 0 | 1 |
| 1571889600013 | 1 | 0 | 1 |
| 1571889600015 | 2 | 1 | 9 |
| 1571889600017 | 2 | 0 | 1 |
По-прежнему предполагая, что начальная отметка времени равна 1571889600000, максимальное пороговое значение дельты составляет 3600 с, а занимаемое пространство хранения выглядит следующим образом:
- дельта-алгоритм: 64 + 13 * 7 = 155 бит.
- алгоритм дельта-дельта: 64 + 9 * 4 + 1 * 3 = 103 бита.
Можно видеть, что дельта-дельта-алгоритм дополнительно обеспечивает более высокую степень сжатия, чем дельта-алгоритм. В сценариях практического применения временные метки массивных данных временных рядов являются плотными и непрерывными, и большинство из них удовлетворяют условию дельта-дельта=0, что может значительно сократить пространство для хранения временных меток.
Суммировать
- Алгоритм дельта-дельта часто используется для сжатия временных меток в данных мониторинга, что может значительно снизить затраты на хранение и повысить производительность операций записи и запросов.
- Для данных с большим размахом система должна иметь определенную отказоустойчивость.
- Алгоритм дельта-дельта также имеет определенные недостатки, потому что это алгоритм сжатия переменной длины, поэтому он должен рассчитываться по первому адресу блока данных после распаковки.
приложение
Пожалуйста, укажите источник перепечатки, прошу обратить внимание на мой публичный номер: техническое колесо Япу