一秒可生成500万ID的分布式自增ID算法—雪花算法 (Snowflake，Delphi 版)

概述

        分布式系统中，有一些需要使用全局唯一id的场景，这种时候为了防止id冲突可以使用36位的uuid，但是uuid有一些缺点，首先他相对比较长，另外uuid一般是无序的。

有些时候我们希望能使用一种简单一些的id，并且希望id能够按照时间有序生成。

        而twitter的snowflake解决了这种需求，最初twitter把存储系统从mysql迁移到cassandra，因为cassandra没有顺序id生成机制，所以开发了这样一套全局唯一id生成服务。

结构

        snowflake的结构如下(每部分用-分开):

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

        第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)，然后是5位datacenterid和5位workerid(10位的长度最多支持部署1024个节点） ，最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个id序号）一共加起来刚好64位，为一个long型。(转换成字符串后长度最多19)。

        snowflake生成的id整体上按照时间自增排序，并且整个分布式系统内不会产生id碰撞（由datacenter和workerid作区分），并且效率较高。经测试snowflake每秒能够产生500万个id。

在 ubuntu 18.04 下运行的截图：

源码

{ *
  * twitter_snowflake https://github.com/twitter-archive/snowflake
  * snowflake的结构如下(每部分用-分开):
  * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
  * 1位标识，由于long基本类型在java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0
  * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
  * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序idworker类的starttime属性）。41位的时间截，可以使用69年，年t = (1l << 41) / (1000l * 60 * 60 * 24 * 365) = 69
  * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterid和5位workerid
  * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个id序号
  * 加起来刚好64位，为一个long型。
  * snowflake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生id碰撞(由数据中心id和机器id作区分)，并且效率较高，经测试，snowflake每秒能够产生409.6万id左右。
  *
  * 本算法参考官方 twitter snowflake 修改而来，同时借鉴了网上java语言的版本。
  * 作者：全能中间件 64445322 https://www.centmap.cn/server
  * 使用方法：var orderid := idgenerator.nextid()，idgenerator 不用创建也不用释放，而且该方法是线程安全的。
  * }

// 参考美团点评分布式id生成系统
// https://tech.meituan.com/2017/04/21/mt-leaf.html
// https://github.com/meituan-dianping/leaf/blob/master/leaf-core/src/main/java/com/sankuai/inf/leaf/snowflake/snowflakeidgenimpl.java

unit rtcmw.system.snowflake;

interface

uses
  system.sysutils, system.syncobjs;

type
  tsnowflakeidworker = class(tobject)
  private const
    // 最大可用69年
    maxyears = 69;
    // 机器id所占的位数
    workeridbits = 5;
    // 数据标识id所占的位数
    datacenteridbits = 5;
    // 序列在id中占的位数
    sequencebits = 12;
    // 机器id向左移12位
    workeridshift = sequencebits;
    // 数据标识id向左移17位(12+5)
    datacenteridshift = sequencebits + workeridbits;
    // 时间截向左移22位(5+5+12)
    timestampleftshift = sequencebits + workeridbits + datacenteridbits;
{$warnings off}
    // 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
    sequencemask = -1 xor (-1 shl sequencebits);
    // 支持的最大机器id
    maxworkerid = -1 xor (-1 shl workeridbits);
    // 支持的最大数据标识id，结果是 31
    maxdatacenterid = -1 xor (-1 shl datacenteridbits);
{$warnings on}
  private type
    tworkerid = 0 .. maxworkerid;
    tdatacenterid = 0 .. maxdatacenterid;
  strict private
    fworkerid: tworkerid;
    fdatacenterid: tdatacenterid;
    fepoch: int64;
    fsequence: int64;
    flasttimestamp: int64;
    fstarttimestamp: int64;
    funixtimestamp: int64;
    fishighresolution: boolean;
    /// <summary>
    /// 阻塞到下一个毫秒，直到获得新的时间戳
    /// </summary>
    /// <param name="atimestamp ">上次生成id的时间截</param>
    /// <returns>当前时间戳 </returns>
    function waituntilnexttime(atimestamp: int64): int64;
    /// <summary>
    /// 返回以毫秒为单位的当前时间
    /// </summary>
    /// <remarks>
    /// 时间的表达格式为当前计算机时间和1970年1月1号0时0分0秒所差的毫秒数
    /// </remarks>
    function currentmilliseconds: int64; inline;
    function currenttimestamp: int64; inline;
    function elapsedmilliseconds: int64; inline;
  private
    class var flock: tspinlock;
    class var finstance: tsnowflakeidworker;
    class function getinstance: tsnowflakeidworker; static;
    class constructor create;
    class destructor destroy;
  protected
    function getepoch: tdatetime;
    procedure setepoch(const value: tdatetime);
  public
    constructor create; overload;
    /// <summary>
    /// 获得下一个id (该方法是线程安全的)
    /// </summary>
    function nextid: int64;inline;
    /// <summary>
    /// 工作机器id(0~31)
    /// </summary>
    property workerid: tworkerid read fworkerid write fworkerid;
    /// <summary>
    /// 数据中心id(0~31)
    /// </summary>
    property datacenterid: tdatacenterid read fdatacenterid write fdatacenterid;
    /// <summary>
    /// 开始时间
    /// </summary>
    property epoch: tdatetime read getepoch write setepoch;

    class property instance: tsnowflakeidworker read getinstance;
  end;

function idgenerator: tsnowflakeidworker;

const
  error_clock_moved_backwards = 'clock moved backwards. refusing to generate id for %d milliseconds';
  error_epoch_invalid         = 'epoch can not be greater than current';

implementation

uses
  system.math, system.timespan
{$if defined(mswindows)}
    , winapi.windows
{$elseif defined(macos)}
    , macapi.mach
{$elseif defined(posix)}
    , posix.time
{$endif}
    , system.dateutils;

function idgenerator: tsnowflakeidworker;
begin
  result := tsnowflakeidworker.getinstance;
end;

{ tsnowflakeidworker }

constructor tsnowflakeidworker.create;
{$if defined(mswindows)}
var
  frequency: int64;
{$endif}
begin
  inherited;
{$if defined(mswindows)}
  fishighresolution := queryperformancefrequency(frequency);
{$elseif defined(posix)}
  fishighresolution := true;
{$endif}
  fsequence := 0;
  fworkerid := 1;
  fdatacenterid := 1;
  flasttimestamp := -1;
  fepoch := datetimetounix(encodedate(2019, 12, 12), true) * msecspersec;
  funixtimestamp := datetimetounix(now, true) * msecspersec;
  fstarttimestamp := currenttimestamp;
end;

class destructor tsnowflakeidworker.destroy;
begin
  freeandnil(finstance);
end;

class constructor tsnowflakeidworker.create;
begin
  finstance := nil;
  flock := tspinlock.create(false);
end;

class function tsnowflakeidworker.getinstance: tsnowflakeidworker;
begin
  flock.enter;
  try
    if finstance = nil then
      finstance := tsnowflakeidworker.create;
    result := finstance;
  finally
    flock.exit;
  end;
end;

function tsnowflakeidworker.currenttimestamp: int64;
{$if defined(posix) and not defined(macos)}
var
  res: timespec;
{$endif}
begin
{$if defined(mswindows)}
  if fishighresolution then
    queryperformancecounter(result)
  else
    result := gettickcount * int64(ttimespan.tickspermillisecond);
{$elseif defined(macos)}
  result := int64(absolutetonanoseconds(mach_absolute_time) div 100);
{$elseif defined(posix)}
  clock_gettime(clock_monotonic, @res);
  result := (int64(1000000000) * res.tv_sec + res.tv_nsec) div 100;
{$endif}
end;

function tsnowflakeidworker.elapsedmilliseconds: int64;
begin
  result := (currenttimestamp - fstarttimestamp) div ttimespan.tickspermillisecond;
end;

function tsnowflakeidworker.getepoch: tdatetime;
begin
  result := unixtodatetime(fepoch div msecspersec, true);
end;

function tsnowflakeidworker.nextid: int64;
var
  offset: integer;
  timestamp: int64;
begin
  flock.enter;
  try
    timestamp := currentmilliseconds();

    // 如果当前时间小于上一次id生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
    if (timestamp < flasttimestamp) then
    begin
      offset := flasttimestamp - timestamp;
      if offset <= 5 then
      begin
        // 时间偏差大小小于5ms，则等待两倍时间
        system.sysutils.sleep(offset shr 1);

        timestamp := currentmilliseconds();
        // 还是小于，抛异常并上报
        if timestamp < flasttimestamp then
          raise exception.createfmt(error_clock_moved_backwards, [flasttimestamp - timestamp]);
      end;
    end;

    // 如果是同一时间生成的，则进行毫秒内序列
    if (flasttimestamp = timestamp) then
    begin
      fsequence := (fsequence + 1) and sequencemask;
      // 毫秒内序列溢出
      if (fsequence = 0) then
        // 阻塞到下一个毫秒,获得新的时间戳
        timestamp := waituntilnexttime(flasttimestamp);
    end
    // 时间戳改变，毫秒内序列重置
    else
      fsequence := 0;

    // 上次生成id的时间截
    flasttimestamp := timestamp;

    // 移位并通过或运算拼到一起组成64位的id
    result := ((timestamp - fepoch) shl timestampleftshift)
      or (datacenterid shl datacenteridshift)
      or (workerid shl workeridshift)
      or fsequence;
  finally
    flock.exit;
  end;
end;

function tsnowflakeidworker.waituntilnexttime(atimestamp: int64): int64;
var
  timestamp: int64;
begin
  timestamp := currentmilliseconds();
  while timestamp <= atimestamp do
    timestamp := currentmilliseconds();

  result := timestamp;
end;

procedure tsnowflakeidworker.setepoch(const value: tdatetime);
begin
  if value > now then
    raise exception.create(error_epoch_invalid);

  if yearsbetween(now, value) <= maxyears then
    fepoch := datetimetounix(value, true) * msecspersec;
end;

function tsnowflakeidworker.currentmilliseconds: int64;
begin
  result := funixtimestamp + elapsedmilliseconds;
end;

end.