Redis int-представление строки больше, если строка больше 7 байтов, но меньше в противном случае

Я пытаюсь уменьшить размер объектов Redis насколько могу, и я потратил всю неделю на эксперимент с ним.

При тестировании различных представлений данных я обнаружил, что int-представление строки "hello" приводит к меньшему объекту. Это может быть не так много, но если у вас много данных, это может сделать разницу между использованием нескольких ГБ-памяти и десятками.

Посмотрите на следующий пример (вы можете попробовать сами, если хотите):

> SET test:1 "hello"
> debug object test:1
> Value at:0xb6c9f380 refcount:1 encoding:raw serializedlength:6 lru:9535350 lru_seconds_idle:7

В частности, вы должны посмотреть serializedlength, который в этом случае равен 6 (байтам).

Теперь посмотрим на следующее int-представление:

> SET test:2 "857715"
> debug object test:2
> Value at:0xb6c9f460 refcount:1 encoding:int serializedlength:5 lru:9535401 lru_seconds_idle:2

Как вы видите, это приводит к сокращению байтового объекта (обратите внимание также на кодировку: int, которая, по моему мнению, предполагает, что ints обрабатывается более эффективным способом).

С строкой "hello w" (через несколько минут вы увидите, почему я не использовал "hello world" ), мы получаем еще большую экономию, когда она представлена как int:

> SET test:3 "hello w"
> SET test:4 "857715023" <- Int representation. Notice that I inserted a "0", if I don't, it results in a bigger object and the encoding is set to "raw" instead (after all a space is not an int).
>
> debug object test:3
> Value at:0xb6c9f3a0 refcount:1 encoding:raw serializedlength:8 lru:9535788 lru_seconds_idle:6
> debug object test:4
> Value at:0xb6c9f380 refcount:1 encoding:int serializedlength:5 lru:9535809 lru_seconds_idle:5

Это выглядит здорово, если вы не превышаете строку длиной в 7 байт. Посмотрите, что происходит в представлении int hello wo:

> SET test:5 "hello wo"
> SET test:6 "85771502315"
>
> debug object test:5
> Value at:0xb6c9f430 refcount:1 encoding:raw serializedlength:9 lru:9535907 lru_seconds_idle:9
> debug object test:6
> Value at:0xb6c9f470 refcount:1 encoding:raw serializedlength:12 lru:9535913 lru_seconds_idle:5

Как вы можете видеть, int (12 байт) больше, чем строковое представление (9 байтов).

Мой вопрос здесь в том, что происходит за кулисами, когда вы представляете строку как int, что она меньше, пока вы не достигнете 7 байтов?

Есть ли способ увеличить этот предел, как в случае с "list-max-ziplist-entries/list-max-ziplist-value" или умным способом оптимизации этого процесса, чтобы он всегда (или почти) меньший объект, чем строка?

UPDATE

Я еще экспериментировал с другими трюками, и на самом деле у вас может быть меньше ints, чем строка, независимо от ее размера, но это потребует немного больше работы по моделированию структуры данных.

Я узнал, что если вы разделили int-представление строки в кусках по 8 чисел каждый, она заканчивается меньше.

Возьмем в качестве примера слово "Hello World Hi Universe" и создадим как строку, так и int SET:

> HMSET test:7 "Hello" "World" "Hi" "Universe"
> HMSET test:8 "74111114" "221417113" "78" "2013821417184"

Результаты следующие:

> debug object test:7
> Value at:0x7d12d600 refcount:1 encoding:ziplist serializedlength:40 lru:9567096 lru_seconds_idle:296
>
> debug object test:8
> Value at:0x7c17d240 refcount:1 encoding:ziplist serializedlength:37 lru:9567531 lru_seconds_idle:2

Как вы можете видеть, мы установили int меньше 3.

Проблема в этом будет заключаться в том, как организовать такую вещь, но она показывает, что это возможно тем не менее.

Тем не менее, не знаю, где этот предел установлен. Постоянное использование памяти ~ 700K (даже если у вас нет данных внутри) заставляет меня думать, что существует предопределенный "пул", предназначенный для оптимизации наборов int.

UPDATE2

Я думаю, что нашел, что этот "пул" задается в источнике Redis.

В строке 81 в файле redis.h установлен параметр REDIS_SHARED_INTEGERS 10000

