为什么Redis快？

要说明为什么redis快的话，至少要一篇中篇文章的长度了。我们长话短说：

1. 内核操作，IO关键路径少。
2. 非阻塞网络模型
3. 良好的CodeBase

为什么Redis不够快？

就一个线程，还想怎样？

为什么Redis不是多线程架构呢？

因为共享内存架构，多线程就得要锁、抢占吧。

Anna的利器-Actor模型

Actor模型意味着每个Actor之间不共享内存，发消息来同步。

没有共享内存了，自然就没有锁了。

我们自然就进入了Wait-Free世界。

每个核心pin一个CPU，自然没有抢占了。

然后Actor模型要做真同步的代价太大，所以我们的Anna不是强一致性的，实际上，很多时候，我们也不需要强一致性。

Anna的尖刀-CRDT

和直接一个hashmap相比，Anna选择的是实现一个CRDT-Map。为什么要这样呢?

Anna采用Multi-Master架构，每个Master都可能受到一些写操作，在一个epoch结束时，个个Master需要互相交换更新。如果不使用CRDT，一个简单的做法就是将所有的写操作记录在Log中，发Log给所有其他Master。这样的问题就在于如果操作过多，消息传递、Apply的时间就不会少，而且顺序也变的重要了起来，很难最后收敛到一致。所以使用CRDT，收敛就不是问题了。每个Epoch结束Master只需要把自己的状态发给其他Master即可，CRDT能保证无论状态收到的顺序如何，最后都能收敛。问题解决。

Anna的语法糖-预定义的冲突解决器

用了CRDT很麻烦的时候就是并发操作的时候需要自己写冲突解决器。Riak就是这样的设计，用Cassandra的LWW肯定问题多多，那么Anna怎么做的呢？要实现xxx-consistency怎么做呢？Anna的作者帮你解决了常见的consistentcy的代码编写，实际上得益于CRDT优秀的模块化能力，更改的代码很少超过50行。用的开心。

到18年了，什么变了？

很开心看到Actor模式的部分推广。Erlang、Akka的思想是从本质上思考软件本身。

Parquet

Parquet是成熟的列式存储文件格式，数据以row groups分为partitions，每个partition的数据以列分别存储，Footer存储了每个块的元数据信息。以各种压缩算法来压缩数据。

Presto

Presto是开源的分布式SQL查询引擎。本身不store数据，通过reader读到执行引擎中。可以实现不同类型数据库的join。

故事

之前的Parquet Reader For Presto（后面简称PRFP）没有完全地利用Parquet的优势，所以Uber Team改进了其设计。

假设执行SQL为

SELECT base.driver_uuid FROM rawdata.schemaless_mezzanine_trips_rows WHERE datestr = ‘2017-03-02’ AND base.city_id in (12)

原来的PRFP会分三步走： 1. 以行为单位用Parquet的开源库读所有数据。2. 将行格式转化为Presto的列式内存块。3. 根据断言base.city_id = 12 来过滤这些block，然后就丢给Presto执行引擎执行。

优化

1. 裁列 – 只读所需列，而不是所有列
2. 没有行列转换，直接将Parquet列格式转化为Presto列格式。
3. 利用Footer中的元数据，在特定列不在Row Group中列区间时，跳过这个Group
4. 利用Footer中的Row Group级别的列值字典，不在字典中的city_id的group跳过。
5. 只有有断言filter后有数据的group才生成Parquet数据块。

TreeDoc是CRDT。不熟悉CRDT的可以看我之前的文章。

TreeDoc解决了CRDT中常见的atomid的开销问题，其创新式的用BinaryTree表示一个任意一个有序的atomic。方法就不多赘述了，传统的BT编码模式+一些Tricks。

TreeDoc最有贡献的就是实现了explode/flatten的操作，对于没有并发冲突的部分，flatten为没有atomid 的数组，减少了Overhead。当有并发冲突的时候再explode为BinaryTree。

当然最后的Related work对于OT的描述很解毒。

