leftso 1328 0 2018-06-23 08:19:56

logo-cover-Java编程中在高规模分布式环境中生成唯一的ID
Java编程中在高规模分布式环境中生成唯一的ID

1.前言

当您使用单个MySQL数据库时,可以简单地使用自动增量ID作为主键,但这不适用于分片MySQL数据库。

因此,我研究了各种现有解决方案,最后编写了一个简单的64位唯一ID生成器,该生成器受Twitter 类似服务的启发。

在本文中,我将分享唯一ID生成器的简化版本,该生成器可用于在分布式环境中生成唯一ID的任何用例,而不仅仅是分片数据库。

我还会概述其他现有解决方案并讨论它们的优缺点。

2.现有的解决方案

UUID

UUID是全球唯一的128位十六进制数字。两次生成相同UUID的机会可以忽略不计。

UUID的问题在于它们规模很大,索引不好。当数据集增加时,索引大小也会增加,并且查询性能会受到影响。

MongoDB的ObjectId

MongoDB的ObjectIDs是12个字节(96位)的十六进制数字,它们由 -

  • 以秒为单位的4字节时期时间戳,
  • 一个3字节的机器标识符,
  • 一个2字节的进程ID,和
  • 一个3字节的计数器,从一个随机值开始。

这比先前的128位UUID小。但是再次,这个大小比我们通常在单个MySQL自动增量字段(64位bigint值)中的长度要长。

 

数据库票证服务器

此方法使用集中式数据库服务器来生成唯一增量ID。这就像一个集中的自动增量。Flickr使用这种方法。

这种方法的问题在于票务服务器可能成为写入瓶颈。此外,您还需要在基础结构中引入一个需要管理和扩展的组件。

Twitter雪花算法

Twitter雪花算法是一种专用网络服务,用于高规模生成64位唯一ID。由该服务生成的ID大致可以在时间上排序。

这些ID由以下组件组成:

  • 以毫秒为单位的时间戳 - 41位(给我们69年的时间)
  • 配置的机器ID - 10位(最多可提供1024台机器)
  • 序列号 - 12位(每台机器的本地计数器每4096个滚动一次)

他们预留了1位用于未来目的。由于ID使用时间戳作为第一个组件,它们是可排序的。

由twitter雪花生成的ID适用于64位,并且可以在时间上排序,这非常棒。这就是我们想要的。

但是如果我们使用Twitter雪花,我们将再次在我们需要维护的基础设施中引入另一个组件。

 

3.分布式64位独特ID生成器受Twitter Snowflake启发

最后,我写了一个简单的序列生成器,根据Twitter雪花服务中概述的概念生成64位ID。

由这个序列发生器生成的ID由以下部分组成 

  • 以毫秒为单位的时期精度 - 42位。可以使用42位表示的最大时间戳是2 42 - 1,或4398046511103,这就是出来Wednesday, May 15, 2109 7:35:11.103 AM
  • 机器ID - 10位。这给了我们1024台机器。
  • 每台机器的本地计数器 - 12位。计数器的最大值将是4095.之后,它会翻转并从0再次开始。

您的微服务可以使用此序列生成器独立生成ID。这是有效的,符合bigint的大小。

这是完整的程序 -

import java.net.NetworkInterface;
import java.security.SecureRandom;
import java.time.Instant;
import java.util.Enumeration;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Distributed Sequence Generator.
 * Inspired by Twitter snowflake: https://github.com/twitter/snowflake/tree/snowflake-2010
 */
public final class SequenceGenerator {
    private static final AtomicInteger counter = new AtomicInteger(new SecureRandom().nextInt());

    private static final int TOTAL_BITS = 64;
    private static final int EPOCH_BITS = 42;
    private static final int MACHINE_ID_BITS = 10;

    private static final int MACHINE_ID;
    private static final int LOWER_ORDER_TEN_BITS = 0x3FF;
    private static final int LOWER_ORDER_TWELVE_BITS = 0xFFF;

    public static long nextId() {
        long curMs = Instant.now().toEpochMilli();
        long id = curMs << (TOTAL_BITS - EPOCH_BITS);
        id |= (MACHINE_ID << (TOTAL_BITS - EPOCH_BITS - MACHINE_ID_BITS));
        id |= (getNextCounter() & LOWER_ORDER_TWELVE_BITS);
        return id;
    }

    private static int getNextCounter() {
        return counter.getAndIncrement();
    }

    static {
        MACHINE_ID = createMachineId();
    }

    private static int createMachineId() {
        int machineId;
        try {
            StringBuilder sb = new StringBuilder();
            Enumeration<NetworkInterface> networkInterfaces = NetworkInterface.getNetworkInterfaces();
            while (networkInterfaces.hasMoreElements()) {
                NetworkInterface networkInterface = networkInterfaces.nextElement();
                byte[] mac = networkInterface.getHardwareAddress();
                if (mac != null) {
                    for(int i = 0; i < mac.length; i++) {
                        sb.append(String.format("%02X", mac[i]));
                    }
                }
            }
            machineId = sb.toString().hashCode();
        } catch (Exception ex) {
            machineId = (new SecureRandom().nextInt());
        }
        machineId = machineId & LOWER_ORDER_TEN_BITS;
        return machineId;
    }
}
 

上述生成器使用机器的MAC地址为该机器创建唯一标识符。您也可以在环境变量中配置MachineID并直接使用它。这将保证唯一性。

现在让我们来了解它是如何工作的。让我们说这是June 9, 2018 10:00:00 AM GMT。这个特定时间的纪元时间戳是1528538400

为了生成ID,我们首先用左值填充最左边的42位,

id = 1528538400 << (64 - 42)
接下来,我们采用配置的机器ID并用机器ID填充接下来的10位。假设机器ID是786 -
id |= 786 << (64 - 42 - 10)
最后,我们用本地计数器填充最后的12位。考虑到计数器的下一个值是3450(在上述程序中取出低位12位之后),最终的ID就像这样获得 -
id |= 3450 
这给了我们我们的最终ID。