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函数来生成这个序号了。

全文完

假设有N个区间，将它们表达为，其中下标i位于区间中

为了判定这组区间中是否存在两个区间是有重叠的，首先对这组区间进行排序，使得对于排序后的每一个区间而言，都有（这里的i小于N-1）。

为了说明要如何判定这些区间中是否存在重叠，首先我们假设这其中确实存在着至少两个这样的区间，假设分别是第j个和第k个（假设j小于k），它们必然会满足这样的关系

这是因为如果，那么所有位于区间中的数都将会小于 b_k，那么第j个区间与第k个区间就不可能有交集了，因此上述不等式一定成立。再加上这一组区间都是按照区间的下界递增排序的，那么必然有

假设，由于k和j都是正整数，这意味着在第j和第k个区间之间，必然还存在着一个区间l，那么这个区间的必然满足

这就意味着第j个区间和第l个区间也存在交集，它们的交集是子区间（这里假设）。这就说明了，如果可以在一组区间中找到两个不相邻的区间，它们存在重叠的部分，那么一定可以找到第三个区间，使得这个区间与其中的一个区间也存在重叠。

这表示如果我们要判定一组区间是否存在重叠，那么只需要先将它们基于区间的起点按照递增排序后，比较每一对相邻的两个区间是否存在重叠即可。

最近产品需要一个搜索商城中的商品的功能，于是接触了一下Elastic Search。虽然久仰它的大名，但一直都没有真正用过。这次稍微摸索了一下，顺便记录下来，说不定哪天就真的需要用上了。

安装

首先需要下载Elastic Search，我选择了.zip格式的安装包，下载地址在这里。下载完成后就拿到了一个5.2.2版本的Elastic Search的安装包，只需要解压即可使用。因为我喜欢把软件安装到主目录的app目录下，所以我用的命令是

1
2

cd /home/liutos/app
unzip ../installer/elasticsearch-5.2.2.zip

主目录下的installer是我习惯的用来存放软件的安装包的位置。解压后生成了一个名为elasticsearch-5.2.2的新目录。在这个目录下有一个名为bin的子目录，只需要进入该目录运行其中的elasticsearch文件即可，实例命令为

1
2

cd elasticsearch-5.2.2/bin
./elasticsearch -d

为了让Elastic Search可以不占用当前的终端，添加了-d选项，使其以后台进程（daemon）的方式运行。Elastic Search需要JVM才能运行，在执行上面的命令之前请各位自行准备好Java程序的运行环境。成功启动后，Elastic Search默认会监听9200端口，可以通过浏览器访问http://localhost:9200来确认Elastic Search是否正常启动了

使用

创建索引

遵照官方文档中的指导，先创建一个索引以便后续向这个索引中添加文档。假设要创建的索引是为商品准备的，取名为products，可以通过如下的命令创建出来

1

curl -X PUT 'http://localhost:9200/products'

创建成功后Elastic Search的响应结果为

1

{"acknowledged":true,"shards_acknowledged":true}

如果希望Elastic Search返回更可读的形式，可以添加?pretty参数到上面的URL的末尾。

文档的增删查改

索引已经创建了，就可以创建文档了。Elastic Search的文档是对象形式的，假设现在要创建的对象的类型为product，示例命令如下

1
2
3
4
5

curl -X POST 'http://localhost:9200/products/product' --data '
{
  "id": 1,
  "name": "Product 1"
}'

在我的机器上，Elastic Search的响应结果为

1

{"_index":"products","_type":"product","_id":"AVqpZHmVckriR6iVcbaW","_version":1,"result":"created","_shards":{"total":2,"successful":1,"failed":0},"created":true}

其中名为”_id”的字段的值为Elastic Search自动为这份新写入的文档分配的ID，通过这个ID可以从Elastic Search中取出这份文档，示例命令如下

1

curl 'http://localhost:9200/products/product/AVqpZHmVckriR6iVcbaW?pretty'

相当的RESTful的接口路径，也许你已经猜到了，删除一个文档的代码就是将请求的GET方法替换为DELETE。是的，示例代码如下

1

curl -X DELETE 'http://localhost:9200/products/product/AVqpZHmVckriR6iVcbaW?pretty'

再次查找刚才的ID的文档时，响应结果中的”_found”字段的值就已经变成了false了。关于修改文档的方法，请参考官方手册中的章节。

