¿Qué es el algoritmo Hi / Lo?

464

¿Qué es el algoritmo Hi / Lo?

Encontré esto en la documentación de NHibernate (es un método para generar claves únicas, sección 5.1.4.2), pero no he encontrado una buena explicación de cómo funciona.

Sé que Nhibernate lo maneja, y no necesito saber el interior, pero tengo curiosidad.

database algorithm nhibernate hibernate hilo DiegoCofre
fuente

Respuestas:

541

La idea básica es que tiene dos números para formar una clave primaria: un número "alto" y un número "bajo". Básicamente, un cliente puede incrementar la secuencia "alta", sabiendo que puede generar claves de forma segura a partir del rango completo del valor "alto" anterior con la variedad de valores "bajos".

Por ejemplo, suponiendo que tiene una secuencia "alta" con un valor actual de 35, y el número "bajo" está en el rango 0-1023. Luego, el cliente puede incrementar la secuencia a 36 (para que otros clientes puedan generar claves mientras está usando 35) y saber que las claves 35/0, 35/1, 35/2, 35/3 ... 35/1023 son todo disponible.

Puede ser muy útil (especialmente con ORM) poder establecer las claves primarias en el lado del cliente, en lugar de insertar valores sin claves primarias y luego recuperarlas en el cliente. Además de cualquier otra cosa, significa que puede establecer fácilmente relaciones padre / hijo y tener todas las claves en su lugar antes de hacer cualquier inserción, lo que simplifica su procesamiento por lotes.

Jon Skeet
fuente
14
¿Está diciendo que los "rangos bajos" se coordinan dentro del cliente, mientras que la "secuencia alta" corresponde a una secuencia de DB?
Chris Noe
14
¿Los valores hi & lo se componen típicamente en un solo valor entero o como una clave comercial de dos partes?
Chris Noe
51
como una dirección IP entonces: ICANN le da un número alto de 'red', luego tiene tantos números bajos de 'host' como desee, dentro del límite del rango CIDR que se le da.
gbjbaanb
66
@ Adam: Básicamente, nada, es potencialmente más barato incrementar un valor (la parte "alta") que generar un montón de claves. (Es potencialmente mucho más barato en términos de transferencia de datos; puede "reservar" una gran cantidad de claves con un ancho de banda mínimo).
Jon Skeet
44
@ Adam: Eso es cierto si las teclas son solo números. No tanto para los GUID :) Pero sí, en el caso de números simples, cualquier "incremento atómico en una cantidad fija" servirá. Eso es efectivamente lo que está haciendo hi-lo, si lo piensas como un número dividido en dos secciones.
Jon Skeet el
157

Además de la respuesta de Jon:

Se utiliza para poder trabajar desconectado. Un cliente puede pedirle al servidor un número alto y crear objetos que aumenten el número lo mismo. No necesita ponerse en contacto con el servidor hasta que se agote el rango inferior.

Stephan Eggermont
fuente
1
Prefiero esto por brevedad.
Desarrollador Marius Žilėnas
34

Como esta es una pregunta muy común, escribí este artículo , en el que se basa esta respuesta.

Los algoritmos hi / lo dividen el dominio de secuencias en grupos "hi". Se asigna un valor "hola" sincrónicamente. Cada grupo "hola" recibe un número máximo de entradas "lo", que puede asignarse fuera de línea sin preocuparse por las entradas duplicadas concurrentes.

  1. La base de datos asigna el token "hola" y se garantiza que dos llamadas simultáneas verán valores únicos consecutivos
  2. Una vez que se recupera un token "hola" solo necesitamos el "incrementSize" (el número de entradas "lo")

  3. El rango de identificadores viene dado por la siguiente fórmula:

    [(hi -1) * incrementSize) + 1, (hi * incrementSize) + 1)

    y el valor "lo" estará en el rango:

    [0, incrementSize)

    se aplica desde el valor inicial de:

    [(hi -1) * incrementSize) + 1)

  4. Cuando se utilizan todos los valores "lo", se obtiene un nuevo valor "hola" y el ciclo continúa