Operational transformation (OT) considers collaborative
editing based on non-commutative operations. To
this end, OT transforms the arguments of remote operations
to take into account the effects of concurrent executions. OT
requires two correctness conditions : the transformation
should enable concurrent operations to execute in either
order, and furthermore, transformation functions themselves
must commute. The former is relatively easy. The latter is
more complex, and Oster et al. prove that all previously
proposed transformations violate it. Later solutions [14–16]
are complex, and their correctness is hard to verify.
OT attempts to make non-commuting operations commute
after the fact. We believe that a better approach is to design
operations to commute in the first place. This is more
elegant, and avoids the complexities of OT.

blog要发展为morning paper的感觉了。

和传统的直接timeout相比，PAFD的做法是过去heartbeat的平均间隔的标准差和均值，算出一个模型，给定F(phi, time to the latest hb) => timeout概率，让应用层来决定是否timeout。Akka和Cassandra都用了。

最近小忙，这次水一波。

Finally, HotSpot终于能比较好的利用现代CPU的SIMD了。

• 现况
  1. Hotspot 支持一部分的x86 SIMD指令。
  2. C2能做Superword Optimaztion。
  3. 数组的拷贝、填充、比较都默认SIMD化了。

• JVM Intrinsics
  • @HotSpotIntrinsicCandidate说明函数实现被JVM用手写汇编或者IR优化了。

• 已经被优化的：

  • 除了上面说的还有Arrays.equals();
  • Array.mismatch()(Java9)。