REDISH_SHARED_INTEGERS

Я подозреваю, что он определяет ограничение длины байта набора.

Я должен попытаться перекомпилировать его с более высоким значением и посмотреть, могу ли я использовать более длинное значение int (он, скорее всего, выделит больше памяти, если это тот, о котором я думаю).

Update3

Я хочу поблагодарить Антиреса за ответ! Не ожидал этого.

Как он меня заметил, len!= использование памяти.

В своем эксперименте я получил еще больше и увидел, что объекты уже слегка сжаты (сериализованы). Возможно, я что-то пропустил из документации Redis.

Подтверждение происходит от анализа ключа Redis командой redis-memory-for-key , которая фактически возвращает использование памяти, а не сериализованную длину.

Например, возьмем строку "hello" и int, которые мы использовали ранее, и посмотрим, что результат:

~ # redis-memory-for-key test:1
Key             "test:1"
Bytes               101
Type            string
~ #
~ # redis-memory-for-key test:2
Key             "test:2"
Bytes           87
Type            string

Как вы можете заметить, intset меньше (87 байт), чем строка (101 байт) в любом случае.

UPDATE4

Удивительно, что более длинный ввод, похоже, влияет на его серийную длину, но не на использование памяти.

Это позволяет фактически построить сопоставление 2digit- char, в то время как оно все еще более эффективно с памятью, чем строка, даже не разбивая его.

Под отображением 2digit- char я имею в виду, что вместо сопоставления "привет" на "85121215" мы сопоставляем его цифрам с фиксированной длиной 2 каждый, префикс "0", если цифра < 10, как "0805121215".

Пользовательский script затем будет действовать, разделив каждую две цифры и преобразуя их в их эквивалент char:

08 05 12 12 15
\  |  |   |  /
 h e  l   l o

Этого достаточно, чтобы избежать неоднозначности (например, "o" и "ae", которые приводят к значению "15" ).

Я покажу вам, что это работает, создавая другой набор и, следовательно, анализируя его использование памяти, как и раньше:

> SET test:9 "0805070715"

Unix shell
----------
~ # redis-memory-for-key test:9
Key             "test:9"
Bytes           87
Type            string

Вы можете видеть, что у нас есть победа в памяти.

Такая же строка "hello" , сжатая с Smaz для сравнения:

>>> smaz.compress('hello')
'\x10\x98\x06'

// test:10 would be unfair as it results in a byte longer object
SET post:1 "\x10\x98\x06"

~ # redis-memory-for-key post:1
Key            "post:1"
Bytes          99
Type           string

Ответ 1

Мой вопрос здесь в том, что происходит за кулисами, когда вы представляете string как int, что он меньше, пока вы не достигнете 7 байтов?

Обратите внимание, что целое число, указанное в качестве теста # 6, больше не закодировано как целое, но как raw:

Тест SET: 6 "85771502315"

Значение по адресу: 0xb6c9f470 refcount: 1 кодировка: raw serializedlength: 12 lru: 9535913 lru_seconds_idle:

Итак, мы видим, что "сырое" значение занимает один байт плюс длину его строкового представления. В памяти вы получаете это плюс накладные расходы.

Целочисленная кодировка, я подозреваю, кодирует число как 32-битное целое число; то он всегда будет нужно пять байт, один для указания его типа и четыре для хранения этих 32 бит.

Как только вы переполняете максимальное представляемое целое число в 32 бита, которое равно 2 миллиардам или 4 в зависимости от того, используете ли вы знак или нет, вам нужно вернуться к необработанной кодировке.

Скорее всего,

2147483647 -> five bytes     (TYPE_INT 0x7F 0xFF 0xFF 0xFF)
2147483649 -> eleven bytes   (TYPE_RAW '2'  '1'  '4'  '7'  '4'  '8'  '3'  '6'  '4'  '9')

Теперь, как вы можете сжимать строковое представление, ПРЕДОСТАВЛЯЕМОЕ, ЧТО ВЫ ТОЛЬКО ИСПОЛЬЗУЕТЕ УСТРОЙСТВО ASCII?

Вы можете получить строку (140 символов):

When in the Course of human events it becomes necessary for one people
to dissolve the political bands which have connected them with another

