distribution

分布式系统概要

Posted by keming on September 2, 2021

1. 分布式基础概念

分布式通信范式

  1. 消息传递（TCP）
  2. 共享内存（ftok）：没法多机
  3. 分区内存（PGAS）：介于1/2之间，比如RDMA技术，避免CPU的过多参与
  • 消息传递可以通过共享内存实现
    • 比如单机多进程的TCP socket通信，最底层调用是共享内存
  • 共享内存可以通过消息传递时间
    • 比如CPU多核共享内存，实现是cache通过总线的通信

分布式设计原则

  1. 接口简单（KISS），接口实现秘密（Keep Secret）
  2. 容错：端到端去设计（中间的错误让它发生），让操作原子化，记录修改日志（append only，在不同层次不用重复记录，不能有副作用）
  3. 性能：端到端阿姆达尔，区分通常情况和最坏情况，优雅降级（流量削峰）
  4. 命名：概念正确
  5. 分层：分层解决所有问题，但中间层会有开销

分布式的顺序

  • 向量时钟表达因果关系
  • 全序广播最完整，但开销特别大

分布式一致性

事务的隔离

  • 2PL/Strict PL (Phase Locking)
  • OCC: Optimistic Concurrency Control
  • MVCC: Multi-version Concurrency Control
    • OCC的加强，一个对象维护了多个版本，避免了读操作到来时和更早的写操作的冲突，或者写操作与更早的写操作的冲突
    • 冲突只有：写操作到来与更早的读操作

CAP（考虑了故障）

  • Consistency：读是否一定能看到最近写的结果
  • Availability：可用性（节点故障）

  • Partition-Tolerance：分区容忍性（网络故障）

  • 关系型数据库：CA
  • 非关系型数据库：CP
  • 文档型的：AP

多节点达成共识

  • Viewstamped Replication
  • Paxos
  • Gossip（Redis）
  • Raft
    • 选主：每个任期最多有一个主节点，leader需要定期给follower发送心跳包，如果follower一直没有收到，会尝试发起选举。
    • 日志复制：client发给leader，leader再发给followers。半数以上的followers确认收到之后，leader才会返回给client ok。各节点日志不一致时需要反复确认，把leader的日志增加到followers里面（各follower可能数据有多有少）。
    • 成员变化：每个节点看到的成员数量可能不一致，leader会记录节点新旧状态的信息，并和各个follower商议更新。
  • 区块链：
    • 最长链优先

2. 资源管理与调度框架

  • 通常位于架构的最底层

三种部署

  • 进程
    • 性能最高，资源隔离最差
  • 虚拟机
    • 隔离和安全性最好，服务运行在两层操作系统上，性能最差
  • 容器
    • 兼顾了安全性和性能
    • 与微服务有关
    • 目前的主流

发展方向

  • 从集中式到分布式
  • 从资源预留到细粒度资源共享
  • 调度器从单一类型到多种类型

集中式

  • Borg（Google），Hadoop，Spark，Quasar，Quincy，Yarn，Kubernetes（开源，流行）
  • 调度器有全局资源状态信息，调度质量更高，吞吐率低，时延高
  • 可以在单调度器内部做并发

two level

  • Mesos（Twitter）
  • 一层调度器有全局资源状态信息，二层调度器有部分资源状态信息
  • 一层调度器往二层调度器offer资源是串行的，二层调度器的调度之间是并行的
  • 二层调度器之间难以协调资源状态，会有干扰
  • 多框架共享集群资源（提高资源利用率），更加细粒度
  • 二层调度器不用频繁查资源，只用等待一层调度器的汇报，减少通信开销，有点缓存的意思

Share State

  • Omega，Apollo，Tarcil，Firmament，Nomad
  • 所有调度器拥有全局资源信息
  • 需要同步状态，处理冲突，可以并发多种调度策略，方便扩展

完全分布式

  • Sparrow
  • 所有调度器拥有全局资源信息
  • 调度器之间不同步状态，不处理冲突，做分布式的work stealing
  • 时延低，但是调度质量不好，适合短任务，用不了复杂的调度的策略

Hybrid

  • Mercury（微软，基于Yarn），Hawk
  • 集中式调度器处理长任务，分布式调度器处理短任务

3. 分布式协同

三个基础

  • 时间：分布式时钟（向量时钟是逻辑时钟的一种，逻辑时钟表示偏序关系）
  • 通信方式：网络
  • 语言：协同算法

