如何使用CL实现snowflake

TL;DR;

这是一篇为了完成写作KPI而写的博客,总结起来就是提供了一种用Common Lisp实现来自于Twitter的雪花算法的实现方案。成品在这里,本文只是简单地描述一下生成雪花ID的大致思路,详细内容请各位移步代码仓库查看。

上述代码仓库中的snowflake算法——如果我的实现确实可以称作snowflake算法的话——的思路来自于下列两个地方:

  1. http://www.lanindex.com/twitter-snowflake,64位自增id算法详解/
  2. https://github.com/sony/sonyflake

如何获取时间戳

Common Lisp本身提供了一个获取时间戳的函数,也就是get-universal-time,可惜的是,这个函数所返回的并不是通常意义上的Epoch时间戳,而是自己的一套计算时间的方式中的表示时间的整数。为了获得UNIX时间戳,需要借助于第三方库local-time。为了可以获取到毫秒精度的时间戳,一个可运行的函数如下

1
2
3
4
5
6
(defun now ()
"Returns the number of milliseconds elapsed since 1 January 1970 00:00:00 UTC."
(let* ((now (local-time:now))
(seconds (local-time:timestamp-to-unix now))
(milliseconds (local-time:timestamp-millisecond now)))
(+ (* 1000 seconds) milliseconds)))

如何获取机器ID

这里参考了Sony的雪花ID算法中的思路,基于机器的内网IP地址来生成机器ID。当然了,Common Lisp标准中是没有提供获取机器的内网IP地址的方法的,这一点也可以借助于第三方库实现,选用的是ip-interfaces。通过这个库提供的get-ip-interfaces函数可以获取到机器的所有“接口”,遍历这个接口的列表后即可找出其中的内网IP。一台机器可能会有多个内网IP,我的方法是选用了第一个找到的内网IP地址。当然了,还需要一个将向量转化为数值的函数,并取出转化为数值后的IP地址的低10位,作为机器ID。

序号

如果希望生成的ID是保持递增的,那么就需要维护一个可以原子递增的数值计数器。在真实的使用中可以通过Redis的INCR指令来生成这一个ID,但是因为这里的雪花ID算法是作为一个独立的库实现的,不需要依赖于数据库等外部组建,因此这里就直接使用了Common Lisp自带的random函数来生成这个序号了。

全文完