庄周梦蝶

生活、程序、未来

编程小记: bug、clojure 状态和 paxos

| Comments

一个 Bug

前段时间观察我们 API 系统的 hystrix 监控,一直发现一个函数 cache/add 的调用特别的高,在整个集群范围内高峰的时候接近 3 到 4 万的 QPS,跟其他指标比起来非常的碍眼,极不正常。

抽了点时间专门调查了下,原来是不小心掉进去了 hystrix request cache 的坑里。

Hystrix Request Cache 的原理很简单,在同一个 RequestContext 里,对某个 command 调用同样的参数,第一次调用的结果将被缓存,后续的对同样参数的请求将直接返回第一次的结果,通过内存换效率,类似 clojure 的 memoize

简单例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(require '[com.netflix.hystrix.core :refer [defcommand with-request-context]]))

(def call-times (atom 0))

(defcommand myinc
  {:hystrix/cache-key-fn (fn [i] (str i))}
  [i]
  (swap! call-times inc) ;;统计调用次数
  (+ 1 i))

(with-request-context
  ;;调用了两次 myinc
  (myinc 1)
  (myinc 1))

(println @call-times) ;; call-times 只统计了一次调用。

业务代码里有一段逻辑大概是这样:

1
2
3
4
5
6
(def get-or-create [k nv]
  (if-let [v (get-value k)]
    v
    (if-not (add k nv)
      (recur k nv)
      nv)))

其中 get-value 是一个 hystrix command 设置了 cache-fn 启用了请求缓存。这段代码是尝试先从缓存里加载 k 对应的值,如果没有,就将 nv 存储到 k 键上,如果 add 存储成功,返回 nv,如果 add 失败,循环重试(表示有其他人 add 成功,我们可以重试 get-value)。

问题就出在 recur 循环上,因为 get-value 启用了请求缓存,那么循环调用 get-or-create 的时候因为仍然在同一个 RequestContext 里,导致 (get-value k) 一直为空,但是接下来的 add 也继续失败,不停地 recur 循环。后果就是 get-valueadd 都被无限调用,并且耗费了大量 CPU。

解决起来也简单,在 recur 之前清空请求缓存即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defn invalidate-get-cache [k]
    (..
     HystrixRequestCache
     (getInstance (get-command-key)
                  (HystrixConcurrencyStrategyDefault/getInstance))
     (clear k)))

(def get-or-create [k nv]
  (if-let [v (get-value k)]
    v
    (if-not (add k nv)
      (do
        ;;清空 get-value 请求缓存
        (invalidate-get-cache k)
        (recur k nv))
      nv)))

volatile! 和 local.var

在 Clojure 1.7 之前,为了保存一个可变的状态,你的大部分选择是 atom,除非为了 STM 协作事务才使用 ref。但是 atom 严格的原子性导致它的效率在简单的场景里就不是特别合适,比如我只是保存一个局部的可变状态,它只是在局部范围内可变,收集或者统计一些状态,不会发布到外面,完全没有必要保证严格的原子性。还有配置型的全局状态,接近只读。

因此 Clojure 1.7 为了改善 transducer 的实现效率引入了新的可变状态保存器—— volatile,它的语义与 Java 里的 volatile 完全一样,仅保证可见性,不保证原子性

1
2
3
4
5
6
7
8
9
10
11
12
13
(def val (volatile! 0))

@val
;;=> 0

(vswap! val inc)
;;=> 1

(vreset! val "nothing")
;;=> "nothing"

@val
;;=> "nothing"

不保证原子性的意思就是 (vswap! val inc) 这个递增调用在多线程环境下会产生不同步的结果。

在一些不需要原子操作的场合就非常适合替代 atom 了,比如全局状态、局部状态等。

