分布式序列号生成?

我过去通常使用数据库序列实现 序列号生成序列号生成

e.g. Using Postgres SERIAL type http://www.neilconway.org/docs/sequences/

我很好奇如何为没有数据库的大型分布式系统生成序列号。是否有人有任何经验或建议的最佳做法,以实现序列号生成的 线程安全方式为多个客户?

89047 次浏览

You could have each node have a unique ID (which you may have anyway) and then prepend that to the sequence number.

For example, node 1 generates sequence 001-00001 001-00002 001-00003 etc. and node 5 generates 005-00001 005-00002

Unique :-)

或者,如果您想要某种集中式系统,您可以考虑让您的序列服务器以块的形式分发。这大大降低了开销。例如,您不需要为必须分配的每个 ID 从中央服务器请求一个新的 ID,而是从中央服务器请求以10,000块为单位的 ID,然后只需在用完时执行另一个网络请求。

Why not use a (thread safe) UUID generator?

我应该详细说明一下。

UUID 保证是全局唯一的(如果您避免使用基于随机数的 UUID,因为唯一性非常可能)。

无论使用多少个 UUID 生成器,通过每个 UUID 的全局唯一性都可以满足您的“分布式”需求。

Your "thread safe" requirement can be met by choosing "thread safe" UUID generators.

假设每个 UUID 的保证的全局唯一性满足您的“序列号”要求。

请注意,许多数据库序列号实现(例如 Oracle)不保证单调增加或(甚至)增加序列号(在每个“连接”的基础上)。这是因为连续批次的序列号按照每个连接在“缓存”块中分配。这保证了全局唯一性 还有保持足够的速度。但是实际分配的序列号(随着时间的推移)可能会在多个连接分配时混乱!

如果它真的必须是全局顺序的,而不仅仅是唯一的,那么我会考虑创建一个单独的、简单的服务来分发这些数字。

分布式系统依赖于大量的小型服务交互,对于这种简单的任务,您真的需要或者真的会从其他复杂的分布式解决方案中受益吗?

有一些策略,但是我知道没有一个能够真正的分布并且给出一个真正的序列。

  1. 有一个中央数字发生器。不一定是个大数据库。memcached有一个快速的原子计数器,在绝大多数情况下,它对于整个集群来说已经足够快了。
  2. 为每个节点分隔一个整数范围(如 Steven Schlanskter 的回答)
  3. 使用随机数或 UUID
  4. 使用一些数据,连同节点的 ID,并散列它(或 Hmac它)

就我个人而言,如果我想拥有一个几乎是连续的空间,我会倾向于使用 UUID 或 memcached。

现在有了更多的选择。

尽管这个问题“老”了,我还是来了,所以我认为留下我知道的选项(到目前为止)可能会有用:

  • 您可以尝试使用 Hazelcast,在它的1.9发行版中,它包含了 java.util.concur.AtomicLong 的分布式实现
  • 也可以使用 Zookeeper。它提供了创建序列节点的方法(附加到 znode 名称,尽管我更喜欢使用节点的版本号)。但是要小心这一个: 如果你不想在你的序列中遗漏数字,它可能不是你想要的。

干杯

好吧,这是一个非常古老的问题,我现在第一次看到这个问题。

您需要区分 序列号唯一的身份证,它们(可选)可以根据特定的标准(通常是生成时间)进行松散排序。真正的序列号意味着知道所有其他工作者都做了什么,因此需要共享状态。要以分布式、高规模的方式实现这一点并不容易。您可以查看诸如网络广播、每个工作人员的窗口范围和 distributed hash tables for unique worker IDs之类的内容,但这是一项繁重的工作。

惟一 ID 是另一回事,有几种以分散方式生成唯一 ID 的好方法:

