¿Generación de números de secuencia distribuidos?

103

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

por ejemplo, utilizando el tipo SERIAL de 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 una 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 una manera segura para múltiples clientes?

Jon
fuente
Esta pregunta es antigua, pero por favor vea mi nueva respuesta stackoverflow.com/questions/2671858/…
Jesper M
¿Cómo usas nextval.org? El sitio web es un poco extraño y no sé de qué se trata. ¿Es algún comando de Unix? ¿O algún servicio en la nube?
diegosasw

Respuestas:

116

Bien, esta es una pregunta muy antigua, que ahora veo por primera vez.

Deberá diferenciar entre números de secuencia e ID únicos que (opcionalmente) se pueden ordenar libremente por un criterio específico (generalmente tiempo de generación). Los números de secuencia verdaderos implican el conocimiento de lo que han hecho todos los demás trabajadores y, como tales, requieren un estado compartido. No hay una manera fácil de hacer esto de una manera distribuida y a gran escala. Puede buscar en cosas como transmisiones de red, rangos en ventanas para cada trabajador y tablas hash distribuidas para identificaciones de trabajador únicas , pero es mucho trabajo.

Los ID únicos son otra cuestión, hay varias buenas formas de generar ID únicos de manera descentralizada:

a) Puede utilizar el servicio de red Snowflake ID de Twitter . El copo de nieve es un:

  • Servicio en red, es decir, realiza una llamada de red para obtener una identificación única;
  • que produce ID únicos de 64 bits que están ordenados 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 varias instancias en su LAN / WAN;
  • escrito en Scala, se ejecuta en la JVM.

b) Puede generar los ID únicos en los propios clientes, utilizando un enfoque derivado de cómo se crean los UUID y los ID de Snowflake. Hay varias opciones, pero algo parecido a:

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

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

  • Los últimos 10 bits más o menos: un valor único para cada generador. Usando esto, no necesitamos hacer ninguna sincronización entre generadores (lo cual es extremadamente difícil), ya que todos los generadores producen ID 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 tales identificaciones sean únicas a nivel mundial, solo es muy probable que sean únicas. (Para colisionar, uno o más generadores tendrían que crear el mismo valor aleatorio exactamente al mismo tiempo). Algo como:

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

d) La salida más fácil es utilizar UUID / GUID .