但是,其实呢,这还不够, volatile 本身仍然有可见性的严格要求,每次读取都强制从 main memory 读取最新的值,如果我只是局部变量在用,或者完全不需要同步的场合里,一个更轻量级的状态保存器是有必要的。因此我写了个 local.var。它就更简单了,只是一个 Object 里保存了一个 value 值,没有任何同步的语义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(require '[local.var :refer [transient-var! ltv-reset! ltv-swap! transient-var?]])

(let [sent (transient-var! false)]
    ;;send emails to client
    ;;......
    (ltv-reset! sent true)
    (if @sent
        (println "Sent email successfully!")
        (println "Sent email failed.")))

(def x (transient-var! 1))
@x         ;; => 1
(deref x)  ;; => 1

(ltv-reset! x 99) ;; => 99
@x                ;; => 99

(ltv-swap! x inc)   ;; => 100
(transient-var? x)  ;; => true

@(future (ltv-reset! x 100))   ;; =>  IllegalAccessError Local transient var used by 
                               ;;     non-owner thread  local.var/ltv-reset!

并且类似 transient 集合那样,加了 Thread Owner 的保护,避免被多线程修改。

Paxos

最近连读了几篇一致性算法的论文。 Paxos 琢磨的最多,毕竟它没有像 RAFT 那样有清晰明确的算法步骤,围绕它的解释也有一大堆论文,made simple, made live, made pratical,乃至于要 made crazy 了。

这里稍微总结下我的理解。

第一, Paxos 解决什么问题? 简单地说就是在多个参与者的情况下确定一个值,并且这个值是唯一的。少数服从多数,超过一半的参与者确定的值,就可以代表整个群体的的确认值。中央决定了,就你来当领导。

第二,为了达到这个目标应该怎么做?我们分解下步骤:

  1. 每个人提出一些提议,以供大家选择,这称为 proposal 阶段。
  2. 每个人收到他人的提议,决定要不要接受,产生一个选择集。
  3. 在选择集合中确定唯一的一个,并让所有人知道。

对应到 paxos 过程就是其中的 proposal、accept 和 learn 三阶段。Proposal 阶段产生提议,结合 accept 阶段来确定唯一的值,最终 learn 阶段通知这个确定结果给所有参与者。

为了让选择收敛唯一,又引入了一个 MaxVote 机制,每一轮投票选择的值都是上一轮确定的最高提议编号的值,如果没有,则任意选择一个新值。哪怕有冲突导致多轮投票,确定后的值却不会变。

Paxos instance 是确定一个值,那么 multi paxos 就是确定多个值的过程。为了避免冲突频繁提升提议编号,加速达成一致的效率, multi paxos 自然而然地要求产生一个 leader proposer ,它来产生一系列提议并赋予编号,还可以缩减 prepare 阶段。

更进一步,我们在谈论值,那么值到底是什么? 结合实际的工程项目,需要跟 Replication State Machine 结合起来,简单来讲,值就是日志,paxos 的过程就是要决定一系列日志的顺序在所有参与机器之间保持一致,那么一致顺序的日志回放加上状态机变迁,我们可以让所有参与者里的状态机状态保持一致,也就是达到了在机器之间复制状态机的目的,这就是我们工程上想要的一致性。

Leiningen 代理设置

| Comments

墙已经成为平常工作效率最大的敌人。由于我们内部的 maven 仓库也部署在海外,导致 Leiningen 下载依赖经常超时。你不得不走代理才能解决。这里记录下大部分要点。

首先修改 lein 脚本本身,默认不超时,建议加入超时设置,找到下面类似的代码:

1
2
3
4
5
6
7
8
9
10
 "$LEIN_JAVA_CMD" \
            "${BOOTCLASSPATH[@]}" \
            -Dfile.encoding=UTF-8 \
            -Dmaven.wagon.http.ssl.easy=false \
            -Dmaven.wagon.rto=600000 \
            $LEIN_JVM_OPTS \
            -Dleiningen.original.pwd="$ORIGINAL_PWD" \
            -Dleiningen.script="$SCRIPT" \
            -classpath "$CLASSPATH" \
            clojure.main -m leiningen.core.main "$@"

新增的配置选项是 -Dmaven.wagon.rto=600000,也就是 10 分钟超时。

其次,如果你有一个 HTTP 代理, lein 尊重 http_proxyhttps_proxy 环境变量,可以将下面代码加入 ~/.profile,也可以使用的时候 export 下:

1
2

http_proxy=http://username:password@proxy:port
https_proxy=http://username:password@proxy:port

设置代理后,所有 lein 发起的 http 请求都将走代理,你可以可以设置一个白名单避免代理:

1
http_no_proxy="*example1.com|*example2.com|*example3.com"

最后,如果你用的是 socks5 代理,比如 shadowsocks 搭建的代理服务器,那么可以安装 privoxy 将 socks5 转为 HTTP 代理:

1
$ brew install privoxy

安装后,默认配置在 /usr/local/etc/privoxy/config 文件,找到下面类似这行代码,修改成你的 socks5 代理配置:

1
    forward-socks5t   /               127.0.0.1:1080 .

我这里是 127.0.0.1:1080

默认 privoxy 监听在 8118 端口,因此设置 http_proxy 为该端口即可:

1
2
export https_proxy=http://127.0.0.1:8118
export http_proxy=http://127.0.0.1:8118

深夜杂感

| Comments

可能是今晚上 8 点就上床睡觉,11 点醒过来就再也不睡着了。胡思乱想,趁着还清醒,可以稍微总结下。

人们总是说过了 30 岁,是个坎。我原来不觉的,上周刚过了 32 周岁的生日,慢慢有那么点感觉。这感觉是什么?具体地来说,是更谨小慎微,并且缺乏用于尝试和勤奋自律的劲头。

坦率地说,有家有室后,你的生活的很大一部分精力是投入在家庭生活里。如果你 20 出头,看这种日子会觉的索然无趣,但是人到中年,你会感觉,家可能是才是最重要的部分,你会乐在其中。

所有时间管理的核心其实就是分配你的精力。这边投入多了,那边必然少了。加上身体机能的下降,生活的磨砺,你的心性会有渐进的变化。变化有好有坏,哪个方向,在于一心。

但是呢,我不甘心如此下去了。

还没有去过几个国家,还没有做出一点值得称道的东西,还没有写过一门编程语言,还没有做过超大规模的系统……

过去别人说程序员当不了一辈子, 很庆幸我还在写代码,并且仍然留有热情,并且预计这个热情可以持续下去。

那么,趁还有半辈子,可以立个 flag,继续前行,莫忘初衷,是以为记。

Redis 高可用(1)——Sentinel 篇

| Comments

最近在学习 Redis 的高可用方案,就从 sentinel 开始。本篇文档基本只是 redis sentinel 官方文档的摘要和总结,感兴趣的直接阅读官方文档是更好的选择。

基本原理

Sentinel 的原理并不复杂:

  • 启动 n 个 sentinel 实例,这些 sentinel 实例会去监控你指定的 redis master/slaves
  • 当 redis master 节点挂掉后, Sentinel 实例通过 ping 检测失败发现这种情况就认为该节点进入 SDOWN 状态,也就是检测的 sentinel 实例主观地(Subjectively)认为该 redis master 节点挂掉。
  • 当一定数目(Quorum 参数设定)的 Sentinel 实例都认为该 master 挂掉的情况下,该节点将转换进入 ODOWN 状态,也就是客观地(Objectively)挂掉的状态。
  • 接下来 sentinel 实例之间发起选举,选择其中一个 sentinel 实例发起 failover 过程:从 slave 中选择一台作为新的 master,让其他 slave 从新的 master 复制数据,并通过 Pub/Sub 发布事件。
  • 使用者客户端从任意 Sentinel 实例获取 redis 配置信息,并监听(可选) Sentinel 发出的事件: SDOWN, ODOWN 以及 failover 等,并做相应主从切换,Sentinel 还扮演了服务发现的角色。
  • Sentinel 的 Leader 选举采用的是 Raft 协议

一张示意图,正常情况下:

Sentinel 原理

当 M1 挂掉后:

Sentinel 原理

节点 2 被提升为 master,Sentinel 通知客户端和 slaves 去使用新的 Master。

搭建实验环境

  • 两个 redis,一个主一个从,分别监听在 6379 和 6380 端口
1
2
$ redis-server
$ redis-server --port 6380
  • redis-cli -p 6380 连上 6380 端口的 redis,执行 slaveof 127.0.0.1 6379 将它设置为 6379 的 slave。
  • 启动三个 sentinel 实例,分别监听在 5000 – 5002 端口,并且监控 6379 的 redis master,首先是配置文件

s1.conf:

1
2
3
4
port 5000
sentinel monitor mymaster 127.0.0.1 6370 2
sentinel down-after-milliseconds mymaster 1000
sentinel failover-timeout mymaster 60000

其他两个配置文件是 s2.conf 和 s3.conf 只是将 port 5000 修改为 5001 和 5002,就不再重复。需要确保配置文件是可写的,因为 Sentinel 会往配置文件里添加很多信息作为状态持久化,这是为了重启等情况下可以正确地恢复 sentinel 的状态。

启动:

1
2
3
$ redis-sentinel s1.conf
$ redis-sentinel s2.conf
$ redis-sentinel s3.conf

配置说明:

  • port ,指定 sentinel 启动后监听的端口,sentinel 实例之间需要通过此端口通讯。
  • sentinel monitor [name] [ip] [port] [quorum],最重要的配置,指定要监控的 redis master 的 IP 和端口,给这个监控命名 name。Quorum 指定至少多少个 sentinel 实例对 redis master 挂掉的情况达成一致,只有达到这个数字后,Sentinel 才会去开始一次 failover 过程。
  • down-after-milliseconds,设定 Sentinel 发现一个 redis 没有响应 ping 到 Sentinel 认为该 redis 实例不可访问的时间。
  • failover-timeout,Sentinel 实例投票对于同一个 master 发起 failover 过程的间隔时间,防止同时开始多次 failover。

Sentinel 启动后会输出类似的日志:

1
2
17326:X 13 Oct 12:00:55.143 # +monitor master mymaster 127.0.0.1 6379 quorum 2
17326:X 13 Oct 12:00:55.143 * +slave slave 127.0.0.1:6380 127.0.0.1 6380 @ mymaster 127.0.0.1 6379

表示开始监控 mymaster 集群,并输出集群的基本信息。

以及 Sentinel 之间的感知日志,比如 s3 节点的输出:

1
2
18441:X 13 Oct 12:01:39.985 * +sentinel sentinel eab05ac9fc34d8af6d59155caa195e0df5e80d73 127.0.0.1 5000 @ mymaster 127.0.0.1 6379
18441:X 13 Oct 12:01:52.918 * +sentinel sentinel 4bf24767144aea7b4d44a7253621cdd64cea6634 127.0.0.1 5002 @ mymaster 127.0.0.1 6379

查看信息

可以用 redis-cli 连上 sentinel 实例,查看信息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
$ redis-cli -p 5000
127.0.0.1:5000> sentinel master mymaster
 1) "name"
 2) "mymaster"
 3) "ip"
 4) "127.0.0.1"
 5) "port"
 6) "6379"
 7) "runid"
 8) "4b97e168125b735e034d49c7b1f45925f43aded9"
 9) "flags"
10) "master"
11) "link-pending-commands"
12) "0"
13) "link-refcount"
14) "1"
15) "last-ping-sent"
16) "0"
17) "last-ok-ping-reply"
18) "729"
19) "last-ping-reply"
20) "729"
21) "down-after-milliseconds"
22) "1000"
23) "info-refresh"
24) "6258"
25) "role-reported"
26) "master"
27) "role-reported-time"
28) "11853370"
29) "config-epoch"
30) "0"
31) "num-slaves"
32) "1"
33) "num-other-sentinels"
34) "2"
35) "quorum"
36) "2"
37) "failover-timeout"
38) "60000"
39) "parallel-syncs"
40) "1"

sentinel master [name] 用于查看监控的某个 redis master 信息,包括配置和状态等,其他命令还包括:

  • sentinel masters 查看所有监控的 master 信息。
  • sentinel slaves [name] 查看监控的某个 redis 集群的所有 slave 节点信息。
  • sentinel sentinels [name] 查看所有 sentinel 实例信息。

更重要的一个命令是根据名称来查询 redis 信息,客户端会用到:

1
2
3
127.0.0.1:5000> SENTINEL get-master-addr-by-name mymaster
1) "127.0.0.1"
2) "6379"

测试 Failover

我们让 6379 的 master 主动休眠 30 秒来观察 failover 过程:

1
$ redis-cli -p 6379 DEBUG sleep 30

我们可以看到每个 sentinel 进程都监控到 master 挂掉,从 sdown 状态进入 odown,然后选举了一个 leader 来进行 failover,最终 6380 成为新的 master, sentinel 的日志输出:

1
2
3
4
5
6
7
8
9
10
18441:X 13 Oct 15:26:51.735 # +sdown master mymaster 127.0.0.1 6379
18441:X 13 Oct 15:26:51.899 # +new-epoch 1
18441:X 13 Oct 15:26:51.900 # +vote-for-leader eab05ac9fc34d8af6d59155caa195e0df5e80d73 1
18441:X 13 Oct 15:26:52.854 # +odown master mymaster 127.0.0.1 6379 #quorum 3/2
18441:X 13 Oct 15:26:52.854 # Next failover delay: I will not start a failover before Thu Oct 13 15:28:52 2016
18441:X 13 Oct 15:26:53.034 # +config-update-from sentinel eab05ac9fc34d8af6d59155caa195e0df5e80d73 127.0.0.1 5000 @ mymaster 127.0.0.1 6379
18441:X 13 Oct 15:26:53.034 # +switch-master mymaster 127.0.0.1 6379 127.0.0.1 6380
18441:X 13 Oct 15:26:53.034 * +slave slave 127.0.0.1:6379 127.0.0.1 6379 @ mymaster 127.0.0.1 6380
18441:X 13 Oct 15:26:54.045 # +sdown slave 127.0.0.1:6379 127.0.0.1 6379 @ mymaster 127.0.0.1 6380
18441:X 13 Oct 15:27:20.383 # -sdown slave 127.0.0.1:6379 127.0.0.1 6379 @ mymaster 127.0.0.1 6380

日志的几个主要事件:

  • +sdown master mymaster 127.0.0.1 6379,发现 master 检测失败,主观认为该节点挂掉,进入 sdown 状态。
  • +odown master mymaster 127.0.0.1 6379 #quorum 3/2,有两个 sentinel 节点认为 master 6379 挂掉,达到配置的 quorum 值 2,因此认为 master 已经客观挂掉,进入 odown 状态。
  • +vote-for-leader eab05ac9fc34d8af6d59155caa195e0df5e80d73 准备选举一个 sentinel leader 来开始 failover。
  • +switch-master mymaster 127.0.0.1 6379 127.0.0.1 6380 切换 master 节点, failover 完成。
  • +config-update-from sentinel eab05ac9fc34d8af6d59155caa195e0df5e80d73 127.0.0.1 5000 @ mymaster 127.0.0.1 6379 更新 sentinel 配置。
  • 6379 休眠回来,作为 slave 挂载到 6380 后面,可见 sentinel 确实同时在监控 slave 状态,并且挂掉的节点不会自动移除,而是继续监控。

此时查看 sentinel 配置文件,会发现增加了一些内容:

1
2
3
4
5
6
7
8
9
# Generated by CONFIG REWRITE
dir "/Users/dennis/opensources/redis-sentinel"
sentinel failover-timeout mymaster 60000
sentinel config-epoch mymaster 1
sentinel leader-epoch mymaster 1
sentinel known-slave mymaster 127.0.0.1 6379
sentinel known-sentinel mymaster 127.0.0.1 5001 8ba1e75cbf4c268be4a2950ee7389df746c6b0b4
sentinel known-sentinel mymaster 127.0.0.1 5002 4bf24767144aea7b4d44a7253621cdd64cea6634
sentinel current-epoch 1

可以看到 sentinel 将最新的集群状态写入了配置文件。

运维

命令

除了上面提到的一些查看信息的命令之外, sentinel 还支持下列命令来管理和检测 sentinel 配置:

  • SENTINEL reset <pattern> 强制重设所有监控的 master 状态,清除已知的 slave 和 sentinel 实例信息,重新获取并生成配置文件。
  • SENTINEL failover <master name> 强制发起一次某个 master 的 failover,如果该 master 不可访问的话。
  • SENTINEL ckquorum <master name> 检测 sentinel 配置是否合理, failover 的条件是否可能满足,主要用来检测你的 sentinel 配置是否正常。
  • SENTINEL flushconfig 强制 sentinel 重写所有配置信息到配置文件。

增加和移除监控以及修改配置参数:

  • SENTINEL MONITOR <name> <ip> <port> <quorum>
  • SENTINEL REMOVE <name>
  • SENTINEL SET <name> <option> <value>

增加和移除 Sentinel

增加新的 Sentinel 实例非常简单,修改好配置文件,启动即可,其他 Sentinel 会自动发现该实例并加入集群。如果要批量启动一批 Sentinel 节点,最好以 30 秒的间隔一个一个启动为好,这样能确保整个 Sentinel 集群的大多数能够及时感知到新节点,满足当时可能发生的选举条件。

移除一个 sentinel 实例会相对麻烦一些,因为 sentinel 不会忘记已经感知到的 sentinel 实例,所以最好按照下列步骤来处理:

  • 停止将要移除的 sentinel 进程。
  • 给其余的 sentinel 进程发送 SENTINEL RESET * 命令来重置状态,忘记将要移除的 sentinel,每个进程之间间隔 30 秒。
  • 确保所有 sentinel 对于当前存货的 sentinel 数量达成一致,可以通过 SENTINEL MASTER [mastername] 命令来观察,或者查看配置文件。

客户端实现

客户端从过去直接连接 redis ,变成:

  1. 先连接一个 sentinel 实例
  2. 使用 SENTINEL get-master-addr-by-name master-name 获取 redis 地址信息。
  3. 连接返回的 redis 地址信息,通过 ROLE 命令查询是否是 master。如果是,连接进入正常的服务环节。否则应该断开重新查询。
  4. (可选)客户端可以通过 SENTINEL sentinels [name] 来更新自己的 sentinel 实例列表。

当 Sentinel 发起 failover 后,切换了新的 master,sentinel 会发送 CLIENT KILL TYPE normal 命令给客户端,客户端需要主动断开对老的master 的链接,然后重新查询新的 master 地址,再重复走上面的流程。这样的方式仍然相对不够实时,可以通过 sentinel 提供的 Pub/Sub 来更快地监听到 failover 事件,加快重连。

如果需要实现读写分离,读走 slave,那可以走 SENTINEL slaves [name] 来查询 slave 列表并连接。

生产环境推荐

对于一个最小集群,Redis 应该是一个 master 带上两个 slave,并且开启下列选项:

1
2
min-slaves-to-write 1
min-slaves-max-lag 10

这样能保证写入 master 的同时至少写入一个 slave,如果出现网络分区阻隔并发生 failover 的时候,可以保证写入的数据最终一致而不是丢失,写入老的 master 会直接失败,参考 Consistency under partitions

Slave 可以适当设置优先级,除了 0 之外(0 表示永远不提升为 master),越小的优先级,越有可能被提示为 master。如果 slave 分布在多个机房,可以考虑将和 master 同一个机房的 slave 的优先级设置的更低以提升他被选为新的 master 的可能性。

考虑到可用性和选举的需要,Sentinel 进程至少为 3 个,推荐为 5 个,如果有网络分区,应当适当分布(比如 2 个在 A 机房, 2 个在 B 机房,一个在 C 机房)等。

其他

由于 Redis 是异步复制,所以 sentinel 其实无法达到强一致性,它承诺的是最终一致性:最后一次 failover 的 redis master 赢者通吃,其他slave 的数据将被丢弃,重新从新的 master 复制数据。此外还有前面提到的分区带来的一致性问题。

其次,Sentinel 的选举算法依赖时间,因此要确保所有机器的时间同步,如果发现时间不一致,Sentinel 实现了一个 TITL 模式来保护系统的可用性。

更好,还是更坏?

| Comments

变化时时刻刻,缓慢的,或剧烈的,无可避免,就像崔健唱的那样:不是我不明白,这世界变化快。不要说世界,就说自个儿,变化也太快,更重要的是你也不明白这变化是好的,还是坏的。当然,更佛家一点的说法,色即是空,空即是色,世界就是我,我就是世界,所以没有特别必要强调『我』或者『世界』,因为两者是『一体』的。

明显坏的变化,肚子大了,三高来了,今年还犯了一次痛风,要和啤酒海鲜菠菜说再见了。身体在告警:您的余额要不足了,请及时充值。跑步不少,但是欠费更多。

还有个坏的变化,工作上的冲劲似乎没了,叹气的时候多了,旁观的时候多了,憋着话的时候也多了。妥协的多了,抗争的少了。眼看着一头牛要滑向深渊,你得用力拽住、劝慰,再慢慢拉回来。

