• 2020-04-05

    接口与实现分离

    Views: 2286 | No Comments

    我在遇到"接口与实现分离"这个编程领域的概念时, 感到非常模糊. 随着编程经验的积累, 才明白了"接口与实现分离". 用 Java 的程序员应该天天用到 interfalce 和 class, 不过, 即使是 Java 程序员, 可能偶尔也会违反广义的分离原则.

    我最近接触到的一个违反"接口与实现分离"原则的例子, 可以分享一下.

    RTT(round trip time)是一个非常重要的时间概念, 这会让程序变得很"慢". 例如:

    func(1);
    func(2);
    func(3);
    

    如果每一次函数调用要花 100ms 的话, 那么做完 3 件事要花 300ms. 有经验的程序员立即就做了代码"优化":

    func([1,2,3]);
    

    把函数参数改成数组, 一次传入 3 个任务, 利用了 batch 机制, 做完 3 件事也仅需要 100 ms. 看起来完美解决问题. 但是, 工程上这样做带来了缺点, 那就是改变了接口(interface). 这是一个经典的违反"接口与实现分离"原则的例子, 接口因实现而被迫改变.

    如果函数执行是放在网络服务器上面, 而调用者是所谓的客户端, 一般的网络编程都是可以并发处理的, 例如在 3 个线程中调用函数. 这时, 接口改变之后, 反而没有用. 因为任务是不同的客户端发起的, 除非你增加一层抽象来积累请求. 这个优化看起来美好, 但是却增加了使用者的成本.

    所以, 工程上应该由 func() 函数的实现者来做请求积累, 在函数内部把并发的请求合并成一个 batch, 减少 RTT.

    Posted by ideawu at 2020-04-05 12:15:41
  • 2020-03-07

    为什么 Leader Based 的分布式协议 Raft 是更好的

    Views: 3854 | No Comments

    为什么 Leader Based 的分布式协议 Raft 是更好的? 这个问题隐式地表达了 Paxos 多主特性是不好的. 之前谈过, Paxos 不区分读写, 读和写都要进行完整的 Paxos prepare-accept 两阶段流程, 否则, 就无法保证一致性. 事实上, 我看过一些 Paxos 实现, 它们基于优化的考虑, 简化了 prepare-accept 两阶段流程, 最终失去了一致性保证而不自知. 可见, 优化是万恶之源.

    一个常见的错误是把多数派读当做一致性读, 之前已经谈过, 这是错误的.

    但是, 为什么大家一而再, 再而三地一定要优化 Paxos 呢? 很显然, 大家已经发现 Paxos 的理论模型在很多场景并不实用(请原谅我这么直白, 你可以自己想象成非常委婉的语言). 于是, 每个人都按自己的理解去简化 Paxos 实现, 然后错误地拿"Paxos"来当挡箭牌证明自己拥有 Paxos 的所有优点, 而不知道自己犯了逻辑上不严谨的错误, 只是因为计算机和网络环境出错的概率比较小, 而自己的代码其它部分又有 bug, 所以不愿意把 bug 算到自己错误地简化了 Paxos 这个做法头上.

    我发现, 错误的 Paxos 实现各有各的不同, 而正确的 Paxos 实现最终都实现成了 Raft 的样子.

    首先, 日志复制状态机的理论更有普适的实际意义. Multi-Paxos 错误地暗示要实现成以 key 为维度, 但现实世界的数据是结构化的, KV 是特例. 结构化要求不能以离散的 key 为维度来同步数据, 而是应该同步数据的操作序列, 也就是日志复制. 所以, 除非全量同步数据, 否则把 Paxos 应用到结构化数据上面一定会带来严格意义上的错误的.

    其次, Leader Based 是更有普适意义的一种理论上已经证明具有严谨性和正确性的优化手段. 我所见过的任何不基于选主的对 Paxos 进行优化的方案, 几乎全是错误的, 都没有理论上的严谨证明, 实际上的错误也显而易见. 如果你的 Paxos 实现不是基于选主的, 同时你又意图做优化, 那么, 我几乎非常确定, 你已经犯错了.

    为什么优化必须先选主? 之前的文章已经谈过, 多个副本数据的不一致性是一定的, 没有任何协议和手段能避免, 所有的一致性协议都是让数据看起来一致来让自己具有一致性功能. 当多个副本不一致时, Paxos 要求在读和写的时候同步数据, 来修复这种不一致, 修复完后才能返回给客户端. 但是, 所有的优化都破坏了这个原则, 然后声称自己对 Paxos 做了优化. 哪有这样的好事? 你破坏了 Paxos 基石, 却没有提供对等的理论证明.

    再回到选主这个话题. 选主的一个重要作用, 就是对多副本的不一致性进行统计和确认. 一个简单的例子, 当某个 key 只存储于一个节点或者两个节点, 无论是多数节点还是少数节点没关系, 那么这个 key 到底是不是有效的? Paxos 的做法是读的时候做同步. 有一个非常违反直觉的的地方, 那就是, 如果数据存在于多数节点, 那么这个数据是否是有效的呢? 答案仍然是未知的

    很违反常理, 是不是? 设想这样一场景, 当你去读这份数据时, 你会遇到两个情况: 一是多数节点有共识, 二是没有多数节点共识. 对于有共识, 很简单, 那就是有共识. 但是, 对于无共识, 除非你读到了所有节点的明确的答复, 否则你不能确定是否有共识, 因为还有节点未答复.

    但是, 如果有 Leader, 那么 Leader 自己就能确定, 不需要读"全部"节点. 这就是做了优化. 现在, 问题就剩下怎么避免出现两个"自认"的 Leader. 这也是 Raft 要解决的问题.

    Posted by ideawu at 2020-03-07 18:47:08 Tags: ,
  • 2020-03-06

    不用 git rebase 合并 commit 历史

    Views: 3493 | No Comments

    不通过 git rebase 来合并 commit logs. 实在没弄明白 git rebase 为什么会要求我解决我从来没有修改过的文件冲突, 真是莫名其妙. 网上一大堆人深受其害. 大家 rebase 的目的非常简单, 就是要合并 commit logs. 在已经 merge from master 的情况下.

    通过新建一个临时本地分支, 然后将代码合并(其实就是拷贝过来), 这样新分支就只有一条 commit log 了, 然后回去你的分支, 把你的分支重置为临时分支, 然后提交到远程.

    为什么 git rebase 不能做这么简单的事?!

    git checkout -b tmp master
    git merge --squash my_feature
    git commit
    git checkout my_feature
    git reset --hard tmp
    git push -f
    git branch -D tmp
    

    据说, rebase 的原理是一个版本一个版本地 merge, 所以同一个文件你可能要解决一百次冲突, 而这个冲突是别人导致的别人已经解决过的, 然后你又重复解决别人引入和已经解决的冲突.

    好像 git rebase -i 然后把中间的版本(pick xxx)删除即可?

    git 这样解释:

    当您执行 git rebase 操作时,通常会移动提交。 因此,您可能会遇到引入合并冲突的情况。 这意味着您的两个提交修改了同一个文件中的同一行,而 Git 不知道要应用哪个更改。

    What the FUCK? 开什么玩笑? 我修改了同一行两次, 当然保留最新的修改! 谁神经病要保留旧的修改!

    Posted by ideawu at 2020-03-06 18:22:59
  • 2020-02-13

    龟兔赛跑问题和Floyd环检测算法

    Views: 3981 | No Comments

    例如要检测如下的环, 找出 a 点到 b 点的距离 mu, 以及环的周长 lam.

                    +----------------+
                    |                | 
    +---------------+----------------+
    a    mu         b                c
                    |       v        |
    

    用快慢指针同时遍历. 首先可知, 如果环存在, 快慢指针会在 c 点相遇. c 到 b 点的距离是 v. 那么可知, 相遇时, 快慢指针走过的距离是:

    慢: mu + m * lam + v
    快: mu + n * lam + v
    

    它们是两倍关系, 所以:

    2 * (mu + m * lam + v) = mu + n * lam + v
    2 * mu + 2 * v + 2 * m * lam = mu + n * lam + v
    v = n*lam - 2*m*lam - mu
    

    这时, 两个指针再以同样的速度前进. s 从 a 点出发, f 从 c 点出发. 可以知道, 当 s 走了 mu 距离后, 到达 b 点. 而 f 走了 mu 距离后, 也到达 b 点. 两者相遇.

    n*lam - 2*m*lam - mu + mu = n*lam - 2*m*lam
    
    Posted by ideawu at 2020-02-13 18:12:10
  • 2020-02-12

    动态规划算法的发现

    Views: 3875 | No Comments

    1. 问题可分而治之且 BFS

    首先, 问题必须是可分而治之的, 并在最后合并. 分而治之(递归)是为了穷举, 合并是为了找最优.

    Result r(costs[], target){
    	args = [];
    	for(cost in costs){
    		tmp = r(costs - cost, target - cost) + cost;
    		args += tmp;
    	}
    	return G(args);
    }
    

    虽然上面的代码是 DFS, 但形式上是 BFS, 而且也应该写成 BFS, 只不过 BFS 的代码不简洁而已.

    思考: 与贪婪算法的区别.

    2. 合并函数 G(...) 可迭代处理

    因为 G() 是可以转换成迭代的, 所以代码变成:

    Result r(costs[], target){
    	ret = PRE;
    	for(cost in costs){
    		tmp = r(costs - cost, target - cost) + cost;
    		ret = G(ret, tmp);
    	}
    	return ret;
    }
    

    PRE(开始之前)是引入的边界外的参数, 以便让代码处理逻辑简化, 不然要加 if 条件判断, 就无法在形式化上统一.

    3. 增加缓存

    Result r(costs[], target, dp){
    	cache_key = make_cache_key(costs, target);
    	if(dp[cache_key]){
    		return dp[cache_key];
    	}
    	ret = PRE;
    	for(cost : costs){
    		tmp = r(costs - cost, target - cost, dp) + cost;
    		ret = G(ret, tmp);
    	}
    	dp[cache_key] = ret;
    	return ret;
    }
    

    4. 将递归转成迭代

    #### 推导型

    Result forward(costs, target){
    	init(dp);
    	cc[PRE] = costs;
    	for(curr in range(PRE, target)){
    		costs = cc[curr];
    		for(cost : costs){
    			dp[next] = G(dp[next], dp[curr] + cost);
    			cc[next] = costs - cost if dp[next] updated;
    		}
    	}
    	return dp[target];
    }
    

    #### 回溯型

    Result backtrack(costs[], target){
    	dp[PRE] = PRE;
    	cc[PRE] = costs;
    	for(curr in range(atomic, target)){
    		for(prev in get_prev_list(curr)){
    			costs = cc[prev];
    			cost = costs.link(prev, curr); 
    			dp[curr] = G(dp[curr], dp[prev] + cost);
    			cc[curr] = costs - cost if dp[curr] updated;
    		}
    	}
    	return dp[target];
    }
    

    5. 缓存可淘汰: 滑动窗口

    这一条件不是必须的, 因为很多动态规划解法无法淘汰缓存. 如果缓存可淘汰, 而且是可以用滑动窗口的方式淘汰, 那么就是非常**经典且巧妙的**动态规划解法.

    对于推导型动态规划, 只需要缓存最长的推导距离. 对于回溯型动态规划, 只需要缓存最长的回溯距离.

    这里举的例子是单节点推导, 下一节点只依赖单一的前序节点, 但有些问题需要依赖多个前序节点才能出方案, 例如斐波那契数列. 需要注意.

    Posted by ideawu at 2020-02-12 15:57:31
  • 2020-01-15

    分而治之算法(divide and conquer)

    Views: 4193 | No Comments

    分而治之算法(divide and conquer)是计算机算法领域最常用最有效的算法之一, 体现到编程上就是树(数据结构), 递归函数. 一般的代码模板是这样的:

    func recursive(N){
    	if(!N){return;}
    	a, b = split(N); // divide 
    	proc(a);         // conquer a
    	recursive(b);      // process b
    }
    

    对于寻路, 分段处理最终达成目标这种模式的问题, 一般的代码模板是:

    func recursive(N){
    	if(!N){return;}
    	a, b = split(N); // divide 
    	r = proc(a);     // conquer a
    	if(r){recursive(r + b);}  // conquer remain + b
    	recursive(b);      // process b
    }
    

    多了一步:

    if(r){recursive(r + b);}
    

    因为前一段的剩余, 要和后一段组成新的问题, 然后被处理.

    Posted by ideawu at 2020-01-15 16:36:14 Tags:
|<<<123456789>>>| 1/12 Pages, 67 Results.