搜索

准备数据

最简单的搜索接口的使用就是通过浏览器访问http://localhost:9200/products/_search这个地址了。在我的机器上，看到的页面内容为如下的JSON字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

{

    "took": 42,
    "timed_out": false,
    "_shards": {
        "total": 5,
        "successful": 5,
        "failed": 0
    },
    "hits": {
        "total": 0,
        "max_score": null,
        "hits": [ ]
    }

}

为了方便接下来的演示，先通过Elastic Search的_bulk接口向其批量创建文档数据，示例代码如下

1

curl -X POST 'http://localhost:9200/_bulk?pretty' --data-binary '@docs'

其中docs文件中的内容为

1
2
3
4
5
6
7
8

{"create": {"_index": "products", "_type": "product", "_id": 1}}
{"name": "设计模式之禅"}
{"create": {"_index": "products", "_type": "product", "_id": 2}}
{"name": "失控：全人类的最终命运和结局"}
{"create": {"_index": "products", "_type": "product", "_id": 3}}
{"name": "构建高性能Web站点", "price": 75.00, "author": "郭欣"}
{"create": {"_index": "products", "_type": "product", "_id": 4}}
{"name": "大型网站技术架构：核心原理与案例分析", "price": 59.00, "author": "李智慧", "publisher": "电子工业出版社"}

尽管这里是一个文本文件，但是根据官方文档的说法，此处需要使用curl的二进制模式来发送数据，否则会报错。

个性化搜索

如果希望找到《失控》这本书的信息，那么可以根据书名进行查找，示例代码如下

1

curl 'http://localhost:9200/products/_search?q=name:失控'

Elastic Search提供了许多的搜索选项，如果全部通过URL中的query string来传递将会非常难以构造。为此，可以使用Elastic Search提供的基于HTTP body的参数传递方式，示例代码如下

1

curl -X GET 'http://localhost:9200/products/_search' --data '{"query": {"match": {"name": "失控"}}}'

Elastic Search支持相当丰富的搜索选项，这里不逐一介绍了，大家可以从官方文档的这里开始翻看。本来想在Chrome的POSTMAN插件中试验搜索功能的，结果当我选定了GET方法后，就不需要我提交HTTP body了，因此还是用curl进行演示。回到正题，如果我们搜索的是一个“站”字，那么Elastic Search会吐出两个结果，此处可以使用搜索接口的from和size参数，分别控制返回的内容取自搜索结果中的哪一个片段。例如想要取出结果中的第二个，可以使用下列代码

1

curl -X GET 'http://localhost:9200/products/_search?pretty' --data '{"from": 1, "size": 1, "query": {"match": {"name": "站"}}}'

通过结合使用from和size参数，可以实现许多应用中所要求的分页功能。在我厂的业务场景中，商品信息还是很多的，不可能全部放入到Elastic Search中作为文档数据存储，Elastic Search只是负责提供搜索出来的商品ID即可，之后再通过商品ID从原来的商品的数据库中按照顺序取出对应的完整的商品信息。因此，在搜索Elastic Search时实际上只需要商品的ID就足够了，可以通过Elastic Search提供的_source字段控制接口吐出的内容，示例代码如下

1

curl -X GET 'http://localhost:9200/products/_search?pretty' --data '{"query": {"match_all": {}}, "_source": ["_id"]}'

这样在吐出的内容中_source字段的值就会是一个空对象，应用程序只需要取每一个hits数组中的记录的”_id”字段即可。这样做的目的是减少Elastic Search通过网络传输了一部分毫无必要的数据，略微优化一下网络开销

全文完

什么是尾递归

如果一个函数在定义时引用了自身，那么这个函数就是一个递归函数。例如我们所熟知的阶乘就可以通过递归函数的形式予以定义

1
2
3
4

(defun fact (n)
  (if (<= n 0)
      1
      (* n (fact (1- n)))))

在if语句的备选路径上，正在定义的函数fact被自身所调用，因此fact就是一个递归函数了。递归有一类较为特殊的形式，叫做尾递归，它们的特征是递归函数的调用位于被定义函数的最后一个步骤。也就是说，这个递归调用的返回值也就是整个函数调用的返回值，后面不再有其它的计算步骤了。例如实现了辗转相除法的下面这个函数就是尾递归的

