Arthur tiancaiamao@gmail.com atom egg for Chicken www.zenlife.tk Copyright (c) 2015, Arthur Mao 伟大的野心家,实践家 Arthur的博客 2005-07-31T12:29:29Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>好久没更新博客了,<a href="https://github.com/tiancaiamao/shen-go">shen-go</a> 也是停滞的状态。其实这期间一直有探索,如果更新下一版应该怎样做。</p> <p>自己实现语言的编译是可行的,但是仅靠一人之力实现一门语言的生态是不靠谱的。如果没有好的库和生态,实现出来也就是一个玩具。我最期望的是能够做一个自己平时开发都会使用的语言。生态的构建,一种方式是像 lua 那样,做成一门嵌入式的语言,去借用宿主语言的生态。或者是支持方便的 FFI 扩展。在 shen-go 的 v0.3 里面,我实现了一个 load-plugin 的功能,可以用 Go 写代码,生成 plugin,然后 load 进去使用。</p> <p>如果和其它 Go 语言实现的各种玩具 lisp 项目比较,这个项目应该是算很靠谱了,至少做了一个 bytecode 的 VM。然而这只是一个性能与复杂度的折衷阶段。当前的实现没法将性能压榨到我所想要的极限。在<a href="http://www.zenlife.tk/eval-as-universal-machine.md">这一篇</a>里面,我已经说过了,其实并不想优化 VM。这个做法的性能是有尽头的,再往 JIT 方向做,复杂性又不能接受。</p> <p>于是编译到一个现有的东西,无论是语言或者平台,似乎是更好的选择。</p> <h2>几个新的想法</h2> <p>Go 语言可以 load 插件,这个让我萌生一个想法:其实可以把 shen 编译到 Go 的源代码,然后生成二进制的 plugin,再 load 进来调用。在<a href="http://www.zenlife.tk/expression-implementation.md">之前的一篇博客</a>里面,也已经提到过。这种 code gen 的方式,就等于是在做 AOT 编译了。</p> <p>顺带说一说,Go 的 plugin 其实是有一点 ugly 的,我在看了下实现才发现,它是走的 cgo,调用 dlopen。cgo 是一个我希望避免的事情,普通的 Go 函数调用大概在 4-5ns,而一个 cgo 函数调用要到 70ns。那么其它方式直接 load Go 的程序执行?<a href="https://github.com/dearplain/goloader">当然也有人造过轮子了</a>。</p> <p>另外一个想法是关于 fixnum tagging。假设我实现了 shen 编译到 Go,那么,不做 fixnum tagging 肯定不能忍。这个优化对 runtime 的性能影响太重要了。编译成 Go 却不做这个,就像配电脑,配置了一个顶级的 CPU,结果只给它配了 256M 的内存条。</p> <p>我甚至一度以为找到了一种 fixnum tagging 的简单实现方式。在 new 一个对象的时候,返回的是 uintptr,但是额外用一个地方记录下分配的对象的指针或者 unsafe.Pointer。比如用一个全局的数组记录。uintptr 不具备保护功能,但只要那个数组里面还有引用,就能保护该对象不被 GC 掉。</p> <pre><code>func newCons() uintptr { ret := &amp;Cons{} gcProtect = append(gcProtect, ret) return uintptr(unsafe.Pointer(ret)) } </code></pre> <p>然而所有对象变成了都需要这个额外数组的保护。因为分配出去的 Cons 不是具备保护里面成员的功能的:</p> <pre><code>type Cons struct { // uintptr 即使对象被引用也保护不了里面的 car 和 cdr 成员不被 GC car uintptr cdr uintptr } </code></pre> <p>那么,如何回收 gcProtect 数组就成了一个问题。我需要遍历一遍 gc 的 root 区域,然后递归地 trace 里面的所有被引用对象。这就跟自己实现 GC 时,mark sweep 里面的 mark 阶段一样了,也相当于把 GC 自己实现了一遍。</p> <p>最后得出了结论,除非自己手动实现一套 GC,否则 fixnum tagging 在 Go 语言里面是做不了的。</p> <p>很排斥自己去弄 GC 的,复杂度偏高了。实现是一方面原因,更不爽的是,在托管内存和非托管内存之间交互,给使用会带来一些限制,最终会非常恶心。于是暂放下了这些想法,转而看能不能选择编译到其它目标目标。</p> <h2>编译目标的探索</h2> <p>之前<a href="http://www.zenlife.tk/erlang.md">看了点 erlang</a>,其实就是想编译到 erlang 的字节码。但是研究之后发现,erlang 的 core lambda 部分跟 shen 的 klambda 语义差别有点大,erlang 把 pattern match 做到 cora lambda 里面了,导致我无法在只做简单的 ast 变换就把 shen 的 klambda 编译到 core erlang,进而生成 beam 的虚拟机字节码,于是这个尝试就失败了。另外,我发现在 erlang 里面完全禁止副作用,连全局变量都没有,这个约束还是挺大的。</p> <p>编译到 clojure。clojure 也算是一个简洁的 lisp 方言,把 shen 编译过去实现来讲难度也并不大,社区有人实现过。然而想到 clojure 不过是运行在 jvm 之上的,就觉得考虑编译成 clojure 还不如直接考虑 jvm。</p> <p>编译到 jvm,也已经有相应的项目了。研究了一番,最后放弃的原因,说到底还我对 java 并不怎么熟习,虽然 jvm 生态是没什么问题,但是平时我也用不上啊。</p> <p>编译到 javascript。有三个周末的时间我确实就这么干了,并且<a href="https://github.com/tiancaiamao/cora/tree/d286c75c7c1dc4246bbf20f8a75f670bd578d5cd">捣鼓了一个 demo 出来</a>。总体来说,javascript 确实是一门挺简单的语言,难怪那么多的语言都会编译成 js。在第一个周末花了不到一天的时候稍微看了一下语法,就已经能干活了,顺畅无比。中间也仅仅被 Temporal Dead Zone 给坑了一次,另外就是异步的模式有点不适应,实现 read 之类的几个 primitive 以及 repl 需要调整一下。</p> <p>一个小插曲是,做编译到 js 的时候脑袋抽了,想尝试一下编译到 lua,很快放弃了这种想法。lua 并没有一个好的生态,扩展都要依赖于写 C。写 C 这种事情,写过 Go 之后再也不想做了。另外,在编译到 js 的时候我是用 trampoline 实现的尾递归,而 lua 语言本身是支持尾调用的,原以为应该这是一个很好的优势。结果发现 a and b or c,这种东西在 lua 里面居然是不能够尾调用的,坑了。</p> <p>编译到 javascript 之后,总觉得 object 有点重,想看看有没什么对底层有更好控制的方式。然后 Go 的 1.11 要支持 webassembly 了。之前我就相信它是代表着未来的,webassembly 感觉会火,所以又考虑了一下要不要尝试编译到 webassembly。有人已经尝试过把 <a href="https://github.com/google/schism">scheme 编译到 webassembly</a>。webassembly 是类似于一个栈虚拟机,目前还不支持 GC。编译那边只要做一个闭包变换,可以考虑用 C 之类的写 GC 和对象等 runtime 部分。本来感觉一切都挺好的,直到我思考 eval 该如何实现。webassembly 是模块级加载的,并不是动态执行 webassembly 代码,这就导致 lisp 里面的 eval 函数没法动态编译和运行。要么就再之上实现一个解释器,eval 的东西就通过解释器跑。这样子编译到 webassembly 的优势就没有了 -- 我希望获得原生的性能,然而 eval 的函数并不能。</p> <p>编译到 C 在<a href="http://www.zenlife.tk/scheme-to-c.md">很久以前就研究过</a>,也参考过 chicken 的做法。后来发现 chicken 的性能并不太好,所以对这个方向有些怀疑。感觉 chicken 被 cheney on the M.T.A 拖累了,它直接在栈上分配对象,会导致 GC 倾向于过于频繁。可能更多是优化得不够到位吧。</p> <h2>gambit 的启发</h2> <p>这次我发现了 gambit。gambit 是一个编译到 C 的 scheme 语言实现。<a href="https://ecraven.github.io/r7rs-benchmarks/">benchmark</a> 显示 gambit 性能仅次于 chez,排名第二! 那它为什么跟 chicken 不一样,达到了更好的性能?我研究了一下,还是挺有收获的。</p> <p>在<a href="http://churchturing.org/y/90-min-scc.pdf">《The 90 minutes Scheme to C compiler》</a>里面可以看到一个大概的做法。前面部分的编译都和 chicken 一样,做 cps 变换,然后做闭包变换。gambit 在中间步骤是设计了虚拟机的!它做完闭包变换,并没有像 chicken 那样直接变成等价的 C 的代码,而是生成了它的中间层 gvm 的虚拟机指令。cps 变换使得所有的函数调用都不会返回,像 chicken 那个做法就会让栈不停增长,再用特殊的方式来处理。而在 gambit 设计的虚拟机里面,它将函数调用直接实现成 jump 了。</p> <p>gambit 对 C 的使用姿势特别有趣:语言即是虚拟机。不是解释执行的,但是又不使用宿主语言本身的堆栈寄存器等进程布局,不做等价的翻译。它里面定义了各种乱七八糟的宏:</p> <pre><code>jump: switch (pc) { case 0: /* (lambda () (let ((r.5 (%closure (lambda (self.10 k.6 N.1)... */ BEGIN_CLOSURE(1,0); END_CLOSURE(1,0); PUSH(LOCAL(0/*r.5*/)); GLOBAL(0/*fact*/) = TOS(); PUSH(GLOBAL(0/*fact*/)); BEGIN_CLOSURE(2,0); END_CLOSURE(2,0); PUSH(INT2OBJ(5)); BEGIN_JUMP(3); PUSH(LOCAL(2)); PUSH(LOCAL(3)); PUSH(LOCAL(4)); END_JUMP(3); case 2: /* (lambda (self.12 r.4) (let ((r.2 (%+ r.4 1))) (%halt r.2))) */ PUSH(LOCAL(1/*r.4*/)); PUSH(INT2OBJ(1)); ADD(); </code></pre> <p>这样子做法,性能可能比手写汇编更好。C 语言优化了这么多年,编译器自然是成熟稳定并且足够聪明的,对应的 sp, hp 和中间变量都会直接在寄存器分配,比在汇编里面手动指定更高效。另外,所有的 lambda 都丢到一个函数里面,又带来一个特别的好处, WholeProgramOptimization,即全程序优化,参见 MLton。因为所有函数都写在一起了,编译器可以不用考虑跨函数调用的 ABI,那么函数调用就可以避开过使用内存栈传参,优化有可能直接用寄存器传参。</p> <p>gambit 对性能方面很有追求。网上随手搜到这篇 paper,可以体现这种态度。《Speculative Inlining of Predefined Procedures in an R5RS Scheme to C Compiler》。在 scheme 语言里面,一些基本运算像加减乘除都是函数,这些内置的函数都是可以被重载掉的,所以无法做内联。这种非常基础的操作都要走函数调用,开销还是很大的。而实际上大部分时候没人去改一些 buildin function,那么 Speculative Inlining 做的是什么呢? 它假定了 buildin 不会被重载,先判断一下,没被改过就调用 buildin 的,否则 try 修改过的,这样前面判断的部分就可以 inline 掉了,于是避开调用开销。</p> <pre><code>(f (car (g 5))) -&gt; (f (let ((x (g 5))) (if (and (’ ##eq? car ’ car ) (’ ##pair? x)) (’ ##car x) (car x)))) </code></pre> <p>虽然 gambit 带来很多启发,但是不一定需要使用它的做法。对于 CPS 的态度依然还是和原来一样,shen 里面并不需要实现 call/cc。CPS 引入的复杂度偏高,做完 CPS 会额外多出一堆的 closure,后期又要继续将这步变换引入的负担给“优化掉”,那么做这一步的意义是值得怀疑的。gambit 做了很重的优化,这是我不会选择做的事情。</p> <p>编译目标在虚拟机这一层仍然会保留概念,但是学习 gambit 拿语言当虚拟机用。这里有个额外的好处,因为有这一层概念,会为将来解释执行和原生执行共存留下设计的空间。到时候 eval 肯定要做的,那么可以把 eval 的做成以 interpret 方式去操作这一层 vm,而其它场合用 native 方式来操作 vm。</p> <p>是 C 还是 Go? 由于 fixnum tagging 必须自己搞 GC,基本上已经是把 Go 当 C 在用了。用 C 的好处是 gcc 的 label as value 的扩展,可以做 threaded code,对比 <a href="http://www.zenlife.tk/go-switch-statement.md">Go 里面 switch 实现的很糟糕</a>。坏处是用 C 写了用 Go 调用不了。我参考过<a href="https://blog.filippo.io/rustgo/">这一篇</a>,但是考虑到 lisp 的 repl 是没机会重新编译的,这个方法应该用不了。为了生态还是用 Go 吧。</p> www.zenlife.tk/shen-go-next-notes.md 2018-07-15T16:51:42Z shen-go 下一版的胡思乱想 2018-07-15T16:51:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>有些编程语言里面有个概念叫做&quot;类型安全&quot;,本文说的的安全的代码,其目标都是一样的。每种类型都有相应的约束,代码就安全了。比如 int 的约束,它的取值范围肯定是有上下界的,比如集合的约束,它里面所有元素肯定是唯一的。再举个反例,void 指针这东西,就是一个类型不安全的,它指向的目标不知道会是啥。rust 或者许多函数语言里面,不会出现空指针,代码就比较&quot;安全&quot;。</p> <p>假设我们使用的语言支持 dependent type,我们可以定义一个有序数组类型,它是个数组,里面的元素全部是有序的。编译器要帮我们检查类型,我们无法搞出一个不满足约束的实例出来。实现这种类型有个问题,即类型依赖于值了,值可能在运行时才能得到,于是无法完全在编译期做检查。如果要模拟运行一遍,把所有可能的值都取到,这就很蛋疼了。</p> <p>类型即约束,强调所谓&quot;类型安全&quot;的语言里面,编译器帮我们把约束检查了。在弱鸡语言里面,这个约束就需要我们手动维护了。如何维护好约束,那就是这里要说的编写安全的代码。</p> <p>先从最简单的例子开始看,我们要实现一个集合类型,编译器不支持 dependent type,怎么做呢?定义一个集合类,所有这个集合类的修改,都需要走这个类的 API,就可以保证约束满足。面向对象里面的&quot;封装&quot;的概念,其实解决的一个重要问题,是把副作用控制在一个范围内不扩散,从而维护这个类型的对象的约束。良好的封装,类型的修改操作都是由对象的方法来执行,于是代码就是安全的。</p> <p>接下来就看实际的问题了,数据库的例子。假设数据库的 table 是一种类型,那么这种类型必须要满足一个约束:数据和索引一致性。插入了数据,一定要加索引;删除了数据,也需要删除索引。我们可以提供一个 table 的类型,然后提供修改操作的 API。所有对 table 的操作,都要透过这套 API 来进行,这样我们就要以满足数据索引一致性的约束了。比如 AddRecord 这个 API,如果操作成功了,数据和索引肯定是都写入的。</p> <p>实现 AddRecord 时,会遇到这样一个问题:写数据成功了,写索引时失败了,返回错误。这时,整个操作是不能有副作用的,数据不能写进去。这是一个比较常见的 case,要么做回滚,要么是原子性 commit。那如果我们无法做回滚操作时,怎么办呢?我们把所有修改先缓存起来,只有全部成功,才去 apply。如果中途遇到任何错误,就丢弃修改了。</p> <p>再类似的,一个 SQL 里面有多行 statement,需要全部成功时才应用修改,中间失败时,不留下副作用。为此,必须引入一个 dirty table 的概念。写操作需要写到 dirty table 里面,不能直接作用于 table。另外,前面的 statement 需要对后面可见,所以读操作要做一个融合,先读 dirty table,读不到才会穿透了去读 table。</p> <p>dirty table 的引入,让代码更复杂了。编写安全的代码,要求仍然是,涉及到 dirty table 的修改也一定要通过某一层 API。</p> <p>除了数据索引一致性外,实现 table 时还会遇到另一个问题:unique key 的唯一性。比如 create table 的时候,可能会有 primary key 或者 unique 的列,这也是约束。on duplicate key 的处理就是一个麻烦的事情。比如插入一条数据,它里面有一列可能跟其它列冲突了,需要 on duplicate key update,改成另一个值。可能修改之后,又冲突了。这里的约束必须保证不管怎么修改,数据都是唯一的。</p> <p>当我们有了 table,有了 dirty table,on duplicate key 的各种处理等等,所有东西混到一起的时候,代码就很容易乱了。什么时候数据索引没维护好,什么时候改漏了,比如改了 table 没改 dirty table,这些都是 bug 的温床。编写安全的代码,一定要注意好分层,每层的 API 就是用来维护约束的。如果跨了 API 层修改,比如上层直接去改 table 的数据,非常容易出错。如果设计好 API 也是一门学问,下层暴露的东西太少,上层无法透过 API 完成功能,必然引起上层直接绕过 API 把自己的功能再实现一遍,重复代码又是 bug 的温床。下层提供的东西太多,那又跟没封装过没啥区别,最后还是保证不了约束。</p> <p>这些仍然不够,还需要注意写测试。单元测试的意义,是保证在一定范围内约束不被打破,尤其是当涉及到重构的时候。</p> <p>小结一下,如何编写安全的代码:</p> <ul> <li>语言的类型系统提供了最基本的保障</li> <li>更复杂的对象约束,要透过 API 的封装来保证</li> <li>注意良好的分层,切忌跨 API 访问下层</li> <li>单元测试</li></ul> www.zenlife.tk/write-safe-code.md 2018-08-07T01:53:42Z 编写安全的代码 2018-08-07T01:53:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>画个心吧! 之前应该有看到别人画过,但是是什么时间,具体第一次在哪看过,来源已不可考。既然七夕快到了,自己写着玩一下吧。</p> <p><img src="static/love0.png" alt /></p> <p>原理是这样的,我们可以把输出当作比如 <code>50 * 100</code> 的点素点阵,这就是我们的 canvas 了。</p> <pre><code>for y := 0; y &lt; height; y++ { for x := 0; x &lt; width; x++ { fmt.Printf(&quot;%c&quot;, '*') } fmt.Println() } </code></pre> <p>这是一个 x 轴往右, y 轴往下的坐标系。怎么样画一个函数呢? <code>y = f(x)</code>,如果把 x 和 y 代入到函数里面,就 print 一个星号,否则 print 一个空格。我们可以写一个函数来判断:</p> <pre><code>func point(x, y int) byte { if x == y { return '*' } return ' ' } </code></pre> <p>函数可以换成别的,这样就可以画出不同的曲线了。接下来是一个神奇的公式:</p> <p><code>(x^2 + y^2 - 1)^3 = x^2 * y^3</code></p> <p>这个函数画出来的图案,就是一个心。它的值域范围 x 和 y 轴大概都在 -1.5 到 1.5 左右,所以我们要把 <code>50 * 100</code> 的 canvas 缩放到这个范围。另外,坐标系需要调整到 canvas 的中心,而不左上角。y 轴反向之后:</p> <pre><code>x =&gt; [0 ~ 100] -y =&gt; [-50 ~ 0] </code></pre> <p>调整坐标原点,以 canvas 为中心而不是左上角:</p> <pre><code>x - 50 =&gt; [-50 ~ 50] 25 - y =&gt; [-25 ~ 25] </code></pre> <p>再把范围缩放到 <code>-1.5 ~ 1.5</code> 之间:</p> <pre><code>(x - 50) / 100 * 3 =&gt; [-1.5 ~ 1.5] (25 -y) / 50 * 3 =&gt; [-1.5 ~ 1.5] </code></pre> <p>于是我们就可以把整段代码写出来了:</p> <pre><code>package main import &quot;fmt&quot; func main() { for y := 0; y &lt; 50; y++ { for x := 0; x &lt; 100; x++ { y1 := (25.0 - float32(y)) / float32(50) * 3 x1 := (float32(x) - 50.0) / 100.0 * 3 tmp := (x1*x1 + y1*y1 - 1) if tmp*tmp*tmp-x1*x1*y1*y1*y1 &lt; 0 { fmt.Printf(&quot;%c&quot;, '*') } else { fmt.Printf(&quot;%c&quot;, ' ') } } fmt.Println() } } </code></pre> <p>效果是这样子的:</p> <p><img src="static/love1.png" alt /></p> <p>我们可以把星号换掉,随机生成一些字符:</p> <p><img src="static/love2.png" alt /></p> <p>可以用自己喜欢的妹子(或者汉子也行)的名字去随机,注意需要是 ascii 字符,中文字体宽度有问题,可以用 base64 编码一下。既然是内容,可以在里面写一些句子。唔,似乎用摩尔斯码也不错,只用 . 和 - 去写摩尔斯码。</p> <p>继续说画心,我们可以画好几层的心,大小不一样,越靠内层的,&quot;颜色&quot; 越重,反正就是 canvas 输出当像素点阵用的:</p> <p><img src="static/love3.png" alt /></p> <p>做这一步需要注意两个点,一个是不同大小的心,缩放要调整一下,不能占满整个 canvas,而中心还是要对齐的。另一个是由于点的颜色有深度了,需要用数组先存起来,之后再画。颜色深度由浅入深可以依次用 <code>. ! + * #</code></p> <p><img src="static/love4.png" alt /></p> <p>把代码融合进去也可以,像 C 语言代码混乱大赛那样玩。</p> <p><img src="static/love5.png" alt /></p> <p>甚至可以生成一段心形程序,发个密码给 TA 去解。或者藏一个 brain fuck 代码。对于一个 geek 来说,这都不算个事儿。</p> <p>祝大家玩得开心!今天画个心,明天可以画点别的,后天再 new 一个女朋友,完美!(手动滑稽</p> www.zenlife.tk/chinese-valentine-day.md 2018-08-12T11:20:42Z 七夕快到了,做点好玩的 2018-08-12T11:20:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>简单介绍一下 VLDB 的一篇 paper:<a href="http://www.vldb.org/pvldb/vol11/p648-tian.pdf">Contention-Aware Lock Scheduling for Transactional Databases</a></p> <h2>问题</h2> <p>多个事务访问到相同资源的时候,会涉及到加锁,怎么样进行调度,会使得各个事务的延迟尽量短,系统整体的吞吐更高,以及保证调度的公平性?</p> <p>这个问题是比较难搞的。</p> <ul> <li>首先这是一个<strong>在线问题</strong>。在事务结束之前,一个锁将会被持有多久,无法事先预知。</li> <li>其次<strong>依赖关系特别复杂</strong>。一个事务可能持有许多的锁,以及多个事务间可能都依赖同一个锁。</li> <li>接着是<strong>访问模式的不确定</strong>。不同的事务有不同的访问模式,有些对象可能是比较 popular 的,被许多事务依赖,不同对象之间并不等价。</li> <li>锁的模式也有多种类别。比如写锁是排它的,而读锁是可共享的。</li></ul> <p>常规的系统大多采用的是 FIFO 的调度方式,也即是哪个事务请求先到达就先执行,并对相应的资源加锁。paper 里面指出,FIFO 的策略效果其实是很差的,而它提出的 contention aware 调度策略则相当牛逼。另外,MySQL innodb 引擎在 8.0.3 版本以后,默认采用的也是这篇 paper 里面的方法。</p> <h2>想法</h2> <p>contention-aware 调度的意思是,根据事务整体的锁竞争会对系统造成的影响,将事务分配优先级。调度是根据优先级进行的,而不是按 FIFO 方式。</p> <p>那么第一个点就是如何确定锁竞争的激烈程度,下面是一些直观的想法。</p> <h3>最多锁持有优先(MLF)</h3> <p>一个事务,它持有的锁越多,则越有可能 block 住其它的事务。所以最多锁持有可以作为一种评判标准。</p> <p>持有锁越多的事务,越优先调度。我们将这种方式称为“最多锁持有优先”。</p> <p>这里的问题在于,对象之间并不是等价的。有些对象很 popular,持有它的锁会 block 住其它事务,而另一些对象其实并不 block 其它事务。依赖的节点多,并不意味着导致锁竞争。大部分上的节点都不会发生冲突。只有冲突节点上,才造成锁竞争。</p> <h3>最多 block 锁持有优先(MBLF)</h3> <p>事务依赖的锁,只有当这个锁还同时被其它事务依赖时,才导致锁竞争。所以上面的算法可以优化一下,不使用依赖的节点数量,而使用依赖的锁数量。</p> <p>这里的问题在于,没有考虑进去锁的因素,将所有锁都看作相同的。假设有两个锁,其中一个 block 住了一个事务,而另一个锁 block 住了 10 个事务,在这个评判标准里面,两个锁还是被等同处理的。</p> <h3>依赖子图深度优先(DDF)</h3> <p>锁 block 住的事务多了,这个锁重要性也就提升了。为了抓住锁之间的重要性不同这个因素,我们可以考虑 “事务依赖的锁,锁 block 住的事务” 这一层关系,可以画一个依赖图出来。用子图的深度来衡量整个 block 的程度,也即反映了锁竞争的程度。</p> <p>从事务到依赖图的叶子节点的路径深度,作为一个事务的优先级。</p> <h3>最大依赖集优先(LDSF)</h3> <p>因为我们不能考虑事务什么时候到达,什么时候结束,所以我们只能考虑当前执行中的事务。考虑事务之前的依赖图关系。</p> <p>如果把依赖图画出来后,就会发现,“依赖子图深度优先” 跟 “最多 block 锁持有优先”,一种是反映图的垂直方向,一种是图的水平方向。把它两结合到一起考虑,就会变成“最大依赖集优先”。</p> <p><strong>将锁授予依赖集最大的事务,它能继续执行往前推进,则意味着依赖集里面的所有事务,都有潜在推进的可能。这样最有利于系统整体的向前推进。</strong></p> <h3>修正的最大依赖集优先(bLDSF)</h3> <p>上面的最大依赖集优先是一个简化了的场景,假定只存在排它锁。实际上,如果存在共享锁,则问题会变得复杂一些。</p> <p>共享锁会有一个&quot;饥饿&quot;问题,它被一直持有,导致排它锁加不上去,从而申请排它锁的事务时间会被拖长,造成系统整体的吞吐下降。所以论文里面还有一个结论是说,共享锁并不是分配给越多的事务就越好。</p> <p>paper 里面有关于共享锁的处理细节,这里先略过。</p> <h2>算法实现</h2> <p>输入是依赖图,依赖对象;输出是应该将什么样的锁,分配给什么样的事务集合。</p> <ol> <li>如果还有其它事务仍然对象 o 上面持有锁,则返回空</li> <li>获取在对象 o 上面等待共享锁的集合 {t1,t2...tm}</li> <li>获取在对象 o 上面等待排它锁的集合 {ta,tb...tn**</li> <li>计算一个<strong>共享锁的子集</strong>,使依赖集 {g(t1) |+ g(t2) |+ ...g(tk)} / f(k) 达到最大值</li> <li>取排它锁的依赖集的最大值</li> <li>如果是从共享锁依赖集算出来的最大值,大于排它锁算出来的值,则唤醒共享锁的一个子集的事务</li> <li>否则,唤醒依赖集最大的那个排它锁事务</li></ol> <p>这算法并不是来一个事务,就给它授予锁,或者遇到锁了将它排队(FIFO)。而是从头到尾的扫描整个 waiting 的事务,找出一个满足条件的并授予锁。</p> <p>如何计算依赖集大小?</p> <p>计算依赖集要遍历子图,而且每次依赖图变化了,每个节点要重新实时的计算,这种方式代价太高了。所以 paper 里面是取一个近似值。如果一个事务 t,没有锁 block 这个事务,那么 <code>g(t) = 1</code>。否则,它依赖某些锁,这些锁被事务集合 <code>t1...tn</code> 占着,则 <code>g(t) = g(t1)+g(t2)...+g(tn) + 1</code>。这是一个近似算法,原因是依赖图不是一个树,而是一个 DAG,是有节点重叠的。</p> <p>另外的麻烦的点是算共享锁的子图的依赖集情况,先略过了。</p> <p>大致就这些,至于结果对比...各种吊打 FIFO 策略,就不提了。最后我想质疑一下的是,它的数据场景构造的有一些极端,发论文嘛,动不动就说 100x 提升...真实 case 里面达不到冲突严重到那种程度,所以数据肯定不会有那么好看。</p> www.zenlife.tk/contention-aware-lock-schedule.md 2018-10-11T11:26:42Z 事务的锁调度 2018-10-11T11:26:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>有个项目 POC,性能达不到要求。一个小朋友抓了一下火焰图,感觉 parser 占的挺高,就吭哧吭哧要优化 parser。这做事方式,没有讲究方法论。</p> <h2>用数据说话,拒绝先入为主</h2> <p>首先没有分析系统的瓶颈。影响系统整体性能的因素很多,瓶颈有可能在 CPU,当然也有可能是网络,磁盘,甚至调度器,锁等等等。抓火焰图看的只是 CPU。CPU 是不是打满了,瓶颈是不是在 CPU,这是首先要确认的。</p> <p>其次没有用数据说话,parse 占用的 CPU 高,并不能代表 parse 消耗的时间最长,是系统瓶颈。就算 parse 是耗时,那它耗时究竟是多长呢?跟其它步骤相比呢,比如和 optimize,execute 相比呢,这需要量化。做事情呐,一定要拒绝先入为主,要用数据说话,不能够 &quot;我觉得 parser 占 CPU,所以要优化它&quot;。</p> <p>假设系统处理一个任务要经过三个主要步骤,耗时比较分别占 10% 20% 70%,将第一个步骤优化 30%,那对系统整体的提升也只有 3%。而如果我们找到那个瓶颈的 70%,将它提升 30%,对系统整体的提升却有 21%。一定要先抓住主要矛盾,先定位瓶颈。</p> <h2>培养数据敏感性</h2> <p>有时候做压测,就觉得结果不如自己想象中好,总觉得应该哪里还能有提升,但是又不知道如何定位到瓶颈。这是缺乏数据敏感性,说白了是平时太懒得思考和分析,没养成好习惯。</p> <p>假设我们得到的是 8000 QPS,80 并发连接。那么大脑马上应该反应,平均每个连接上面,是每秒处理 100 个请求。所以,平均处理一个请求需要 10ms。 如果我们有监控,是不是应该去看看,80% 95% 99% 999% 这些时间分别是多少,数据是否能对上。80 跟平均应该是相差不多的。</p> <p>假设我们看到,80 跟 99 差得特别多,比如 80 在几百 us,而 99 到了几十 ms,我们是不是应该立刻思考哪些因素影响响应时间的分布情况,考虑长尾问题。 会不会统计的请求类型不同,大部分请求类型都很快,而特定几类很慢,将所以将整体 99 响应时间拖长了?或者拿我们自己的数据库监控来说,是不是应该马上看一下,有没有事务冲突重试,看下锁的监控是什么样子的?</p> <p>假设我们算出平均处理一个请求需要 10ms,并且我们知道系统各阶段会经历什么。还是拿我们的系统举例,一个 SQL 请求进到数据库以后,要做 parse 生成 AST,然后 optimize 生成执行计划,接着 execute 执行它。另外我们的事务模型需要取一个全局唯一时钟 tso。那么我们就可以算一算,各步骤分别占用的耗时,加起来跟整个请求处理时间是否吻合。</p> <p>parse 正常情况下落在 100 us,optimize 也是 几百 us,execute 对简单点查就等于走一次网络时间,tso 也是一次网络时间,我们在同数据中心内,一次网络也就 500 us,小于 1ms。 取 tso 跟 parse + optimize 是并行的,parse + optimize 正常小于 tso,制约因素会落在 tso,那么经过分析,点查的理论处理时间应该在两次网络请求,2ms。</p> <p>如果跟理论算的不一样,就应该看监控定位问题。是不是应该想到 <a href="go-scheduler-pitfall.md">tso 的问题</a>。也要修正自己的理论,比如 SQL 特别复杂,那 parse 时间会不会升高严重,或者 parse + optimize 超过了 tso 时间成为制约因素?这些都是需要数据敏感性的。怕就怕,没有数据敏感性,多快叫快?多慢叫慢?没有分析方法,拿到监控也是大脑一片空白。</p> <p>数据敏感性一定要建立起来。有一个 jeff dean 的 what are the numbers that every computer engineer should know,网上可以搜到,推荐每个程序员都应该了解一下:</p> <pre><code>Latency Comparison Numbers (~2012) ---------------------------------- L1 cache reference 0.5 ns Branch mispredict 5 ns L2 cache reference 7 ns 14x L1 cache Mutex lock/unlock 25 ns Main memory reference 100 ns 20x L2 cache, 200x L1 cache Compress 1K bytes with Zippy 3,000 ns 3 us Send 1K bytes over 1 Gbps network 10,000 ns 10 us Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD Read 1 MB sequentially from memory 250,000 ns 250 us Round trip within same datacenter 500,000 ns 500 us Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD Send packet CA-&gt;Netherlands-&gt;CA 150,000,000 ns 150,000 us 150 ms </code></pre> <p>另外,我更推荐自己实验,自己平时总结数据,自己动手得到的数据,印象更加深刻!平时多积累。比如说当我看到这个 <a href="https://github.com/bg5sbk/go-labs">repo</a>,就知道这个程序员的数据敏感性肯定挺好,那基本素质绝对不会差。</p> <h2>先假设再求证</h2> <p>观察到性能问题后,在分析时应该是先假设,再求证的。注意要排除掉外界干扰因素,比如说以前遇到过<a href="近期竞价服务的几个性能优化点.md">同机器上部署了其它业务,周期性打满 CPU的</a>。</p> <p>曾经有一次使用过某个 SB 的 bench 工具,可以控制固定流量的负载去观察系统表现。结果发现不太对。把 top 刷新时间调短后,观察 CPU 使用很不稳定。就怀疑 bench 程序有问题。 果然,它是这样控制固定的 QPS 的:在每一秒的前期疯狂的制造很高的并发请求,然后就等待直到下一秒。比如生成 1000 QPS 负载,它实际全部落在每秒的几分之一秒内,完全不均匀。到了系统那边,就变成了一下暴发流量,一下又空了,性能随之波动。根本不是在测试固定 QPS 下的效果。</p> <p>以前聊过 Go 的调度导致的问题,同样是假设网络问题,假设 runtime 有问题,再一步一步分析,验证。 最近在 tso 问题上面,又有一个新的发现。某系统每小时周期性的跑一些分析型任务,然后观察到 tso 的获取时间会周期性变长。对应机器配置特别高,所以跑周期任务时,负载其实也并不高,不是之前遇到的调度问题。 另外我们观察到,分析任务跑的时候,内存会从平时 300M 以内,上升到 6~7G,内存的上涨波动,跟 tso 的时间波动能正好对得上。</p> <p>好啦,只聊方法论,基于这个观察,可以做一个假设,内存占用影响到 GC 时间,然后 GC 时间影响到 tso 对应的 goroutine,进而影响了延迟。Go 语言的 GC 的 stop the world 时间是很短的,但是注意到,即使不用 stop the world,扫描某个 goroutine 的时候,还是需要挂起这个 goroutine 的,所以它是 stop the goroutine 的。如果整个系统依赖于这个核心的 goroutine,那系统整体延迟还是受影响的。如果求证怎么做?可以模拟类似的场景,然后看内存使用高和内存使用低时,对比 trace 的区别。</p> <p>个人经验,在几个用 Go 语言做系统里面,我观察到机器配置较高的时候,开多个 Go 进程比单个大 Go 进程性能好。最后部署都是前面挂 proxy 起多个进程,而不是单台机器上只部署一个大的进程的。那怎么分析这个现象呢? 可以假设,调度那一层的损耗并不是随着负载 O(n) 的事情,当负载 N 越大,其实性能损失并不线性增加。就类似为什么排序使用二分的时候可以获得更好的性能。比如说,程序有单点,有全局的 lock,这些随着线程 CPU 核数增加时,并不会 scalable。另外,在系统调度的这一层,单进程和多进程也不同。多进程相对于单进程,是否会更多的从系统那边获取被调度机会。验证起来并不太好做。</p> <h2>先估算再实现</h2> <p>性能是应该在系统设计阶段就估算的。我们公司有一个架构师(前金山快盘之父),做过一次分享,他的方法论我很认同。他有一个特点,不计较一城一池的得失,而强调宏观把控。 系统有 CPU,网络,磁盘等等很多资源,他强调的是,如何<strong>合理的</strong>把各项资源吃满,只要这一个点做到位了,系统整体的性能不会差到哪去。</p> <p>他喜欢把终端窗口切成好多,放到一个屏幕里,然后同时监控 CPU,网络,磁盘等等。如果一会 CPU 一个波峰其它很低,一会儿又磁盘吃满了 CPU 空着,这种系统整体的吞吐就不太好。 反之,如果整体曲线是各项相对平滑,那说明这个系统合理地把各项资源都利用上了,这就是一个设计得好的系统。</p> <p>举个例子,对一个下载类的任务,从一处下载数据,然后将数据压缩,最后要将结果存盘。这是典型的分阶段任务,不同阶段资源瓶颈不同。下载需要网络,压缩主要是耗 CPU,而存盘需要磁盘 IO。 如果才能达到更好的吞吐呢?假设串行的做,系统就会出现典型的先卡在网络,再卡在 CPU,最后卡在磁盘。如果我们将任务划分成小块,然后流水线的做这些事情,就可以把各阶段的等待时间消除掉。 提升吞吐,就那几个关键字:并行,批量,流式。但这里面的门道却很多,任务切分按多大?切大切小分别有什么问题。不同机器性能不一致,有特定的就比其它慢怎么搞?数据乱序到达如何处理,重传的幂等性。如何确定各级流水线,分别该分配多少线程呢?扯远了。各级流水线生产者消费者之间,用消息队列串起来,最终的结果,肯定只有一个消息队列塞满,其它都空着。塞满的那一个,就对应整个系统的瓶颈所在。</p> <p>估算,提前要做 benchmark,这个例子里面,网络传输的速度多少,写盘速度多少,然后各种压缩算法的数据处理速度是多少 M/s,这些做到心里有数。按照他的方法,在设计阶段,整体系统大概的吞吐量,就应该能估算出来。 代码写得挫没关系,不计较一城一池的得失,各个环节,哪一步有不符合预期,再去做细节优化,慢慢调整,最终整个系统的性能目标就是可控的。</p> <p>最后,我发现在系统性能这一块,是区分新手老手的一个很好的试金石。因为系统的性能分析的东西,基本是靠经验积累上来的。看校招,看新人,这些地方就很明显。</p> www.zenlife.tk/performance-analysis.md 2018-10-19T01:27:42Z 性能分析方法论 2018-10-19T01:27:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>本文面向的阅读对象是使用过 scheme 的卫生宏,希望了解它是如何实现的,或者在实现自己的 lisp 语言的一类人。 另一个基础要求是,至少知道动态作用域和静态作用域。</p> <h2>宏的分类</h2> <p>scheme 语言里面,宏是一个很让人误解的话题,它使用是 syntax-rules。其实 syntax-rules 是混杂了两个概念,所以使它的理解变得复杂。应该拆成两个维度来理解。一个维度是卫生/非卫生。另一个维度是过程宏/高级宏。</p> <p>先说过程宏和高级宏维度。一些其它的 lisp 或者 common lisp 里面,有 defmacro,这是很直观的,宏就类似于一个普通函数,它的是输入参数的 sexp,然后输出也是 sexp。这个宏函数里面具体实现了如何变换的过程,所以是过程宏。 在 scheme 的 syntax-rules 里面,它是使用了模式匹配的方式,来描述如何将一个 sexp 变换成另一个 sexp。这就是高级宏,或者说模式匹配宏。</p> <p>再来说卫生宏。卫生或者不卫生,跟高级宏过程宏其实是不相关的概念。如果用两个维度来分类,那么 syntax-rules 是高级宏,是卫生宏。而一些 lisp 的 defmacro 是非卫生宏,是过程宏。 还有另外一些系统,是卫生的,却是过程宏。</p> <pre><code>defmacro 过程宏 不卫生 syntax-rules 高级宏 卫生 syntatic-closure 过程宏 可实现卫生 explicit-renaming 过程宏 可实现卫生 syntax-case 可过程或高级 可实现卫生 </code></pre> <h2>什么是卫生</h2> <p><strong>卫生或者不卫生的本质问题,还是作用域问题</strong>,理解这个了,对于卫生宏就理解了。</p> <p>让我们先看,defmacro 存在什么问题呢?</p> <pre><code>(defmacro (swap! A B) (let ((tmp ,A)) (set! ,A ,B) (set! ,B tmp))) (swap! tmp x) </code></pre> <p>展开之后,变成了</p> <pre><code>(let ((tmp tmp)) (set! tmp x) (set! x tmp)) </code></pre> <p>这里是一个变量重名问题,宏里面引入的 tmp,跟宏调用的参数 tmp 相互冲突了。有经验的 lisp 程序员会说,应该使用 <code>(gemsym tmp)</code>,然而,这并不是卫生的。也并不能解决更多问题。</p> <p>假设用户这么玩,定义宏 test:</p> <pre><code>(define x 'hello) (defmacro (test) '(print x)) </code></pre> <p>调用宏展开</p> <pre><code>(let ((x 'world)) (test**** </code></pre> <p>得到的结果是 hello 还是 world 呢?这个点就能体现卫生宏和非卫生宏的本质区别了。一个符号 x,它在宏定义的位置是代表的什么含义,以及它在宏展开的位置代表的是什么含义。<strong>非卫生宏是做 sexp 的无脑替换。卫生宏是需要理解语义的</strong>。</p> <p>这个问题非常类似于静态作用域和动态作用域的问题。函数定义:</p> <pre><code>(define x 3) (define (f) x) </code></pre> <p>函数调用:</p> <pre><code>(let ((x 5)) (f)) </code></pre> <p>在函数定义的作用域里面,x 的值是 3。在函数调用的时候,作用域里面有一个变量 x 对应的值是 5。如果一门语言采用动态作用域,调用 f 返回值将会是 5,因为动态作用域用函数使用时的上下文决定一个变量的值。在静态作用域里面,f 返回值是 3。</p> <p>这里要强调的一个概念是“引用透明性”。静态作用域好处就在于,不管 f 在哪里被调用(引用),它的结果都是确定的,因此不会有意想不到的 bug。 前面说了,卫生或者不卫生的本质问题,还是作用域问题。宏要处理一系列符号,宏又有宏定义阶段和宏展开阶段,卫生问题说白了就是哪些符号是对应在宏定义阶段,哪些符号是对应在宏展开阶段。如果宏是卫生的,它就具有“引用透明性”,定义阶段就确切知道每个符号的意义,不会出现意外的绑定。</p> <h2>历史算法</h2> <p>历史上比较有影响力的几个算法,下面是一个简单的时间线。</p> <ul> <li>1986: Kohlbecker - introduced the idea of hygiene, low-level, used an O(n^2) coloring algorithm</li> <li>1987: Kohlbecker - introduced declare-syntax, high-level, the precursor to syntax-rules</li> <li>1988: Bawden &amp; Rees - &quot;Syntactic closures,&quot; low-level, faster than Kohlbecker's algorithm</li> <li>1991: Clinger &amp; Rees - Explicit renaming, low-level, based on syntactic-closures but also supports syntax-rules</li> <li>1992: Dybvig - Syntax-case, primary motivation to remove the distinction between low-level and high-level</li></ul> <p>一个一个解释。第一个,KFFD,Kohlbecker 在 86 年的一篇 paper 里面首次提出了宏的卫生的概念。四位作者的首字符缩写出来,就是 KFFD。具体实现方式跳过了,这个算法低效,并且现今已经没有人在用了。</p> <p>第二个,syntax-rules。作者还是 Kohlbecker,在 87 年的一篇 paper 里面,提出了用模式匹配的方式来声明宏的 idea。这就是 syntax-rules 的前身了。</p> <p>第三个,syntax closure。开始重点介绍。既然我们知道了卫生宏的本质问题,符号到底对应宏定义时期的环境,还是宏展开时期的环境,我们可以添加两个参数:</p> <pre><code>(define-syntax foo (lambda (form usage-environment macro-environment) ...)) </code></pre> <p>在 macro 里面显示的指定,每个符号是对应定义时期,还是展开时期,这样就不会出现误解了。再可以简化一下,把宏定义期环境作为默认值,就可以去掉 <code>macro-environment</code> 参数,于是得到 <code>sc-macro-transformer</code>:</p> <pre><code>(define-syntax swap! (sc-macro-transformer (lambda (form env) (let ((a (make-syntactic-closure env '() (cadr form))) (b (make-syntactic-closure env '() (caddr form)))) `(let ((value ,a)) (set! ,a ,b) (set! ,b value)))))) </code></pre> <p>这里面的 let value set! 等等都是在宏的定义期环境里面的符号,因此不会跟运行期环境里面的符号冲突。而 a 和 b 这两个符号,则是 swap! 宏里面指定了使用宏展开时期的环境。</p> <p>第四个,通过 explicit renaming,来决定卫生问题。<code>er-macro-transformer</code> 跟 <code>sc-macro-transformer</code> 在使用方面看起来只是一个提供的是环境,另一个提供的是函数,由 rename 函数决定了使用宏定义时的环境。</p> <pre><code>(define-syntax swap! (er-macro-transformer (lambda (form rename compare) (let ((a (cadr form)) (b (caddr form))) `(,(rename 'let) ((,(rename 'value) ,a)) (,(rename 'set!) ,a ,b) (,(rename 'set!) ,b ,(rename 'value))))))) </code></pre> <p>syntatic closure 和 explicit renaming,符合那些 defmacro 的人的使用习惯,如果把 <code>rename</code> 当成 <code>gensym</code> 来用,但它是可以实现成卫生的。背后的算法还是区分了宏定义环境和宏展开环境,不是简单的重命名。</p> <p>第五个要说的,是 syntax-case。syntax-case 是在 r6rs 以及 chez-scheme 里面实现的,作者也正是 chez 编译器的作者 Dybvig。syntax-case 非常强大,既可以支持高级宏,也可以支持过程宏,并且可以处理卫生和不卫生。 但是强大的代价是这个宏系统非常复杂,理解,使用和实现上面都是。</p> <p>最后最后提一下,当前最先进的(截止2018年)应该是 racket 和 gerbil 的宏系统。使用的实现的是用的 <a href="http://www.cs.utah.edu/plt/scope-sets/index.html">Scope Set</a>。这个 matthew flatt 在 2012 年就出 paper 了。 在 racket 里面,引入了语法对象 syntax。为 syntax 绑定了 scope,多了一层抽象来处理宏。 这不只是记法问题。本来有 symbol。决定 symbol 要区分是 variable 或是 identifier 又需要 quote。我觉得有越搞越复杂的倾向。有点脱离了 sexp 这些简单的初衷。</p> <p>由这些个算法的发展历史小结一下,这个问题在研究上基本已经到头了。目前并没有什么既简单,又强大的方案出来。syntax-case 很强大但复杂。我觉得如果是自己实现,可能 syntatic closure 或者 explicit renaming 会<a href="http://mumble.net/~jar/pubs/scheme-of-things/easy-macros.pdf">好一点</a>。</p> <h2>更多思考</h2> <h3>宏的展开次序问题</h3> <p>宏展开是一个递归展开的过程,那么展开的顺序是一个需要考虑的问题。这在语言标准里面是没定义的。另外,如果宏带副作用的,整个结果就不确定了。导致宏不是一个可组合的东西。</p> <h3>编译期展开和运行期展开</h3> <p>完全展开和非完成展开,解释器可以实现成运行期展开,每遇到宏就进行展开了再解释。编译器必须要求宏是编译期完成展开的。需要一个 expander 递归的处理宏展开的过程,直到这个过程结束。注意,过程宏是可以在展开时期做计算的,整个宏展开过程就不保证收敛了。</p> <h3>宏展开过程中引入的作用域</h3> <p>宏调用宏,展开的过程中,会引入新的宏展开作用域,也是卫生需要考虑到的。</p> <h3>过程宏的问题,为什么r7rs r5rs 标准里面都是用的 syntax-rule</h3> <p>过程宏很难标准化。主要是它把编译器和运行期的耦合弄得不确定了。前面说过,卫生的宏展开,是要考虑语义的。而考虑语义的东西,有些在运行期才能决定。</p> <pre><code>(let ((x 3)) (macro-test (if x &gt; 5)) </code></pre> <p>比如过程宏根据某条件做展开,条件要在运行期计算才确定。宏展开期间它前不知道一些运行期的条件,这就无法完全编译期展开了。 syntax-rule 的一个好处,它可以避免过程宏的这种问题,写出来的宏是可以完全展开的。</p> <h3>跟模块,separate compilation 的关系</h3> <p>宏跟模块有莫大的关联性,racket 强大在 module,这也是为什么它需要采用复杂的 macro 系统来支持 module 的实现。</p> <p>宏可以在展开时计算一些东西,计算依赖的函数本来是运行期的,被依赖到了编译器。</p> <p>有了 module 和 separate compilation 之后,其个宏要引入其它模块函数,而在使用这个模块的宏,另外模块还没有编译,这里面的依赖就会有些难搞。</p> <p><a href="explicit-renaming-macro.md">接下篇...</a></p> <h2>参考资料</h2> <ul> <li><a href="https://lists.gnu.org/archive/html/chicken-users/2008-04/msg00013.html">macro systems and chicken</a></li> <li><a href="https://news.ycombinator.com/item?id=15394603">评论区 groovy2shoes 的回复</a></li> <li><a href="http://mumble.net/~jar/pubs/scheme-of-things/easy-macros.pdf">Implementing Lexically Scoped Macros</a></li> <li><a href="http://www.cs.utah.edu/plt/scope-sets/index.html">Binding as Sets of Scopes</a></li></ul> www.zenlife.tk/scheme-hygiene-macro.md 2018-10-22T15:48:42Z scheme 卫生宏实现介绍 2018-10-22T15:48:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p><a href="scheme-hygiene-macro.md">接上篇</a>,前面对 scheme 卫生宏的实现方式有个整体的介绍,这一次具体讲其中 explicit renaming 这种方式的实现原理。</p> <p>首先讲 <a href="https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B1-conversion">alpha 变换</a>。alpha 变换这东西,说的就是函数的参数名字其实是无所谓的。</p> <pre><code>(lambda (a b) (+ a b)) </code></pre> <p>跟下面这个完全是等价的。</p> <pre><code>(lambda (a1 b2) (+ a1 b2)) </code></pre> <p>alpha 变换就是自由的把函数名字随便换。alpha 变换这么实现:</p> <pre><code>(define (alpha-convert exp env) (match (x (symbol? exp)) (replace-symbol x env)) (lambda (x) body) (let ((new-env (cons (x . x1) env))) `(lambda (x) ,(alpha-convert body new-env)))) </code></pre> <p>用一个环境,环境里面是 <code>(原符号 . rename后的符号)</code>。</p> <p>为什么要讲 alpha 变换呢? 因为 explicit renaming 其核心就是在做 alpha 变换!</p> <p>考虑一个宏:</p> <pre><code>(swap! x y) (let ((tmp x)) (set! x y) (set! y tmp)) </code></pre> <p>如果我们把展开宏显式的重命名一下,注意前面说过的卫生的原则 -- 卫生的本质问题,还是作用域。把需要使用 宏定义时作用域 的变量用 [] 框起来:</p> <pre><code>([let] (([tmp] x)) ([set!] x y) ([set!] y [tmp])) </code></pre> <p>[let] [set!] [tmp] 指代的是宏定义时的符号,而 x y 则是宏展开时期的符号。每一次宏展开生成都赋予一个唯一 id,因此我们可以把上面写成:</p> <pre><code>([let 1] (([tmp 1] x)) ([set! 1] x y) ([set! 1] y [tmp 1])) </code></pre> <p>如果有多次的宏展开,比如 (swap! (or x 1) y) 第一次展开 swap! 时:</p> <pre><code>([let 1] (([tmp 1] (or x 1)) ([set! 1] (or x 1) y) ([set! 1] y [tmp 1])) </code></pre> <p>第二次再展开 or 之后:</p> <pre><code>([let 1] (([tmp 1] ([if 2] x x 1)) ([set! 1] ([if 2] x x 1) y) ([set! 1] y [tmp 1])) </code></pre> <p>注意其中的 [let 1] 跟 [if 2] 分别是对 swap! 和 or 的两次展开过程,每次展开都对应了一个唯一 id。如果我们有一个 [let 1] 和 [let 3],它俩有可能是同一个东西,只是在不同的宏展开过程中赋予的 id 不同。</p> <p>如果看 <code>er-macro-transform</code> 的说明,它说每次展开都是在不同的词法环境中,所以不同的宏展开后的符号不会跟其它任何地方冲突。怎么理解的呢?嗯,其实就是做了 alpha 变换。对于前面的前面的例子,如果我们再夹杂一个 alpha 变换,可以写成这样子:</p> <pre><code>([let 1] (([tmp 1] x@523423132) ([set! 1] x@523423132 y@44512342) ([set! 1] y@44512342 [tmp 1])) </code></pre> <p>alpha 变换使用的 宏展开时环境: ((x . x@523423132) (y . y@44512342))</p> <p>这是最重点的地方,准确来说,遇到宏展开会做两步操作:</p> <ul> <li>第一步是在宏展开时,把 let set! 变成 [let 1] [set! 1]</li> <li>第二步是将展开的结果做 alpha 替换,对普通的符号,使用宏展开时环境替换;对于 [let 1] 这种,使用宏定义时环境替换</li></ul> <p>或者放点代码会更清楚一点:</p> <pre><code>(define (expand exp menv env) (cond ((symbol? exp) (alpha-convert exp env)) ((generated? exp) (let ((env-of-def (assq (generated-uid exp) menv))) (alpha-convert (generated-sym exp) env))) ((pair? exp) (let ((den (binding (car exp) menv env))) (cond ((special? den) (expand-special-form den exp menv env)) ((macro? den) (expand-macro den exp menv env)) (else (expand-application exp menv env))))) (else exp))) ;; for const like string, number and so on </code></pre> <p>其中的 env 是一个符号,到一个绑定。绑定内容可能是 alpha 变换后的符号,或者特殊表 if begin set! lambda,也可能是宏。</p> <p>宏的表示是 转换函数,以及宏定义时环境。generated 就是 (name . uid)</p> <p>menv 是 uid 到 env 的映射,因为展开 generated 需要两步,通过 generated-uid 从 menv 获取到 generated 定义时的环境,下一步在是在该环境里面对 generated-sym 做 alpha 变换。</p> <pre><code>(define (expand-macro mac exp menv env) (let* ((transform (macro-func mac)) ;;提取宏转换函数 (env-of-def (macro-env mac)) ;;提取宏定义时环境 (uid (unique-id)) ;;每次展开生成唯一 id (new-menv (cons (uid . env-of-def) menv)) ;;唯一 id 到 env 绑定 (rename (lambda (x) (make-generated x uid))) ;; rename 会传递给宏用于绑定 宏定义时环境 (new-exp (transform exp rename))) ;; 调用宏转换函数,会生成 [let uid] (expand new-exp new-menv env))) ;; 对宏展开的结果,递归再展开 </code></pre> <p>expand-special-form 是对 if begin set! lambda 等东西做展开,其中 lambda 的展开:</p> <pre><code>(define (expand-lambda exp menv env) (let* ((args (cadr exp)) ;; (a b c) (values (map rename args)) ;; (a@5 b@6 c@7) (binds (map cons args values)) ;; ((a . a@5) (b . b@6) (c . c@7)) (new-env (append binds env))) ;; 新的 env,用于 alpha 变换 `(lambda ,values ,@(expand-sequence (cddr exp) menv new-env)))) </code></pre> <p>expand-special-forma 里面另个比较特殊的是 expand-defmacro,它要将 mac 加到 env 里面去。 应该解释清楚了。</p> <hr /> <p>最后看一个问题是,为什么 alpha 变换是卫生的,而 gensym 不是?</p> <pre><code>(let ((tmp#jsdjflsdf 32)) (some-macro)) </code></pre> <p>在 some-macro 展开用 <code>(let ((tmp (gensym))))</code> 引入的 tmp,可能正好是 <code>tmp#jsdjflsdf</code>,就会被前面的绑定误捕获了。而在 alpha 变换中,<code>tmp#jsdjflsdf</code> 在环境里面是 <code>tmp#jsdjflsdf@123</code>,宏展开时的 id 不可能是 <code>@123</code>,它只能是一个不一样的 id 了。</p> www.zenlife.tk/explicit-renaming-macro.md 2018-11-04T12:49:42Z 使用 explicit renaming 实现卫生宏 2018-11-04T12:49:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <h3>lisp 缺一个好的语法</h3> <p>满世界的人都对全是括号的表示充满讨厌,我也讨厌。有人说,lisp 有语法么? lisp 的标准语法不是 S表达式么。极端分子甚至强调 S表达式就是世界上最好的语法,括号是它精华的东西,认为搞些其它花里胡哨的语法偏离了教义。</p> <p>先打脸</p> <pre><code>(defun map F [] -&gt; [] F [X | Xs] -&gt; [(F X) | (map F Xs)]) </code></pre> <p>这种写法不比下面这种优雅得多? 不要拿模式匹配说事,模式匹配的问题后面讲。</p> <pre><code>(define map (lambda (f l) (if (null? l) '() (cons (f (car l)) (map f (cdr l)))))) </code></pre> <p>S表达式里面,只有两种东西,一种是 symbol,一种是 cons。然而实际上语言都会支持各种原子类型的符号,比如 number,比如字符串。</p> <p>遇到自定义类型的时候,就有一点欠缺了,定义结构体什么的,纯用 S表达式就有点别扭。 为什么不用 <code>#R&quot;(?&lt;=95|98|NT|2000)Windows&quot;</code> 来表示正则? 或者是自定义用来表示结构体的语法 <code>T{A : 3, B : &quot;sd&quot;}</code>。一旦这些东西多起来之后,S表达式就不那么纯粹了。</p> <h3>reader 宏很有意义,自定义 reader 收获更大</h3> <p>其实 lisp 是有 reader 宏的,像单引号的 quote,反引号的 quasiquote,逗号的 unquote,这些都是内置的 reader 宏。reader 在遇到任何这些特殊符号的时候,就自动改写S表达式了。<code>(quote s)</code> 的等价写法 <code>'s</code>。</p> <p>reader 宏是很有意义的,比如我们遇到 <code>{</code> 就按我们自己定义的方式来解析,最后输出的还是 S表达式。既然能够接受 reader 宏,为什么不更推进一步,自定义整个 reader 呢?</p> <p>自定义 reader 之后,语法喜欢什么口味都可以自己设计,比如即使变成这样子,都是完全合理的,反正过了 reader 之后,就是正统的 S表达式了:</p> <pre><code>func f() { } </code></pre> <p><strong>不用关心真正的语法,可以用任何自己喜欢的表示,自己写 reader,然后转换成 S表达式。</strong></p> <h3>quote 的问题</h3> <p>quote 是一个 reader 宏。在<a href="https://www.zhihu.com/question/60702229/answer/213029957">知乎回答问题</a>的时候,提到过 quote。</p> <blockquote> <p>quote 存在的真正意义就是,让用户可以选择到底是代码还是数据,但它只是实现的途径之一,但并不是必须的。</p></blockquote> <p>在 shen 语言里面,一个符号求值后得到的是它自身,不需要使用 quote。为了区分变量和符号,求值规则就有点特殊了,要取决于上下文,有绑定就是变量,没有绑定就是符号:</p> <p><code>(lambda (x) x y)</code> 在这个 lambda 里面, <code>x</code> 是变量, <code>y</code> 是符号</p> <p>即使不使用 shen 这么特殊的规则,要生成符号也完全可以使用其它方式,比如 <code>(intern &quot;x&quot;)</code>。只要有办法制造符号,制造 cons,就可以制造 S表达式。任何语言,只要写一个 reader,制造 S表达式还不是很简单的事情? 那岂不是所有语言都可以是 lisp 了? 那我们 lisp 党的迷之优越岂不是荡然无存了?</p> <p>扯了半天废话,我是要说什么来着,哦, quote 没毛卵用,并不是 lisp 里面必须的。</p> <h3>嵌套反引用有害</h3> <p>直接<a href="http://xlambda.com/blog/2013/03/10/nested-backquotes-considered-harmful/">帖个链接</a>,不解释了。</p> <p>为了解决嵌套反引用的问题,我提出(其实不是我提出的,shen 语言是这么干的)一个更好的语法表示:中括号的表示不求值,圆括号表示需要求值。</p> <pre><code>[A (f B [C D])] </code></pre> <p>不论嵌套多少层,仍然是一目了然。</p> <h3>pattern match 的 pattern 语法</h3> <p>不管是 syntax-rules,还是 pmatch 里面,pattern 的写法都让人感到很不一致,像是不在同一门语言里面。 举一个例子:</p> <pre><code>(pmatch exp [,x (guard (symbol? x)) x] [(,M ,N) `(,(compile-bc M) ,(compile-bc N))] [(lambda (,x) ,y) (guard (eq? x y)) `I] [(lambda (,x) (,M ,y)) (guard (eq? x y) (not (occur-free? x M))) (compile-bc M)] [(lambda (,x) (,M ,N)) (guard (and (not (occur-free? x M)) (occur-free? x N))) `((B ,(compile-bc M)) ,(compile-bc `(lambda (,x) ,N)))] [(lambda (,x) (,M ,N)) (guard (and (occur-free? x M) (not (occur-free? x N)))) `((C ,(compile-bc `(lambda (,x) ,M))) ,(compile-bc N))] [(lambda (,x) (,M ,N)) (guard (or (occur-free? x M) (occur-free? x N))) `((S ,(compile-bc `(lambda (,x) ,M))) ,(compile-bc `(lambda (,x) ,N)))] [(lambda (,x) ,M) (guard (not (occur-free? x M))) `(K ,(compile-bc M))] [(lambda (,x) ,M) (guard (occur-free? x M)) (compile-bc `(lambda (,x) ,(compile-bc M)))]** </code></pre> <p>注意观察到,匹配符号用的符号本身,匹配变量就需要加一个逗号。 我认为不是很好,最符合直觉的方式,应该<strong>让 pattern 匹配的对象,跟构造这个对象使用的同一种语法</strong>。比如:</p> <ul> <li>pattern 是一个数字 42,那它应该匹配到的也是 42;</li> <li>pattern 是一个字符串 &quot;xyz&quot;,那它匹配的也是一个字符串 &quot;xyz&quot;;</li> <li>构造一个 symbol 的方式是 (quote s),缩写是 <code>'s</code>,那以匹配符号 s 的 pattern 也应该是 <code>'s</code>;</li> <li>pattern 是 <code>(cons X Y)</code>,它用于构造一个 cons,那么匹配的也应该是一个 cons;</li> <li>x 就直接匹配任何变量了</li></ul> <p>还记得前面说过自定义 reader,在自定义的 reader 里面,构造 list 的方式是使用中括号 []。然后</p> <pre><code>[a b c] </code></pre> <p>经过 reader 转换成 S表达式以后,变成</p> <pre><code>(cons a (cons b (cons c nil))) </code></pre> <p>注意到没,pattern 匹配的对象,跟构造对象使用的是同种语法表示!整个语言就更一致了。</p> <p>构造一个 symbol 是使用 <code>(quote s)</code>,那么模式匹配中也使用 <code>(quote s)</code>。 假设我们自定义结构体的语法,比如 <code>T{A, B}</code>,那这个东西当 pattern 表示时,也应该匹配结构体 T 对象。</p> <p>最后看一个,<code>(quote (a b c))</code> 的含义是啥? 它不是一个构造链表的函数,不应该使用这种东西放在模式匹配里面。 即使没有 quote,假设构造符号使用的是 <code>(intern &quot;xxx&quot;)</code>,那模式匹配的写法也应该是 <code>(intern &quot;xxx&quot;)</code>。</p> <p>为了避免 <code>(quote (a b c))</code> 这种奇怪的东西出现在语言里面,最好的办法是,语言里面只允许使用 <code>(quote symbol)</code>,不能 quote 其它的。</p> <p>好啦,看个例子:</p> <pre><code>(match v x -&gt; (+ x 2) ;; 模式匹配一个变量 [] -&gt; #t ;; #t 和 #f 和 [] 都是基本对象 [a b] -&gt; a ;; [a b] 其实是 (cons a (cons b [])) [a | b] -&gt; a ;; [a | b] 等价于 (cons a b) T{a} -&gt; a ;; 如果有自定义结构体 'a -&gt; 'b ;; 匹配一个符号, 'a 等价于 (quote a) _ -&gt; (error &quot;nothing&quot;)) ;; 下划线跟变量差不多 </code></pre> <p>定义函数也是使用模式匹配的,跟 match 一样:</p> <pre><code>(defun f a b -&gt; 42 ;; 跟 match 不同的是这里可以多参数 ['lambda x] y -&gt; y) </code></pre> <p>跟 shen 语言不同的是,不使用大小写区分变量和符号,符号使用 quote</p> www.zenlife.tk/lisp-better-syntax.md 2018-11-11T18:30:42Z 一个更优雅的 lisp 语法设计 2018-11-11T18:30:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>根据业务特点定制的分配器,绝对是最高效的实现之一。比如说,发送网络消息包需要拼凑很多对象来生成包,发送完成后,消息包的那块内存就不再使用了。于是,这里可以申请一块内存反复使用。相比于每次申请释放内存,无论下层的内存管理如何实现,是不可能抵得上重用来得高效的。比如说,业务本身是无锁的,特定实现相比通用的实现就简单的多。</p> <p>通用的分配器则难以利用到业务特点。通用实现一般是基于地址做回收的,广义概念的回收,不管是 GC 还是 free 的回收。基于地址回收就涉及原内存里面挖了洞,于是要考虑有各式各样大小的对象池子去优化,要考虑回收的时候对象合并,考虑匹配大小的对象,还有内部碎片外部碎片这些。于是有了 freelist,buddy 算法,bitmap 等等很多东西。</p> <p>我们有一个业务场景,内存分配比较有特点。对象不停的分配,分配出来之后,会存活一段时间,再之后,就很少被使用了。不同于网络消息那种一次的交互的简单例子,它是一段时间内的存在较多交互,存活一段时间。另外一点,在整个存活时间内,内存使用量比较大,小对象特别的多,会对 GC 那边扫描造成非常大的压力。主要还是想优化小对象数量,于是,我设计了一个基于时间的定制分配器。</p> <p>接口的设计上面,只暴露两个函数:</p> <pre><code>func alloc(size int) ([]byte, int) func gc(safeTS int) </code></pre> <p>注意 <code>alloc</code> 函数的返回值,除了分配的内存本身,它还额外返回了一个 timestamp。这就是这个对象的分配时间(概念上的时间,只是一个单调递增的数字而已)。</p> <p>然后是 <code>gc</code> 函数,它会回收掉所有在 safeTS 时间之前的对象。</p> <p>业务使用的时候,必须自己去处理还在使用中的对象,比如说重新分配一下,刷新一下时间,有点像 lease 的续租。然后业务自己去调用 <code>gc</code> 将旧的对象全部释放掉。分配和释放都是由业务自已来控制的。</p> <p>业务怎么知道哪些对象还会被使用呢? 可以把对象的创建时间存到对象里面。调用 <code>gc</code> 之前,用来跟 safeTS 去比较。如果对象创建时间小于 safeTS,并且它还需要继续被使用,那么就需要重新为它分配,然后让使用者更新对它的引用。被使用者引用在有些业务场景是不知道的,于是就不能这么干了,这是一个限制。当然我们的场景是可以的。</p> <p>然后实现细节。有一些内存块,比如说每块 1M(随便拍脑袋定的)。分配时从当前内存块里面加划出内存。</p> <p>回收时,整块内存做回收。每次操作时间会加加。每个内存块上面,会记录一个 minTS。注意有个约束条件,所有在这块内存里面划出去的对象,它们对应的创建时间都是大于 minTS 的。</p> <pre><code>block1(minTS=0) obj(ts=1) obj(ts=2) ... obj(ts=29) -&gt; block2(minTS=30) obj(ts=31) obj(ts=32) ... -&gt; block3(minTS=77) ... -&gt; </code></pre> <p>整个过程没有删除操作,直到开始回收。把整个旧的大块内存直接删除。假设我们要回收到 <code>safeTS = 44</code>,那么直接删除掉 block1 就好了,因为所有 block1 上面的对象的时间肯定是处于 <code>[1, 30)</code> 的,小于 safeTS。</p> <p>不像 GC 做标记清扫,这个算法不会根据对象地址去标记,清扫也不用重新整理内存,非常高效。假设对象过了一定时间后都是不再使用的。业务自己要去处理将活着的对象挪走。</p> <p>大半夜写博客<a href="https://github.com/pingcap/tidb/pull/8344/files#diff-4931e8b3fc11f830a7973b15df9e5efeR59">写代码</a>,感觉头脑都不太清醒了...</p> www.zenlife.tk/time-based-allocator.md 2018-11-17T02:27:42Z 基于时间的定制分配器 2018-11-17T02:27:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>把公司项目迁移到 Go1.11 的 module 了,这个过程中对于版本控制,依赖管理之类的事情有了更加深入的了解。 本来懒得写东西,有同事说起,“我们从 glide 到 dep,一直到现在切换到 module 了,为什么项目的依赖还是很难用”,所以我觉得还是有必要写一写。让更多的人理解 go module 以及语义版本,还是有意义的。</p> <p>包是一个固定的路径,而包的代码是会动态的变化的。如果今天 import 一个包可以编译过,明天那个包升级一下,项目就挂了,肯定是不能忍的。过去的一个做法,我们把所有的依赖都放进 vendor 里面,就不受外部包的升级之类的影响了。</p> <p>仅仅是代码拷到 vendor 不行,需要知道使用的是哪个版本的包,要有工具帮忙做这个事情,glide 到 dep 都是这样的工具。这些工具会有一个描述文件,一个 lock 文件,以及 vendor 代码。 描述文件里面,可以写很多灵活的规则,指定一个包使用哪个版本,比如使用 1.1.1,或者版本大于多少且小于多少,使用某个分支,又或者是某个 commit hash。lock 文件是工具根据描述文件的说明生成出来的,每个包使用具体到哪个 commit 都是确定的。</p> <p>主流的依赖管理工具都是这么干的,无论是在 rust 还是 javascript 或者其它语言里面。一开始在 Go 做 dep 的时候,也准备就按主流搞法做,然而 russ cox 对这个方向越做越觉得不对。</p> <p>使用 commit hash 是一个非常糟糕的行为,它让项目之间无法合作。比如项目 A 描述它要依赖 C 的 commit hash 5,项目 B 描述它依赖项目 C 的 commit hash 10,这也没问题。然后当 B 要引用 A 的时候,工具就懵逼了:你让我到底是选择 C 的 commit hash 5,还是 commit hash 10 呢? 于是工具只能把错误抛出来。</p> <p><strong>在描述文件里面指定依赖,是把所有的心智负担交给做依赖管理的人了。那个人当然会觉得难用!</strong></p> <p>假设我是项目 A 的维护者,我肯定要骂项目 B 的作者是傻逼。但是他听不到,也不知道自己很傻逼,我没法控制项目 B 的修改,于是只能默默去改自己的项目 A 的依赖,将 C 的版本依赖,改成一个既能兼容 commit hash 5,又能兼容 commit hash 10 的版本,好,我指定了一个大于版本 0.8 吧。然后再赞自己一句,真是太 TMD 机智了。</p> <p>过了几天,项目 C 升级了,它做了一个不兼容的改动,然后我的项目 A 想 update 一下自己的依赖,结果就跪了。于是又得重新默默处理 A 的依赖,顺便再问候 C 的女性长辈。</p> <p>一个投机取巧的处理方式是,把同一个包的不同版本给编译多份。A 依赖 C 的 commit hash 5,B 依赖 C 的 commit hash 10,A 依赖 B,那么,把 B 的版本 5 和 版本 10 分别都编译进 binary,问题就解决了。包的不同的版本,其实是不同的包。初看这个想法挺机智的,直到有一天遇到了这个问题:</p> <pre><code>func init() { http.Registe(&quot;/debug/requests&quot;) } </code></pre> <p>这是一个只能做一次的代码,但是 C 在版本 5 和 版本 10 里面分别都做了一次,然后就 panic 了。</p> <p><strong>这所有的一切都是不可协作的方式,每个人写自己的包的时候,没有考虑别人</strong>。提供灵活的规则去指定版本是不管用的。在描述文件里面指定依赖,是把所有的心智负担交给做依赖管理的人了。那个人当然会觉得难用! 嗯,重要的话重复几遍。所以 Go 觉得这个方式不可行。靠谱的方式应该是,由写包的人要遵循某个约定,剩下的版本选择交给工具去做。这个约定就是 -- 语义版本。</p> <p>语义版本才是 Go module 的核心。写包的人必须遵循语义版本,他写出来的包才能跟其它人协作。这是重要的开发哲学,<strong>心智负担从维护项目的人身上,转移到了各个包的开发者身上</strong>。我们看一下语义版本是什么。</p> <p><a href="https://semver.org/">https://semver.org/</a></p> <p>版本号是 MAJOR.MINOR.PATCH 的形式。当做了不兼容的 API 改动的时候,MAJOR 版本号就需要变。当做了能后向兼容的改动的时候,MINOR 版本号要变。对于前后完全兼容的版本,则只需要更改 PATCH 版本。</p> <p>最小版本选择,这也是 Go module 一个很有特点的地方。在主流工具做法里面,所有的包会指定自己的依赖,然后求解得到满足依赖的结果,它们会倾向使用最新的版本。然而 Go 不一样,它是选择满足条件的最小的版本。也就是没事不要瞎升级。选择最小的版本,会让约束更松,从而可选择而更多,兼容性更好。Go 没有像普通工具多做一个 lock 文件,然后锁定版本。这些都是在 Go 的工具链里面整个的。只有用户决定要升级某个包的时候,才会去升级。升级方式是这样:</p> <pre><code>GO111MODULE=on go get -u github.com/repo/pkg@version </code></pre> <p>一行命令它会自动更新相应的依赖。可以是 @version,也可以是 branch。如果是 branch 会默认使用该 branch 上面的最新的版本,没打版本,则是最新的那次提交。</p> <p>Go 是这样处理语义版本的,它假设 1.0 之后,是稳定的版本。如果没有打版本,它还是会把同一个包的不同版本,当前不同的包处理。打了版本之后,它会寻找一个兼容的版本。比如之前的例子,</p> <ul> <li>项目依赖 的 commit hash 5 跟 commmit hash 10,那么这个包的两个版本都会被编译进去</li> <li>如果依赖写成 v1.0.5 和 v1.0.10,这两版本是兼容的,则选择最小版本依赖 v1.0.5</li> <li>如果同时依赖是 v1.5.0 和 v1.10.0,最小的兼容版本是 v1.10.0。</li></ul> <p>注意,如果包不遵循语义版本会怎么样? 如果没有打版本,还是使用 commit hash,那么 Go module 也帮不上忙,又回到了 dep 那种时代,于是维护的人还是会觉得很痛苦。</p> <p>如果一个项目,明明是不兼容的改动,然而它的版本依然是 v1.1.1 写成 v1.1.2,那么造成的结果是升级就跪了。比如加了一个 API,那就应该 v1.1.1 就到 v1.2.0。这对所有暴露的 API 都需要慎重考虑, Go 语言在一开始就是遵循标准流程的。</p> <p>处理开发分支,有一个 replace 命令:</p> <pre><code>GO111MODULE=on go mod edit -replace github.com/repo/pkg=github.com/your-fork/pkg@version </code></pre> <p>它可以让原本依赖的 github.com/repo/pkg 包,实际使用 github.com/your-fork/pkg@version。</p> <p>实际使用过程中,说一个比较恶心的地方是 repo 间的相互引用成环。比如 github.com/pingcap/tidb-tools 要引用 github.com/pingcap/tidb,而 tidb 又要引用 tidb-tools/tidb-binlog/pump_client 就很麻烦,至今没想到好办法。</p> <p>Go module 并不是万能药。万能药是靠语义版本来保证的。语义版本的理念非常的好,如果大家都照做了,天下大同,相互协作就简单了。如果不遵循,则依然是混乱。关键还是要写代码的人对自己的严格要求。</p> www.zenlife.tk/go-module-semantic-version.md 2018-11-18T13:06:42Z 关于 Go1.11 module 和语义版本 2018-11-18T13:06:42Z