Puede encontrar una explicación más detallada en este artículo :

Y esta presentación visual también es fácil de seguir:

ingrese la descripción de la imagen aquí

Si bien el optimizador hi / lo está bien para optimizar la generación de identificadores, no funciona bien con otros sistemas que insertan filas en nuestra base de datos, sin saber nada sobre nuestra estrategia de identificadores.

Hibernate ofrece el optimizador agrupado-lo , que ofrece las ventajas de la estrategia de generador de alta / baja al mismo tiempo que proporciona interoperabilidad con otros clientes de terceros que no conocen esta estrategia de asignación de secuencia.

Al ser eficiente e interoperable con otros sistemas, el optimizador agrupado-lo es un candidato mucho mejor que la estrategia de identificación heredada hi / lo.

Vlad Mihalcea
fuente
Realmente no te entiendo a veces jajaja así: mientras que el optimizador hi / lo está bien para optimizar la generación de identificadores (Ok, bueno), no funciona bien con otros sistemas (¿qué quieres decir con otros sistemas? ¿Cuáles son los primeros unos?) insertando filas en nuestra base de datos (¿No se utiliza la generación de identificadores para insertar filas también?), sin saber nada sobre nuestra estrategia de identificadores.
Adelin
Otros sistemas, como un DBA que intenta ejecutar una instrucción INSERT. Si lee los datos de la secuencia actual, ¿cree que es fácil descubrir el siguiente valor de identificación sabiendo que usamos hilo en esta tabla de DB en particular?
Vlad Mihalcea
Mis disculpas si el comentario no es adecuado para su respuesta, pero me preguntaba qué optimizador se usa de manera predeterminada ¿O depende de DB (estoy usando PostgreSQL)? Porque no puedo entender la relación entre el valor de secuencia actual y las ID generadas. Estoy usando @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "name") @SequenceGenerator(name="name", sequenceName = "name_seq", allocationSize=100)para mis identificaciones.
Stefan Golubović
1
Desde Hibernate 5, Pooled es el nuevo Optimizer, no Hi / lo. Consulte este artículo para obtener más detalles sobre el Optimizador agrupado.
Vlad Mihalcea
@VladMihalcea, creo que tienes un error tipográfico en la viñeta tres, primer fragmento en , (hi * incrementSize) + 1)... debería ser , hi * incrementSize), ¿verdad?
Huiagan
23

Lo es un asignador en caché que divide el espacio de teclas en grandes fragmentos, generalmente basado en el tamaño de algunas palabras de máquina, en lugar de los rangos de tamaño significativo (por ejemplo, obtener 200 teclas a la vez) que un humano podría elegir con sensatez.

El uso de Hi-Lo tiende a desperdiciar grandes cantidades de claves en el reinicio del servidor y genera grandes valores de clave hostiles para los humanos.

Mejor que el asignador Hi-Lo, es el asignador "Linear Chunk". Esto utiliza un principio similar basado en tablas, pero asigna pequeños trozos de tamaño conveniente y genera buenos valores amigables para los humanos.

create table KEY_ALLOC (
    SEQ varchar(32) not null,
    NEXT bigint not null,
    primary key (SEQ)
);

Para asignar la siguiente, digamos, 200 teclas (que luego se mantienen como un rango en el servidor y se usan según sea necesario):

select NEXT from KEY_ALLOC where SEQ=?;
update KEY_ALLOC set NEXT=(old value+200) where SEQ=? and NEXT=(old value);

Siempre que pueda confirmar esta transacción (usar reintentos para manejar la contención), ha asignado 200 claves y puede dispensarlas según sea necesario.

Con un tamaño de fragmento de solo 20, este esquema es 10 veces más rápido que la asignación de una secuencia de Oracle, y es 100% portátil entre todas las bases de datos. El rendimiento de la asignación es equivalente a hi-lo.

A diferencia de la idea de Ambler, trata el espacio de teclas como una línea numérica lineal contigua.