协同算法

  • Paxos
    • 时间用epoch表示
    • 预沟通阶段：Proposer发消息给所有Acceptor，Acceptor根据last 收到的epoch，选择返回数据，或拒绝回复（收到更新的请求就回复）。
    • 提议阶段：Proposer根据多个Acceptor的承诺，提出提议（此时才发送数据），由Acceptor决策
    • 只能决策一个值，至少要两个来回
  • Multi-Paxos
    • Proposer选一个leader做一个代表，减少竞争
    • 两个阶段变成一个阶段

google 的组件

  • Chubby
  • 和Borg协同，作为架构最底层

4. Serverless native

  • 云原生开发有三种
    • 微服务 –> Serverless –> Serverless Native(Huawei)
    • 微服务适合服务型，长任务
    • Serverless 免运维，避免了感知服务框架，适合短任务
    • Serverless Native比前者更适合大数据处理
  • serverless：AWS Lambda，Google Knative

六个关键技术

  • 有状态编程模型
    • 对于普通serverless来说，需要把状态维护在外置db，加锁访问导致性能差
  • 极速冷启动
    • 轻量级运行环境
    • 预加载空实例
    • 函数池化
    • 网络配置优化
  • 函数秒级自动伸缩
    • 快速采集：poll方式改为可push
    • 准确决策
    • 快速执行：极速冷启动
  • 端云协同
    • 苹果CloudKit，AWS CloudFront+Lambda
  • 函数高速总线
    • 普通serverless的函数调用需要通过公网转发
    • 在节点内部函数直接通信
  • 轻量化安全底座QVisor
    • 接近虚拟机的安全性和软硬结合
    • 仅内存占用比容器更大，其余方面都比容器好

5. 分布式网络与协议

TCP的问题

  • 时延远高于硬件通信
  • 内存占用率高

RDMA协议（RoCE）

  • 零拷贝（网卡直接访问数据）
  • 协议卸载：报文封装/拥塞控制之类，降低cpu开销
  • 单边操作：降低cpu开销

RDMA的虚拟化

  • TCP/IP通过虚拟交换机做ip转换

  • RDMA的网络协议栈在网卡，所以没法用虚拟交换机

    • 纯软件Freeflow，性能差一点

    • 纯硬件AccelNet，需要特殊硬件

    • 纯软件MasQ，操纵QPC，创建连接阶段增加一点延时，发送时很完美

6. 分布式搜索引擎

  • 过程：
    • 查询理解–>粗召回–>精召回–>摘要

L0

  • 云化基础设施

  • 大数据平台
  • 数据库
  • 机器学习平台
  • 内容合作方（如天气等额外信息）
  • 可爬取网页
  • 搜索engine

L1 搜索engine

  • 在线系统：用户
  • 离线系统：开发者
  • 运营系统：干预手段
  • 运维系统

L2 在线系统

  • 接入分发系统（balance）

  • 检索系统
  • 排序系统
  • 摘要系统
  • NLP系统（为其他模块提供服务）

L2 离线系统

  • 爬虫
  • 内容提取
  • 审核
  • 网页分析
  • 优质网页筛选
  • 在线数据构建
  • 分发

排序

  • 传统方式

    • 布尔模型
    • 向量空间（用TF-IDF做特征）
    • 概率模型：ES用了BM25

  • 机器学习LTR（Learning to Rank）

    • 能整合更复杂的特征
    • 单文档回归：忽视了文档间的关系，推荐场景有使用
    • 文档对回归：评估了文档间的相关性

    • 文档列表法：直接生成所有文档的得分，复杂度高，数据也难以获取。

    • lamdamart算法是个备选

7. 区块链

  • 本质上就是个分布式记事本

基本

  • 透明可信
  • 防篡改
    • 每个区块存着上一个区块头的hash，区块内容变化后区块头上的merkle hash也会变，上一个篡改后链就断掉了
  • 隐私安全
  • 高可靠
  • 基本过程
    • 发起方A把交易写到缓存区，算hash，做签名，然后广播
    • 接收方B/C收到后，核验A身份，挖区块（猜随机值），写出一个区块，并广播
    • 其他接收方D收到后，更新本地账本

四个基础技术

  • hash计算(sha256)：对交易做hash，生成merkle根节点签名
  • 数字签名：主要是发起交易者做私钥签名
  • P2P网络
  • 共识算法：解题（猜随机值）速度快的成为leader，最长链成为共识

应用

  • 数字货币
  • 智能合约
  • 流程管理、物流追踪
  • 住房租赁平台
  • 跨境支付
  • 公益扶贫
  • 数字版权

系统

  • HyperLedger Fabric
    • 可插拔共识系统
    • 性能不行
    • 没有跨链方案

  • HyperChain

    • 性能还不支持大规模商业系统

    • 高可用
    • 高扩展

  • XuperChain

    • 模型简洁
    • 高性能