你可以使用 Twitter's Snowflake ID network service。雪花是:

  • 网络服务,即你打一个网络电话,以获得一个唯一的 ID;
  • 它生成64位唯一 ID,这些 ID 按生成时间排序;
  • and the service is highly scalable and (potentially) highly available; each instance can generate many thousand IDs per second, and you can run multiple instances on your LAN/WAN;
  • 用 Scala 编写,在 JVM 上运行。

b) You could generate the unique IDs on the clients themselves, using an 这种方法来源于如何制作 UUID 和雪花的 ID。 There are multiple options, but something along the lines of:

  • 最重要的40位左右: 时间戳; ID 的生成时间。(我们使用时间戳中最重要的位使 ID 可以按生成时间进行排序。)

  • The next 14 or so bits: 每台发电机计数器, which each generator increments by one for each new ID generated. This ensures that IDs generated at the same moment (same timestamps) do not overlap.

  • 最后10位左右: A unique value for each generator.使用这个函数,我们不需要在生成器之间进行任何同步(这非常困难) ,因为所有生成器都会因为这个值而产生不重叠的 ID。

C)您可以在客户端上生成 ID,只需使用 timestamp and random value.,这样就避免了需要知道所有的生成器,并为每个生成器分配一个唯一的值。另一方面,这样的 ID 不是 保证全局唯一的,它们只是 very highly likely唯一的。(要发生碰撞,一个或多个发生器必须在完全相同的时间创建相同的随机值。)类似于:

  • 最重要的32位: 时间戳,的 ID 的生成时间。
  • 最低有效的32位: 32位随机数,为每个 ID 重新生成。

d) The easy way out, 使用 UUID/GUID.

它实现了 AtomicLong的分布式和可伸缩的版本,下面是一个例子:

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


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

我写了一个简单的服务,可以生成半唯一的非顺序64位长数字。它可以部署在多台机器上,以实现冗余和可伸缩性。它使用 ZeroMQ 进行消息传递。有关它如何工作的更多信息,请查看 github 页面: ZUID

使用一个数据库,单个内核可以达到每秒1.000 + 的增量。很简单。您可以使用它自己的数据库作为后端来生成这个数字(因为它应该是它自己的聚合,用 DDD 术语来说)。

我也遇到过类似的问题。我有几个分区,我想得到一个抵消计数器为每一个。我实现了这样的东西:

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

然后执行下列声明:

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

如果您的应用程序允许,您可以立即分配一个块(这是我的情况)。

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

如果您需要进一步的吞吐量,不能提前分配偏移量,您可以实现自己的服务使用实时处理 Flink。我能够得到每个分区大约100K 的增量。

希望能有帮助!

可以使用 Redis 和 Lua 对分布式 ID 生成进行归档。Github中可用的实现。它产生一个分布式和 k 排序的唯一 id。

这个问题类似于: 在 iscsi 的世界中,每个轮/卷必须由运行在客户端的发起者唯一地标识。 Iscsi 标准规定,前几位必须表示存储提供商/制造商的信息,其余的单调增加。

类似地,可以使用分布式节点系统中的初始位来表示节点 ID,其余的可以单调增加。

一个不错的解决方案是使用基于长时间的生成。 它可以在分布式数据库的支持下完成。

我知道这是一个老问题,但我们也面临着同样的需要,无法找到满足我们需要的解决办法。 我们的要求是得到一个惟一的 id 序列(0,1,2,3... n) ,因此雪花没有帮助。 我们创建了自己的系统来使用 Redis 生成 ID。Redis 是单线程的,因此它的列表/队列机制总是一次给我们一个弹出。

What we do is, We create a buffer of ids, Initially, the queue will have 0 to 20 ids that are ready to be dispatched when requested. Multiple clients can request an id and redis will pop 1 id at a time, After every pop from left, we insert BUFFER + currentId to the right, Which keeps the buffer list going. Implementation 给你

我对 gcloud 的看法是,使用存储文件。

Implemented as cloud function, can easily be converted to a library.

https://github.com/zaky/sequential-counter