java - ¿Generación de número de secuencia distribuida?

apache-zookeeper sequences

Question

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

Por ejemplo, utilizando el tipo de SERIE Postgres http://www.neilconway.org/docs/sequences/

Sin embargo, 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 de números de secuencia de manera segura para múltiples clientes?

Answer 1

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

Probablemente debería expandirme sobre esto.

Los UUID tienen una garantía global única (si se evitan los basados ​​en números aleatorios, donde la singularidad es muy probable).

Su requisito "distribuido" se cumple, independientemente de cuántos generadores UUID utilice, por la singularidad global de cada UUID.

Su requisito de "hilo seguro" puede cumplirse seleccionando generadores UUID "seguro para hilos".

Se supone que su requisito de "número de secuencia" se cumple con la exclusividad global garantizada de cada UUID.

Tenga en cuenta que muchas implementaciones de números de secuencias de bases de datos (por ejemplo, Oracle) no garantizan el aumento monótonamente, o (incluso) el aumento de los números de secuencia (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 2

Ahora hay más opciones.

Esta pregunta es "vieja", llegué aquí, así que creo que podría ser útil dejar las opciones que conozco (hasta ahora):

• Podrías probar Hazelcast . En su versión 1.9, incluye una implementación distribuida de java.util.concurrent.AtomicLong
• También puedes 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.

Aclamaciones

Answer 3

El problema es similar a: en el mundo iscsi, 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.

Del mismo modo, uno puede usar los bits iniciales en el sistema distribuido de nodos para representar el ID de nodo y el resto puede ser monótonamente creciente.

Answer 4

Escribí un servicio simple que puede generar números semi-únicos no secuenciales de 64 bits de largo. 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, mira la página zUID : zUID

Answer 5

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

1. tener 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 tu cluster.
2. separe un rango entero para cada nodo (como la respuesta de Steven Schlanskter )
3. usar números aleatorios o UUID
4. usa algún dato, junto con la ID del nodo, y hash it all (o hmac it)

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

Answer 6

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

Answer 7

Puede hacer que cada nodo tenga una ID única (que puede tener de todos modos) y luego anteponerla al número de secuencia.

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

Único :-)

Alternativamente, si desea algún tipo de sistema centralizado, podría considerar hacer que su servidor de secuencia 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 8

Sé que esta es una pregunta antigua, pero también estábamos enfrentando la misma necesidad y no pudimos encontrar la solución que satisfaga nuestras necesidades. Nuestro requisito era obtener una secuencia única (0,1,2,3 ... n) de identificadores y, por lo tanto, el copo de nieve no ayudaba. Creamos nuestro propio sistema para generar los identificadores usando Redis. Redis tiene un solo hilo, por lo tanto, su mecanismo de lista / cola siempre nos daría 1 pop a la vez.

Lo que hacemos es crear un buffer de identificadores. Inicialmente, la cola tendrá de 0 a 20 identificadores listos para enviarse cuando se solicite. Múltiples clientes pueden solicitar una identificación y redis mostrará una identificación a la vez. Después de cada pop desde la izquierda, insertamos BUFFER + currentId a la derecha, lo que mantiene activa la lista de búferes. Implementación here

Answer 9

Si realmente tiene que ser globalmente secuencial, y no simplemente único, entonces consideraría crear un servicio único y simple para distribuir estos números.

Los sistemas distribuidos dependen de muchos pequeños servicios que interactúan, y para este tipo de tarea simple, ¿realmente necesita o se beneficiaría realmente de alguna otra solución compleja y distribuida?

Answer 10

Una solución que es decente es usar una generación basada en mucho tiempo. Se puede hacer con el respaldo de una base de datos distribuida.

Answer 11

Usando 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. Implementé algo como esto:

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

Luego ejecutó la siguiente declaración:

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

Si su aplicación lo permite, puede asignar un bloque de inmediato (ese era mi caso).

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

Si necesita mayor rendimiento y no puede asignar compensaciones por adelantado, puede implementar su propio servicio usando Flink para el procesamiento en tiempo real. Pude obtener incrementos de 100K por partición.

¡Espero eso ayude!

Answer 12

OK, esta es una pregunta muy antigua, que ahora estoy viendo por primera vez.

Tendrá que diferenciar entre los números de secuencia y los ID únicos que son (opcionalmente) fácilmente ordenables por un criterio específico (típicamente 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 buscar cosas como transmisiones de red, rangos de ventana para cada trabajador y tablas hash distribuidas para identificadores de trabajador únicos , pero es mucho trabajo.

Las identificaciones únicas son otra cuestión, existen varias buenas formas de generar identificaciones únicas de forma descentralizada:

a) Puede usar el servicio de red de identificación de copo de nieve de Twitter . Snowflake es un:

• Servicio en red, es decir, realiza una llamada de red para obtener una identificación ú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) Puede generar los ID únicos en los clientes, utilizando un enfoque derivado de cómo se crean los UUID y los ID de Snowflake. Hay varias opciones, pero algo como:

• Los 40 bits más significativos: una marca de tiempo; el tiempo de generación de la ID. (Estamos utilizando los bits más significativos para la marca de tiempo para que los identificadores puedan ordenarse por tiempo de generación).

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

• Los últimos 10 o más bits: un valor único para cada generador. Al usar esto, no necesitamos hacer ninguna sincronización entre generadores (que es extremadamente difícil), ya que todos los generadores producen identificaciones que no se superponen debido a este valor.

c) Puede generar los ID en los clientes, utilizando solo una marca de tiempo y un valor aleatorio. Esto evita la necesidad de conocer todos los generadores y asignar a cada generador un valor único. Por otro lado, no se garantiza que estos ID sean globalmente únicos, es muy probable que sean únicos. (Para colisionar, uno o más generadores tendrían que crear el mismo valor aleatorio al mismo tiempo). Algo similar a:

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

d) La salida más fácil, use UUID / GUID .

Answer 13

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

Config config = new Config();
config.addAddress("some.server.com:8291");
Redisson redisson = Redisson.create(config);
RAtomicLong atomicLong = redisson.getAtomicLong("anyAtomicLong");
atomicLong.incrementAndGet();