477 votos

¿Cuál es el Hi/Lo algoritmo?

¿Cuál es el Hi/Lo algoritmo?

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

Sé que Nhibernate controla, y no tengo la necesidad de conocer el interior, pero tengo curiosidad.

559voto

Jon Skeet Puntos 692016

La idea básica es que usted tiene dos números para hacer una clave principal a un "alto" y "bajo" número. Un cliente puede, básicamente, el incremento de la "alta" de la secuencia, sabiendo que puede, a continuación, de forma segura generar claves de toda la gama de la anterior "alto" valor con la variedad de "baja" de los valores.

Por ejemplo, suponiendo que tiene una "alta" de la secuencia con un valor actual de 35, y el "escaso" número está en el rango 0û1023. A continuación, el cliente puede incrementar la secuencia 36 (para otros clientes para que sean capaces de generar las llaves mientras está usando 35) y saber que teclas 35/0, 35/1, 35/2, 35/3... 35/1023 están todos disponibles.

Puede ser muy útil (especialmente con Orm) para ser capaz de establecer las claves principales en el lado del cliente, en lugar de inserción de los valores sin necesidad de claves primarias y luego ir a por ellos de nuevo en el cliente. Aparte de cualquier otra cosa, esto significa que usted puede fácilmente hacer relaciones padre/hijo y tiene las llaves de todos en su lugar antes de hacer cualquier inserta, lo que hace que la formación de lotes ellos más simple.

161voto

Stephan Eggermont Puntos 11224

Además de Jon respuesta:

Se utiliza para poder trabajar desconectado. Un cliente puede pedir al servidor para un hi número y crear objetos de aumentar el número lo mismo. No necesita comunicarse con el servidor hasta que el rango de lo que se usa.

37voto

Vlad Mihalcea Puntos 3628

El hi/lo de los algoritmos de divide las secuencias de dominio en "hola" a los grupos. Un "hola" valor es asignado de forma sincrónica. Cada "hola" grupo se le da un número máximo de "lo" de las entradas, que se pueden asignar off-line sin tener que preocuparse acerca de los concurrentes entradas duplicadas.

  1. El "hola" token es asignado por la base de datos, y dos llamadas simultáneas se garantiza que vea los únicos valores consecutivos
  2. Una vez que un "hola" token se recupera solo necesitamos el "incrementSize" (el número de "lo" entradas)
  3. Los identificadores rango está dado por la siguiente fórmula:

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

    y el "lo" valor estará en la gama:

    [0, incrementSize)
    

    se aplica desde el valor de inicio:

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

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

Y esta presentación visual es fácil de seguir así:

enter image description here

26voto

Thomas W Puntos 7179

Mejor que el Hi-Lo asignador, es el "Lineal Chunk" asignador. Este utiliza una tabla similar basado en principio, pero asigna pequeño, muy bien-trozos del tamaño y genera agradable amigable valores.

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

Para asignar los próximos, digamos, 20 teclas (que se celebró como un rango en el server y se usa 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);

El suministro de usted puede confirmar esta transacción (uso de reintentos para manejar una disputa), se han asignado 20 teclas y se puede prescindir de ellos, según sea necesario.

Con un trozo de tamaño de tan sólo 20, este sistema es 10 veces más rápido que la asignación de un Oráculo de la secuencia, y es 100% portable entre todas las bases de datos. El rendimiento de la asignación es equivalente a hi-lo.

A diferencia de Ambler la idea, de que trata el keyspace como un contiguos lineal numberline.

Esto evita el impulso de claves compuestas (que nunca fueron realmente una buena idea) y evita el desperdicio de todo lo-palabras cuando se reinicia el servidor. Genera "amigable", a escala humana los valores de la clave.

El señor Ambler la idea, por comparación, asigna el alta de 16 o 32 bits, y genera gran ser humano hostil valores clave como el hi-palabras de incremento.

Comparación de asignación de teclas:

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 correspondió con el Señor Ambler de vuelta en los 90 sugieren que esta mejora de esquema para él, pero él estaba demasiado pegado y obstinado a reconocer las ventajas y clara sencillez de uso de un número lineal-línea.

El diseño inteligente, su solución es fundamentalmente más complejo en el número de línea (las claves compuestas, gran hi_word productos) que Linear_Chunk mientras que el logro de ninguna ventaja comparativa. Su diseño es, pues, matemáticamente demostrado deficientes.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X