optimization - length - long title seo

Redis int la representación de una cadena es más grande cuando la cadena es más de 7 bytes pero más pequeña de lo contrario

Question

Estoy tratando de reducir el tamaño de los objetos de Redis tanto como pueda y he tomado toda la semana para experimentar con él.

Al probar diferentes representaciones de datos, descubrí que una representación int de la cadena "hello" da como resultado un objeto más pequeño. Puede que no parezca mucho, pero si tiene muchos datos, puede hacer una diferencia entre usar unos pocos GB de memoria y docenas de ellos.

Mira el siguiente ejemplo (puedes probarlo tú mismo si quieres):

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

En particular, debería mirar serializedlength que es 6 (bytes) en este caso.

Ahora, mira la siguiente representación de la misma:

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

Como puede ver, da como resultado un objeto de byte más corto (tenga en cuenta también la codificación: int, que creo que sugiere que los ints se manejen de una manera más eficiente).

Con la cadena "hola w" (verás en unos momentos por qué no usé "hola mundo" en su lugar) obtenemos un ahorro aún mayor cuando se representa como un 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

Se ve bien siempre y cuando no excedas la cadena de 7 bytes. Mira lo que sucede con una representación de "hola 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

Como puede ver, el int (12 bytes) es más grande que la representación de cadena (9 bytes).

Mi pregunta aquí es, ¿qué está sucediendo detrás de escena cuando representas una cadena como un int, que es más pequeña hasta que alcanzas los 7 bytes?

¿Hay una manera de aumentar este límite como lo hace con "list-max-ziplist-entries / list-max-ziplist-value" o una manera inteligente de optimizar este proceso para que siempre (o casi) resulte en un objeto más pequeño? que una cuerda?

ACTUALIZAR

He experimentado más con otros trucos, y en realidad puedes tener más ints que cadenas, independientemente de su tamaño, pero eso implicaría un poco más de trabajo en el modelado de la estructura de datos.

Descubrí que si se divide la representación int de una cadena en partes de ~ 8 números cada una, termina siendo más pequeña.

Tome como ejemplo la palabra "Hello World Hi Universe" y cree tanto una cadena como int SET:

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

Los resultados son los siguientes:

> 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

Como puede ver, tenemos el conjunto de int más pequeño por 3 bytes.

El problema en esto será cómo organizar tal cosa, pero muestra que es posible, no obstante.

Aún así, no sé dónde se establece este límite. El uso persistente de ~ 700K de la memoria (incluso cuando no tiene datos dentro) me hace pensar que hay un "grupo" predefinido dedicado a la optimización de los conjuntos int.

Actualización2

Creo que he encontrado dónde se define este "conjunto" de intset en la fuente de Redis.

En la línea 81 en el archivo redis.h está la definición de REDIS_SHARED_INTEGERS establecida en 10000

REDISH_SHARED_INTEGERS

Sospecho que es el que define el límite de la longitud de un byte intset.

Tengo que intentar recompilarlo con un valor más alto y ver si puedo usar un valor int más largo (lo más probable es que asigne más memoria si es el que pienso).

ACTUALIZACIÓN3

¡Quiero agradecer a Antirez por la respuesta! No esperaba eso.

Como me hizo notar, len! = Uso de memoria .

Avancé en mi experimento y vi que los objetos ya estaban ligeramente comprimidos (serializados). Puede que me haya perdido algo de la documentación de Redis.

La confirmación proviene de analizar una clave Redis con el comando redis-memory-for- key , que en realidad devuelve el uso de la memoria y no la longitud serializada.

Por ejemplo, tomemos la cadena "hello" e int que usamos antes, y veamos cuál es el resultado:

~ # 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

Como se puede observar, el intset es más pequeño (87 bytes) que la cadena (101 bytes) de todos modos.

Actualización 4

Sorprendentemente, un conjunto de entrada más largo parece afectar su longitud serializada pero no el uso de memoria.

Esto hace que sea posible crear una asignación de 2 dígitos en caracteres mientras que sigue siendo más eficiente en memoria que una cadena, sin siquiera fragmentarla.

Por mapeo de 2 dígitos-charla quiero decir que en lugar de mapear "hola" a "85121215" lo mapeamos a dígitos con una longitud fija de 2, prefijándolos con "0" si el dígito <10 es como "0805121215".

Una secuencia de comandos personalizada luego procedería separando cada dos dígitos y convirtiéndolos a su carácter equivalente:

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

Esto es suficiente para evitar la desambiguación (como "o" y "ae" que dan como resultado el dígito "15").

Le mostraré esto funciona creando otro conjunto y, por lo tanto, analizando el uso de la memoria como lo hice antes:

> SET test:9 "0805070715"

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

Puedes ver que tenemos un triunfo de memoria aquí.

La misma cadena de "hola" comprimida con Smaz para comparación:

>>> 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

Answer 1

Mi pregunta aquí es, ¿qué está sucediendo detrás de escena cuando representas una cadena como un int, que es más pequeña hasta que alcanzas los 7 bytes?

Tenga en cuenta que el número entero que proporcionó como prueba # 6 ya no se codifica realmente como un número entero, sino como en bruto:

Prueba SET: 6 "85771502315"

Valor en: 0xb6c9f470 refcount: 1 codificación: serializedlength sin procesar: 12 lru: 9535913 lru_seconds_idle:

Así que vemos que un valor "sin procesar" ocupa un byte más la longitud de su representación de cadena. En la memoria obtienes eso más la sobrecarga del valor.