Jesper M
fuente
Cassandra admite contadores ( cassandra.apache.org/doc/cql3/CQL.html#counters ), aunque existen algunas limitaciones.
Piyush Kansal
Es fácil establecer la posición de los números de secuencia para el índice de mapa de bits, pero la identificación única a veces es demasiado larga (64 bits o 128 bits), ¿cómo se puede asignar una identificación única a una posición de índice de mapa de bits? Gracias.
Brucenan
2
Me gustó mucho la opción #b ..... podría permitir una gran escala y no causar muchos problemas de concurrencia
puneet
2
twitter/snowflakeya no se mantiene
Navin
Si desea una implementación con licencia de Apache2 de la opción B, consulte bitbucket.org/pythagorasio/common-libraries/src/master/… También puede obtenerla de maven io.pythagoras.common: distribution-sequence-id-generator: 1.0 .0
Wpigott
16

Ahora hay más opciones.

Aunque esta pregunta es "antigua", 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 puede utilizar Zookeeper . Proporciona métodos para crear nodos de secuencia (agregados a los nombres de znode, aunque prefiero usar los números de versión de los nodos). Sin embargo, tenga cuidado con este: si no quiere números perdidos en su secuencia, puede que no sea lo que desea.

Salud

Paolo
fuente
3
Zookeeper fue la opción con la que fui, hay una buena descripción y un escrito de esto en la lista de correo que comencé. mail-archive.com/[email protected]/msg01967.html
Jon
Jon, gracias por señalar ese hilo, ese es exactamente el tipo de solución que estaba pensando. Por cierto, ¿hiciste el código para superar la limitación MAX_INT?
Paolo
15

Puede hacer que cada nodo tenga un ID único (que puede tener de todos modos) y luego anteponerlo 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 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 deba asignarse, solicita ID en bloques de 10,000 al servidor central y luego solo tiene que hacer otra solicitud de red cuando se agote.

Steven Schlansker
fuente
1
Me gusta su punto sobre la generación de ID de lote, pero limita cualquier posibilidad de cálculo en tiempo real.
ishan
He implementado un mecanismo similar. En eso, además de que los clientes almacenan en caché un bloque de secuencias, he agregado varios servidores-hosts que almacenan en caché los bloques de secuencias. Se mantiene un (único) generador maestro en algún almacenamiento de alta disponibilidad o en un host de un solo maestro, al que solo se puede acceder la flota de servidores-hosts. El almacenamiento en caché del servidor también nos ayudaría a tener más tiempo de actividad, a pesar de que el maestro único se cae por un momento.
Janakiram
11

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

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

Redisson redisson = Redisson.create(config);
RAtomicLong atomicLong = redisson.getAtomicLong("anyAtomicLong");
atomicLong.incrementAndGet();
Nikita Koksharov
fuente
8

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

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

wsorenson
fuente
3
... y ¿qué sucede cuando el servidor que ejecuta ese servicio deja de funcionar?
Navin
¿Tiene una alerta que le dice a alguien que inicie otra? A veces eso estará bien. Creo que la respuesta es intentar decir "mantener las cosas en perspectiva". La solución distribuida perfecta tiene sus propios inconvenientes y, a veces, cuanto más simple, mejor.
nic ferrier
6

Hay algunas estrategias; pero ninguno que yo sepa se puede distribuir realmente y dar una secuencia real.

  1. tener un generador de números central. no tiene por qué ser una gran base de datos. memcachedtiene 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. separe un rango entero para cada nodo (como la respuesta de Steven Schlanskter )
  3. utilizar números aleatorios o UUID
  4. usar algún dato, junto con la ID del nodo, y hash todo (o hmac )

personalmente, me inclinaría por los UUID, o memcached si quiero tener un espacio en su mayoría contiguo.

Javier
fuente
5

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

Probablemente debería ampliar esto.

Se garantiza que los UUID son únicos a nivel mundial (si evita los basados ​​en números aleatorios, donde la singularidad es muy probable).

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

Su requisito de "seguridad para subprocesos" puede cumplirse eligiendo generadores de UUID "seguros para subprocesos".

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

Tenga en cuenta que muchas implementaciones de números de secuencia de bases de datos (por ejemplo, Oracle) no garantizan un aumento monotónico o (incluso) un 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 "almacenados 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) se pueden mezclar cuando están siendo asignados por múltiples conexiones!

Phil
fuente
1
Si bien los UUID funcionan, el problema con ellos es que debe tener cuidado con la forma en que los almacena si finalmente necesita indexar las claves generadas. También suelen ocupar mucho más espacio que una secuencia aumentada monótonamente. Consulte percona.com/blog/2014/12/19/store-uuid-optimized-way para ver una discusión sobre cómo almacenarlos con MySQL.
Pavel
2

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-ordenables.

SANN3
fuente
2

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 nuestra necesidad. Nuestro requisito era obtener una secuencia única (0,1,2,3 ... n) de identificadores y, por lo tanto, el copo de nieve no ayudó. Creamos nuestro propio sistema para generar los identificadores usando Redis. Redis es de un solo subproceso, por lo que su mecanismo de lista / cola siempre nos da 1 pop a la vez.

Lo que hacemos es, creamos un búfer de identificadores. Inicialmente, la cola tendrá de 0 a 20 identificadores que están listos para ser enviados cuando se soliciten. Varios clientes pueden solicitar una identificación y redis mostrará 1 identificación a la vez. Después de cada ventana emergente desde la izquierda, insertamos BUFFER + currentId a la derecha, lo que mantiene la lista de búfer en funcionamiento. Implementación aquí

Zohair
fuente
0

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

Majid Azimi
fuente
0

Con una base de datos, puede alcanzar más de 1.000 incrementos por segundo con un solo núcleo. Es bastante sencillo. Puede usar su propia base de datos como backend para generar ese número (ya que 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 ejecute la siguiente declaración:

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

Si tu aplicación te lo permite, puedes asignar un bloque a la vez (ese fue 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 y no puede asignar compensaciones por adelantado, puede implementar su propio servicio utilizando Flink para el procesamiento en tiempo real. Pude obtener alrededor de 100K incrementos por partición.

¡Espero eso ayude!

usuario2108278
fuente
0

El problema es similar a: En el mundo iscsi, donde cada lun / volumen debe ser identificable de forma única 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 fabricante / proveedor de almacenamiento, y el resto aumenta monótonamente.

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

usuario1860223
fuente
1
por favor agregue algunos detalles más
Ved Prakash
0

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

refutar
fuente