Esto evita el impulso de las claves compuestas (que nunca fueron realmente una buena idea) y evita desperdiciar palabras bajas completas cuando se reinicia el servidor. Genera valores clave "amigables" a escala humana.

La idea del Sr. Ambler, en comparación, asigna los altos 16 o 32 bits, y genera grandes valores clave hostiles a los humanos a medida que aumentan las palabras hi.

Comparación de claves asignadas: 

Linear_Chunk       Hi_Lo
100                65536
101                65537
102                65538
.. server restart
120                131072
121                131073
122                131073
.. server restart
140                196608

En cuanto al diseño, su solución es fundamentalmente más compleja en la línea numérica (teclas compuestas, productos grandes de alta palabra) que Linear_Chunk sin lograr ningún beneficio comparativo.

El diseño Hi-Lo surgió temprano en el mapeo OO y la persistencia. En la actualidad, los marcos de persistencia, como Hibernate, ofrecen asignadores más simples y mejores por defecto.

Thomas W
fuente
44
Buena publicación, pero no estás respondiendo la pregunta.
orbfish
1
+1 para una respuesta interesante. Estoy de acuerdo en que la gran mayoría de las aplicaciones no obtienen ninguna ventaja de Hi-Lo sobre el enfoque más simple; sin embargo, creo que Hi-Lo se adapta mejor al caso especial de múltiples asignadores en aplicaciones altamente concurrentes.
richj
1
Gracias @richj! Mi punto es que puede usar asignadores múltiples o tamaños de bloque grandes con "asignación de bloque lineal", pero que, a diferencia de Hi / Lo, mantiene una correspondencia lineal del asignador NEXT_VAL con las teclas de la tabla y es sintonizable. A diferencia de HiLo, no se necesita multiplicación, ¡simplemente no es necesario! El multiplicador y almacenamiento de NEXT_HI hace que HiLo sea más complejo y rompe la capacidad de ajuste, ya que al cambiar el tamaño de bloque cambiará arbitrariamente la siguiente clave que se emitirá ... Ver: literatejava.com/hibernate/…
Thomas W
2
Estoy interesado en múltiples asignadores independientes. Con Hi-Lo es obvio que el valor alto se puede dividir en ID de asignador / ID de bloque. No era inmediatamente obvio (para mí) que se puede aplicar el mismo enfoque a Linear Chunk, pero es básicamente el mismo problema de dividir el rango total entre los asignadores. Lo tengo ahora. Gracias.
richj
1
Oh, después de pensarlo, creo que la columna SEQ se asigna a un nombre de tabla. Por ejemplo, hay un asignador de la tabla Clientes, uno para la tabla Órdenes, etc. Perdóname, soy lento, a veces.
Rock Anthony Johnson
1

Descubrí que el algoritmo Hi / Lo es perfecto para múltiples bases de datos con escenarios de replicación basados ​​en mi experiencia. Imagina esto. tiene un servidor en Nueva York (alias 01) y otro servidor en Los Ángeles (alias 02), entonces tiene una tabla PERSON ... así que en Nueva York cuando se crea una persona ... siempre usa 01 como valor HI y el valor LO es el siguiente secuencial. por ejemplo.

  • 010000010 Jason
  • 010000011 David
  • 010000012 Theo

en Los Ángeles siempre usa el HI 02. por ejemplo:

  • 020000045 Rupert
  • 020000046 Oswald
  • 020000047 Mario

Entonces, cuando usa la replicación de la base de datos (sin importar la marca), todas las claves primarias y los datos se combinan fácil y naturalmente sin preocuparse por duplicar claves primarias, colisiones, etc.

Esta es la mejor manera de avanzar en este escenario.

Theo
fuente
No funciona en Hibernate. El algrotirm HiLo obtiene un nuevo valor de secuencia en cada transacción, por lo que el contador HI aumenta de forma acorde. Pero en su ejemplo, el contador HI siempre es constante para un DB.
Dmitry1405