另一个可能是不好不坏的变化,从无产者变成可疑的有产者(当老毛还挂在城楼上的,我们可能是有产者吗?),心态没那么愤世嫉俗了,关注民生新闻少了,愤怒的次数少了,有『小粉红』的倾向,从全盘西化转向中国人的事情还是要自己解决。某些观点越来越中立,越来越中庸。同样,也可能越来越宽容,大家要和谐,不要搞大新闻。

好的变化也有一些,恢复写博客算是一个,陆续在更新开源库也算一个,读书相比去年也读的多了一点,闲书少了,技术的多了一点。其他的,和儿子关系相处更好了一点,也算是个好变化。

无论是好的,还是坏的,只能接受,因为这就是世界,也就是我。正面的或者负面的,你只能拥抱、亲吻、吵架、小心地劝导、耐心地包容,它们将伴随一生,如影随形,越早承认并坦然接受这一点,生活会更好点。

Xmemcached 2.0.1 is out!

| Comments

陆续准备更新一些 Java 开源库,先从 xmemcached 开始。我在 LeanCloud 也用了自己这个库,用来和 memcached 和 kestrel 交互,总体还是稳定靠谱的。

昨天晚上更新了 2.0.1 版本,主要变更如下:

  • 将心跳和连接修复线程设置为 daemon 线程。
  • 默认关闭客户端的 shutdown hook,如果需要开启,可以通过启动传参 -Dxmemcached.shutdown.hook.enable=true
  • 改进了内部日志,更符合习惯。
  • 修复二进制协议的 Auth 授权实现。
  • 新增 setSelectorPoolSize 可用于单独设置每个客户端实例的 NIO Reactor 线程池大小。
  • 特别感谢 bmahe,做了很多代码清理和重构的工作。
  • 一些小的内部 Bug 修复,感谢所有贡献 PR 的朋友。
  • 搬迁了文档和设计了新首页 http://fnil.net/xmemcached/

Maven 只要修改下引用即可:

1
2
3
4
5
 <dependency>
       <groupId>com.googlecode.xmemcached</groupId>
       <artifactId>xmemcached</artifactId>
       <version>2.0.1</version>
  </dependency>

Java 与 CPU 高速缓存

| Comments

上周在公司临时做了个小分享,科普了下 CPU 高速缓存,以及 Java 程序员应该关注的问题,比如利用时空局部性原理,避免多核下的伪共享(False Sharing)等,因为是下午临时写的 PPT,可能有一些谬误,有兴趣的不妨看看

或者直接看链接: http://www.slideshare.net/killme2008/java-cpu-64198539

最近关注这个问题是因为在阅读《现代体系结构上的 Unix 系统——内核程序员的对称处理和缓存技术》一书,这是伞哥推荐的书,确实非常棒,澄清了我很多概念,推荐有兴趣的朋友阅读下。

Java 里伪共享的问题(False Sharing)已经被谈论了很多,甚至 Java8 都引入了 @Contended来帮助你做数据对齐,但是还有一个问题似乎没什么人谈过,那就是在获得自旋锁时减少对高速缓存行的争用,为了说明这个问题,我写了个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;

public class BusyLock {

  private int count;
  // 自旋锁状态
  private AtomicInteger state;

  private BusyLock() {
      this.count = 0;
      this.state = new AtomicInteger(0);
  }

  /**
  * 利用 CAS 实现自旋锁
  */
  private void lock() {
      while (!state.compareAndSet(0, 1))
          ;
  }

  /**
  * 解锁
  */
  private void unlock() {
      state.set(0);
  }

  /**
  * 递增 count,使用自旋锁保护 count
  */
  public void incr() {
      lock();
      count = count + 1;
      unlock();
  }

  /**
  * 测试,开启 50 个线程递增 count,每个线程循环 10 万次。
  * 
  * @param warnUp
  * @throws Exception
  */
  public static void runTests(boolean warnUp) throws Exception {
      int threads = 50;
      int n = 100000;
      BusyLock bl = new BusyLock();
      Thread[] ts = new Thread[threads];
      long start = System.nanoTime();
      CyclicBarrier barrier = new CyclicBarrier(threads + 1);
      for (int i = 0; i < threads; i++) {
          ts[i] = new Thread(new Runnable() {

              @Override
              public void run() {
                  try {
                      barrier.await();
                      for (int j = 0; j < n; j++)
                          bl.incr();
                      barrier.await();
                  } catch (Exception e) {

                  }
              }
          });
          ts[i].start();
      }
      barrier.await();
      barrier.await();
      for (Thread t : ts) {
          t.join();
      }
      long duration = (System.nanoTime() - start) / 1000000;
      if (!warnUp)
          System.out.println("count= " + bl.count + ",cost:" + duration
                  + "ms");

  }

  public static void main(String[] args) throws Exception {
      // 测试,先 warm up
      runTests(true);
      // 实际测试
      runTests(false);
  }

}

代码稍微注释了下,熟悉 Java 类库的都应该可以理解。为了演示这个问题,这里没有用 ReentrantLock,而是使用 AtomicInteger 来实现自旋锁保护 count 这个资源,incr 方法会递增 count,启动 50 个线程并发循环调用 incr,然后计算耗时。

我们关注的是 lock 方法的实现:

1
2
3
4
private void lock() {
  while (!state.compareAndSet(0, 1))
      ;
}

利用 compareAndSet 来尝试更新 state,1 表示锁定状态,0 表示空闲,每个线程都尝试去取得锁的所有权,如果失败,进入 while 忙等待。compare-and-set 都是利用 CPU 提供的原子指令(一般是 test_and_set)来实现。

这个实现没有问题,但是当考虑到多核状态下的高速缓存的时候,如果对于锁的争用非常激烈,那么会有很多的线程在 while 上的 compareAndSet 原子操作上等待,保存 state 的缓存行就会在多个 CPU 之间『颠簸』,导致了不必要的总线争用。

为了减少总线争用,我们可以改进下 lock:

1
2
3
4
5
6
7
8
private void lock() {
  while (!state.compareAndSet(0, 1))
      //对于未能取得锁所有权的线程,在内层循环上等待
      //因为获取了 state 一份共享的高速缓存副本,
      //不会再进一步产生总线通信量
      while (state.get() == 1)
          ;
}

通过增加一个内循环 while (state.get() == 1),让没有获得锁的线程在 state 状态上等待,避免原子操作,可以减少总线争用。每个忙等待的 CPU 都将获得 state 状态的共享副本,以后的循环都将在共享副本上执行,不会再产生总线通信。

当占有锁的线程释放锁(原子地设置 state 为 0)的时候,这些共享的副本会失效(write-invalidate 策略,比如常见的 MESI 协议)或者被更新到最新状态(write-update 策略),这时候才会产生总线通信。

测试两个版本的 lock 方法,在我的机器上有比较明显的差异,没有内层循环的 lock 版本耗时在 6-8 秒,而增加了内层循环的 lock 耗时在 2.5 -5 秒。

Clojure method missing 迷思

| Comments

Clojure 的元编程是基于宏(Macro)来实现的。宏很强大,但是有些场合,我偶尔会怀念 Ruby 的 Method missing。

什么是 Method missing?

什么是 Method missing?看一个简单的例子,Ruby 的 Hash 访问是通过 [] 运算符:

1
2
3
4
5
6
7
8
 > h={a: 1, b: 2}
 => {:a=>1, :b=>2}

 > h[:a]
 => 1

 > h[:b]
 => 2

但是这种代码写多了也烦,我想用 dot 语法,也就是 h.a 来访问,可能更方便一点,这时候祭出 open class + method missing 就可以了:

1
2
3
4
5
6
7
8
  class ::Hash

    def method_missing(name, *args)
      return self[name.to_sym] if key? name.to_sym
      super(name, *args)
    end

  end

我们给标准库的 Hash 类添加了 method_missing 方法,它会『兜底』所有 Hash 没有实现的方法,将方法名和参数传递给 method_missing,我们在上面的例子里将方法名转为 symbol,然后判断这个 symbol 在 hash 里是否存在,如果存在,返回它对应的值,否则调用原始的 super.method_missing(也就是报错)。

修改之后,我们可以这么获取 h 中对应的值了:

1
2
3
4
5
> h.a
 => 1

> h.b
 => 2

