Generación de número de secuencia distribuida?

Question

En general, he implementado generación de número de secuencia usando secuencias de bases de datos en el pasado.

p. Ej. Uso de Postgres SERIAL tipo http://www.neilconway.org/docs/sequences/

Tengo curiosidad por saber cómo generar números de secuencia para grandes sistemas distribuidos donde no hay base de datos. ¿Alguien tiene alguna experiencia o sugerencia de una mejor práctica para lograr la generación del número de secuencia en un hilo seguro manera para múltiples clientes?

Answer 1

Usted podría tener cada nodo tiene un identificador único (que puede tener de todos modos) y luego agregar el prefijo que al número de secuencia.

Por ejemplo, el nodo 1 genera la secuencia de 001 a 00.001 001 a 00002 001-00003, etc., y el nodo 5 genera 005-00001 005-00002

:-) único

Alternativamente, si desea algún tipo de un sistema centralizado, podría considerar hacer que su secuencia servidor se distribuya en bloques. Esto reduce significativamente los gastos generales. Por ejemplo, en lugar de solicitar una nueva ID del servidor central para cada ID que debe asignarse, solicita ID en bloques de 10.000 desde el servidor central y luego solo tiene que hacer otra solicitud de red cuando se agote.

Answer 2

¿Por qué no utilizar un generador UUID (seguro para hilos)?

Probablemente debería ampliar esto.

UUID se garantiza que sea único global (si se evitan los basados ​​en números aleatorios, en los que la singularidad es sólo muy probable).

Su requisito "distribuido" se cumple, independientemente del número de generadores UUID se utiliza, por la singularidad global de cada UUID.

Su requisito de "hilo seguro" se puede cumplir seleccionando generadores UUID "seguro para subprocesos".

Su requisito de "número de secuencia" se supone que cumple la unicidad global garantizada de cada UUID.

Tenga en cuenta que muchas implementaciones de número de secuencia de bases de datos Oracle (por ejemplo) no garantizan ya sea monótona creciente, o (incluso) el aumento de números de secuencia (en una base por "conexión"). Esto se debe a que un lote consecutivo de números de secuencia se asigna en bloques "en caché" por conexión. Esto garantiza la singularidad global y mantiene la velocidad adecuada. ¡Pero los números de secuencia realmente asignados (a lo largo del tiempo) pueden mezclarse cuando hay asignaciones múltiples!

Answer 3

Si realmente tiene que ser globalmente secuencial, y no simplemente único, entonces yo consideraría la creación de un único servicio, simple para la dispensación de estos números.

Los sistemas distribuidos se basan en una gran cantidad de pequeños servicios que interactúan, y por este simple tipo de tarea, es lo que realmente necesitan o podrían realmente beneficiarse de alguna otra solución compleja, distribuida?

Answer 4

Existen algunas estrategias; pero ninguno de los que conozco puede distribuirse realmente y dar una secuencia real.

1. tienen un generador de números central. no tiene que ser una gran base de datos. memcached tiene un contador atómico rápido, en la gran mayoría de los casos es lo suficientemente rápido para todo su clúster.
2. separar un rango de números enteros para cada nodo (como Steven Schlanskter's answer)
3. uso de números aleatorios o UUID
4. usan alguna parte de los datos, junto con el ID del nodo, y hash que todos (o hmac IT)

personalmente, me inclinaría a los UUID, o memcached si quiero tener un espacio mayormente contiguo.

Answer 5

Ahora hay más opciones.

tú a esta pregunta es "viejo", que llegué aquí, así que creo que puede ser útil para salir de las opciones que conozco (hasta ahora):

• Usted podría intentar Hazelcast. En su versión 1.9, incluye una implementación distribuida de java.util.concurrent.AtomicLong
• También puede usar Zookeeper. Proporciona métodos para crear nodos de secuencia (anexados a nombres znode, prefiero usar los números de versión de los nodos). Tenga cuidado con esto: si no quiere números perdidos en su secuencia, puede que no sea lo que quiere.

Saludos

Answer 6

bien, esta es una pregunta muy antigua, que estoy viendo ahora en primer lugar.

Tendrá que diferenciar entre números de secuencia y identificadores únicos que están (opcionalmente) vagamente se puede ordenar por un criterio específico (por lo general el tiempo de generación). Los números de secuencia verdaderos implican conocimiento de lo que todos los demás trabajadores han hecho, y como tal requieren un estado compartido. No hay una manera fácil de hacerlo de una manera distribuida y de gran escala. Puede ver cosas como transmisiones de red, intervalos de ventanas para cada trabajador y distributed hash tables for unique worker IDs, pero es mucho trabajo.

identificadores únicos son otra cosa, hay varias buenas maneras de generar identificadores únicos de una manera descentralizada:

a) Se podría utilizar Twitter's Snowflake ID network service. Snowflake es un:

• Servicio en red, es decir, usted hace una llamada de red para obtener una ID única;
• que produce identificadores únicos de 64 bits que se ordenan por tiempo de generación;
• y el servicio es altamente escalable y (potencialmente) altamente disponible; cada instancia puede generar miles de ID por segundo y puede ejecutar múltiples instancias en su LAN/WAN;
• escrito en Scala, se ejecuta en la JVM.

b) Se podría generar los identificadores únicos de los propios clientes, utilizando un enfoque derivado de how UUIDs y se hacen los ID de copo de nieve. Hay varias opciones, pero algo en la línea de:

• Los más significativos 40 o más bits de marca de tiempo: Un ; el tiempo de generación de la ID. (Estamos utilizando los bits más significativos de la marca de tiempo para hacer identificadores de orden-poder por tiempo de generación.)

• Los siguientes 14 bits de más o menos: Un contador por cada generador, la que cada generador de incrementos en uno por cada nueva identificación generada Esto garantiza que los ID generados en el mismo momento (las mismas marcas de tiempo) no se superpongan.

• Los últimos 10 bits aproximadamente: Un valor único para cada generador. Al usar esto, no necesitamos hacer ninguna sincronización entre generadores (lo cual es extremadamente difícil), ya que todos los generadores producen identificaciones no superpuestas debido a este valor.

c) Se podría generar los identificadores de los clientes, utilizando sólo una marca de tiempo y valor aleatorio. Esto evita la necesidad de conocer todos los generadores y asigna a cada generador un valor único. Por otro lado, tales ID no son garantizados para ser únicos en el mundo, son solo muy altamente probable para ser únicos. (Para chocar, uno o más generadores tendrían que crear el mismo valor aleatorio exactamente al mismo tiempo.) Algo a lo largo de las líneas de:

• Los más significativos 32 bits: Marca de tiempo, el tiempo de generación de la CARNÉ DE IDENTIDAD.
• Los 32 bits menos significativos: 32 bits de aleatoriedad, generados de nuevo para cada ID.

d) La salida fácil, use UUIDs/GUIDs.

Answer 7

Se puede hacer con Redisson. Implementa la versión distribuida y escalable de AtomicLong. Aquí está el ejemplo:

Config config = new Config(); 
config.addAddress("some.server.com:8291"); 

Redisson redisson = Redisson.create(config); 
RAtomicLong atomicLong = redisson.getAtomicLong("anyAtomicLong"); 
atomicLong.incrementAndGet(); 

Answer 8

He escrito un servicio simple que puede generar números semi-únicos no secuenciales de 64 bits de longitud larga. Se puede implementar en múltiples máquinas para redundancia y escalabilidad. Utiliza ZeroMQ para mensajes. Para obtener más información sobre cómo funciona, consulte la página de github: zUID

Answer 9

Utilizando una base de datos puede alcanzar más de 1,000 incrementos por segundo con un solo núcleo. Es bastante fácil. Puede usar su propia base de datos como backend para generar ese número (como debería ser su propio agregado, en términos de DDD).

Tuve lo que parece un problema similar. Tenía varias particiones y quería obtener un contador de compensación para cada una.He implementado algo como esto:

CREATE DATABASE example; 
USE example; 
CREATE TABLE offsets (partition INTEGER, offset LONG, PRIMARY KEY (partition)); 
INSERT offsets VALUES (1,0); 

A continuación, ejecuta la siguiente instrucción:

SELECT @offset := offset from offsets WHERE partition=1 FOR UPDATE; 
UPDATE offsets set offset=@offset+1 WHERE partition=1; 

Si su aplicación le permite, se puede asignar un bloque a la vez (que era mi caso).

SELECT @offset := offset from offsets WHERE partition=1 FOR UPDATE; 
UPDATE offsets set offset=@offset+100 WHERE partition=1; 

Si necesita más rendimiento de un no se puede asignar compensaciones de antelación puede implementar su propio servicio utilizando Flink para el procesamiento en tiempo real. Pude obtener incrementos de 100K por partición.

Espero que ayude!

Answer 10

La generación de ID distribuida se puede archivar con Redis y Lua. La implementación está disponible en Github. Produce identificadores únicos distribuidos y k-clasificables.

Answer 11

El problema es similar a: En iscsi world, donde cada luns/volúmenes tienen que ser identificables de forma exclusiva por los iniciadores que se ejecutan en el lado del cliente. El estándar iscsi dice que los primeros bits deben representar la información del proveedor/proveedor de almacenamiento y el resto monótonamente creciente.

De forma similar, se pueden utilizar los bits iniciales en el sistema distribuido de nodos para representar el ID de nodo y el resto puede aumentar monótonamente.