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>C 太底层了,写代码真的不舒服。不爽的地方之一是要手动管理内存,另一个是对象信息缺失。我们看一个例子,假设要实现一个 hash 表。</p> <pre><code>struct HashEntry { int key; int value; }; </code></pre> <p>如果我们希望是一个更通用的 hash 表。那么 hash 表的 key 和 value 应该是 <code>void*</code> 类型。一旦 key 是一个指针以后,我们就必须考虑内存管理。如果我们是一个浅拷贝语义,那么根据谁分配谁释放的原则,这块内存就应该是由外面去释放的。然而这里立马会遇到一个问题:如果 hashEntry 里面把 key 浅拷贝了一份,外面把那块内存释放了,这里就会出现悬挂指针(dangling pointer)。所以这里不能是一个浅拷贝语义。</p> <p>假设我们是一个深拷贝语义,会面临什么问题? 首先,对象的递归拷贝性能和实现上都是不靠谱的。需要所有的对象里面引用的对象,都实现一个clone的方法。其次是释放,有clone就要有释放,于是释放函数也要全部有。要释放两次,外面一次,在 hash 析构的时候还要做一次,把 entry 给释放掉,如果忘记了释放,就泄漏了。</p> <p>所以这里我们最好是一个move语义。一旦把 key value 放到 hash 里面之后,内存管理的归属就转到 hash 里面了。外部如果还持有,那也只是一个引用。我说过 rust 心智负担太重,从这个角度看是有一点不公正的。作用域/生命期/ownship,问题摆在那里,不管有没有制造那么多概念,手动管内存还是得考虑的。</p> <p>但是问题并没有完,如果 key 是简单的对象,比如 <code>char*</code>,我们只需要 free 就好了。而如果是复杂对象,它里面还引用其它的东西,那就需要有一个析构函数。最终这个 hash 会很丑:</p> <pre><code>typedef bool (*eq_func) (void*, void*); typedef int (*hash_func) (void*); typedef void (*free_func) (void*); void new_hash(eq_func, hash_func, free_func) </code></pre> <p>丑的原因是什么呢?根源之一是对象信息缺失,一个通用对象必须是 <code>void*</code> ,如何做 key 判等,如何得到一个 hash 值,如何释放对象,这些都必须额外提供。</p> <p>好,请今天的主角出场:fat pointer !</p> <p>fat pointer是用来解决对象信息问题的。它的基本原理是这样,分配一个对象出去时,故意在返回地址的前一个地址预留一个空间,也就是多分配一个指针的空间,在那里面放上对象类型信息。对象类型信息有点像 vtable。</p> <pre><code>var alloc(size_t data_size) { struct Header* head = calloc(1, sizeof(struct Header) + data_size); head-&gt;type = type; return ((var)head) + sizeof(struct Header); } </code></pre> <p>注意,使用 fat pointer 之后释放的时候,就不能直接释放原指针了,要把 free 的位置前移一个。这些东西可以封装起来,提供比较友好的库,<a href="http://libcello.org/">Cello</a> 已经这么干了。</p> <p>fat pointer 只是加入了额外的对象信息,但是并不会干扰普通的 C 代码,并不是强制使用,这一点还是很 neat 的。有了对象信息之后,实现通用的 hash 表,就友好多了。因为 <code>eq_func</code>,<code>hash_func</code>,<code>free_func</code> 那一堆东西都可以跟对象绑定到一起,少了很多维护负担。</p> <p>有了对象信息之后,在这个基础之上实现 GC 是不是一个好主意呢?我认为不是。在 C 里面实现 GC ,获取 <code>scan_root</code> 是比较 trick 的。另外,GC 需要对象信息。而如果在 fat pointer 对象里面混入了原生 C 对象,在 scan 遍历对象信息时就会 panic。像无论是 GC,或者是 coroutine,我认为这些东西最好丢到一个虚拟机层去做。但是真这么做也会涉及到另一个问题,托管内存跟原生内存的交互。</p> <p>托管内存跟原生内存的交互,只在需要的时候使用托管内存,不使用就不为性能买单。理想很美好,现实很骨感。</p> <p>这里需要一条约束:原生内存不能以任何形式去引用到托管内存。因为托管内存随时可能被 GC 掉,如果原生内存里面引用了,就可能出现悬挂指针了。我只发现了一门语言真正把这个事情做对了,就是 lua。做对是做对了,然而交互的时候 API 真的还是不太爽。shen-go 暂时不敢用 C 重写,担忧的点就包括这些。但是很多底层的东西,像threaded code,fixnum tagging用 Go 都是做不了的。</p> <p>Anyway,fat pointer 提供对象信息,这个想法是挺不错的。Cello 库使用基本功能,也是挺不错的。</p> www.zenlife.tk/fat-pointer.md 2018-01-07T11:14:42Z 在 C 里面使用 fat pointer 2018-01-07T11:14:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>刚刚给shen-go打上了v0.2版。从v0.1到v0.2主要做的是一些性能优化相关的事情,分享一些数据。</p> <p>最早的时候我实现了一个klambda解释器,那时跑shen的测试需要165s完成。</p> <p>在发布v0.1版的时候,实现了编译到bytecode,跑测试时间大概是25s的样子,从纯的解释器到未优化过的bytecode,大概是快了6倍多。</p> <p>接着就是v0.1到v0.2版做的事情,<a href="shen-go-optimize.md">前面有提到过</a>:</p> <p>vm的大幅改进,主要是将环境拆成堆上和栈上两部分,尽量地避免在堆上分配对象。加上vm那边一些细节上的优化,这块做了之后时间缩短到了16s。</p> <p>对hash函数做了 peephole optimizations,时间缩短到15.3s。</p> <p>接着对variable? integer? 等几个函数做 peephole optimizations 之后,时间缩短到13.9s。</p> <p>调整了 symbol 的表示,不再是string而直接记一个offset,比较就可以不用string比较。做了这个之后时间是12.5s。</p> <p>优化了函数调用,从map实现改到了直接数组offset获取,最终是11.6s。</p> <p>let的优化没做,peephole optimization还可以再彻底一些,感觉得如果做到极致,估计能就刚进10s的样子。</p> <p>threaded code 和 fixnum tagging 我尝试了一下,在Go语言里面都做不了。如果是换成 C 语言写vm,可以做这些优化,并且内存管理也做的更激进一些,我推测bytecode方式的极限可能在 7-8s。</p> <p>顺便分享一些 shen 在其它语言下实现的数据。</p> <p>shen-c 是完全基于解释器实现的,太挫了就不想说它了。</p> <p>shen-scheme 在 chibi-schem 下的实现,大概是22s的级别。这也是一个字节码实现,还是 C 语言做的,只比我 bytecode 未优化的时候略快一点,也算是挺挫的了。无节操的推测一下可能是scheme的异常处理机制拖累了它。</p> <p>shen-elisp 是编译到 emacs lisp 的 bytecode,速度大概在30秒刚出头。elisp 不算一门正儿八经的编程语言啦。</p> <p>shen-jvm 是直接编译到 JVM 的,速度大概在 4.几秒的样子。</p> <p>shen-cl 官方维护的版本,通过 common lisp 编译到 native 的实现,速度大概也是同样量级,4.5s。比 shen-jvm 慢一点点。</p> <p>shen-chez,这就是王垠说的世界上最牛的编译器,1.6s!还真是一个秒天秒地的版本,我算是领教了。</p> <p>F#看论坛上给的结果,好像都是10几秒的版本吧,Truffle 好像更慢一点。我没具体去测。不过如果编译到某个平台的虚拟机,比如.Net或者Graal,这结果还真是挺挫的。</p> <p>结论就是,bytecode大概就10-20s的量级了,做得非常有节操会进10s内。而JVM虚拟机这种带了JIT或者common lisp到native的大概就4s的级别。最牛B的chez吊打其它。</p> <p>shen-go 在基于 bytecode 实现里面已经最快的了。基本做不下去。弃坑弃坑</p> <p>供参考,以上。</p> <p>(最后,数据都有时效性,只是当下的比较,说不定哪个升级下变牛逼了,就不准确了。</p> <p>所以嘛,想知道准确的性能测试结果,这东西最好自己做)</p> www.zenlife.tk/shen-go-v0.2.md 2018-01-08T01:06:42Z shen-go v0.2发布:从165s优化到11s 2018-01-08T01:06:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>switch 在 Go 的编译器里面几乎没做过什么优化,性能还是挺低下的。</p> <p>写成这样子:</p> <pre><code>switch c { case 0: case 1: case 2: case 3: ... } </code></pre> <p>跟直接写成</p> <pre><code>if c == 1 { } else if c == 2 { } else if c == 3 { } </code></pre> <p>就没啥太大区别。</p> <p>也不能责怪编译器蠢,毕竟 Go 语言里面还要支持像 string 类型,支持表达式,以及像这种</p> <pre><code>switch c.(type) </code></pre> <p>C 语言里面 switch 语句是会优化成跳转表的,比较高效。</p> <p>可以考虑换种写法,</p> <pre><code>var jumpTable []func(){} // 把各个case要做的事情做成函数放到一张表里 f := jumpTable[c] // 直接通过case id找到对应的函数 f() // 并跳转去执行 </code></pre> <p>我测试了一下 Go 的 switch 到底有多么低效,case 稍多,放了32个。</p> <p>https://gist.github.com/tiancaiamao/28fd53ff9b29eaac30f84b4ba04e2e7e</p> <p>对比的结果是:</p> <pre><code>switch cost: 70.476µs jumt table cost: 9.065µs </code></pre> <p>大部分时候没有写那么多switch case的需求,但是有一个场景还是会用到,就是 interpreter。在 C 里面可以做 threaded code,在 Go 里面做不了。我还是希望做出 Go 能达到的最佳优化,于是把 shen-go 的指令分发从 <a href="https://github.com/tiancaiamao/shen-go/commit/92ae53e4555a09a215e9546ade466d682195906e#diff-89570c464637c8d662a375fdd8f47b90L145">switch方式</a>切换到了 <a href="https://github.com/tiancaiamao/shen-go/commit/92ae53e4555a09a215e9546ade466d682195906e#diff-89570c464637c8d662a375fdd8f47b90R149">jump table</a>。</p> <p>结果很今人失望,性能反而下降了。分析原因,主要是 swtich 的写法可以充分利用到函数内联,比如</p> <pre><code>switch c { case opPrimCall: primCall() case opPop: stackPop() } </code></pre> <p>这里面的primCall和stackPop这些都是可以inline的,而jump table由于函数地址是动态获取的,利用不到编译器的inline优化。</p> <pre><code>vm.code[vm.pc](vm) </code></pre> <p>相当于节省了switch定位具体哪一条操作的开销,却引入了额外的函数调用开销。</p> <p>有没有什么方法能够既不使用低效的 switch,又能充分利用到函数内联呢?</p> www.zenlife.tk/go-switch-statement.md 2018-01-13T21:24:42Z switch在Go语言的性能 2018-01-13T21:24:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>打算写一个系列,讲一下 SQL 优化方面的东西。这一篇先整理一下要写内容。整个 SQL 优化器是一个很大的话题,不可能一二篇博客就能说得清楚的。所以这个系列得一点一点的写。</p> <p>从输入一条 SQL 语句,到这条语句的执行,要经历很多阶段:将 SQL 解析成抽象语法树(AST),将 AST 变换到内部表示(IR)。然后优化器的输入就是 IR,它将生成最优的查询计划(Plan),然后会变成具体的执行器(Executor),里面有许多的算子。最的执行会获取数据,再给用户返回结果。</p> <p>这个系列要专注的是从 IR 到生成 Plan 的过程。从大的方面,优化过程可以分为逻辑优化和物理优化两个部分。逻辑优化主要是基于规则的优化(RBO),物理优化会具体选择某一个算子具体的实现,比如 Join 用哪一种,读数据用哪一种,这里可能需要用到一些统计信息,决定哪一种方式代价最低,所以是基于代价的优化(CBO)。</p> <p>在逻辑优化的步骤,我会挑一些具体的例子讲。比如,列裁剪,min/max消除,非关联子查询转 Join,谓词下推,投影消除,topN下推等等。</p> <p>在物理优化里面,主要会写一下求最优解的算法,代价计算用到的公式,统计信息会提及一点,然后还打算写一下 join reorder。</p> <p>执行器的部分不太涉及,如果所有内容都写话题就太大了,该是厚厚的一本书要讲的东西。感觉还是需要对执行器有一点点基础了解,像几种不同的 Join 的实现方式,像子查询的 Apply 算子,还有聚合 Aggregate 这些,完全不懂也是无法知道 SQL 到底是怎么被执行的。</p> <p>好了,introduction 写完了,等<a href="sql-optimizer2.md">下一篇</a>再进入正题。</p> www.zenlife.tk/sql-optimizer1.md 2018-02-25T19:53:42Z SQL优化器庖丁解牛篇(一) 2018-02-25T19:53:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <h2>逻辑算子</h2> <p>发现对于零基础的读者,如果不先讲算子,后面都没法讲。所以还是先写一点。</p> <ul> <li>DataSource 这个就是数据源,也就是表。 <code>select * from t</code> 里面的 t</li> <li>Selection 选择,就是 <code>select xxx from t where xx = 5</code> 里面的 where 过滤条件条件</li> <li>Projection 投影,也就是 <code>select c from t</code> 里面的列 c</li> <li>Join 连接, <code>select xx from t1, t2 where t1.c = t2.c</code> 就是把 t1 t2 两个表做 join,这个连接条件一个简单的等值连接。join 有好多种,内关联,左关联,右关联,全关联...</li></ul> <p>选择,投影,连接(SPJ) 是最基本的算子。</p> <p>select b from t1, t2 where t1.c = t2.c and t1.a > 5</p> <p>变成逻辑查询计划之后,t1 t2 对应的 DataSource,负责将数据捞上来。上面接个 Join,将两个表的结果按 t1.c = t2.c 连接,再按 t1.a > 5 做一个 Selection 过滤,最后将 b 列投影。下图是未经优化的直接表示:</p> <p><img src="../static/spj.png" alt /></p> <ul> <li>Sort 就是 <code>select xx from xx order by</code> 里面的 order by,排序。无序的数据,通过这个算子之后,向父结点输出有序的数据。</li> <li>Aggregation 就是 <code>select sum(xx) from xx group by yy</code> 的 group by yy,按某些列分组。分组之后,可能带一些聚合操作,比如 Max/Min/Sum/Count/Average 等,这个例子里面是一个 sum。</li> <li>Apply 这个是用来做子查询的,后面再讲它的作用。</li></ul> <p>逻辑优化做的事情,就是把 SQL 转成由逻辑算子构成的查询计划,这颗树的结构会被变来变去,使得执行时代价尽量的小。</p> <p>物理算子跟逻辑算子的不同之处,在于一个逻辑算子可能对于多种物理算子的实现,比如 Join 的实现,可以用 NestLoop Join,可以用 HashJoin,可以用 MergeSort Join等。比如 Aggregation,可以用 Hash 或者排序后分组不同的做法,比如 DataSource 可以直接扫表,也可以利用索引读数据。</p> <h2>列裁剪</h2> <p>列裁剪的思想是这样子的:对于用不上的列,没有必要读取它们的数据,去浪费无谓的IO。</p> <p>比如说表 t 里面有 a b c d 四列。</p> <p>select a from t where b > 5</p> <p>这个查询里面明显只有 a b 两列被用到了,所以 c d 的数据是不需要读取的。那么 Selection 算子用到 b 列,下面接一个 DataSource 用到 a b 两列,剩下 c 和 d 都可以裁剪掉,DataSource 读数据时不需要将它们读进来。</p> <p>算法是自顶向下地把算子过一遍。某个结点需要用到的列,等于它自己需要用到的列,加上它的父亲结点需要用到的列,将没用到的裁掉。从上到下的结点,需要用到的列越来越多。</p> <p>主要影响的Projection,DataSource,Aggregation,因为它们跟列更相关。Projection 里面干掉用不上的列。DataSource 里面裁剪掉不需要使用的列。</p> <p>Aggregation 涉及哪些列?group by 用到的列,以及聚合函数里面用到的列。比如 <code>select avg(a), sum(b) from t group by c d</code> ,这里面 group by 用到的 c 和 d,聚合函数用到的 a 和 b。</p> <p>Selection 就是看它父亲要哪些列,然后它自己的条件里面要用到哪些列。Sort 就看 order by 里面用到了哪些列。Join 里面,把 join 条件用到的各种列都要加进去。</p> <p>通过列裁剪这一步操作之后,查询计划里面各个算子,只会记录下它实际需要用到的那些列。<a href="sql-optimizer3.md">下一篇</a>敬请期待!</p> www.zenlife.tk/sql-optimizer2.md 2018-02-27T01:48:42Z SQL优化器庖丁解牛篇(二) 2018-02-27T01:48:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <h2>最大最小消除</h2> <p>select min(id) from t</p> <p>换一种写法,可以变成</p> <p>select id from t order by id desc limit 1</p> <p>严格意义上,这并不算标准的逻辑优化里面需要做的事情。那么这个改动有什么意义呢?</p> <p>前一个语句,生成执行计划,是一个 TableScan 上面接一个 Aggregation,也就是这是一个全表扫描的操作。对于后一个语句,TableScan + Sort + Limit,在某些情况,比如 id 是主键或者是存在索引,数据本身是有序的, Sort 就可以消除,最终变成 TableScan 或者 IndexLookUp 加 Limit,这样子就不需要全表扫了,读到第一条数据就得到结果!全表扫跟只查一条数据,这可是天壤之别。也许这一点点写法上的区别,就是几分钟甚至更长,跟毫秒级响应的差距。</p> <p>最大最小消除,做的事情就是由 SQL 优化器“自动”地做这个变换。比如说,</p> <p>select max(id) from t</p> <p>生成的查询树会被转换成下面这种:</p> <p>select max(id) from (select id from t order by id desc limit 1 where id is not null) t</p> <p>min也是类似:</p> <p>select min(id) from t</p> <p>select min(id) from (select id from t order by id limit 1 where id is not null) t</p> <p>注意这只是其中一个变换规则,经过这步变换之后,还会执行其它变换。所以中间生成的算子,还有可能在其它变换里面被继续修改掉。总之,这是一个挺好的例子,说明逻辑优化做的事情:对这颗树,通过一系列规则,做各种变换,得到一个最优的逻辑查询计划。</p> <h2>投影消除</h2> <p>投影消除把不必要的 Projection 算子给消除掉。那么,什么情况下,投影算子是可消除的呢?</p> <p>首先,如果 Projection 算子要投影的列,跟它的孩子结点的输出列,是一模一样的,那么投影就是一个废操作,可以干掉。比如说 select a,b from t 在表 t 里面就正好就是 a b 两列,那就没必要 TableScan 上面做一次 Projection 了。</p> <p>然后,Projection 下面孩子结点又是一个 Projection 这种,那孩子结点这次投影操作就没意义,可以干掉。像 Projection(A) -> Projection(A,B,C) 只需要保留 Projection(A) 就够了。</p> <p>类似的,在投影消除步骤里,Aggregation 也算某种意义上的投影操作,因为从这个结点出来的都是列的概念了。因此在 Aggregation -> Projection,这个 Projection 也是可以干掉的。</p> <p>这个代码应该怎么写呢?</p> <pre><code>func eliminate(p Plan, canEliminate bool) { 对 p 的每个孩子,递归地调用 eliminate 如果 p 是 Project 如果 canEliminate 为真 消除 p 如果 p 的孩子的输出列,跟 p 的输出列相同,消除 p } </code></pre> <p>注意 canEliminate 那个参数,它是代表是否处于一个可被消除的“上下文”里面。比如 Projection(A) -> Projection(A, B, C) 或者 Aggregation -> Projection 递归调用到孩子结点 Projection 时,该 Projection 就处理一个 canEliminate 的上下文。</p> <p>说白了就是,一个 Projection 结点是否可消除,一方面由它父结点告诉它,它是否是一个冗余的 Projection 操作,另一方面是由它自己和孩子结点的输入列做比较,看是否是可消除的。</p> <p><a href="sql-optimizer4.md">下一篇</a></p> www.zenlife.tk/sql-optimizer3.md 2018-03-01T01:56:42Z SQL优化器庖丁解牛篇(三) 2018-03-01T01:56:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>之前觉得,语言的巴别塔应该通过建立一层公共抽象层去消除,所以我是支持 .NET/CLR 这类事物的。如果不管用什么语言,写出来的库,都可以相互调用,天下大同,挺美好的。</p> <p>最近有了一点新的感悟:不需要VM,只要eval就够了。这种感悟就类似于突然理解了 &quot;lisp不需要机器&quot; 这句话。</p> <p>先解释什么是可运行。真正的硬件,只懂得0和1,所以只有生成 native binary 了才是可运行的。如果实现了一个解释器,然后去解释脚本语言,虽然这个脚本语言不是二进制的,但它还是可以算作可运行。对于一门编译型语言,源代码不能算是可运行的,因为不经过编译,它并不能直接跑。函数是可运行的,因为只要调用它,它就被执行了。</p> <p>什么是编译呢?编译就是把不可运行的东西,转化成可运行的。比如 C 或者 Go 的源代码,都是不可运行的,需要经过编译,生成二进制文件。其实编译并不是一个绝对的概念,我觉得只要把不可运行的东西,翻译到能够被运行,这个过程在某种程度上都算作编译。</p> <p><strong>写编译器很难。解释器性能差。VM是折中方案。</strong></p> <p>这里不得不说的,就是在软件开发里面,分层的重要性。“计算机科学领域的任何问题都可以通过增加一个简介的中间层来解决”。合理分层可以控制复杂度。比如说 VM + jit 的方案,挺复杂的,但是复杂性度上升是平滑的,这一点很重要!</p> <p>通过 VM 这一层,屏蔽更下面的细节。对上面只要暴露字节码,而下层实现怎么做优化,就变成另外的问题了,上层是不用关心的。每一层只解决特定的问题,事情被拆小之后,就简单多了。坏处当然也不是没有。过多的层,也会引入混乱。比如本来希望在VM层能实现天下大同,可实际上各个语言自己撸自己的一套,白白浪费了很多人力物力。想想这个世界上有多少的 VM 实现?</p> <p><strong>引入 VM 之后,下一个要考虑的就是优化性能了。</strong></p> <p>VM 层引入的抽象,就是性能损失的根源。因为在某个语言中实现 VM,没法直接利用硬件那一层:寄存器分配,内存次数访问,缓存友好性,实际执行的指令条数...</p> <pre><code>func (v *VM) add() { v.stk[v.sp-1] = v.stk[v.sp-1] + v.stk[v.sp] } </code></pre> <p>在 VM 里面一条虚拟的指令,生成出来变成了这么多的机器指令:</p> <pre><code>MOVQ &quot;&quot;.VM+16(SP), AX MOVQ 24(AX), CX LEAQ -1(CX), DX MOVQ 8(AX), BX MOVQ (AX), AX CMPQ DX, BX JCC 68 MOVQ -8(AX)(CX*8), DX CMPQ CX, BX JCC 68 MOVQ (AX)(CX*8), BX ADDQ BX, DX MOVQ DX, -8(AX)(CX*8) MOVQ (SP), BP ADDQ $8, SP RET </code></pre> <p>而实际上在硬件层面做同样的事情,一条就够了</p> <pre><code>ADDQ BX, DX </code></pre> <p><strong>为了弥补 VM 这一层抽象带来的开销,引入 JIT 导致过多的复杂度。</strong></p> <p>看个 C 和 lua 的例子。出发点是很好的:并不是所有地方都需要性能,开发效率,灵活性,可以兼顾。发现一个函数不够快的时候,总是能够通过改用 C 实现,来提升性能。这是典型的 VM 带来的好处。再看 JIT。通过实现 JIT 让 lua 更快时,一个矛盾就出现了:JIT 优化,和使用 C 写关键函数优化,二者不可兼得。就像是实现 JIT 的方式来优化 VM,投入产出比似乎变低了(编译器实现者的角度)?</p> <p><strong>有没有什么方式,不做 JIT,又能得到性能上的全部好处呢?那就是 eval!</strong></p> <p>编译一门语言,做代码分析,生成 SSA,消除死代码,做内联,分配寄存器等等等,费了那多的精力去优化,然而实现另一门语言,这些过程又得重新来一遍(虽然 LLVM 的出现会缓解这种问题)。换个角度思考,假设一门语言支持 eval,那么实现一门新的语言,只需要翻译成宿主语言,调用 eval 就行了。宿主语言所有的编译优化,都被得以利用。写解释器得到原生性能,想着都很美好。</p> <p>支持 eval 好处很明显,它可以达得到宿主语言的性能;达到宿主语言的可移植性;可以调用宿主语言丰富的库,充分利用已有的生态环境。不过语言到语言翻译,没有 eval 不行。假设我写一个 lisp,翻译成 Go,会有一个问题:翻译成 Go 代码不是可运行的。因为 Go 语言并没有提供 eval。只有 eval 才能打破了什么是&quot;可运行的&quot;界线。源代码不算可运行,除非源代码加上编译器,并且这门语言可以动态生成和执行代码,才是可运行的。</p> <p>eval 之上,可以有强大的宏。宏很容易用 eval 实现,而且更灵活。至于讨论宏这个 feature 是否邪恶,我觉得只要编译期不依赖运行期,就没问题。</p> <p>整个 idea 最初的出发点是,能不能有某种办法,用写解释器的实现难度,得到编译器性能。</p> <p><strong>我真的不需要 VM,只是想要一种 eval 机制。</strong>如果真要说清楚 eval 机制到底是什么,那应该是:&quot;Eval as universal machine&quot;</p> www.zenlife.tk/eval-as-universal-machine.md 2018-03-13T03:02:42Z 我不想优化VM,只想要eval 2018-03-13T03:02:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>DDL 是 Data definition language。数据库里面的建表,删库,加索引,添加删除列,等等这些都是 DDL 操作。这次聊一聊 TiDB 里面的 DDL 的演化。其实我指的是 DDL 这个模块实现相关的东西。不涉及到算法本身,纯粹聊分布式系统在工程上的话题。最近同事在做 DDL 的并行优化相关的事情,我思考了一下:如果换作是我在设计,我会怎么做。</p> <p>这个模块一步一步变成现在这个样子,其实是有很多点需要考虑。</p> <p>第一个点是,引入 leader。TiDB 是一个分布式数据库,节点是有许多个的。每个节点上,都有可能执行 DDL 语句。插入删除这种 DML 语言可以各自执行,但是像 DDL 这种修改 schema 的操作是不能在每个节点上各自执行的。各个分布式节点看到的 schema 必须是同一份,不然就乱套了。节点一给某列加了个索引,节点二直接这列删了,如果这两操作放在各自节点上去做,schema 就不统一了。所以 DDL 都是由一个 leader 节点去做的。普通节点上面收到 DDL 请求,只是把消息发送出去,等 leader 做完了说没问题,再给客户端返回。</p> <p>第二个点是,必须全局持久化状态。DDL 的具体算法部分比较复杂,一次 schema 的变更要经历很多个阶段。想想分布式系统里面,任何节点都是不可靠的,可能随时就挂掉了。DDL 的 leader 节点可能就挂,但执行的进度不能丢。我们必须知道做到哪个阶段了,如何恢复,所以必须记状态。本地持久化不行,因为 leader 可以挂掉,每个节点都可以顶替充当 leader 的位置。所以 DDL 执行的状态必须是全局持久化的。</p> <p>这个状态我们记录在 TiKV 里面的。毕竟 TiKV 本身就是很好的分布式持久化的存储,这里正好用上。有一个问题要注意,是取消操作。一旦 DDL 开始执行,并且执行进度都是持久化的,即使节点挂了再起来,还是会继续执行。做 DDL 的过程异步补数据会对正常使用时有一定影响。所以这里是要考虑取消操作的。实现取消也是要注意数据索引的一致性。TiDB 开始没支持 DDL 取消操作,后面实现了。</p> <p>第三个点是,引入 worker 和任务分发模型。有些 DDL 操作做起来是比较耗时的,比如建索引,必须根据当前的数据列去补索引,补完索引才对外可见。表可能非常大,几千万上亿条记录,这个时候只由一个 leader 去干活,就太慢了。于是可以改一改模型,做成 leader 分发,worker 干活。worker 可以开启多个,加快处理速度。</p> <p>索引变成 KV 以后是对应一块逻辑的范围,有可能很离散。要注意哪些 worker 该负责哪块区间。如果按区间范围写死了分配给 worker,可能有的闲有的忙,有的区间没数据,而有的区间要处理的数据很多。所以这里不要按逻辑区间分配范围,可以用 scan 做。这也是我们发现的问题并优化掉的一个点。</p> <p>DDL 的作业队列,是利用 KV 抽象出一个类似 redis 的 List 的 API。包括早期的 leader 和 worker 的一些信息,都是直接利用 TiKV 来做的。<a href="online-schema-change-optimize.md">后来的优化</a>把 leader 和 worker 这一部分信息记到 etcd 里面去了。那个优化解决的是 schema lease 等待的问题,优化之后像删掉一列这种不需要补数据的 DDL 操作就能瞬间完成。</p> <p>这里面也有几个工程上值得关注的地方。leader 和租约机制,在 etcd 里面记录信息,leader 不断更新自己的租约。如果 TiDB 的 leader 节点被 kill -9 之类的异常退出,就没机会去清掉自己写在 etcd 里面的信息,于是其它节点必须等待租约过期后才能去再竞选 leader。DDL 操作会被卡往,lease 设置的越长,这种情况下卡住的时间越久。</p> <p>DDL job 队列的(分布式)全局锁。全局状态这种东西,有人读有人写,而底层是用的 TiKV 事务实现,冲突的代价还是挺大。因为大家都会访问到一个 key 上面,这里存在热点,冲突相对严重,会影响性能。还有 leader 要知道 worker 还是不是在干活,如果 worker 挂了,不能让整个 DDL 停了。必然涉及有一些全局状态的交互。</p> <p>第四点是并行 DDL。也就是演化到现在,正在做的事情。早期为了设计简单,让 DDL 排队依次执行的,假定用户并不会频繁的执行 DDL 操作。只用了一个作业队列排队。然而这里有一个问题:排在前面任务的会阻塞后面的任务。比如,执行一个表A的添加索引,表A有一千万行,会执行很久,执行表B的添加一列,执行表C的添加一列,后两个操作本来是可以并行执行的,却被排队卡往了,这样用户体验挺不好。</p> <p>如果我来设计这里,我会这样做。<strong>把状态和消息给分离</strong>。leader 和 worker 之间的协作,属于消息。而具体到某个 DDL job 执行到什么情况了,这个属于状态。消息可以通过 etcd 来交换,而状态则仍然持久化在 TiKV。</p> <p><strong>设计合理的数据结构</strong>。状态的数据结构,也就是所有当前 DDL job 的表示。可以构造一个依赖图,看哪些 DDL job 的操作是有依赖的,哪些是无冲突的。比如,一个 DDL 是为某列加索引,另一个 DDL 删除这一列,这两者显然相互冲突,无法并行。而如果一个 DDL 是在改表 A,另一个 DDL 在改表 B,这两者就是无冲突的。在单机里面,也就是 leader 节点的进程,我们可以弄一个图的数据据构,然后做一个拓扑排序,就可以决定 DDL 的操作次序了。</p> <p>状态是要持久化的,我们可以把它做成一个数组,每一项就是一个 DDL job。持久化的时候变成顺序的 kv 就行了,key 是 DDL job 的 ID,value 是对应的 Job 的状态信息。获取全部的 DDL job 只需要 scan 一次。job的 ID依次递增不重用。加载到 leader 进程之后,解析成依赖图。也就是将之前的单个的作业队列,替换成一个图结构,消除掉后面阻塞住前面的情况。可以做成只让 leader 改状态,任务的分发全部走消息,任务完成也由 worker 走消息,而不是直接改状态。这样子不会出现任何读写冲突,之前存在的队列的热点冲突就解决了。</p> <p>消息的设计,leader 和 worker 都在 etcd 上面注册自己。消息交互就通过往结点的路径里面添加事件。leader 的 lease 保证自己挂了会有 worker 顶上来。而 worker 的 lease,可以用于 leader 确认 worker 是否在干活。worker 活干到一个阶段,都可以通过消息告知 leader,由 leader 去改状态。</p> <p>大致想法就是这个样子,这是理想情况。不过应该不会实现成这样,毕竟要考虑很多历史包袝,保持向下兼容。</p> www.zenlife.tk/ddl-evolution.md 2018-03-25T00:58:42Z DDL 模块的设计和演化 2018-03-25T00:58:42Z 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