Method missing 体现的就是 Ruby 的动态性,在求值 h.a 的时候,Ruby 运行时发现 Hash 没有 a 这个方法,那么会转而去调用 method_missing(a)

它有什么用呢?除了上面这个简单的例子之外,举一个更常见的场景——远程调用的本地客户端 stub。

通常,在静态类型语言里,RPC 定义一些远程接口,客户端如果想要『无缝』地调用这些接口,需要通过一层代理层,来将本地调用转化成远程调用,由代理层来处理远程调用的细节,客户端的代码显得更干净和规整。代理层通常是通过 RPC 接口定义工具编译生成代码。无论是 gRPC,还是 thrift 之类,都是这么做的。

但是有了 method missing,这一层代理就不需要有一个编译的过程,完全可以动态地将请求转发给远程客户端,发起真正的远程调用并返回结果。

还是以 Ruby 里的 JSON RPC 的一个实现库 jimson 为例,服务端实现一个 sum 接口:

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

class MyHandler
  extend Jimson::Handler

  def sum(a,b)
    a + b
  end
end

server = Jimson::Server.new(MyHandler.new)
server.start

客户端调用:

1
2
3
require 'jimson'
client = Jimson::Client.new("http://www.example.com:8999")
result = client.sum(1,2)

client.sum , client 实质上并没有 sum 方法,它通过 method_missing 将这个调用转化成一个 JSON RPC 的 method 调用,同时将方法名称 sum 和参数 1, 2 传递给了服务端处理,处理完成后返回结果给调用客户端。

Clojure 里怎么办?

前一段时间,我在尝试用 clojure 实现一个 JSON RPC 调用库的时候,就一直琢磨这个问题,我有一个方法:

1
2
3
(ns example)
(defn sum [a b]
  (+ a b))

现在我可以在别的地方直接 require 调用:

1
2
(require '[example :as e])
(e/sum 1 2) ; => 3  

现在假设 sum 定义在远端服务端,我在本地客户端还想用 (e/sum 1 2) 这样的方式调用,并且还能查看文档、参数列表等元信息,我能怎么办?

最终我采用的解决办法也不是 method missing,当时还没有深入思考这个特性在 clojure 里应该怎么去实现。而是这样的方式:

  • 引入 defrpc 宏用来定义远程函数,包装 defn,同时导出一份函数的元信息(doc, arglists等)给服务端。
  • 扩展 JSON RPC 协议,添加特别的 method —— __metadata,专门用于发布服务端提供的 RPC 接口的元信息列表。
  • 实现了一个 require-remote 宏,它会调用 __metadata 远程接口获取服务端的接口元信息,然后动态生成代理的 namespace 和 function,并 require 到当前 namespace。

最终,服务端的代码变成:

1
2
3
4
5
(ns example)
(defrpc sum
   "sum some numbers."
   [a b]
   (+ a b))

客户端在初始化 RPC 客户端之后(设置连接信息之类),只要替换掉 requirerequire-remote 即可:

1
2
(require-remote '[example :as e])
(e/sum 1 2) ; => 3  

这样的改动之后,基本上我原来的那些代码几乎不用做多少修改,只是替换下 defn(换成 defrpc) 和 require (换成require-remote)就可以完美地在拆分运行。

为了解决元信息获取接口的远程依赖和接口兼容问题,避免在打包编译的阶段报错,RPC 客户端也引入了元信息的本地缓存。

这个实现如果稍微整理下代码也可以开源出来,不过现在真的太懒,没有精力做这样的事情了,思路大体如此,有兴趣的自己实现也不难。

Clojure 的 method missing 在哪里?

说了这么多,还是没有提到正文, Clojure method missing 在哪里呢?在上一节,我不得不引入一个元信息发布接口,然后在客户端去动态根据这些元信息生成一堆代理的 namespace 和 functions,看起来比很多静态语言高明了一点,但是其实只是将代理层的编译从静态变为了运行时动态生成罢了。

本质上的问题,客户端在调用远程一个接口的时候,它在本地确实是不存在的,Clojure 或者 Java 之类的解决方案仍然是动态或者静态地生成代理层,代理层转发调用给远程客户端,而 Ruby 的 method missing 则是在运行时委托给 method_missing 转发给远程客户端,后者明显更具有『动态性』,前者因为有了编译的过程,为了让编译通过,需要代理层的存在,而后者不需要。

那么 clojure 有没有办法来引入 method missing 呢?

我先做了一个尝试,基于宏来实现,请看这个 gist

我们先在 missing-test 里定义了 method-missinghello 方法:

1
2
3
4
5
6
7
8
(ns missing-test)

(defn method-missing [func args]
  (println "missing '" func "' with args:" args)
  [func args])

(defn hello [name]
  (str "hello," name))

然后在另一个 namespace,我们尝试调用它:

1
2
3
4
5
6
(ns missing-example
  (:require [missing-test :as t]))

(with-method-missing (the-ns 'missing-test)
  (println (t/hello "dennis"))
  (println (t/world "dennis")))

这将会输出:

1
2
3
4
hello,dennis
missing ' world ' with args: dennis
[world dennis]
nil

hello 方法在 missing-test 里定义了,它返回 hello,dennis,而 world 方法没有定义,所以会去调用 method-missing,先打印 missing ' world ' with args: dennis,然后返回函数名和参数组成的 vector。

关键代码是 with-method-missing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defmacro with-method-missing [ns & body]
  (let [ns (eval ns)]
    `(do
      ~@(clojure.walk/postwalk
         (fn [form]
           (if (and (list? form)
                    (this-ns? ns (first form))
                    (method-missing? ns (first form)))
             (list `apply (get (ns-publics ns)
                               'method-missing)
                   (vec (cons
                         (name (first form))
                         (next form))))
             form))
         body))))

这个宏做的事情很简单,遍历整个 body 结构,发现任何一个 (a/b p1 p2) 这样的 list,会尝试解析下 a/b 在对应的 namespace 是不是存在,如果不存在 b 方法并且定义了 method-missing,就转而调用 a/method-missing 方法,也就是将 body 里的所有类似 (a/b p1 p2) 转成了 (a/method-missing p1 p2) 的 form。完整的代码参见 gist

这里仍然没有任何的动态性,with-method-missing 将在编译期间展开,不存在的方法将替换成存在的 method-missing,这一切都在编译期间就决定了,不会拖到运行时。

那么,到底能不能实现真正动态的 method missing,并且去掉蹩脚的 with-method-missing,答案是可以的,但是需要去修改 clojure 编译器。

我尝试写的一个 patch,非常简单,在 var 解析的过程里加上一个步骤即可。

打上这个 patch 后,编写 method missing 很容易了:

1
2
3
4
(ns missing-test)

;;定义 method missing,简单地返回参数
(defn -method-missing [ & args] args)

到另一个 namespace 调用:

1
2
3
4
5
6
(ns missing-example)
(require '[missing-test :as t])

(t/hello 3)  ;; => ("hello" 3)

(t/world (range 1 10))  ;; => ("world" (1 2 3 4 5 6 7 8 9))

helloworld 方法都在 missing-test 里没有定义,因此调用 -method-missing 方法,返回调用的方法名称和参数。

翻译:深入理解 Clojure Persistent Vectors 实现 Part 3

| Comments

前言

原文地址:http://hypirion.com/musings/understanding-persistent-vector-pt-3

为什么翻译这系列博客?一直觉着翻译是学习的笨功夫,阅读一遍可能理解了概要,但是其实还是有很多细节遗漏了,翻译这个过程可以查缺补漏,更重要的是,我想重新写博客了 :D。

正文

关于 Clojure Persistent vectors 这个系列博客的 Part 1Part 2 应该可以让你对 persistent vector 的工作原理的有个大概的了解,但是,其实这里仍然有许多不同的方法可以消减(算法)的常数因子(的影响)。可能最容易理解的部分是尾部(tail),我们将在这篇博客里介绍。

尾部的基本原理

Visualisation of two vectors without a tail.

回想下 (conj [1 2 3 4] 5) 这个操作的可视化展示,没有任何尾部实现时:如果在最右叶子节点有空间,我们仅需要拷贝向下到达该叶子节点的路径,并将最后这个新元素插入到拷贝中。

有尾部的时候会有什么不同呢?让我们瞧下:

Visualisation of two vectors with a tail.

不再是在树里面保存最右叶子节点,取而代之,我们在 vector 的头部(header)就持有一个它的直接引用:这是上篇博客后加入 vector 头部的最后部分。指向最右叶子节点的引用称为尾部

对于 conj 操作,我们以检测尾部有没有足够空间而告终。因为这里刚好是这种情况 —— 我们拷贝了尾部,并将新元素插入其中。请注意这是常量时间,不是近乎常量时间。所以,每次在尾部有空余空间的时候,我们 conj 新元素到 vector 的时候,我们都是在做常量时间的操作。

这使得批量操作变得特别快。如果你接连做大量的 conj 操作,结果是每个操作的耗时平均起来更少。对于一个分支因子是 2 的 vector, 1/2(50%) 的 conj 操作(平均起来)是常量时间。如果将分支因子替换成 32, 31/32 的所有 conj 操作都将实际上是常量时间。只有 3.1% 的操作是近乎常量时间,意味着我们得到一个相当显著的常数削减。对于连续的 disj 操作我们也得到同样的性能好处。

所以这看起来是非常吸引人的改进。但是我们如何实现它呢?

尾部偏移量(tail offset)

在我们了解如何实现实际操作之前,我们需要学习一个很容易理解的概念:一个 vector 的尾部偏移量。为了理解 vector 一些操作需要做的修改,我们需要了解这个概念。

尾部偏移量其实就是元素在一棵树里的总量(译者注:请注意,现在最右叶子节点不在树里了,而是在 vector 头部作为尾部存在,因此树里的元素是减少了)。在实践中,就是 tail_offset = vector.length - tail.length。就是这么一个公式,没有比这个公式更多的解释了。我们需要尾部偏移量的理由是,有的时候我们需要回去执行『老的』操作:查找或者修改元素要求我们知道它们是不是在树里,或者是否在尾部里。

举一个尾部偏移量的例子,回想下前文提到的 5 个和 6 个元素的 vector。5 个元素的 vector 在它的尾部里只有一个元素,所以他的尾部偏移量是 4(译者注:vector 长度 5 减去尾部长度 1,结果为 4,后文类似)。拥有 6 个元素的 vector 的尾部偏移量也是 4, 因为它的 尾部引用有 2 个元素。

A visualization of two vectors with 7 and 10 elements, with tails.

更多尾部偏移量的例子请参考上图中的两个 vector。拥有 7 个元素的 vector 的尾部偏移量是 6,而有 10 个元素的 vector 的尾部偏移量是 8。

查找

有没有尾部引用,对于在 vector 中查找一个值的过程来说并没有太大的不同。从根本上有两种情况要考虑:

  • 我们想要查找的值在尾部。
  • 我们想要查找的值在树里面。

这里就是我们需要使用到尾部偏移量的地方。查找过程写成伪代码看起来是这样:

1
2
3
4
5
if lookup_index < tail_offset:
  # tree_lookup = old lookup technique
  return tree_lookup(lookup_index)
else:
  return tail[lookup_index - tail_offset]

因为我们知道尾部偏移量就是元素在树里的总量,我们仅仅需要检查待查找的元素是否比尾部偏移量小。如果是,我们就执行『老的』查找过程,否则,我们知道它在尾部。在那种情况下,我们把索引减去尾部偏移量(这就是我们称之为偏移量的原因),然后使用计算得来的新的索引位置到尾部里查找。

更新

跟查找的实现类似,更新也跟原来的更新实现非常相似。唯一的区别发生在你想更新的值就在尾部里面。再次有两种情况:一是你要更新的值在树里面,另一个就是你要更新的是尾部。

1
2
3
4
5
6
7
8
if update_index < tail_offset:
  # tree_update is the old update technique
  return tree_update(update_index, elt)
else:
  vector_copy = copy_head(this)
  vector_copy.tail = copy_tail(this.tail)
  vector_copy.tail[lookup_index - tail_offset] = elt
  return vector_copy

首先,我们看下更新的元素在树里面的情况。我们仍然以 Part 1 里的老例子为例,更新索引位置 5 的元素:

1
2
(def brown [0 1 2 3 4 5 6 7 8])
(def blue (assoc brown 5 'beef))

这可以得到下面这棵树:

A visualization of two vectors with tails, one with the value at index 5 updated.

正如 Part 1 所解释的那样,我们做了路径拷贝并替换叶子节点上的元素。但是呢,注意到它们共享了尾部:毕竟,它没有变动,因此为什么要费心去拷贝它呢?

第二种情形是我们要修改的元素在尾部。让我们重用前面的例子,但是将索引位置修改 8:

1
2
(def brown [0 1 2 3 4 5 6 7 8])
(def blue (assoc brown 8 'beef))

A visualization of two vectors with tails, one with the value at index 8 updated.

这次看到我们拷贝了 vector 的『头部』和尾部,然后在它上面执行了修改操作。因为我们对树没有做任何修改,我们就可以和没有修改之前的 vector 共享树的部分。这个操作的耗时就是常量的,不是近乎常量级的。

插入

查找和更新都很简单,但是如果我们查看下插入和删除呢?没错,结果是它们也同样不难。对于插入来说,我们再次有两种情形要考虑,但是这次有一点点不同:

  • 在尾部有足够空间。
  • 在尾部没有空间了。

第一种情况非常容易:拷贝下尾部,在它的末尾插入新元素。这篇博客的第一幅图刚好就展示了它是如何工作的。但是当尾部没有足够空间的时候我们应该怎么办?

原理和 Part 1 描述的插入过程很像,但是有一点小修改:不再是插入一个单一的值,替代地,我们插入一个叶子节点。回想下,尾部就是一个叶子节点,被 vector 的根节点直接指向。

A visualization of two vectors, where one - coloured blue - has the other's (coloured brown) tail in its tree.

在上面的示例里,褐色 vector 的尾部已经满了:你没法往尾部插入更多的元素了。一个 conj 操作将创建蓝色的 vector,在那里面我们了解到我们必须将尾部本身插入树中。按照 Part 1 的规则,我们将尾部放入树里面,然后创建一个新的尾部用来存放新元素。

实际上,插入本身不需要更多解释了,并不难理解和掌握它。但是当一个实际的 vector 实现做插入的时候,需要特别小心处理索引。幸运地是,实现过程中需要面对的最大困难是所谓大小差一的错误(off-by-one error,译者注:也就是数组索引位置处理不当,通常在边界的时候多处理或者少处理了一个元素)。

删除

当处理删除的时候,我们面临一个设计上的抉择:某些情况下,我们不得不把叶子节点向上移动作为尾部。但是什么时候应该这样做呢?我们应该在 vector 里保留空的尾部吗?并且只有在对一个尾部已经为空的 vector 执行出队操作的时候才去向上移动叶子节点吗?或者,我们总是保留一个非空的尾部在 vector 中?

结果证明至少有两个理由要求我们保证在所有情况下尾部为空[1]:最显而易见的理由是你现在能够保证 peek 操作一定是常量时间的。另一个不那么明显的理由是随机查找,平均来说将更快:如果在尾部查找一个元素比在树里查找耗时更短,那么更好的是让尾部保持『满』的状态,而不是一个空的尾部。

因此,我们以 —— 你可能猜到了 —— 两种不同的情况处理来结束讨论:

  • 在尾部,我们拥有多于一个的元素。
  • 在尾部,我们只有一个元素。

正如我刚才提到的,不会有任何 vector 会在尾部没有元素(除了空的 vector 这种异常情况)。假设尾部至少有一个元素在完全没有问题的。

A visualization of two vectors, where one vector has copied and popped a tail.

如果在尾部我们有多于一个的元素,我们只需要拷贝这个尾部,删除它的最后一个元素,然后返回新的 vector。上面的例子显示给我们只有尾部不同,正是我们预期的那样。

请记住如果我们对同一个 Persistent Vector 做两次出队操作,我们将创建两个尾部,尽管它们的内容是一样的:

A visualization which shows that popped tails may be equal, but not memory equal.

如果我们在尾部只有一个元素,我们需要将树中的最右叶子节点『提升』为新的尾部,还要将它(译者注:最右叶子节点)从树上移除。这些步骤跟在没有尾部的 vector 执行查找和出队一个元素的操作相似,只是将查找和删除元素替换为查找和删除叶子节点。

最复杂的例子出现在你需要删除空的节点并干掉根节点,就像 Part1 描述的那样。但是,如果你按照 Part 1那里介绍的规则行事,并且将叶子节点当做『元素』,你会觉的还好处理。下面就是这么个例子,把最右叶子节点『提升』为根节点。

A visualization which shows both root killing and empty node removal, with tails.

Next Up

这个系列的下一篇将解析 transient:我们为什么需要它们,以及它们的工作原理。最终这个系列博客的最后一篇博客将包含 ArrayList 和 Persistent Vector 的性能对比。


[1] 持有非空尾部的有没有什么不利的地方?从理论角度出发,空的 vector 将更多是一种边缘情况,因为它不符合这个规则(译者注:指尾部非空)。但是从实践角度出发,这没有关系。空的 vector 本来就是一种特殊情况,因此采用这个设计后,实现本身并不会更复杂。

翻译:深入理解 Clojure Persistent Vectors 实现 Part 2

| Comments

前言

正文

在前一篇关于 Clojure Persistent Vectors 的博客里(如果你还没有读过,请点击阅读),我们大致理解了 vector 里元素的插入、更新和出队操作是如何工作的。我们还没有真正了解到是如何定位到正确的元素,在这篇博客我将介绍查找元素是如何实现的。

为了理解我们是如何在树的节点里面选择正确的分支,我想最好是先给这些结构一个合适的名称,并解释为什么这样命名。通过一个数据结构的名称来解释分支选择似乎听起来很奇怪,但是如果考虑到这个名称可能描述了它的工作原理的话,这还是有意义的。

名称

Clojure persistent vector 数据结构的一个更正式的名称是 持久的按位分区的矢量前缀树(persistent bit-partitioned vector trie)[1]。我在前篇博客介绍的其实是持久的按数字分区的前缀树(persistent digit-partitioned vector tries)是如何运行的,但是不用担心,一个按位分区前缀树只是一个按数字分区的前缀树的优化,对于上篇博客的内容来说,两者并没有区别。在本篇博客,会介绍一点两者在性能上的小区别。否则它们其实没有根本上的差异。

我猜测你可能并不了解上面段落提到的这些术语,所以我将在下文一一解释。

持久性

在上一篇博客,我使用了术语持久性(persistent)。我说我们想要数据结构是持久的,但是并没有真正解释到底持久性本身意味着什么。

一个称为持久的数据结构并不修改它自己本身:严格来讲,他们并不一定要在内部是不可变的,只是需要被(外界)认为是不可变的。无论何时你在一个持久的数据结构上执行了更新、插入或者删除操作,一个新的数据结构将返回给你。老的版本仍然是一致的,并且无论什么时候你给它一个输入,它总是返回同样的输出(译者注:也就是没有副作用,side effects)。

当我们谈论一个 完全 持久的数据结构的时候,这个数据结构的任何版本都是可以修改的,意思是作用在某个版本上的所有可能的操作,都可以作用在另一个版本上。在早期的『函数式数据结构』时代,更常见的方式是和数据结构一起『欺骗』,通过修改内部结构让老的版本随着时间逐渐『腐朽』,同时跟最新版本相比是越来越慢。虽然如此,Rich Hickey(译者注:Clojure 作者)决定让 Clojure 持久数据结构的所有版本都有一样的性能承诺,无论你正在使用的是数据结构的哪个版本。

矢量(Vector)

一个矢量就是一个一维的可增长的数组。例如 C++ 的 std::vector 或者 Java 的 java.util.ArrayList 就是可变矢量的实现。实际上也没有比这个更多的解释了。一个矢量前缀树是指一棵用来表示矢量的前缀树(trie)。它并不一定必须是持久的,但是在我们这里介绍的是持久的。

前缀树(Trie)

前缀树是特殊的一种树,我想最好先解释更多的常见的树来展示前缀树的实际不同之处。

在红黑树和其他类型的二叉树里,映射或者元素存在于内部的节点上。选择正确的分支是通过比较元素/关键字(key)和当前节点来确定的:如果元素比当前节点的元素小,那么我们选择左分支,如果更大,我们就走到右分支。叶子节点通常都是空指针或者 nil,不包含任何东西。

A RB-tree, from Wikipedia's article “Example red-black tree” by Cburnett, CC-BY-SA 3.0

上面图中的红黑树是从维基百科的文章里摘录过来的。我并不想详细介绍它是如何运作的的,但是我们选择一个小小的例子,看看我们是如何判断 22 是否在这棵红黑树里:

  1. 我们从根节点 13 开始,和 22 对比下。因为 13 < 22,所以我们进入分支。
  2. 新节点包含了 17,和 22 对比。因为 17 < 22,我们仍然进入分支。
  3. 下一个我们进入的节点是 25。因为 25 > 22,我们进入分支。
  4. 下一个节点是 22,因此我们知道 22 包含在这棵树里。

如果你想知道关于红黑树的更好的解释,我推荐你阅读 Julienne Walker 的 红黑树教程

从另一方面观察,一棵前缀树将它的所有的值都保存在它的叶子节点中[2]选择正确的分支是通过使用关键字的一部分来定位。因此,一棵前缀树可以有多于两个的分支,在我们这里,它最多拥有 32 个分支!

A trie

大致的一棵前缀树插图展示在上面图中。它展示的前缀树是一个 map:接收长度为 2 的字符串,当字符串在前缀树里存在的时候返回一个整数。ac 的值是 7,而 ba 的值是 8。前缀树是这么工作的:

对于字符串,我们把字符串拆成字符。然后使用第一个字符,找到表示该值的边(edge),然后沿着边往下走。如果该值没有找到对应的边(edge),我们就停止访问,表示它在前缀树里不存在。否则,我们继续使用第二个字符来查找边,不停下去直到没有剩余字符了。最终完成的时候,如果存在,我们就返回当前的值。

ac 字符串为例,我们按照下列步骤处理:

  1. ac 拆成成 [a, c] 的字符列表,并从前缀树的根节点开始。
  2. 判断对于字符 a,节点上有没有一条边,如果存在,我们沿着这条边向下访问。
  3. 判断对于字符 c,节点上有没有一条边,如果存在,我们同样沿着这条边向下访问。
  4. 后面没有剩余的字符了,这就是意味着当前节点包含了值 7,因此我们返回 7。

Clojure 的 Persistent Vector 就是一棵前缀树,它把元素的索引位置(index)作为关键字(key)使用。但是,正如你所料到的那样,我们需要将索引整数按照某种方式拆分。为了拆分整数,我们要么使用数字分区的方式,或者它的更快版本——位分区

数字分区(Digit partitioning)

数字分区的意思是说我们把关键字拆分成数字,作为填充前缀树的基础。例如,我们可以将关键字 9128 拆分成 [9, 1, 2, 8],基于这个列表将元素放入前缀树中。如果前缀树的深度超过了这个数字列表的大小,我们可能还需要在列表前面填充一些 0。

我们也可以使用任何其他我们喜欢的基数,不仅仅是 10。这样一来,我们就需要将关键字转换成想要使用的基数,并使用转换后的数字。仍然以 9128 为例,9128 换算成基数为 7 的数字就是35420,接下来我们就要使用列表 [3, 5, 4, 2, 0] 来查找或者插入前缀树。

Visualization of the 35420 lookup.

(译者注:图中的 9145 显示错误,其实是 9128。)

上面这棵前缀树(横向展开,不包含我们不会访问的边和节点)展示了我们如何遍历一棵数字分区的前缀树:我们挑选了最高位有效的数字,在这里是 3,然后进入那个指定的分支。接着以同样的方式使用第二高位有效的数字,一直到没有剩余的数字为止。当我们访问到最后分支的时候,和我们在一起的对象 —— 这里就是最后数组的的第一个对象(译者注:绿色的 0) —— 就是我们想要定位的对象。

如果你知道怎么找到数字,那么实现这样一种查找程序并不很难。下面是一个 Java 版本的实现,与查找无关的细节都被剥离掉了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class DigitTrie {
  public static final int RADIX = 7;

  // Array of objects. Can itself contain an array of objects.
  Object[] root;
  // The maximal size/length of a child node (1 if leaf node)
  int rDepth; // equivalent to RADIX ** (depth - 1)

  public Object lookup(int key) {
    Object[] node = this.root;

    // perform branching on internal nodes here
    for (int size = this.rDepth; size > 1; size /= RADIX) {
      node = (Object[]) node[(key / size) % RADIX];
      // If node may not exist, check if it is null here
    }

    // Last element is the value we want to lookup, return it.
    return node[key % RADIX];
  }
}

rDepth 的值表示根节点的一个子节点的最大大小:一个有 n 个数字组成的数字,将拥有 RADIX 的 n 次幂数量的可能值,而且我们必须能将它们毫无冲突地全部放入前缀树。

lookup 方法的 for 循环里,size 的值表示当前节点的一个子节点的可以拥有的最大大小。对于每个我们访问过的子节点,这个 size 大小被分支因子递减,分支因子即是数字前缀树的基数。

对结果做一次取模运算的原因是为了忽略掉高位有效数字 —— 那些我们在前面用于分支选择的数字。我们可以在每次分支选择进入子节点的时候从关键字里移除高位数字,但是在那种情况下,代码会变得稍微复杂一点[3]

位分区

数字分区的前缀树通常需要做大量的整数除法和取模运算。在每次分支选择的时候必须执行这些运算会带来不少的时间损耗。如果可能,我们当然更想要加快这一部分的运算。

因此,正如你所料,位分区前缀树是数字分区前缀树的一个子集。所有基于 2 的次幂(2, 4, 8, 16, 32 等)为基数的数字分区前缀树,都可以转成位分区前缀树。只要了解一些位运算的知识,我们就能移除这些耗时的算术运算。

从概念上讲,它的工作原理跟数字分区是一样的。尽管如此,我们原来把关键字拆分为数字,现在替换成拆分为预定义大小的位簇(bit chunk)。对于 32-路的分叉前缀树来说,每一部分都需要 5 位,对于 4-路的分叉前缀树来说,每一位簇需要 2 位。更一般的说法,我们需要的是和我们的指数大小一样的位数(译者注:举例来说,32 是 2 的 5 次幂,5 是指数,因此是 5 位)。

但是,这样做为什么更快呢?通过使用一些位运算的技巧,我们可以同时消除整数的除法和取模。如果 power 是 2 的 n 次幂,我们可以得到 x / power == x >>> n[4]x % power == x & (power - 1)。这两个公式其实是等价,跟整数的本质表示有关,也就是位组成的序列。

如果我们使用这个结果,并和前面的实现组合起来,我们将得到下列代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class BitTrie {
  public static final int BITS = 5,
                          WIDTH = 1 << BITS, // 2^5 = 32
                          MASK = WIDTH - 1; // 31, or 0x1f

  // Array of objects. Can itself contain an array of objects.
  Object[] root;
  // BITS times (the depth of this trie minus one).
  int shift;

  public Object lookup(int key) {
    Object[] node = this.root;

    // perform branching on internal nodes here
    for (int level = this.shift; level > 0; level -= BITS) {
      node = (Object[]) node[(key >>> level) & MASK];
      // If node may not exist, check if it is null here
    }

    // Last element is the value we want to lookup, return it.
    return node[key & MASK];
  }
}

这近似于 Clojure 语言的实现。看 Clojure 语言里的这些代码来检验这一点。唯一的区别是它做了边界检查以及末尾检查。

需要重点注意的是在这里我们不仅改变了运算符,而且还把 rDepth 值替换成了 shift 值。不再是存储完全的值,而只是存储指数部分。这使得我们可以对关键字使用位移运算,也就是 (key >>> level) 这一段。如果你相当熟悉位运算,其他部分也都很直白,容易理解。虽然这样,我们还是为不熟悉这些技巧的朋友举个例子。下面这个解释很详细,如果你觉的自己已经理解了,可以忽略。

为了图形化展示,假设我们只有 2 位分区(4-路分叉),而不是 5 位(32-路分叉)。如果我们想在一棵拥有 887 个元素的前缀树里查找某个值,我们有 shift 值等于 8:根节点的所有子节点每个最多可以包含 1 << 8 == 256 个元素。宽度(width)和掩码(mask)也都同时被改变:掩码 mask 是 3,而不是原来的 31。

Visualization of the 626 lookup.

假设我们想查找的关键字 626 对应的内容, 626 的二进制表示是 0000 0010 0111 0010。按照上面或者 Clojure 语言里编写的算法,一步一步介绍,我们会按照下列步骤处理:

  • node 被设置为根节点,而 level 设置为 8。
  • 因为 level 大于 0,我们开始进入 for 循环。
    • 我们先执行运算 key >>> level,在这里就是 636 >>> 8,这将消去前面(低位)的 8 位,剩下来是 0000 0010,也就是十进制的数字 2。
    • 接下来计算掩码 (key >>> level) & MASK == 2 & 3。掩码将前两位之外的位都设置为 0。这里的结果没有区别,结果仍然是 2。
    • 我们将当前节点 node 设置为它在位置 2 的子节点。
  • level 减去 2,设置为 6
  • 因为 level 还是大于 0,我们继续执行 for 循环。
    • 我们再次计算 key >>> level == 636 >>> 6。这将切掉后 6 位,剩下的是 0000 0010 01,也就是十进制的数字 9 。
    • 然后执行掩码运算: (key >>> level) & MASK == 9 & 3,换成二进制就是 1001 & 0011,这会消去最前头的 10,剩下的是 01,也就是十进制的数字 1。
    • 我们将当前节点 node 设置为它在位置 1 的子节点。
  • level 减去 2,也就是设置为 4
  • 因为 level 还是大于 0,我们继续执行 for 循环。
    • 636 >>> 2 留给我们的是 0010 0111 00
    • 前面(低位)的两位是 0b00 == 0
    • 我们将 node 设置为它的第一个子节点,也就是索引位置为 0 的子节点。
  • level 减去 2,也就是设置为 0
  • 因为 level (最终)不再大于 0,我们跳出了 for 循环。
  • 我们对 key 使用 mask 做了一次掩码运算,返回二进制 10。因此,最后我们返回 node 节点在索引位置 2 的内容。

这几乎也是你在 Clojure vector 里的执行一次查找值的操作所经历的每一步机械指令,只是深度变成了 5。这样的 vector 将包含 1 到 3300 万元素。实际上,位移和掩码运算是现代 CPU 里最高效的运算之一,所以这让整个处理过程更加有效。从性能角度来讲,查找过程剩下的唯一『痛点』是高速缓存 miss。对于 Clojure 来说,这些都交由 JVM 自身很好地被处理了。

这些就是前缀树和 Clojure Vector 实现里如何查找元素的所有内容了。我猜这里最难理解的部分是位运算,其他任何部分都非常直白。你只是需要对前缀树如何工作有一个粗略的了解,这就够了!

如果你读完这篇博客,接下来的一篇 Part 3,将解释尾部引用 —— vector 的一个性能优化原理。


[1] 如果你想更学究一点,你可能想讨论这到底是不是 正式 的名称。Daniel Spiewak 在他的演讲 “Extreme Cleverness” 里将它们称为 “位映射矢量前缀树”(Bitmapped Vector Tries)。在 Clojure 社区里。他们更倾向于称之为 vector 或者 persistent vector。我们的目标并不是提供一个最广为人知的名称,而是一个名称可以在这系列博客里解释这个数据结构最重要的特性:即这是一个持久的前缀树,通过使用把元素的索引按位分区的方式来模拟一个 vector。

[2] 这里我撒了点小谎,只是为了让解释更简单一些:一些前缀树的变种可能会将它们的值实际存储在内部节点上,但是我们要讲解的这个不是这样。

[3] 尽管如此,它却可能更快!x86 上的div 指令(除法)会把商数和余数存在两个不同的寄存器里,因此我们能承受无论如何都要执行的除法。剩下的唯一工作就是 subl 指令,它可以比取模运算更快。如果你想实现一个非常快的按数字分区的前缀树,这里需要注意下。

但是这取决于你使用的基数。在特定情况下,一个除法运算可以分解成一些位运算和乘法运算的组合,一个取模运算也可以采用类似的方式优化。

[4] 小提示:在 Java 里,>>> 是一个逻辑位移(任何移掉的多出来位都会补为 0),而 >> 是一个算术运算(移掉的位都将和最高有效位拥有同样的值)。因为我们并没有使用有符号位,所以这里其实几乎没有区别,尽管我猜测 >>> 在某些机器架构上可能会比 >> 更快。

对于 C/C++/GO 的朋友们来说,>>> 等同于无符号类型的 >>