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>这一次讲谓词下推。谓词下推是相当重要的一个优化。比如 <code>select * from t1, t2 where t1.a &gt; 3 and t2.b &gt; 5</code> ,假设 t1 和 t2 都是 100 条数据。如果把 t1 和 t2 两个表做笛卡尔集了再过滤,我们要处理 10000 条数据,而如果先做过滤条件,那么数据量就会少很多。这就是谓词下推的作用,我们尽量把过滤条件下靠近叶子节点做,可以减少访问许多数据。</p> <p>谓词下推实现的接口函数大概是这样子:</p> <pre><code>func (p *baseLogicalPlan) PredicatePushDown(predicates []expression.Expression) ([]expression.Expression, LogicalPlan) </code></pre> <p>函数会处理当前的算子 p,假设在 p 上层要添加 predicates 这些过滤条件。函数返回的下推之后,还剩下的条件,以及生成的新 plan。这个函数会把能推的尽量往下推,推不下去了剩下的,加一个 Selection 条件在当前节点上面,变在新的 plan。比如说现在有条件 a > 3 AND b = 5 AND c &lt; d,其中 a > 3 和 b = 5 都推下去了,那剩下就接一个 c &lt; d 的 Selection。</p> <p>DataSource 算子很简单,会直接把过滤条件加入到 CopTask 里面。</p> <p>我们看一下 Join 算子是如何做谓词下推的。</p> <p>首先会做一个简化,将左外连接和右外连接转化为内连接。什么情况下外连接可以转内连接?</p> <p>左向外连接的结果集包括左表的所有行,而不仅仅是连接列所匹配的行。如果左表的某行在右表中没有匹配行,则在结果集右边补 NULL。谓词下推时,外连接转换为内连接的规则:如果我们知道接下来的的谓词条件一定会把包含 NULL 的行全部都过滤掉,那么做外连接就没意义了,可以直接改写成内连接。</p> <p>什么情况会过滤掉 NUll 呢?比如,某个谓词的表达式用 NULL 计算后会得到 false,比如说谓词里面用 OR 多个条件,其中有条件会过滤 NULL,又或者用 AND 条件连接,并且每个都是过滤 NULL 的。</p> <p>用 OR 连接起来的条件这个说法比较 low,有个高大上的术语叫析取范式 DNF (disjunctive normal form)。对应的还有合取范式 CNF (conjunctive normal form)。反正如果看到代码里面写 DNFCondition 之类的,知道术语会好理解一些。</p> <p>接下来,把所有条件全收集起来,然后区分哪些是 Join 的等值条件,哪些是 Join 需要用到的条件,哪些全部来自于左孩子,哪些全部来自于右孩子。</p> <p>区分开来之后,对于内连接,可以把左条件,和右条件,分别向左右孩子下推。等值条件和其它条件保留在当前的 Join 算子中,剩下的返回,也就是在这个 Join 上面接一个 Selection 节点作为新的 Plan 返回。</p> <p>谓词下推不能推过 MaxOneRow 和 Limit 节点。</p> <p>先 Limit N 行,然后再做 Selection 操作,跟先做 Selection 操作,再 Limit N 行得到的结果是不一样的。比如数据是 1 到 100,Limit 10 就是从 1 到 10,再 Select 大于 5 的,一个得到的是 1 到 10,另一个得到的是 5 到 15。MaxOneRow 也是同理,跟 Limit 1 效果一样。</p> <p>说一下构建 unique key 和 MaxOneRow 属性。这个不属于优化的步骤,但是优化过程需要用来这里的一些信息。</p> <p>收集关于唯一索引的信息。我们知道某些列,是主键或者唯一索引,这种情况一列不会在多个相同的值。构建 unique key 就是要将这个信息,从叶子节点,传递到 LogicalPlan 树上的所有节点,让每个节点都知道这些属性。</p> <p>对于 DataSource,对于主键列,和唯一索引列,值都具有唯一属性。注意处理 NULL,考虑列的 NotNull 标记,以及联合索引。</p> <p>对于 Projection,它的孩子中的唯一索引信息,再到它投影表达式里面用到的那些。比如 a b c 列的值都具备唯一属性,投影其中的 b 列,则输入仍然具有值唯一的属性。</p> <p>哪些节点会设置 MaxOneRow 信息?</p> <ul> <li>如果一个算子的孩子是 MaxOneRow 算子,那它就也带上 MaxOneRow 属性,而且会继续往上传递。</li> <li>如果 Limit 只有一列,它就可以设置 MaxOneRow 属性。</li> <li>如果是 Selection,并且过滤条件是 unique key 等于某个常量,或者 unique key 是某个关联列,那么它也具有 MaxOneRow 属性。</li> <li>对于 Join,如果它的左右孩子都是 MaxOneRow 属性,那 Join 出来仍然会有 MaxOneRow 属性。</li></ul> www.zenlife.tk/sql-optimizer4.md 2018-04-01T20:43:42Z SQL优化器庖丁解牛篇(四) 2018-04-01T20:43:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>表达式计算在一些地方会用到,比如 SQL 语句里面,<code>select * from t where a + 3 &gt; b</code>,其中的 <code>a + 3 &gt; b</code> 就是一个表达式。如何将表达式尽可能实现的高效呢?</p> <h2>AST 解释器</h2> <p>表达式解析出来,会变成一个 AST 树。遍历这个 AST 树进行解释,可以计算出表达式的值。</p> <pre><code>func eval(e Expr) { switch e { case AddExpr: return eval(e.left) + eval(e.right) case GTExpr: return eval(e.left) &gt; eval(e.right) case ConstExpr: return e } } </code></pre> <p>这种基于 AST 的树型解释器不太高效。原因是解释执行嘛,多了太多额外的操作。每遇到一个 Expr,都要判断它是哪种类型;对 AST 树遍历的过程;eval 函数调用这些开销。</p> <p>还要面临的一个问题是值的类型,加法的输入输出都是整型,而大于的输出是布尔型。可能就要用一种统一的格式来表示所有类型,比如</p> <pre><code>type Value { Kind I int B bool } </code></pre> <p>这种打包的通用类型在计算和分配的开销也会比原生类型大得多。</p> <h2>更快的解释</h2> <p>在前面的实现方式里面,我们不停在查看一个表达式是什么表达式,再决定调用什么计算方法。这相当于把 AST 当数据在看待。而如果能把 AST 当计算看待,整个 AST 是一个 executable 的东西,就可以降低 “查看是什么数据,再做什么操作” 这种访问模式的开销。</p> <p>具体做法,我们可以把表达式看成一个实现了 Eval 接口的东西。只要调用 <code>expr.Eval()</code>,就可以得到计算的结果了。</p> <pre><code>type Eval interface { EvalInt() int64 EvalBool() bool } type ConstExpr struct { v int64 } func (e ConstExpr) EvalInt() int64 { return e.v } func (e AddExpr) EvalInt() int64 { a := e.left.EvalInt() b := e.right.EvalInt() return a + b } func (e GTExpr) EvalBool() bool { a := e.left.EvalInt() b := e.right.EvalInt() return a &gt; b } </code></pre> <p>这里用了 EvalInt 和 EvalBool 是处理通用类型问题。注意跟之前的区别,表达式不是当数据看待的,而是当作计算看待。只要把表达式构造出来了,它就可以 Eval 了。</p> <p>但是这种方式性能仍然不是很好,为什么呢?因为虚函数调用的开销太大了。比如执行一个加法表达式,调用虚函数对左右孩子计算 <code>e.left.EvalInt()</code> 和 <code>e.right.EvalInt()</code> 的过程,远大于 <code>a + b</code> 加法运算本身。</p> <h2>字节码和栈计算器</h2> <p>字节码可以把 Expr 的计算操作 “打平”,变成一些指令。最常见的,基于栈的计算器:计算左孩子,将左孩子的计算结果进栈;计算右孩子,将右孩子的计算结果进栈;将栈顶的两个数据进行操作,结果放回栈里面。</p> <pre><code> for pc := 0; pc &lt; len(bc); pc++ { switch bc[pc] { case Add: stk[top] = stk[top] + stk[top-1] case GT: stk[top] = stk[top] &gt; stk[top-1] case Const: stk[top] = v } } </code></pre> <p>我测试了一下字节码模式,发现比上面一种实现略快一些。对比 <code>3 + 5 &lt; 42</code>,执行 10 万遍:</p> <pre><code>使用执行基于 AST 的快速解释:2.153914ms 使用字节码方式:1.145872ms </code></pre> <p>那么字节码解释器的开销在哪里呢?进栈和出栈太多的数据交换是比较低效的。尤其是这里要走内存,而不能用到寄存器。</p> <p>寄存器操作速度在 1ns 数量级的,而内存不带cache至少慢100倍。我们看一个简单的例子:</p> <pre><code>var x int for i := 0; i &lt; 1000000; i++ { x++ } x是全局变量时:1.585067ms x是局部变量时:301.885µs </code></pre> <p>因为全局变量没法优化,必须从内存读取和写回内存。而局部变量直接放寄存器里面了。</p> <p>还有字节码的指令分发,浪费的指令也高于操作本身。switch case 以及取字节码和修改 pc 这些。</p> <h2>CodeGen 与 JIT</h2> <p>如果把上面的字节码,用原生指令实现,性能上就可以有数量级的提升。直接执行 Go 代码的 <code>3 + 5 &lt; 42</code> 10万次要用多久?只需要 28.78µs。</p> <p>正统 JIT 的做法,应该是拿 AST,去生成相应的操作指令,可以利用一些三方库比如 LLVM。但是 Go 语言调用 LLVM 太蛋疼了,需要走 cgo,用 Go 调的开销太大。用 LLVM 做 JIT 的另一个缺点是代码调试的友好性,中间生成的 IR 有 bug 对调试之类的是不太方便的。</p> <p>其实最理想的形式,是宿主语言实现了 eval,<a href="eval-as-universal-machine.md">调用 eval 就可以得到原生性能,就像我之前说的</a>。可惜这只是个奢求。</p> <p>另一个方法是做 CodeGen。我们把 AST 往反方向做,用它生成宿主语言的代码,再去编译到原生,然后用某种方式 load。</p> <p>最后在这里放一个好玩的例子,抛专引玉。</p> <pre><code>const code = `package main import &quot;fmt&quot; func F() { fmt.Println(&quot;hello world&quot;) }` func main() { ioutil.WriteFile(&quot;/tmp/test.go&quot;, []byte(code), 0644) cmd := exec.Command(&quot;go&quot;, &quot;build&quot;, &quot;-buildmode=plugin&quot;, &quot;-o&quot;, &quot;/tmp/a.so&quot;, &quot;/tmp/test.go&quot;) cmd.Run() p, _ := plugin.Open(&quot;/tmp/a.so&quot;) sym, _ := p.Lookup(&quot;F&quot;) sym.(func())() } </code></pre> www.zenlife.tk/expression-implementation.md 2018-04-10T09:30:42Z 表达式计算实现模式 2018-04-10T09:30:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>每隔一定时间,我总会接触一门新的语言。Erlang 算是一门很古老的语言了,对我却是一门新的语言。稍微看了一些,还没实际写过代码。这门语言给我的感觉非常不错,真是有点相见恨晚!</p> <p>Erlang 是一门函数式语言,状态不可变。在这一点相比 lisp,属于更加严格偏向 haskell 的那一派。当然函数式语言共同的优点都是一致的。虽然很多人谈到 Erlang 的特点就只联想到 Actor 模型,其实呢,函数式范式这一点,也是很有特色的(这也不可避免地导致了这门语言的小众)。</p> <p>语法方面。Erlang 受到了 Prolog 较大影响,它的 list 是写作 <code>[a, b, c]</code> 这样子的。然而 Shen 语言也是受了到 Prolog 影响的,接触过 Shen 之后再接触到 Erlang,这就让我有一种很熟习的亲切感了。Erlang 里面变量和符号也是用的类似的约定,用大小表示变量,小写表示 atom。写一个最简单的 Erlang 代码,大概长这样子:</p> <pre><code>fact(0) -&gt; 1; fact(N) -&gt; N * fact(N-1). </code></pre> <p>Erlang 有强大的模式匹配,在试过 Shen 语言之后,觉得模式匹配太好用了,支持模式匹配会让代码清爽很多。scheme 之类的没有在语言内置,用各种库和宏的方式来提供,是有点不好的。</p> <p>数据结构方面,只有 list 和 tuple 两种。这跟 lisp 的哲学很类似,语言也是受了 lisp 那边一些影响的。record 可以通过 tuple 模拟出来,就有点类似 lisp 里面使用宏。Erlang 是 lisp2 的。看过了那么多之后,对于 lisp1 还是 lisp2 早已不那么纠结了。无论 lisp1 或者 lisp2,我都不太介意。</p> <p>类型系统。Erlang 是动态类型语言,不会像 haskell 或者 ml 那个流派的做法,没有强制要求类型安全,而是更加倾向于 lisp。这也很对我的味口。值得一提的是,我<a href="typed-lisp.md">之前的一些思考</a>,认为给 lisp 这类动态语言实现类型的正确做法,Erlang 所采用的正是其中一个方向。Erlang 允许子类型,比较弱化的类型系统,类型只是一种约束,检查代码安全的手段。</p> <p>Actor 模型。在并发编程,算是为数不多的几个靠谱的做法。Go 使用的 CSP,而 Erlang 使用的 Actor。在 Actor 里面是每个 Process 都绑定了一个邮箱,然后每个 Process 都可以往其它的邮箱里面发消息,这就强制使用异步的操作模式。用 Go 可以很容易模拟也 Erlang 这套行为,而反之不行,说明 Go 的灵活性更好一点。在 Go 里面指针,内存这些都没有隔离,并且还可以回到锁的那一套机制。Erlang 是函数式的无状态,更加纯粹一点。</p> <p>库和生态,这才是真正让我觉得相见恨晚的理由!我没有看到哪个函数式语言,在工业上或者说工程上能够比较靠谱的。要么都是太学术了,只是教学型语言。要么太小众了,库和生态都不行。捣腾来捣腾去,除了写写玩具的解释器或者编译器,啥都干不了。OTP 有那么多的代码,资源都很完善。自己实现一门语言,就那么几块:编译器,运行时,以及标准库。最难搞的就是库的生态,这个东西靠一个人的力量根本弄不来。最后都只是自娱自乐。就拿 chez 编译器说,这个性能真的牛逼的一踏糊涂,但是库和生态不行。</p> <p>说说 Erlang 用的虚拟机,是一个叫做 beam 的东西,跟 JVM 扮演的角色差不多。beam 据说是基于 WAM (warren abstract machine) 的,我稍微去了解了一点点 WAM,它其实是一个方便做逻辑编程的虚拟机,是给 prolog 用的。而 Erlang 跟 prolog 的编程模式已经相去甚远了,所以我怀疑实际上这里面可能魔改得有点多。有趣的信息是 beam 虚拟机是一个基于寄存器的虚拟机。另外,beam 是可以编译到原生指令来优化性能的,有一个 HiPE 的项目做这个,目前已经默认包含在官方里面了。</p> <p>runtime 方面的东西,目前了解得还不深入。不过我觉得可玩性要比 Go 高很多。主要是有虚拟机这一层,天然地把一些问题给分层了。就比如说,Go 的 goroutine 就要考虑分段栈的东西,而到了 Erlang 里面,每个 Process 虚拟机绑定自己的内存区域就可以了。垃圾回收也有影响,由于 Process 天然隔离了,所以 Erlang 里面每个 Process 可以自己做自己的 GC 工作,不影响全局。而 Go 的是全局的 GC,要获取低延迟就要投入更多的优化了。还有在低延迟以及软实时在调度层面的考量,Erlang 也是更加重视的。每个 Process 每次可能运行一定的指令数,过了就会被切换走了,而 Go 是在函数调用时才有机会触发切换,非抢占式的。</p> <p>最后说说好玩的。一个之前的同事,就基于 Erlang 的生态系统,做了一个 <a href="http://xlambda.com/">kapok 语言</a>。Erlang 的编译设计分层很好,它定义了一个 Core Erlang 层。Core Erlang 是比较类似于 lisp 的。在这上面可以做一些工作。kapok 也是一个 lisp,我看它好像更多的是建立在 Erlang 的 AST 上面的。而我受 Shen 语言的影响多一点,觉得可以在 Core Erlang 之上,先做一个类似 Shen 语言里面 klambda 那一层。也就是,把 Erlang 的生态当作 lisp 的 runtime 使用,来构建 klambda 语言。然而再在 klambda 之上,去构造自己想要的语言。</p> www.zenlife.tk/erlang.md 2018-04-28T01:30:42Z 相见恨晚的 Erlang 2018-04-28T01:30:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>Go 语言的 context 包里面有个 Context 接口。</p> <pre><code>type Context interface { Deadline() (deadline time.Time, ok bool) Done() &lt;-chan struct{} Err() error Value(key interface{}) interface{} } </code></pre> <p>同时还提供了一个 WithCancel 方法:</p> <pre><code>func WithCancel(parent Context) (ctx Context, cancel CancelFunc) </code></pre> <p>WithCancel 接受一个 Context 并返回一个 Context,返回的 ctx 里面的 Done() 函数会返回一个 chan,当 cancel 调用时,这个 chan 会被关闭。还有一个特性,<strong>当 parent 的 Done() 关闭的时候,孩子 ctx 的 Done() 也会被关闭</strong>。</p> <p>这个特性很重要,实际使用中,WithCancel 让调用者之间构成了一颗树型结构,调用者一般是在不同 goroutine。如果调用父亲 context 的 cancel,就可以将孩子的 Done() 的 chan 同时关掉。因为 Go 语言里面的 goroutine 是协程,这个机制成了一个标准的控制 goroutine 之间作业交互的手段,在孩子 goroutine 里面一般会监听父亲的 cancel 信号:</p> <pre><code>select { case &lt;-ctx.Done(): return } </code></pre> <p>那么我说坑爹的 context.WithCancel 是为什么呢? 我们来看一下它是怎么实现的。</p> <p>关键点是在于,怎么样实现父亲的 Done() 关闭时,孩子的 Done() 也被关闭。</p> <p>一种方式是,父亲和孩子使用同一个 channel。这样子关闭父亲跟关闭孩子就是同一个 channel。那这个做法有什么问题呢?父母和孩子都关闭同一个 channel,它会不会调用多次?同一个 channel 关闭多次就 panic 了,当然这个可以绕过去。另外一个问题,假设父亲和孩子都是在同一个 channel,那么许多 goroutine 都将作用在这同一个 channel 上面,实现里面就是一个很粗粒度的锁了。前面我也提到过<a href="go-context.md">使用 context 时的问题</a>。Go 是不是这么实现的呢? 不是。WithCancel 的说明里面写得很清楚了: WithCancel returns a copy of parent with a new Done channel.</p> <p>另一种方式,一个很挫的方式,专门起一个 goroutine 来监听,如果发现父亲关掉了,那么就关掉孩子:</p> <pre><code>var parent, child chan struct{} go func() { select { case &lt;-parent: close(child) } } </code></pre> <p>感觉这样实现太重了?标准实现到底是不是这样子的呢。</p> <pre><code> func WithCancel(parent Context) (ctx Context, cancel CancelFunc) { c := newCancelCtx(parent) propagateCancel(parent, &amp;c) return &amp;c, func() { c.cancel(true, Canceled) } } </code></pre> <p>再看看这个关键的 propagateCancel 函数:</p> <pre><code>func propagateCancel(parent Context, child canceler) { if parent.Done() == nil { return // 优化:父亲 Done 为空,所以不需要处理父亲关闭时,孩子关闭 } if p, ok := parentCancelCtx(parent); ok { ... } else { // 亮瞎我的狗眼了,真的是开 goroutine 实现的。 go func() { select { case &lt;-parent.Done(): child.cancel(false, parent.Err()) case &lt;-child.Done(): } }() } } </code></pre> <p>中间有一个判断 parentCancelCtx 函数走另一块逻辑是做什么的呢?它是一个特殊的优化的实现,父亲 context 里面维护一个 map,记录自己的孩子。添加孩子的时候就把孩子加到这个 map 里面。这样,在父亲 cancel 的时候,把这个 map 里面的孩子也 cancel 掉,就可以实现关闭父亲时自动关闭孩子了,不需要起 goroutine。</p> <p>遗憾的是,这个优化只认识标准库里面的几个 context,也就是:</p> <pre><code>func parentCancelCtx(parent Context) (*cancelCtx, bool) { for { switch c := parent.(type) { case *cancelCtx: // 标准库的 WithCancel 返回的 context return c, true case *timerCtx: // 标准库的 WithTimeout 返回的 context return &amp;c.cancelCtx, true case *valueCtx: // 标准库的 WithValue 返回的 context parent = c.Context default: return nil, false } } } </code></pre> <p>我发现这个问题是在我们项目代码中,火焰图抓到 propagateCancel 函数的比例有点高。我在在代码里面弄了一个自定义的 Context 实现,它是这样子:</p> <pre><code>type Backoffer struct { context.Context ... } </code></pre> <p>拿它当 context 使用时,每次 WithCancel 就会后台绑定起一个 goroutine。虽然 Go 语言的 goroutine 是很轻量的,但是 cheap but not free 呀!</p> <p>结论就是,WithCancel 对标准库的几个 context 实现做了特殊优化,不会开启 goroutine,然而对用户实现的 context 非常不友好,会额外开启 goroutine,这太坑爹了。</p> www.zenlife.tk/with-cancel.md 2018-05-05T01:30:42Z Go 语言坑爹的 WithCancel 2018-05-05T01:30:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>遇到这个问题是这样的,<code>select * from t where a &lt; 5 and a &gt; 5</code> 我期望它能直接推导出来,这是一个空集,因为 <code>a &lt; 5 and a &gt; 5</code> 恒为假。结果呢?它给我搞出来了一个全表扫!这不就傻逼了。</p> <p>嗯,扫了一眼我们的代码,开始没看太懂。于是决定自己想想怎么做。比如我们有下面这一系列的条件:</p> <p>[= a 1] [= a c] [> b c] [= b d] [> c d] [= d f]</p> <p>那么我们需要做的是,把 <code>a = 1</code> 这个常量表达式,不停地拿到集合里面去做替换,替换过程中,如果有新的常量表达式生成,可以记录下来。<code>[= a c]</code> 这个替换掉之后,就会生成一个 <code>c = 1</code>,继续用它执行下去,可以得出 <code>[&gt; b 1]</code> 和 <code>[&gt; 1 d]</code>,像 <code>[= d f]</code> 这种消除不掉的,就继续保留下来。</p> <p>那么这个算法的基本框架是这样子的,已知的常量表达式 <code>[= a 1]</code> 这种,放到一个叫做 <code>Rules</code> 的集合里面,而未知的待替换的集合,我们叫 <code>Input</code>,拿 <code>Rules</code> 里面的每一条,去 <code>Input</code> 里面做替换,过程中如果有新的 <code>Rule</code> 生成,则放到 <code>Rules</code> 集合里面。直到 <code>Rules</code> 集合的所有规则都使用过了,没有更多的替换时,算法结束。</p> <p>为了体现 lisp 的优越性,我决定用 shen 语言写写这段代码(装个逼)。</p> <pre><code>(define constant-propagate0 [] Input -&gt; Input [Rule | Rules] Input -&gt; (let Pair (apply-subst Rule Input [] Rules) Output (hd Pair) Rules (tl Pair) (constant-propagate0 Rules Output))) </code></pre> <p>这是一个递归函数。第一行,如果 <code>Rules</code> 为空了,算法就结束了。第二行,取第一条 Rule,将它应用到 <code>Input</code> 集合所有成员 <code>(apply-subst Rule Input [] Rules)</code>,它会生成新的 Rules 和新的输入(这里叫 <code>Output</code> 了),递归继续做 <code>constant-propagate0</code>。</p> <pre><code>(define apply-subst Rule [] Output Rules -&gt; (cons [Rule | Output] Rules) [= Var Const] [[= Var Var2] | Input] Output Rules -&gt; (apply-subst [= Var Const] Input Output [[= Var2 Const] | Rules]) [= Var Const] [[= Var1 Var] | Input] Output Rules -&gt; (apply-subst [= Var Const] Input Output [[= Var1 Const] | Rules]) [= Var Const] [[OP Var Var2] | Input] Output Rules -&gt; (apply-subst [= Var Const] Input [[OP Const Var2] | Output] Rules) [= Var Const] [[OP Var1 Var] | Input] Output Rules -&gt; (apply-subst [= Var Const] Input [[OP Var1 Const] | Output] Rules) Rule [H | Input] Output Rules -&gt; (apply-subst Rule Input [H | Output] Rules)) </code></pre> <p><code>apply-subst Rule Input</code> 函数,第三个第四个参数,<code>Output</code> 和 <code>Rules</code> 是为了尾递归才写成这样的,它做的事情就是用 Rule 去跟 Input 里面的各个比较,新的结果会放到 <code>Output</code>,如果有新规则生成会放到 <code>Rules</code>。</p> <p>好了,在 <a href="http://www.shenlanguage.org/">shen 语言</a> 里面(随便找个实现,比如 <a href="https://github.com/tiancaiamao/shen-go">shen-go</a>),敲进去这两函数,然而执行</p> <pre><code>(constant-propagate0 [[= a 1]] [[= a c] [&gt; b c] [= b d] [&gt; c d] [= d f]]) </code></pre> <p>会得到</p> <pre><code>[[= c 1] [&gt; b 1] [= b d] [&gt; 1 d] [= d f] [= a 1]] </code></pre> <p>其实这个算法是借鉴类型推导里面,一个叫做算法W 的做法,简化的版本(好吧,我根本不知道常量传播标准做法应该是怎么做的)。</p> <p>有几个问题,这里只处理了 <code>var = const</code> 这种表达式的推导,这是最简单的情况。其实归纳下来有好几种更复杂的场景。</p> <p><code>var1 = var2</code> 和 <code>var &gt; const</code></p> <p>这种情况其实不难,继续套用上面的算法框架仍然是能够处理的。比如我们只把 <code>var &gt; const</code> 这一类,作为 <code>Rules</code> 集合,把 <code>var1 = var2</code> 当作 <code>Input</code> 集合,拿规则集里面每条规则,过一遍 Input,就可以推导出更准确的 var 范围。</p> <p>像之前的 [= a b] [= b c] [> a 5] [&lt; c 3] ,先从 <code>Rules</code> 里面取出 [> a 5],将它应用到 [= a b] 上面,推出 [> b 5],新的 [> b 5] 被加到 <code>Rules</code> 里面,再应用它到 [= b c] 时,会推出 [> c 5],丢到 <code>Rules</code> 里面... 最后规则里面会出现矛盾 [&lt; c 3] [> c 5],这种场景我们就可以判定 false 了。</p> <p>比较难处理的,是 <code>var1 &gt; var2</code> 这种场景的推导。当 <code>var &gt; const</code> 作用于它时,结果不那么直观。比如 <code>a &gt; b</code>并且 <code>a &gt; 3</code> ,这个得不出啥信息。但 <code>a &gt; b</code> <code>b &gt; 3</code>,这个可以推出 <code>a &gt; 3</code>。也是可以丢到规则集里面继续利用的。主要麻烦在场景复杂了一些。</p> <p>目前就想到这些吧。说说一个同事的脑洞。</p> <ol> <li> <p>如果把所有等号两边的点,都当做图上面的节点,然而 <code>a &lt; b</code> 就构造一条从 a 到 b 的有向边。比如 <code>[&lt; a b]</code> <code>[&gt; a 5]</code> <code>[&lt; b 4]</code>,会构造出 <code>a -&gt; b</code> <code>b -&gt; 4</code> <code>5 -&gt; a</code>,如果我们再手动用 <code>[&lt; 4 5]</code> 构造一条,<code>4 -&gt; 5</code>,那么这个图就会成环了。也就是说,通过这样子构造一个图,然后检测成环,可以判断表达式是否是恒假的。</p></li> <li> <p>如果出现更复杂的 <code>a - b &lt; 3</code> <code>b - c &lt; 5</code> 这种表达式,两者相加可以推出 <code>a - c &lt; 8</code>。继续假想一个图,从 a 到 b 画一条出边,边的权值为 3,含义就是 a 到 b 节点的距离最少是 3。然后 b 到 c 画一条出边,边的权值为 5。把所有这种表达式都构造成图,那么求任意两节点之间的最短路径,就是两个变量的差值。比如 a 到 c 最短路径是 8,就是 <code>a - c &lt; 8</code>。如果再把常量引入,有可能把各变量的一些范围信息推出来。</p></li></ol> <p>暂时还没有更多的想法,这哥们好喜欢图。好晚,不知道自己在想啥了,明天先好好改代码 bug 吧,不脑洞,实用为主。</p> www.zenlife.tk/constant-propagate.md 2018-05-28T01:24:42Z 常量传播 2018-05-28T01:24:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <h2>事务优化</h2> <p>ACID 事务支持是 TiDB 的基础,也是核心竞争力。做 AP 强调性能,即使不保证强一致性至少还能用。TP 里面,做核心的交易业务,不保证事务谁敢用?涉及钱的事情,事务没做好谁敢用?虽说是 TiDB 号称是 HTAP 的数据库,如果打分,事务这块必须是 1,其它的亮点做的好是在后面加 0。如果 1 没做好,那就 0 分了。</p> <p>TiDB 的事务模型是基于 Percolator 做的。模型方面能不能优化,去掉中心化时钟? 这个模型会需要从 pd 取一个全局的时间戳,这需要走一次网络交互,会增加事务延迟。设计之初我们假定,同机房内部网络来回一次就 0.5ms,拿一次 timestamp 几乎全落在 1ms 以内。但是后来发现,还是有很多场景这个迟延是很难严格保证的。比如之前我写过受到机器负载的影响,Go 在 runtime 的调度耗时,再比如,跨机房了,网络天然慢了怎么办?那么,能否在事务模型上修改,不去取 timestamp 呢?</p> <p>锁冲突的处理策略能否优化呢? 现在 TiDB 的冲突处理其实是乐观锁策略,大家都会往 TiKV 存储里面写数据,直到发现冲突了,会自己 abort 掉。实际上,这种 abort 的代价是非常高的,在冲突严重的场景十分低效,相当于冲突时做了很多事情,后面这些事情不仅白做了,而且还要额外的撤销操作:写了一半的数据和锁需要清理掉。那么,我们可不可以做一个排队机制呢? 让可能冲突的事务都去排队,减少乐观锁的冲突开销。在分布式的场景下,如何识别所有节点在哪些 key 上面冲突呢?</p> <p>大小事务优先级怎么做。我们假设事务有些很大,有些比较小。是不是会发生,越大的事务越可能出现冲突概率越高?这种情况下,大的事务会不会多次的失败重试,失败重试?另外,会不会大的事务锁住大量的 key,导致小的事务受影响。到底怎么样做才是更公平的呢,是否应该设置合理的大小事务的优先级策略?</p> <p>隔离级别怎么做?当前 TiDB 的默认的事务隔离级别是 SI,如果想做 SSI 需要使用 select for update 语句。有没有别的方式实现?默认想做成 SSI 该如何实现,会引入哪些性能影响?还有,假设是 RC 又可以实现什么优化? 还有一些更细分的隔离级别是否需要加入考虑? 这些都是值得探讨的。</p> <p>事务为什么需要两阶段提交,一阶段提交行不行?我们是否可以优化数据的分布,将事务所涉及的资源,全部都调度到一个物理的机器上面,然后执行一阶段提交呢。`整个事务实现的执行链很长,性能上还有哪些优化能做?举个例子,我曾经发现一个普通的 SQL 语句, update 带索引的列,竟然花掉了近 20ms。首先它是既需要更新索引又需要更新数据的。然后,一个普通的 update 语言,它可能需要先读后写。读需要先向 pd 拿 timestamp,走一次网络,然后向 TiKV 的 raft leader读,走一次网络。再做写的时候,做两阶段提交要走两次网络。而 raft 那边请求又还涉及,多节点的消息同步网络和写磁盘开销。突然想到,一条SQL语句,从发送给数据库到返回给客户端,整个执行流程的所有细节,是一个很好面试题。</p> <p>再比如多版本数据的 GC 策略。数据 GC 是事务必须考虑的。在 MVCC 之上,不停的写入,同个条记录就会有许多版本。这些旧版本是需要清理掉的。同时,还有残留的锁也是要清理的。之前就出现过很多问题。像数据版本太多,会导致读的速度变慢,因为 rocksdb 那边要顺着 MVCC 不同版本的数据扫,直接找到需要的那个。如果版本多了,扫的 key 就变多,性能就下降。删除数据是很影响性能的,极端的场景,不停地做插入和删除,GC 的速度跟不上怎么办? 清锁的细节如何处理,异步清锁的操作。并发 GC 是否安全? 遇到大事务要读老的数据,GC 应该如何处理,如果清理,读的事务执行就要出错。不清理,如果一直有大事务会把 GC 卡住怎么办?</p> <p>细节很多很多,反正都是做事务优化的人必须考虑到的。更重要的事情,是事务出了 bug 怎么办。上层业务写错了,该重试没重试,或者不该重试却重试了,把错误的数据写进去,或者数据索引不一致了。又或者,下层存储把数据写丢了,却告诉调用者成功了。做事务需要非常强大和全面的分析能力,抗压能力。因为几乎所有的问题,都可以引发事务的问题,这边做事务相关,又称背锅侠。</p> <h2>如何做资源隔离</h2> <p>这也是比较大的一个话题。TiDB 号称是一个 HTAP 混合的数据库。混合嘛,即做 AP 又做 TP,那么就有用户问了,同时在 TP 的集群上面,直接跑 AP 做数据分析,会不会影响 TP 的响应呢? 那我只能如实回答,当然会呀! TiDB 是有一定的分析能力,但是目前阶段还没有一些纯粹 AP 的引擎强大。另外,AP 会吃掉机器大量的资源,同时在执行的线上业务肯定要受到影响。</p> <p>所以问题来了,怎么样调度,使得 AP 和 TP 互不影响呢?或者至少影响尽量地小。TiDB 是无状态的,可以把节点实例独立出来,AP 和 TP 分开。在 TiKV 那边,就没法在物理层面划分了。我们能不能给不同的事务类型,加上不同的优先级和资源分配策略。SQL 一个特别复杂的东西,一条 SQL 语句与另一条 SQL 语句之间,需要的计算资源几乎不可同日而语。到底需要占用多少资源,这个有没有办法量化?它会读多少条数据,写多少磁盘,吃多少 CPU 和 IO,内存占用是怎么样的,这个能否预测和计算? 如果能够预测出来,这是一个消耗资源的请求,那么能不能根据当前系统负载去做一些处理,比如限制它使用的资源量,内存不够先 dump 出去。</p> <p>数据库上云是一个战略方向,好,问题来了,多租户该怎么做。我们能不能做到用户无感知,能不能只部署一套了,按 namespace 卖? 这就需要最好是懂容器,k8s 的人交流探讨。</p> <h2>JIT 怎么做</h2> <p>如何让生成的查询执行得更快呢? 查询优化是一个很大的领域,虽然 TiDB 已经做了不少工作了,但是还有更多的事情其实是空白的。就比如 JIT,直接将查询计划,生成到原生代码,这是很多数据库都已经实现了的。</p> <p>我们要解决一个,如何让 Go 和 Rust 共用一份 JIT 的代码。Go 带 runtime 的语言,中间如何调用 C 或者其它语言的库。</p> <p>涉及到的重构也会有点多,volcano 模型需要在代码层面做哪些调整,推和拉的不同模式会如何影响到执行效率,做向量化在 TP 里面的收益如何。</p> <p>这中间的路线该如何走,需不需要使用 LLVM 呢。这都是很有意思并且具有挑战的事情。这里面自然也涉及了不少汇编和编译器方面的东西,所以,做编译器的人,也是可以转数据库的。</p> <h2>分析定位问题的能力</h2> <p>不是开玩笑,这真的是很有挑战的事情,而且对综合素质要求相当高,如果展开来说,是一个很大的话题。</p> <p>监控,性能,日志,这都是很重要的环节,千万不能小瞧的环节。</p> <p>怎么样做监控,怎么样分析性能,怎么样去发现问题的手段。很多情况下,程序的日志是拿不到的,那能够依赖的就只有监控了。除了直观的系统本身的监控,还有一些额外的信息,比如关于机器情况。网络,系统调用,锁,上下文切换,TCP的协议栈,内核调参各种问题。perf,火焰图,Go 语言本身的相关工具等等。程序崩溃了,需要收集哪些信息。dmsg 怎么看,OOM 问题如何查,gdb 去调 core 文件等等。</p> <p>每次出错,其实都要去反思和总结,查问题的时候根据什么线索,做了什么推理,最后是用什么方式查到问题的。如果走了弯路,下一次如何避免这种弯路。这个过程中,哪些地方卡住过,缺了什么工具? 监控,日志,有哪些是该记录没有记录的。整个过程到最后要去复盘,去文档化,养成一种思维的习惯。</p> <p>在这里,我们遇到过 <a href="https://pingcap.com/blog/2017-09-08-rocksdbbug/">rocksdb 的问题</a>,我们遇到过 grpc 的问题,所有三方库,都不可能是绝对稳定的,甚至操作系统和编译器,都有可能遇到问题。生产部署时,只推荐特定的环境,为什么?是因为我们验证过。像某些特定文件系统的 bug 导致的问题我们也被坑过。</p> <p>有些很难查的 bug,处理这种问题的能力非常重要。比如只有 error 日志 &quot;fatal: morestack on g0&quot;,进程 hang 住,也不退出,也不打印栈,但是所有的 goroutine 都 block 住了。这是一个线上遇到的问题,但是概率特别低,如何抓到它?遇到这少量的线索时怎么处理呢,第一时间要检测到这种情况的发生,监控 log,进程不退出就需要 kill 掉并优先恢复服务。接着是不是应该分析最近改动了啥,如果怀疑编译器的问题,放不同版本编译出来的二进制做对比测试。如果不容易复现,可否考虑抓到线上的流量,放到模拟的环境里面回放? 最终这个定位是在某个版本 Go 编译器自身的<a href="https://github.com/golang/go/issues/23360">问题</a>。处理 panic 的 recovery 的时候,继续在里面做分配,调度器所在的 g0 崩溃了,然而没有让整个进程退出,无法调度了,于是 hang 住。</p> <p>再举一个例子,系统慢了,如何定位为什么慢? 是整体慢还是部分的语句执行慢,是系统负载过高,还是某一项问题,比如 IO,或者写盘。如果是一条 SQL 语句慢,是语句本身复杂还是有热点,或者是代码优化的有问题。生成的查询计划是怎么样的,执行过程中有没有受到什么干扰。还有,如何从海量的信息里面迅速定位出来有用的那些。我们是不是可以做个 tracing 工具,将整个系统的每个步骤执行耗时记录下来,便于定位问题。关键的点是在于,工具和方法论,这是解决问题的手段。</p> <p>另外,到高手阶段,大多都是 printf 的。如果还过于依赖单步调试... 那就呵呵哒。开个玩笑,这边有个同事,我们戏称亚洲第一 rust 程序员,让他review一遍代码,就是开启O4编译(一脸认真)。在大脑里面建模,把代码拆成一小块一小块的,然后人脑跑一遍,训练强大的分析能力,这才是正确的方向。</p> <p>分析定位问题在这边是很有挑战的,真的。这个系统足够复杂。出问题时,涉及到的东西足够底层。</p> <h2>分布式的执行器</h2> <p>让 TiKV 完全负载存储,让 TiDB 完全负责 SQL 层的计算,逻辑上没什么毛病,这也是最开始的做法。然而真的把数据从 TiKV 进程全捞上来,到在 TiDB 进程里面做计算,这个数据走网络开销是很大的,并且计算的过程无法过滤掉不必要的数据。</p> <p>移动数据不如移动计算,所以我们做了 coprocessor,做下推,把一部分计算下推到 TiKV 节点上面去做。TiKV 是分布式的,于是计算量就分摊到整个集群节点上面了。逻辑上,coprocessor 还是属于 TiDB 层面的,而物理上,它又在 TiKV 里面实现。下推以后,TiKV 那边计算与存储耦合得有点多了,倒不是指概念的耦合,而是资源分配。下推的计算量会影响到存储,grpc 网络也是一个很吃 CPU 的部分。</p> <p>可是下推只是解决了一部分的问题。我们需要的,是一个真正的分布式的执行器层。</p> <p>下推之后,还需要在上层做一些聚合的计算,现在操作还只能够在单个 TiDB 节点上面完成。单节点上面资源有限,比如说容易把内存打爆,或者如果有多节点,资源还可以达到更好的利用。面对实际要解决的问题:一个大的 Join 查询,把机器内存打暴了怎么办? Go 语言是一个带 GC 的语言。这 GC 语言里面做内存控制,也是一个相对麻烦事情。</p> <p>分布式执行器,需要把纯粹 SQL 生成的执行计划,跟计划的执行(哦,有点绕)拆开来。这个执行计划应该是分布式的,可以被拆到其它节点上去并行执行,最后将结果汇总并返回,把多核或者说多线程的思维,进一步分散到多机器去做。但是这个引入的复杂度就不是一点了,因为跨了机器,机器挂了怎么办,木桶效最慢的一环影响整体速度怎么处理,哪些是能拆的,哪些不能拆,以及怎么拆,细节都很多。</p> <p>这是一个复杂的分布式计算框架,跟 map reduce 不一样的地方,这里不是分片了暴力扫数据,shuffle 然后汇总的简单计算模型。这里可能会利用索引,利用统计信息,数据库领域几十年优化的经验,会跟分布式计算紧密地结合在一起。</p> <p>把执行器逻辑层的单节点扩到多节点,开发真正的分布式执行器层,这也是一个有挑战并且很大的事情,路漫漫其修远兮。</p> <h2>优化器,统计信息,Join reorder</h2> <p>都列到这一坨了。优化器这边,从最开始非常 naive 的基于规则的优化,到后面有了基于代价的优化。再然后统计信息也做得越来越完善,越来越准确。</p> <p>现在优化器这边比较稳定下来了,统计信息方面也支持自动的做 analyze,并且根据查询反馈去动态的更新。抛开学术不谈,至少在工程层面,这些问题绝对是处于技术前沿了的。</p> <p>所以这就完了?不,挑战才刚开始!这里有两个问题核心,一个是数据量估算的准不估,另一个是代价算的对不对。统计信息是估算准不准的问题,而代价对不对就更难衡量。CPU 磁盘IO 内存,网络,到底分别占多少比重呢?比如一个逆序扫磁盘,跟顺序扫盘,代价就不是一个级别。比如一个场景走索引需要两次网络,而扫表要扫的区域是N条记录,N多大的时候代价是小于走网络的? 其实这些很多都是拍脑袋拍的,如何让玄学调参尽量地少一点。优化器能不能更智能一些,把一些写得比较弱智的子查询,直接转化得跟DBA优化过的一样高效。</p> <p>还有就是 join reorder 一块盲区,目前没有根据代价来算。有时候为了达到最佳效果,还要手动去调整顺序。</p> <h2>数据分布和调度</h2> <p>我们专门有一个子系统,负责集群的数据分布和调度,它就是 pd。外界往往对 pd 了解的最少,其实它是非常关键的。</p> <p>先说数据分布。存储在逻辑上是一个大的 kv 数据库,table 和 索引都会映射到一部分的 kv 范围。按照 kv 的 range,整个存储被划分为一个一个的 region。逻辑层面的 region,跟物理层面的节点,会形成一个映射关系。pd 做的事情,就是管理这个映射关系。假设一张表很大的情况下,它会涉及好多个 region,region 最终会散布在各个节点上面,于是请求就分散到各个节点上了。如果表很小呢?它会只包含一个 region,这个表被频繁访问,那这个 region 对就的节点就可能变成热点了。</p> <p>数据分布是动态的,由 pd 调度。我们希望 region 在节点上的分布要尽量地均匀,于是流量也会分散开。但实际上呢? 不同 region 被访问的模式其实是不一样的。数据有冷有热,部分 region 可能被频繁在访问,而部分则很少被访问到。那么,调度就不能单考虑均匀,还得照顾到热点,将热点打散。</p> <p>由于 region 分布不同,不同机器的磁盘空间占用可能不一样,这又是一个考虑因素。如果疯狂的往某个机器上调度,那个机器的盘也许就被写爆了,这又是要考虑到的点。</p> <p>还有,要考虑到 raft group 的安全性,每个 region 默认是三副本的。那么,就要考虑单节点 down 机,或者整机架,甚至是机房的故障, region 的副本就需要交错着放。出个题目,这个可靠性的概率怎么算? 节点挂掉时,还有需要被副本之类的操作。加节点也是涉及调度。</p> <p>单考虑一个因素时,问题并不复杂。但是要考虑到许多种策略时,pd 那边数据分布和调度的事情就变成了一个比较麻烦的问题。如果评估某个策略和算法是有效的?如果模拟真实的情况,去验证一个新的策略?</p> <h2>存储和性能</h2> <p>存储是一直要优化的方向,对性能的追求没有极致。从最早尝试使用 hbase 到后来决定自研分布式存储 TiKV。从最早的每一行的一个列作为一条 kv 记录,然后改到行存,每一行作为一条 kv 记录,都是在存储模型方面做过的调整和探索。</p> <p>还有针对业务特点的各种细化,比如实现事务时,要写锁记录,要写 MVCC 数据。其实对不同模型的请求,写操作的特征是很不一样的。锁数据的存在时间很短,写数据成功后马上就删除,而 MVCC 数据要一直保存。于是我们利用 rocksdb 的 column family,把锁和数据放到不同的 column family,并且对应设置不同的 compaction 策略,调整不同的参数。早期都是把性能几倍几十倍的往上提升的。</p> <p>业务一些细节还有很多,比如我们切分 region 按大小来,是否就合理。同样大小 64M 的 region,存放数据,跟存放索引,其实记录条数相差还是比较大的,那么同样是扫一个 region 工作量就会相差较大,这又会让多个 worker 分配工作量时划分不太均匀。比如一个 index scan,读数据读完了,读索引还是慢悠悠的做,那就会有不必要的等待。另外,不同 region 的大小又会有什么影响呢? 跟数据打散的程度会有什么关联性? 还有,不同大小对于 snapshot 或者对于 pd 的心跳方面会存在什么影响?</p> <p>LSM 的删除,compaction 的代价还是挺大的,抖动也会比较影响。rocksdb 里面的各种细节参数多如牛毛,这也是需要大牛来&quot;玄学调参&quot;的,都是要求对里面的实现细节都了如指掌。</p> <p>对于新技术的调研,这边也没有落下。就说说写放大,在 MVCC 那一层,要写入不同的版本,MVCC 是一次放大。到了 raft 那边,多副本的存在,会将写再放大几倍。再到 rocksdb 存储,其本身又是有 kv 的版本的。删除操作并不是物理删除,而是追加写一个版本。后台的 compaction 之前的“高效”写入的副作用了,尤其是要一层一层的做下去,这里面是巨大的放大。TiDB 里面设置了事务大小限制的,部分原因就是上层的事务被放大很多倍,大块写入很快就会把磁盘的 IO 耗尽。那么,如果能把 LSM 的 key 跟 value 分离开来,在 LSM 里面只存 key,写放大就会大大的减少,badger 就是这么做的,还有 rocksdb 的新 feature blobdb 也有这个。我们会测试各种不同的写入大小,64,128,256 等等,各种不同的读写模式,顺序的,随机的,去跟 rocksdb 对比,结果各有优劣吧。那么,能否让大的 kv,我们用 kv 分离的方式存,而对小的 kv 我们仍然是整体写 LSM?</p> <p>我们一直都还没把 raft log 的存储独立出来。其实 raft log 存储的业务特点是很明显的,就是日志和快照。日志就是一个队列,并且是没有修改操作的。rocksdb 并不是特别优化的场景,是否可以订制化这种业务模型的存储,从而提升性能呢?</p> <hr /> <p>TiDB 招人很难。这篇打个<a href="https://pingcap.com/recruit-cn/">招骋广告</a>。</p> <p>说了这么多(发现一扯淡就收不住了),有没有动心了? 快到碗里来(内推 mkl@pingcap.com)。</p> www.zenlife.tk/challenge-at-pingcap.md 2018-06-02T11:38:42Z 在 PingCAP 的一些技术挑战 2018-06-02T11:38:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>有同事说我老是讲哲学,不是在讲道理。好吧,那我认命了。今天再摆一个观点,认同则已,不认同我也不去解释道理了,当它是哲学吧。今天要讲的是简单,正确性,和性能的取舍。这是程序员很容易遇到的一个选择题,我选择简单。</p> <p>我们知道网上有一个著名的观点,叫做 worse is better。这个观点,其实就是新泽西佬说 MIT 佬,也就是搞 unix 那帮人,为了简单,什么都不顾了,居然还做成了,真是世风日下!准确地说,其实就是代表了“简单”最后胜利了,worse is better 是一种吐糟,同时也是这个胜利的体现。</p> <p>什么,连正确性都不要了? 反对者总会拿着这个点抨击,无限放大的说事。抛开剂量谈毒性,都是耍流氓。首先,并不是所有场景都会遇到简单和正确性的冲突,请不要断章取义成只要简单就故意放弃正确性。如果一个人无法完全把算法实现正确,那是水平不足,还没资格去谈简单和正确性的&quot;哲学&quot;问题。然后呢,我再换一个方式表述一下:一个程序能否做到完全没有任何 bug?理论上,可以。那实际上呢?不可能。好,这些有 bug 的程序你还用不用?操作系统你用不用?数据库你用不用?编译器你用不用?这里面都是有数不清的 bug 的。怎么样,还那么强调正确性么?又或者这个时候开始变得虚伪了?</p> <p>有一个高大上的算法能屠龙,然而正确地实现它需要花一年。有另外一种简单做法能保证 99.999 的情况下正确,即使出错的情况下,影响也不算严重,关键是它只需要搞一个月。那当然选择快糙猛啦。否则搞一年搞到黄花菜都凉了,龙早就被对手搞死,没龙可屠了。快糙猛细分还是有好多场景的,不要拿反例说事。我说的是资源受限情况下理性的选择,那些瞎JB搞自己坑自己的的,根本不是在体现取舍,只是在体现他们 SB。</p> <p>复杂是正确性的敌人。复杂的东西很难做正确。这里需要解释一下。简单的英文单词是 simple,simple 的对立面是 complex。这个单词跟 easy 不同,easy 的对面是 hard。simple 的东西往往是 easy 的。所以选择的 simple 的方案更可能保证 correct,尽量把事情往 simple 去做。simple made easy。选择简单,就是提前去避免复杂性,进而会获得正确性。没有矛盾,选择简单的人往往会把事情做对。假设你有一个同事,他追求的不是简单,他总是把代码写得很绕。有两种可能:一种是他水平低,另一种是他喜欢花式炫技。他觉得为了用上最高端的东西,宁愿复杂一些。反正不管是哪一种,最终都会留下一堆堆的 bug。等他走了,他写出来的那坨都是没法维护的。我见过把代码写得很绕的人,也有炫技的,但是, SB 居多;而我见过能把代码写得非常简单的人,全部是大师手笔。</p> <p>有本书叫 unix 痛恨者手册,很推荐读一读。其中反对 unix 的重要的两股党派就是 lisp 党和 GUI 党。熟习我的人都知道,我其实是 lisp 派,但是客观公正地,个人觉得 unix 哲学真的好用:keep it simple, stupid。</p> <p>我超喜欢简单的事物。</p> <p>举个 raft 和 paxos 的例子。etcd 之后,很少有项目选择 paxos 而不是 raft 的。为啥呢?因为 raft 简单,好理解,更容易实现正确。paxos 复杂,实现都会有各自的细节修改,更难去证明这些细节的正确性。</p> <p>再说说 tidb 和 cockroach。前些日子 tidb 的 star 数开始超越 cockroach 了。cockroach 是一个值得尊敬的竞争对手,我很佩服他们的文档做的很好,技术研究也很深入,代码执行力也强。cockroach 比我们起步早一年,而发展到现在我认为 tidb 的产品成熟度更高一点。重要的原因就是,cockroach 的技术选型更复杂。cockroach 整体都是 P2P 的,而 tidb 的调度系统是中心化的,中心化的调度肯定比去中心化做起来简单。tidb 选择的是全局时钟,而 cockroach 使用的 HLC,前者也是更简单的。tidb 更清晰地分层了,存储层在 tikv,而 cockroach 只用一个进程处理从 SQL 层到存储层。简单的价值就是项目可以快速推进,去客户的真实场景实战打磨。当一边还在思考一些酷炫的方案时,另一边已经身经百战了。这个例子也许不太恰当,但市场就是这样,并不是所有公司都像 google 家全球只需要一个数据库,中心化的调度去支撑 200 节点没有任何毛病。盲目只追求技术,而不是考虑简单实用,就是耍流氓,浪费人力物力。</p> <p>一个很常见的错误,就是在简单和性能之间,选择了性能。简单的东西往往是更好优化的。因为简单,优化空间大。为了优化把代码搞得巨复杂,是不值得的。接下来我将解释这些。</p> <p>第一个例子是Go 的 goroutine 和 channel,对比复杂的锁机制。channel 本身是要基于锁实现的,从这个纯粹的角度,它不可能比锁做得更高效。但是用过 goroutine 和 channel 之后,大家再也不会想回去基于锁做并发编程了。因为这是一个更简单的模型,我们可以在更高层次的抽象上,去解决实际问题,bug 更少,生活质量更高。一个写了十年 C艹 的程序员,去写一个高并发的复杂网络编程,可能不见得会比一个新手学了三个月的 Go 写出来的程序高效。Go 的性能不会比 C艹高,而且 runtime 也比较 heavy。原因是在于 Go 更简单的并发模型,更少的心智负担,这就是简单的力量。</p> <p>再说说 code review 的时候的例子。有次我还在扣一些编程技巧上面的代码细节的时候,一个同事让我注意把关注放在大局,可谓一语惊醒梦中人。这里的代码细节对运行时的性能影响,不会超过 1%。相比起来,在优化器那边,生成更好的执行计划,可能至少是几倍几十倍的区别。另一次是我们有个比较复杂的对象,每次访问网络会构造。有个同事想加个 reset 方法,我则建议别重用,每次直接构造。因为相比网络访问的开销,这里一点对象分配是可以忽略。重用会涉及对象大量的状态调整,还涉及里面 goroutine 的释放和重分配,引起的代码复杂度太高了。过于关注性能,却没注意到真正会影响性能的点,很容易一叶障目。</p> <p>再一个是之前我举过的例子,简单数据结构 PK 复杂数据结构。我曾经做一道题目是&lt;圣经&gt;中的各个单词出现的次数,手写一个二叉排序树,还是递归版本。跟标准库红黑树实现的对比,惊讶地发现看起来一点不优化的做法,居然比标准库要快!然后我看到了 rob pike 写的 5 个编程原则:</p> <blockquote> <p>原则 3. 花哨的算法在 n 比较小时效率通常比较糟糕,而 n 通常是比较小的,并且这些算法有一个很大的常数。除非你确定 n在变大,否则不要用花哨的算法。(即便 n 不变大,也要先遵循第 2 个原则。)</p> <p>原则 4. 相对于朴素的算法来说,花哨的算法更容易出现Bug,更难调试。尽量使用朴素的算法和数据结构。</p></blockquote> <p>心有戚戚焉。只是当我经历了很多代码之后,才明白这个简单的道理。尽量选择简单的做法,不要过早优化,除非发现它真的是热点才优化,把精力放在应该关注的点上。不然,可能赢得了战役,却输掉了战争。</p> <p>只是理解起来需要一些悟性,或者说直觉。有些人天生会有非常敏锐的技术“直觉”,真的很让人嫉妒。另一些人要经历很多训练,写过很多的代码,积累更多的经验,才会获得那么一点点直觉。抛开其它因素不谈,只说技术,王垠就是那种直觉敏锐的一类。有时候我走了很多弯路,回头再看,却发现不过是他已经得到过的结论,只是当时无法理解。伟大的 unix 之父,伟大的 C 语言和 Go 语言的发明者,这些闪耀着光辉的大师,告诉我们该追求简单。如果无法理解大师走过的路,只会把历史的错误一遍一遍地重犯。当然还有更多的人,永远也不会理解......他们会觉得我在扯淡 ╮(╯▽╰)╭</p> <p><strong>选择性能最终得不到性能。选择正确性最终难以保证正确性。唯有选择简单的人,会做对的事情。</strong></p> www.zenlife.tk/simple-correct-performance.md 2018-06-09T01:18:42Z 简单,正确性和性能 2018-06-09T01:18:42Z 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