La codificación de enteros, sospecho, codifica un número como un entero de 32 bits; entonces siempre necesitará cinco bytes, uno para indicar su tipo y cuatro para almacenar esos 32 bits.

Tan pronto como se desborda el número entero máximo representable en 32 bits, que es 2 billones o 4, dependiendo de si usa un signo o no, necesita volver a la codificación bruta.

Asi que probablemente

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

Ahora, ¿cómo puede comprimir una representación de cadena PROPORCIONADA QUE USTED UTILIZA SOLAMENTE UN CONJUNTO ASCII?

Puede obtener la cadena (140 caracteres):

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

y convertir cada carácter a una representación de seis bits; básicamente su índice en la cadena

"ABCDEFGHIJKLMNOPQRSTUVWXYZ01234 abcdefghijklmnopqrstuvwxyz56789."

que es el conjunto de todos los caracteres que puedes usar.

Ahora puede codificar cuatro de estos "caracteres de solo texto" en tres "caracteres binarios", una especie de "codificación de base 64 inversa"; La codificación base64 obtendrá tres caracteres binarios y creará una secuencia de cuatro bytes de caracteres ASCII.

Si tuviéramos que codificarlo como grupos de enteros, ahorraríamos unos pocos bytes, tal vez reducirlos a 130 bytes, al costo de una sobrecarga mayor.

Con este tipo de codificación "reverse base64", podemos obtener de 140 caracteres a 35 grupos de cuatro caracteres, que se convierten en una cadena de 35x3 = 105 caracteres binarios, codificados en bruto a 106 bytes.

Mientras tanto, repito, ya que nunca usas caracteres fuera del rango anterior . Si lo hace, puede ampliar el rango a 128 caracteres y 7 bits, ahorrando así un 12,5% en lugar de un 25%; Luego, 140 caracteres se convertirán en 126, codificados en bruto a 127 bytes, y usted ahorra (141-127) = 14 bytes.

Compresión

Si tiene cadenas mucho más largas, puede comprimirlas (es decir, usar una función como deflate() o gzencode() o gzcompress() ). O bien recto en cuyo caso la cadena anterior se convierte en 123 bytes. Fácil de hacer.

Comprimiendo muchas cuerdas pequeñas: el enfoque de Rube Goldberg

Como los algoritmos de compresión aprenden, y al principio no se atreven a asumir nada, las cadenas pequeñas no se comprimirán mucho. Están "todos comenzando", por así decirlo. Al igual que un motor, cuando se ejecuta frío las actuaciones son inferiores.

Si tiene un "corpus" del texto del que provienen estas cadenas, puede usar un truco que consume mucho tiempo y que "calienta" el motor de compresión y puede duplicar (o mejorar) su rendimiento.

Supongamos que tiene dos cadenas, COMMON y TARGET (la segunda es la que le interesa). Si usas ZCMN , obtendrás, por ejemplo, ZCMN . Si comprimiste TARGET obtendrías ZTRGT .

Pero como dije, ya que el algoritmo de compresión gz está orientado al flujo , y aprende a medida que avanza, la relación de compresión de la segunda mitad de cualquier texto ( siempre que no haya cambios de distribución estadísticos extraños entre las mitades ) siempre es apreciablemente más alta que La de la primera mitad.

Entonces, si fueras a comprimir, por ejemplo, COMMONTARGET , obtendrías ZCMGHQI .

Observe que la primera parte de la cadena, casi hasta el final, es la misma que antes. De hecho, si comprimiste COMMONFOOBAR , obtendrías algo como ZCMQKL . Y la segunda parte se comprime mejor que antes, incluso si consideramos que el área de superposición pertenece totalmente a la segunda cadena.

Y este es el truco. Dada una familia de cadenas ( TARGET , FOOBAR , CASTLE BRAVO ), no comprimimos las cadenas, sino la concatenación de esas cadenas con un prefijo grande . Luego descartamos del resultado el prefijo comprimido común. Así, TARGET se toma de la compresión de COMMONTARGET (que es ZCMGHQI ) y se convierte en GHQI lugar de ZTRGT , con una ganancia del 20%.

El decodificador hace lo contrario: dado GHQI , primero aplica el prefijo comprimido común ZCM ( que debe conocer ); luego descodifica el resultado y, finalmente, descarta el prefijo común sin comprimir, del cual solo necesita conocer la longitud de antemano.

Así que la primera oración anterior (140 caracteres) se convierte en 123 cuando se comprime por sí misma; si tomo el resto de la Declaración y la uso como prefijo, se comprime a 3355 bytes. Este prefijo más mis 140 bytes se convierte en 3409 bytes, de los cuales 3352 son comunes, quedando 57 bytes.

Al costo de almacenar una vez el prefijo sin comprimir en el codificador, y el prefijo comprimido una vez en el decodificador, y todo el thingamajig ejecutándose cinco veces más lento , ahora puedo obtener esos 140 bytes a 57 en lugar de 123 - menos de la mitad de antes de.

Este truco funciona muy bien para cuerdas pequeñas; Para los más grandes, la ventaja no vale la pena. Además, los diferentes prefijos producen resultados diferentes. Los mejores prefijos son aquellos que contienen la mayoría de las secuencias que probablemente aparezcan en el conjunto de cadenas, ordenadas por longitud creciente.

Bonificación adicional: el prefijo comprimido también se duplica como una especie de encriptación débil, ya que sin eso, no se pueden decodificar fácilmente las cadenas comprimidas, incluso si es posible recuperar algunas partes de ellas.