• SuperWord Optimzation

  • 只在C2

  • 只能在unrolled的counted循环做优化。

    • Counted 循环 是是只有单出口的循环。

    • 1 2 3 4 5 6 7

      for (int i = start; i < limit; i+=stride) { // loop body } int i = start; while (i < limit) { // loop body i+=stride; }

    • 可以使用-XX:+PrintCompilation -XX:+TraceLoopOpts查看,或者-XX:+PrintAssembly看生成的代码。

      • Counted Loop: N100/N83 limit_check predicated counted [0,100),+1 (-1 iters)

  • Vector Box Elimination

    • 目前还比较brittle。
    • 这种优化只能解决一些问题，不是通用的优化。
    • JNI很难开发和维护。

    ​

• 注意，手动unroll的代码是不能向量化的。

• Hotspot团队的实验：
  • X86性能优化大概3-8%。
  • 1.5X的性能提升在vector centric micros。

Packrat Parsing

前言

最近看Scala的Parser Generator库的实现，发现其支持记忆化的回溯解析，因为以前没有了解过这方面的知识，所以我就找到了其算法：Packrat Parsing好好研究了下。

What

Packrat Parsing是实现线性时间复杂度的回溯解析算法。

Why

很多递归下降时的算法有两种实现：

1. 回溯法， 理论能力更强，但是最差时间复杂度为指数级别。
2. 预测分析，通过peek等偷看后面的token，能达到线性的复杂度。

Packrat让回溯解析也能做到线性时间复杂度了。

How

记忆化是动态规划算法的本质，因为CFG属于无状态的解析过程，所以完全可以使用记忆化的策略来进行保存中间的计算结果。

1
2
3
4
5
6
7
8

var dv = {
'Additive':  ExprAdditive(dv),
'Multitive': ExprMultitive(dv),
'Primary':   ExprPrimary(dv),
'Number':    ExprNumber(dv),
'Char':      next_dv,
'str':       str,
};

定义一个类似链表的结构，每个结构结点为类似dv的结构，每个key为当前字符串位置进行解析的非终止符，不难想到，对于一个长度为m的字符串，假定有n个非终止符，最多有O(mn)个状态，所以能够达到O(n)的时间复杂度。

Packrat对回溯解析本身并没有太大的改动，仅仅是增加了记忆化的查询、添加，就成功达到了O(n)。

2*(3 + 4)的解析结果 。

js解析数值表达式的demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

function dvAdditive(dv){
if(!('Additive' in dv)){
dv.Additive=ExprAdditive(dv);
}
return dv.Additive;
}
function ExprAdditive(dv){
try{
var mul=dvMultitive(dv);
if(dvChar(mul.dv).value=='+'){
var add=dvAdditive(dvChar(mul.dv).dv);
return {
'value': mul.value+add.value,
'dv': add.dv,
};
} else {
throw {};
}
} catch(e) {
return dvMultitive(dv);
}
}
function dvMultitive(dv){
if(!('Multitive' in dv)){
dv.Multitive=ExprMultitive(dv);
}
return dv.Multitive;
}
function ExprMultitive(dv){
try{
var primary=dvPrimary(dv);
if(dvChar(primary.dv).value=='*'){
var mul=dvMultitive(dvChar(primary.dv).dv);
return {
'value': primary.value*mul.value,
'dv': mul.dv,
};
} else {
throw {};
}
} catch(e) {
return dvPrimary(dv);
}
}
function dvPrimary(dv){
if(!('Primary' in dv)){
dv.Primary=ExprPrimary(dv);
}
return dv.Primary;
}
function ExprPrimary(dv){
try{
if(dvChar(dv).value=='('){
var add=dvAdditive(dvChar(dv).dv);
if(dvChar(add.dv).value==')')
{
return {
'value': add.value,
'dv': dvChar(add.dv).dv,
};
} else {
throw {};
}
} else {
throw {};
}
} catch(e) {
return dvNumber(dv);
}
}
function dvNumber(dv){
if(!('Number' in dv)){
dv.Number=ExprNumber(dv);
}
return dv.Number;
}
function ExprNumber(dv){
var value=0;
while(!isNaN(dvChar(dv).value)){
value=value*10+parseInt(dvChar(dv).value);
dv=dvChar(dv).dv;
}
return {
'value': value,
'dv': dv,
};
}
function dvChar(dv){
if(!('Char' in dv)){
dv.Char={
'value': dv.str[0],
'dv': {
'str': dv.str.slice(1),
},
}
}
return dv.Char;
};
function Expr(str){
return ExprAdditive({
'str': str,
}).value;
}

Ref: https://zhuanlan.zhihu.com/p/25260077

Scala的特性需要解决菱形继承问题，恰好Py也需要，但是两者却使用了不一样的方案，我们来看看究竟。

• How

  • Scala

    • 1	class C extends C1 with C2 with ... with Cn

    • lin(C) = C >> lin(C1) >> lin(C2) >> … >> lin(Cn)

    • 其中>>代表串联并去除重复项，右侧胜出。

  • Python

    • 经典的C3算法。

      • lin(C) = merge(C, lin(C1), lin(C2), …, lin (Cn), C1, C2, …, Cn)

      • merge实现为：

        • 持续的选出最好的头直到list枯竭，最好的头不可以在除了开头的list中位于最后一位。一个好的头可以在多个list中位于第一个，但不能再其他位置出现(除第一个)。
        • 可以记忆化实现。

      • demo

        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

        假定有如下的类继承体系： class A extends O class B extends O class C extends O class D extends O class E extends O class K1 extends A, B, C class K2 extends D, B, E class K3 extends D, A class Z extends K1, K2, K3 那么C3运算过程如下： L(O) := [O] // the linearization of O is trivially the singleton list [O], because O has no parents L(A) := [A] + merge(L(O), [O]) // the linearization of A is A plus the merge of its parents' linearizations with the list of parents... = [A] + merge([O], [O]) = [A, O] // ...which simply prepends A to its single parent's linearization L(B) := [B, O] // linearizations of B, C, D and E are computed similar to that of A L(C) := [C, O] L(D) := [D, O] L(E) := [E, O] L(K1) := [K1] + merge(L(A), L(B), L(C), [A, B, C]) // first, find the linearizations of K1's parents, L(A), L(B), and L(C), and merge them with the parent list [A, B, C] = [K1] + merge([A, O], [B, O], [C, O], [A, B, C]) // class A is a good candidate for the first merge step, because it only appears as the head of the first and last lists = [K1, A] + merge([O], [B, O], [C, O], [B, C]) // class O is not a good candidate for the next merge step, because it also appears in the tails of list 2 and 3, but... = [K1, A, B] + merge([O], [O], [C, O], [C]) // ...class B qualified, and so does class C; class O still appears in the tail of list 3 = [K1, A, B, C] + merge([O], [O], [O]) // finally, class O is a valid candidate, which also exhausts all remaining lists = [K1, A, B, C, O] L(K2) := [K2] + merge(L(D), L(B), L(E), [D, B, E]) = [K2] + merge([D, O], [B, O], [E, O], [D, B, E]) // select D = [K2, D] + merge([O], [B, O], [E, O], [B, E]) // fail O, select B = [K2, D, B] + merge([O], [O], [E, O], [E]) // fail O, select E = [K2, D, B, E] + merge([O], [O], [O]) // select O = [K2, D, B, E, O] L(K3) := [K3] + merge(L(D), L(A), [D, A]) = [K3] + merge([D, O], [A, O], [D, A]) // select D = [K3, D] + merge([O], [A, O], [A]) // fail O, select A = [K3, D, A] + merge([O], [O]) // select O = [K3, D, A, O] L(Z) := [Z] + merge(L(K1), L(K2), L(K3), [K1, K2, K3]) = [Z] + merge([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3]) // select K1 = [Z, K1] + merge([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3]) // fail A, select K2 = [Z, K1, K2] + merge([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3]) // fail A, fail D, select K3 = [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O]) // fail A, select D = [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O]) // select A = [Z, K1, K2, K3, D, A] + merge([B, C, O], [B, E, O], [O]) // select B = [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O]) // select C = [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O]) // fail O, select E = [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O]) // select O = [Z, K1, K2, K3, D, A, B, C, E, O] // done

        ​

https://www.evernote.com/l/Ako9JcTFGjRKuawWE0fGG_AR7tata12cZ8M

• What
  • HPKP是一种Trust on First Use的减少CA被攻击的印象的技术。
• How
  • 第一次用户访问的时候通过meta元素或消息头告诉client在未来某段时间只信任xxx公钥，如果后面访问server没有这个公钥，至少标识给用户看看。
• Why
  • 因为CA太多了，如果一家gg了，client得到的证书都不一定有用。
  • HPKP这种方式可以保证只相信某些公钥。
• What
  • 最近Chrome宣布18年要完全移除HPKP。除了HPKP本身的问题外，大家可以想想这种机制的问题何在？

• 动机

  • 本来某人说要给新生演讲，不知道讲什么，我说我也想讲，她送上了👎的眼神，估计是因为

    作为一只老饼，如果倚老卖老谈所谓的经验，那就很恶心了。

  • 那我就只讲点我觉得比较正的三观吧。毕竟新生们应该能走出更好的路，非得把自己标榜的多厉害树立『权威』其实挺无趣的。

• 正文

  • 目的
    • 我经常问自己的一个问题是：我为什么想要学计算机？我以前总是觉得这个问题挺虚的，后面发现这才是对我来说最根本的一个问题，我也找了很久，曾经我给出了几个答案：
      • 做出伟大的项目
      • money
      • 名声
      • 荷尔蒙
      • 进入好公司工作
    • 最后我的答案是：
      • 追求自己的极限。
      • 用我最喜欢的计算机书籍《SICP》的前言来说就是：
        • 我认为，在计算机科学中保持计算中的趣味性是特别重要的事情。这一学科在起步时饱含趣味性。当然，那些付钱的客户们时常觉得受了骗。一段时间之后，我们开始严肃地看待他们的抱怨。我们开始感觉到，自己真的像是要负起成功地、无差错地、完美地使用这些机器的责任。我不认为我们可以做到这些。我认为我们的责任是去拓展这一领域，将其发展到新的方向，并在自己的家中保持趣味性。我希望计算机科学的领域绝不要丧失其趣味意识。最重要的是，我希望我们不要成为**传道士**，不要认为你是兜售圣经的人，世界上这种人太多了。你所知道的所有关于计算的东西，其他人也都能学到。绝不要认为成功计算的钥匙就掌握在你手里。你所掌握的，也是我认为并希望的，也就是智慧：**那种看到这一机器比你第一次站在它面前时能够做的更多的能力，这样你才能将它向前推进。**
        • 我觉得它差不多就是求知若虚，虚幻若谷的琐碎版了，不过可能对我更加有用些。

• 基础知识
  • 基础知识的重要意义是很显而易见的，缺少基础的时候，最后很难发现一些联系、洞见。之前有人和我说XXX语言没有指针，先不说讨论语言本身的意义，最后那个其实也是Implicit的。。。这就很尴尬了。
  • 基础和底层是两回事，计算机科学本身就是错误的名字，下次说的时候记着默念：『计算科学』。
  • 很多人去看源码、标准等等，说自己看过XXX了，所以我理解了原理，我觉得：
    • 理解原理的判定标准是你能否构建一个新的东西呢？
  • 自上而下和自下而上的关系聊了很多次了，我给出对于我来说比较满意的答案：
    • 自上而下可以破除神秘感，但弱化构造能力。
    • 自下而上可以真正理解原理，但时间成本更高。
    • 所以还是万能的狗皮膏药：看情况吧。

• 语言
  • 作为一个语言不可知论者，讲这个其实本身也是有很强的政治意味的，因为不关心语言本身也是一种对语言的态度。
  • 语言是一种选择，但不是目的，关心钉子「目标」而不要关心锤子「本身」。
  • 如果XXX都是图灵完全的，那就把时间花在讨论它抽象了哪些东西吧。
• 资源
  • 优秀的东西总是稀少的。优秀的东西总是稀少的。
    • 每天我的Reeder都有上千篇前端文章入库，实际上多是入门级的文章。
    • 永远不要马上相信自己找到的是好东西。
  • 教育、努力最后构造的其实是一个品位，你才是那个最重要的内容过滤器。
  • 信息爆炸不是放弃收集信息的借口。
• 广度和深度
  • 凡事把问题二元化的人都是文革的遗风。
  • 理解相互促进、共生的意义。
• 绩点、工作、社团、项目、研究哪个重要？
  • 有个概念叫做偏序，它们就是偏序的。
  • 但凡有人摆出来绩点高/工作好…秒杀全场的论调，慎重。
  • 你的目的是什么？
• 方向问题
  • 你应该有自己的主见，在方向问题上其实只有你才是执行者。
  • 如果你觉得XXX方向一定比YYY方向好，请再次查询『偏序』。
• 刻板印象
  • 程序员的笑话这类的东西，最终都是很低俗的。
  • 女生就学不好计算机是刻板印象。
  • 程序员猝死多是刻板印象。
  • 程序员木讷是有恶意的刻板印象。
  • ……
• 生产者和消费者
  • 热衷于消费没有错，但生产者不是更好玩点么？
  • 消费者是猪。这句话不是我说的。。。

• 给迷茫新手的CS干货书单
  • 《SICP》
    • 能让你重新”正确”思考计算机科学、语言、抽象、函数式…诸多概念。
    • 它就是CS领域的『The Book』。
  • 《CSAPP》
    • 看似很厚，其实是最快的捷径。
    • 一本书顶5门课。
  • 《线性代数就应该这样学》
    • 书名已经解释了一切。
  • 《黑客与画家》
    • 黑客的黑不是说技术，而是思维。
  • 《暗时间》
    • 榜样的力量是无穷的。
  • 《人月神话》
    • 预言者的力量是无穷的。
    • 洞见太少了，所以才宝贵。
  • 《计算的本质》
    • 其实是讲计算理论的书。
  • 《程序员修炼之道》
    • 还是因为洞见太少了，所以才宝贵。
  • 《元素模式》
    • 《设计模式》解毒剂。
    • KISS才是王道好吧。
  • 《风格的要素》
    • 说英语的话，还是这本最解毒。
  • 《编程原本》
    • 真的要理解C++ STL，不如看作者怎么说的。