1
2
3
4

(defun my-gcd (a b)
  (cond ((zerop a) b)
        ((zerop b) a)
        (t (my-gcd b (mod a b)))))

此处命名为my-gcd，是因为在Common Lisp中已经预置了一个叫做gcd的函数了

什么是尾递归优化

递归调用其实也就是函数调用，每一次调用都需要保存当前的执行上下文（寄存器的值、程序计数器的值等信息）并压入栈中。如果递归调用得非常深，那么很可能将栈空间消耗殆尽导致程序崩溃，因此很多时候都会选择使用循环来实现用递归实现的效果。尾递归形式的一个优势，就在于编译器可以对其进行优化，使得原本需要添加一个栈帧的函数调用操作，直接重用当前的调用中所使用的栈帧即可。这样一来，递归函数的调用就不会无节制地消耗栈空间了。

另一种对尾递归进行优化的方式，则是将其改写为【赋值】与【跳转】。例如对于上面的my-gcd函数，可以改写为如下形式

1
2
3
4
5
6
7
8
9

(defun my-gcd (a b)
  (tagbody
   rec
     (cond ((zerop a) (return-from my-gcd b))
           ((zerop b) (return-from my-gcd a))
           (t (progn
                (psetf a b
                       b (mod a b))
                (go rec))))))

如何在Common Lisp中实现

如果要使用递归的形式定义一个计算列表长度的函数，那么很可能会写出这样子的代码

1
2
3
4

(defun my-length (lst)
  (if (null lst)
      0
      (1+ (my-length (rest lst)))))

采用累加器的思路，可以将上述函数改写为下面的尾递归形式

1
2
3
4

(defun my-length (lst acc)
  (if (null lst)
      acc
      (my-length (rest lst) (1+ acc))))

对于第二个版本的my-length函数，同样可以手动改写为基于【赋值】和【跳转】的实现形式，结果如下

1
2
3
4
5
6
7
8
9

(defun my-length (lst acc)
  (tagbody
   rec
     (if (null lst)
         (return-from my-length acc)
         (progn
           (psetf lst (rest lst)
                  acc (1+ acc))
           (go rec)))))

你可能已经注意到了，my-gcd和my-length函数的改写都是很有规律的，甚至可以通过一个宏来帮助我们自动完成这种变换。这个宏所需要做的事情其实只有三件：

1. 将原本的定义中的函数体包裹在一个tagbody中
2. 将原本作为返回值的表达式包裹在一个return-from中
3. 将递归调用的表达式改为按顺序执行的psetf和go的组合

为了降低一下实现难度，第二点暂时就不处理了，函数的实现者必须手动编写return-from语句。因此，如果只考虑首尾两个条件，首先，可以考虑实现第三条，将函数体内的递归调用修改为progn、psetf和go的组合。要实现这个变换，可以使用macrolet，如下

1
2
3
4
5
6
7
8
9
10

