"通信"是一个广义的概念, 不仅限于计算机网络通信, 任何抽象或者具体的对象间的交互行为, 都是一种通信. 对象间一旦进行通信, 便有可靠通信的需求. 可靠通信至少包括三项要求:
为了达到这三项要求, 对应有三条定理(可靠通信三原则):
有些同学可能对排队理论有怀疑, 表示搞一个全局位图(标记集合)也能解决去重问题. 如果深究, 判断标记和修改标记是独立的两步操作, 这两步操作就遇到去重问题, 也即, 对标记集合的操作本身也需要排队. 当然, CAS 是一种解决方案, 但 CAS 的实现内部本质也是排队.
Continue reading »
在计算机领域, 两个操作的先后顺序的确定, 是一个非常严肃的科学问题, 不能仅凭人的直觉来判定.
有两种方式可以规划两个操作的先后顺序:
通信协调是指, 一个操作 (B) 在明确知道另一个操作 (A) 已经结束的前提下才启动, 那么便可以判定 (B) 在 (A) 之后. 这里说的"明确知道", 包含主观上的知道, 也包括客观上的知道. 例如, 对于顺序(串行)操作, 先后顺序是明确的客观的, 即使后一个操作不关心(或者说不知道)前一个操作是否已经完成, 它也应当知道.
绝对时间规划不存在, 即使是原子钟也不是绝对时间. 因此, 绝对时间规划需要假设时间差异(gap), 让两个操作的时间区间有大于 gap 的距离.
相关讨论: 数据库的并发操作与一致性
并发操作对于程序员来说, 这个概念很常见, 但是, 很多人对它的理解未必那么准确.
有很多业务逻辑是严格依赖操作的先后顺序的, 先做什么, 后做什么, 做什么之前必须先做什么, 这些是业务逻辑的本质. 对于并发编程(多线程, 多进程, 分布式), 如果没有做通信协调, 那么系统必然有 BUG, 系统就是错的.
在单机编程时代, 每一项数据只有唯一的一份, 对数据的修改也是 in-place 的. 但是, 在并发编程领域, 包括分布式系统, 数据多版本(Multi Version, Versioning)是核心.
我们先从单机编程的内存操作出发. 对于内存的操作, 都是原地(in-place)更新的. 对象和内存空间强绑定, 当更新对象时, 是将对象的内存空间擦除然后用新数据写覆盖. 到了多线程编程时代, 就引入了锁机制, 因为擦除和写操作过程不是原子性的, 可能擦除到一半时, 就被其它线程读取了, 因此要加锁.
单机的硬盘操作, 基本也是借鉴内存操作, 也是对象和硬盘空间强绑定. 至少大部分程序员的思想是这样的, 这样比较直观. 跟内存操作一样, in-place 也遇到了操作的原子性挑战. 内存本来就是易失的(掉电后丢失), 但硬盘不一样, 数据需要持久化(掉电不丢失), 即使靠加锁解决了访问原子性问题, 但解决不了数据丢失问题. 所以, 硬盘操作是最先引入多版本技术的. 当需要修改某个对象时, 在另外的地方保存对象的新数据, 然后在另外的地方原子性地修改指向新数据的"指针". 事实上, 指针的修改也是多版本的, 不是 in-place 的, 后面会细说.
Continue reading »
我在遇到"接口与实现分离"这个编程领域的概念时, 感到非常模糊. 随着编程经验的积累, 才明白了"接口与实现分离". 用 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.
为什么 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 要解决的问题.
不通过 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? 开什么玩笑? 我修改了同一行两次, 当然保留最新的修改! 谁神经病要保留旧的修改!
|
带有此标志, 表示本博客已经被加入到IT牛人博客聚合网站. |
Loading ...