# 分布式系统原理

- 概念
    - 三态(RPC)
        - 成功
        - 失败
        - 超时
            - 状态未知
                - 重新读检查
                - 写操作设计为幂等(idempotence)
    - 副本(replica)
        - 这里统一指存储副本, 在不同节点上持久化同一数据
        - 副本一致性(consistency)
            - 一致是指在一定条件下, 系统的数据保持相同
            - 常见一致性
                - 强一致性(strong consistency)
                    - 任一用户,任一时间,任一节点读到的都是最新的变更
                - 单调一致性(monotonic consistency)
                    - 任一用户,任一时间,读到某次变更后的数据后, 不会读到比这个更旧的数据
                - 会话一致性(session consistency)
                    - 任一用户,该次会话中读到某次变更后的数据后,不会读到比这更旧的数据
                - 最终一致性(eventual consistency)
                    - 数据更新成功后, 各副本上的数据最终将达到一致的状态(时间不保证, 存在上限?)
                    - 用户始终读一个副本,就能满足单调一致性
                - 弱一致性(weak consistency)
    - 评价指标
        - 性能(performance)
        - 可用性(availiability)
        - 扩展性(scalability)
        - 一致性(consistency)

- 数据
    - 分片(sharding)
        - hash
            - 扩展性不高, 加/减机器, 所有数据需要重分布
                - 解决方式, 映射和机器分离,用metaserver保存hash(key)->node的关系
                    - metaserver开支高,成瓶颈
            - 数据倾斜(data skew)
                - 热点用户数据落到同一节点上
        - range
            - 元信息保存映射信息,开支高
        - chunk
            - 和数据本身的特征没有了关系,只和数据大小有关
            - 所有数据线性排列,按照大小划成chunks.
            - 使用metaserver保存映射信息,也是挑战
        - consistent hash
            - 应用
                - 最早, p2p网络, 分布式哈希表(DHT)的数据分布算法.
            - hash函数的改进
                - 将hash函数的值域限制在长度为N的封闭环上, 令N为虚节点(virtual node)的数量, 远大于实际节点数.
                - 每个node上绑定一定的虚节点,数据映射到虚节点上.
    - 副本和分片
        - 不以节点作为副本单位,以数据块作为副本单位

- 副本控制协议(分布式算法)
    - CAP定理(Brewer's theorem)
        - consistency, availiability, partition tolerance三者只能保证两个
    - 并发控制
        - 多个客户端读写,写写冲突时的解决
    - 分类
        - 中心化(centralized)
            - 简化分布式并发控制, 为中心节点单机并发控制
            - 中心节点宕机,会停服务
            - primary-secondary(master-slave)
                - 副本分为两种, primary, secondary
                    - primary副本作为中心节点,负责更新,并发控制,协调副本一致性
                    - secondary
                - 问题
                    - 数据更新
                        - primary处理并发控制
                        - 向其它N个secondary发送变更操作(数据)
                            - 集中发送(扇出)涉及到x * N的带宽问题
                                - GFS, secondary之间接力发送
                    - 数据读取
                        - 读secondary, 最低满足最终一致性.
                        - 通过副本版本号, 每次更新后递增版本号, 可以打到会话一致性
                        - 强一致性比较困难
                            - 只读primary (资源浪费)
                                - 副本和节点不绑定的话, 每个节点会有很多数据片的primary, 这样可以降低浪费问题.
                                    - 热点数据可能存在问题? 
                            - primary控制secondary的可用性, 只有当secondary的数据同步后,才开放读取
                                - 降低可用性保证一致性
                            - quorum
                    - primary确定/切换(选主)
                    - 数据同步
        - 去中心化(decentralized)