(defun my-length (lst acc)
  (tagbody
   rec
     (macrolet ((my-length (&rest args)
                  `(progn
                     (psetf ,@(mapcan #'list '(lst acc) args))
                     (go rec))))
       (if (null lst)
           (return-from my-length acc)
           (my-length (rest lst) (1+ acc))))))

为了自动生成上面的代码，我编写了这样的一个宏

1
2
3
4
5
6
7
8
9
10

(defmacro define-rec (name lambda-list &body body)
  (let ((rec (gensym)))
    `(defun ,name ,lambda-list
       (tagbody
          ,rec
          (macrolet ((,name (&rest exprs)
                       ,``(progn
                            (psetf ,@(mapcan #'list ',lambda-list exprs))
                            (go ,',rec))))
            ,@body)))))

利用上面这个宏编写一个计算列表长度的尾递归形式的函数，代码如下

1
2
3
4

(define-rec my-length (lst acc)
  (if (null lst)
      (return-from my-length acc)
      (my-length (rest lst) (1+ acc))))

利用macroexpand-1或者是SLIME提供的展开一次宏的调试功能，在我的及其上得到的代码如下

1
2
3
4
5
6
7
8
9
10

(DEFUN MY-LENGTH (LST ACC)
  (TAGBODY
   #:G937
    (MACROLET ((MY-LENGTH (&REST EXPRS)
                 `(PROGN
                   (PSETF ,@(MAPCAN #'LIST '(LST ACC) EXPRS))
                   (GO ,'#:G937))))
      (IF (NULL LST)
          (RETURN-FROM MY-LENGTH ACC)
          (MY-LENGTH (REST LST) (1+ ACC))))))

跟上面手写的代码没有太大的差别，并且用于计算所得到的列表长度也是正确的。那么如何验证这个函数是采用了【赋值】和【跳转】的机制来完成运算的呢？可以借助Common Lisp提供的trace函数。如果使用的真实执行递归调用的my-length函数的定义，那么执行(trace my-length)后运行(my-length '(1 2 4 5) 0)，在我的机器上会输出如下内容

1
2
3
4
5
6
7
8
9
10
11
12

CL-USER> (my-length '(1 2 4 5) 0)
  0: (MY-LENGTH (1 2 4 5) 0)
    1: (MY-LENGTH (2 4 5) 1)
      2: (MY-LENGTH (4 5) 2)
        3: (MY-LENGTH (5) 3)
          4: (MY-LENGTH NIL 4)
          4: MY-LENGTH returned 4
        3: MY-LENGTH returned 4
      2: MY-LENGTH returned 4
    1: MY-LENGTH returned 4
  0: MY-LENGTH returned 4
4

而如果是使用define-rec宏定义的my-length，求值同样的表达式的输出为

1
2
3
4

CL-USER> (my-length '(1 2 4 5) 0)
  0: (MY-LENGTH (1 2 4 5) 0)
  0: MY-LENGTH returned 4
4

显然，这当中没有递归的函数调用，my-length确实不需要调用自身。

全文完

在UC就职时养成了一个习惯，就是将自己所参与的项目的源代码都存放在一个名为uc的目录下。换了工作之后这个习惯仍然保留下来了，只不过原本名为uc的目录现在改名了（假设这个目录叫做work）。在新公司参与的项目比较多，因此在这个work目录下有许多的子目录，大致上的结构如下

1
2
3

work/
|-- A/
|-- B/

其中A和B分别表示一个项目的源代码目录。在work目录下存放的直接是A和B两个项目的目录。work目录本身是放置在~/src/这个目录下的，因此项目A和B的完整根目录路径是~/src/work/A/和~/src/work/B/。由于参与的项目比较多，经常需要在几个项目间交替着编码，因此经常会在终端键入下面的指令

1
2

cd ~/src/work/A/ # 或者
cd ~/src/work/B/

不得不说这样确实是非常的麻烦，因此我很快就定义了一个shell函数来简化这串命令，这个shell函数的定义如下

1
2
3
4
5
6
7
8

function she() {
    dir=${1}
    target="/home/liutos/src/work/${dir}"
    if [ -d "${target}" ]; then
        cd "${target}"
        return
    fi
}

有了这个辅助工具后，要切换到项目A和B中就简单多了，只需要输入

1
2

she A # 或者
she B

即可。但一使用起来就会发现，原本直接使用cd命令时所能享用的目录名补全功能没有了！绝大多数情况下补全功能是非常有用的，为此打算动手为she函数配备一个目录名的补全功能。显然自定义命令行补全的想法已经有前人实践过了，略加搜索就可以找到这么一篇指南。模仿文章中的方法，我先是写了下面的代码骨架

1
2
3
4
5

_she() {
    local cur
    _get_comp_words_by_ref cur
}
complete -F _she she

我的想法是只要当前的输入能够作为work下的一个目录名字的前缀，那么就认为这个子目录是本次补全的目标。为此，我需要先获取到work目录下的所有子目录的名称。利用ls命令可以做到这一点，同时为了便于处理，在这里将ls返回的文件名列表作为数组保存起来。修改后的_she函数的代码如下

1
2
3
4
5
6

_she() {
    local cur
    local dirs
    _get_comp_words_by_ref cur
    dirs=($(ls ~/src/work/))
}

现在，只要遍历${dirs}并找出第一个以用户输入的${cur}为名字前缀的目录即可。最终_she函数的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

_she() {
    local cur
    local dirs
    _get_comp_words_by_ref cur
    dirs=($(ls ~/src/work/))
    for dir in ${dirs[@]}
    do
        case ${dir} in
            ${cur}*)
                COMPREPLY="${dir}"
                return 0
                ;;
        esac
    done
}