¿Cuál es el algoritmo Hi / Lo?

¿Cuál 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 encontré una buena explicación de cómo funciona.

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

La idea básica es que tiene dos números para formar una clave principal: un número “alto” y un número “bajo”. Un cliente puede básicamente incrementar la secuencia “alta”, sabiendo que puede generar claves de forma segura desde todo el rango del valor “alto” anterior con la variedad de valores “bajos”.

Por ejemplo, supongamos 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 usa 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) para poder establecer las claves primarias en el lado del cliente, en lugar de insertar valores sin claves primarias y luego recuperarlos en el cliente. Aparte de cualquier otra cosa, significa que puede hacer fácilmente las relaciones entre padres e hijos y tener las claves en su lugar antes de hacer inserciones, lo que simplifica el procesamiento por lotes.

Además de la respuesta de Jon:

Se usa para poder desconectarse. Un cliente puede pedirle al servidor un número alto y crear objetos que aumenten el número de lo mismo. No necesita contactar al servidor hasta que se agote el rango lo.

Mejor que el asignador Hi-Lo, es el asignador “Linear Chunk”. Esto utiliza un principio similar basado en tablas pero asigna trozos pequeños, 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 las siguientes, por ejemplo, 20 teclas (que luego se mantienen como un rango en el servidor y se utilizan según sea necesario):

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

Siempre que pueda comprometer esta transacción (use rebashs para manejar la contención), ha asignado 20 claves y puede dispensarlas según sea necesario.

Con un tamaño de porción 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 asignación es equivalente a hi-lo.

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

Esto evita el impulso de las claves compuestas (que en realidad nunca fueron una buena idea) y evita el desperdicio de lo-palabras completas cuando el servidor se reinicia. Genera valores clave “amigables” a escala humana.

La idea del Sr. Ambler, en comparación, asigna los 16 o 32 bits altos, y genera grandes valores clave no humanos como el incremento de las palabras.

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 

De hecho, me correspondía con el Sr. Ambler en los años 90 para sugerirle este esquema mejorado, pero él estaba demasiado atascado y obstinado para reconocer las ventajas y la simplicidad clara de usar una línea numérica lineal.

Desde el punto de vista del diseño, su solución es fundamentalmente más compleja en la línea de números (claves compuestas, productos de hi_word grandes) que Linear_Chunk sin obtener ningún beneficio comparativo. Su diseño está matemáticamente probado deficiente.

Los algoritmos hi / lo dividen el dominio de las secuencias en grupos “hi”. Un valor “hi” se asigna sincrónicamente. A cada grupo “hi” se le asigna un número máximo de entradas “lo”, que pueden asignarse fuera de línea sin preocuparse por las entradas duplicadas concurrentes.

  1. El token “hi” es asignado por la base de datos, y se garantiza que dos llamadas simultáneas verán valores consecutivos únicos
  2. Una vez que se recupera un token “hi”, 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) 

    siendo aplicado desde el valor inicial de:

     [(hi -1) * incrementSize) + 1) 
  4. Cuando se utilizan todos los valores “lo”, se recupera un nuevo valor “hi” y el ciclo continúa

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

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

enter image description here

Si bien el optimizador de alta / baja 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 identificación.

Hibernate ofrece el optimizador agrupado-lo , que combina una estrategia de generador hi / lo con un mecanismo de asignación de secuencia de interoperabilidad. Este optimizador es tanto eficiente como interoperable con otros sistemas, siendo un mejor candidato que la estrategia anterior de identificador hi / lo heredado.

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

  • 010000010 Jason
  • 010000011 David
  • 010000012 Theo

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

  • 020000045 Rupert
  • 020000046 Oswald
  • 020000047 Mario

Por lo tanto, cuando utiliza la replicación de la base de datos (sin importar la marca), todas las claves primarias y los datos se combinan de forma fácil y natural sin tener que preocuparse por llaves duplicadas, colisiones, etc.

Esta es la mejor manera de ir en este escenario.