• 2020-06-21

    一个 Paxos 库的功能模块划分

    Views: 2291 | No Comments

    Paxos 算法本身非常狭窄, 只解决共识问题, 如果只在这个领域封装一个 libpaxos 没有必要, 没有太大的使用场景. 如果要封装一个 Paxos 库, 几乎就是要重新发明(实现) Raft. 但 "Paxos" 这个词比较唬门外汉, 所以咱们就说"开发一个 Paxos 库"吧.

    正如计算机领域解决问题的经典思路, 一个 Paxos 库应该拆分成三五个模块: 共识模块, 排序模块, 应用模块, 重传模块.

    共识模块: 使用本节点所知的下一个未使用的日志序号, 执行 Paxos 算法的两阶段. 如果一条日志(对应一个序号)达成共识, 将日志传递给日志排序模块. 这个模块要记录所有已达成共识的序号, 当然, 不一定要离散地记录每一个序号, 可以优化成记录离散的 range, 最终只有一个 range. 维护这些 range, leetcode 上有一些题目有涉及, 有成熟可用的代码.

    排序模块: 接受共识模块传递过来地已达成共识的日志, 按序号进行排序(因为是乱序达成共识). 然后连续地推进 commitIndex. 将 committed 的日志, 按连续的顺序发给日志应用模块.

    应用模块: 接受日志排序模块的输出, 用独立的线程将日志发送给状态机(apply). 状态机 Apply 完成每一条日志之后, 更新 appliedIndex.

    重传模块: 已经达成共识的日志, 不一定能全部被共识模块收到. 这时, 需要日志重传模块从其它节点拉取缺失的日志, 传递给日志排序模块.

    以上各个模块, 组成这样的工作链条:

         +--- 重传模块 --+
        /                \
    @--+----- 共识模块 ---- 排序模块 ---- 应用模块
    

    如果从一条日志的生命周期的角度分析, 这个工作链条代表着日志的生命周期.

    具体的实现编写代码的时候, 每一个模块肯定要对输入进行校验. 例如, 已经达成过共识的日志, 共识模块不再接受(leetcode 上面有判断一个整数是否落在 range 列表中的题). 小于等于 commmitIndex 的日志要被排序模块丢弃, 等等.

    还有优化方面的考虑, 特别是重传模块, 最好借鉴 TCP 流量控制算法. 本质上来说, 整个 Paxos 库其实是在实现并裁剪 TCP 协议. 这里 Paxos 库要用拉取重传, 如果是 Raft 的话, 是推送方(leader)主动重传.

    Posted by ideawu at 2020-06-21 11:11:39
  • 2020-06-21

    C++程序员容易走入性能优化误区

    Views: 2431 | No Comments

    有些 C++ 程序员, 特别是只写 C++ 没有写过 Python/PHP 等慢语言的程序员, 容易对性能有心智负担, 就像着了魔一样, 每写 3 行代码必有一行代码因为性能考虑而优化使得代码变形(复杂而晦涩).

    我认为, 任何系统级的代码, 都不应该刻意地在代码层面"形式化"地在表面功夫上面考虑性能优化, 而是应该把心思放到如何让代码更简洁和清晰上面. 如果逻辑清晰度能提高 10%, 代码行数能减少 10%, 即使单个模块性能下降 20%, 也应该做这笔交易. 理论上, 即使单个模块性能下降 20%, 整个系统的性能下降也许只有 1%(阿姆达尔定律). 根据经验, 如果代码行数减少逻辑清晰度增加, 带来的往往是性能提升而不是下降.

    如果一个 C++ 写的系统中用到了超过 3 处 std::move, 就证明程序员有心智负担了. std::move 并不是性能优化的手段, 而是检测系统是否变臭的标记. 为了不让检测方法失效, 也就是为了避免程序员逃避检测, std::move 外面裹了一层糖衣, 吸引那些着了魔的程序员主动来接受检测主动暴露. 这个符号证明程序员花了大量的精力去追求表面功夫, 而不是把心思放在如何让系统更简洁和清晰上面.

    lock free 也是检测一个 C++ 系统是否发臭的标记, 如果你能在代码中感受到程序员在极力避免使用锁, 也就是明明可以用一行锁解决的事, 它偏偏封装了 5 个辅助类, 引入了 3 个概念, 那么, 显然你也闻到了发臭的味道.

    为什么要强调 C++ 呢? 因为一个 C++ 程序员诞生的时候, 他有极高的机率沾染上"过度优化"的毛病, 这个毛病一直伴随许多 C++ 程序员的职业生命周期. 这是一个慢性病, 影响程序员的个人职业发展, 毁坏程序员参与开发的系统.

    相关文章: C++ bug free 原则

    Posted by ideawu at 09:56:02
  • 2020-06-19

    C++ bug free 原则

    Views: 3350 | No Comments

    ## 性能优化

    * 过早优化是万恶之源
    * 严禁在编程语言的语法层面进行性能优化, 只在逻辑层面和功能结构上进行优化

    ## 内存拷贝

    * 不要害怕内存拷贝
    * 如果想避免内存拷贝, 只能显式地用指针(引用)传递来共享内存, 严禁使用 std::move()
    * 如果指针传递的路径太长, 或者指针的使用者职责不单一, 那就用内存拷贝

    ## 接口设计

    * 不要为了性能考虑而设计 batch 接口, 所有函数都以一次处理一个对象为原则

    ## 并发和锁

    * 串行化使得系统的结构更简洁和清晰
    * 减少并发的长度(粒度), 一旦并发, 要尽快结束并发, 合并结果, 然后再串行化地做后续处理
    * 如果串行化是性能瓶颈, 那就用 worker 线程模型, worker 的逻辑必须非常单一且简短
    * 如果锁能让代码结构更简洁和清晰, 那么放弃部分性能也值得

    Posted by ideawu at 2020-06-19 12:48:51
  • 2020-05-10

    Golang chan 避免死锁

    Views: 8272 | No Comments

    Golang 的管道(chan)无论是否有缓冲, 生产者和消费者不可能做到速度完全匹配, 一旦管道满了, 就相当于生产者直接调用消费者. 如果生产者和消费者使用同一个锁, 就是死锁了.

    所以, 一个重要的原则就是, 在写管道之前, 把所有可能的锁 unlock 掉.

    Posted by ideawu at 2020-05-10 22:28:28
  • 2020-05-10

    我所理解的分布式系统

    Views: 9435 | 1 Comment

    分布式系统要义

    多副本(Replica)

    • 高可靠(数据)
    • 高可用(系统)
    • 高性能(系统)
      • 读性能
      • 写性能(降低)

    分区(Sharding)

    • 突破单机物理限制
      • 多副本: 容量 = MIN(replica)
      • 分区: 容量 = SUM(replica)
    • 提高读和写性能
    • 提高存储容量

    弹性

    • 增加减少副本数量
    • 合并分裂分区

    协作

    • 多副本协作
    • 多分区协作
    • 无协作不分布式

    常见的伪分布式

    • 无分区(争议)
      • 只有多副本算不算分布式?
    • 无协作
      • 全世界独立运行的 MySQL 组成了一个分布式关系数据库集群吗?
      • 有人说 World Wide Web 是一个分布式系统
    • 客户端自己分布式就是伪分布式
      • DBA 部署了2个独立的 Redis, 宣称是分布式 Redis 集群, 但要求业务部门自己把数据写到不同的实例…
      • DBA 部署了4个独立的 Redis, 除了要求业务部门自己拆分数据, 还要求业务部门自己写两个副本…
    • 真分布式和伪分布式之间有模糊地带
    Posted by ideawu at 14:34:14
  • 2020-05-10

    关于从客户端的角度去理解一致性可能产生的误区

    Views: 8050 | No Comments

    很多人从客户端并发的角度去讨论一致性, 这其实是一个错误的方向. 并不是说客户端与一致性无关, 相反, 客户端正是要求一致性的需求者.

    一致性协议不负责客户端的并发协调. 例如抢红包, 防超卖, 秒杀这类业务需求, 不是 Paxos/Raft 能解决的.

    首先, 我们需要定义先后, 何为"先", 何为"后"?

          q1          r1          q2          r2
    ------+-----------+-----------+-----------+-----
    

    如图, q 是指客户端发起请求的时间点, r 是指客户端收到响应的时间点, 两个请求用 1, 2 来表示. 很显然, 两个请求的先后顺序没有争论.

    如果是并发呢? 先后就变得让人迷惑了.

          q1          r1 
    ------+-----------+-----------
             q2          r2
    ---------+-----------+-----------
    

    你说, 哪个请求先哪个请求后? 一般认为, 请求 1 先于请求 2. 这个一般也不会有争论.

    接着, 是最让人迷惑的地方了.

          q1          r1 
    ------+-----------+-----------
             q2    r2
    ---------+-----+-----------
    

    你说, 请求 1 在先还是请求 2 在先? 争论不休吧? 所以, 讨论一个一致性的系统, 必须要求观察者的行为是瞬时的, 不能是并发的.

    观察者(客户端)当然可以并发, 但是, 如果客户端自己都不能分清先后的话, 去预期系统(服务端)的执行结果是没有意义的.

    一个强一致性的系统(服务端)当然可以处理并发请求, 而且请求的处理也不是瞬时, 这没关系. 我们讨论的是服务器在并发处理这些请求时的一致性可预期的行为, 而不是从客户端的角度看客户端并发时的系统的行为, 这里一定要注意.

    事实上, 一个一致性的系统, 只关注行为完成时点的先后的关系, 并不关注行为的发起是什么先后顺序. 所以, 请求到达服务器的时间先后关系没有任何意义.

    一致性, 讨论的是完成时, 不关心发起时.

    Posted by ideawu at 14:30:01
|<<<34567891011>>>| 7/136 Pages, 812 Results.