и преобразовать каждый символ в шестибитное представление; в основном его индекс в строке

"ABCDEFGHIJKLMNOPQRSTUVWXYZ01234 abcdefghijklmnopqrstuvwxyz56789."

который является набором всех символов, которые вы можете использовать.

Теперь вы можете кодировать четыре таких "текстовых символа" в трех "двоичных символах", своего рода "кодирование с обратным основанием 64"; base64 будет получать три двоичных символа и создать четырехбайтную последовательность символов ASCII.

Если бы мы закодировали его как группы целых чисел, мы бы сэкономили несколько байтов - возможно, до 130 байт - за счет больших накладных расходов.

При таком типе "обратного base64" кодирования мы можем получить 140 символов до 35 групп из четырех символов, которые становятся строкой из 35x3 = 105 двоичных символов, необработанных закодированных до 106 байтов.

До тех пор, повторяю, поскольку вы никогда не используете символы вне диапазона выше. Если вы это сделаете, вы можете увеличьте диапазон до 128 символов и 7 бит, таким образом, сохранив 12,5% вместо 25%; Затем 140 символов станут 126, необработанные закодированы до 127 байтов, и вы сохраните (141-127) = 14 байтов.

Сжатие

Если у вас гораздо более длинные строки, вы можете сжать их (т.е. вы используете такую функцию, как deflate() или gzencode() или gzcompress()). Либо прямой; в этом случае указанная строка становится 123 байта. Легко сделать.

Сжатие многих небольших строк: Подход Рубе Голдберга

Так как алгоритмы сжатия учатся, и в начале они не осмеливаются ничего принять, маленькие строки не будут сильно сжиматься. Они "все начинаются", так сказать. Как двигатель, когда он работает холодно, характеристики хуже.

Если у вас есть "corpus" текста, из которого взяты эти строки, вы можете использовать трудоемкий трюк, который "разогревает" механизм сжатия и может удвоить (или лучше) его производительность.

Предположим, что у вас две строки, COMMON и TARGET (второй интересует вас). Если вы z-сжали COMMON, вы получили бы, скажем, ZCMN. Если вы сжали TARGET, вы получили бы ZTRGT.

Но, как я уже сказал, поскольку алгоритм сжатия gz ориентирован по потоку, и он узнает, как это происходит, коэффициент сжатия второй половины любого текста (при условии, что не происходит причудливого статистического распределения между половинами) всегда заметно выше, чем в первой половине.

Итак, если вам нужно сжать, скажем, COMMONTARGET, вы получите ZCMGHQI.

Обратите внимание, что первая часть строки, почти до конца, такая же, как и раньше. Действительно, если вы сжали COMMONFOOBAR, вы получили бы что-то вроде ZCMQKL. А вторая часть сжимается лучше, чем раньше, даже если считать область перекрытия как полностью принадлежащую ко второй строке.

И это трюк. Учитывая семейство строк (TARGET, FOOBAR, CASTLE BRAVO), мы сжимаем не строки, а конкатенацию этих строк с большим префиксом. Затем мы отбрасываем из результата общий сжатый префикс. Таким образом, TARGET берется из сжатия COMMONTARGET (который является ZCMGHQI) и становится GHQI вместо ZTRGT с коэффициентом усиления 20%.

Декодер делает обратное: данный GHQI, он сначала применяет общий сжатый префикс ZCM (который должен знать); затем он декодирует результат и, наконец, отбрасывает общий несжатый префикс, из которого ему нужно знать только длину заранее.

Итак, первое предложение выше (140 символов) становится 123 при сжатии; если я возьму остальную часть Декларации и использую ее в качестве префикса, она сжимается до 3355 байт. Этот префикс плюс мои 140 байтов составляет 3409 байт, из которых 3352 являются общими, оставляя 57 байтов.

Из-за стоимости хранения после несжатого префикса в кодере и сжатого префикса один раз в декодере , а вся операция выполняется в пять раз медленнее, теперь я могу получить эти 140 байтов до 57 вместо 123 - меньше половины предыдущего.

Этот трюк отлично подходит для небольших струн; для более крупных, преимущество не стоит боли. Кроме того, разные префиксы дают разные результаты. Лучшие префиксы - это те, которые содержат большинство последовательностей, которые могут появиться в пуле строк, упорядоченные по длине.

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