《分布式技术原理与算法解析》笔记
《分布式技术原理与算法解析》笔记
开篇词丨四纵四横，带你透彻理解分布式技术
分布式缘何而起：从单兵，到游击队，到集团军
分布式系统的指标：啥是分布式的三围
分布式互斥：有你没我，有我没你
分布式选举：国不可一日无君
分布式共识：存异求同
分布式事务：Allornothing
分布式锁：关键重地，非请勿入
答疑篇：分布式技术是如何引爆人工智能的？
分布式体系结构之集中式结构：一人在上，万人在下
分布式体系结构之非集中式结构：众生平等
分布式调度架构之单体调度：物质文明、精神文明一手抓
定义：单体调度是指，一个集群中只有一个节点运行调度进程，该节点对集群中的其他节点具有访问权限，可以搜集其他节点的资源信息、节点状态等进行统一管理，同时根据用户下发的任务对资源的需求，在调度器中进行任务与资源匹配，然后根据匹配结果将任务指派给其他节点。
架构：单体调度器也叫作集中式调度器，指的是使用中心化的方式去管理资源和调度任务。
特点：单体调度器拥有全局资源视图和全局任务，可以很容易地实现对任务的约束并实施全局性的调度策略。
单体调度代表：K8S、Borg 等。
分布式调度架构之两层调度：物质文明、精神文明两手抓
定义：在两层调度器中，资源的使用状态同时由中央调度器和第二层调度器管理，但中央调度器一般只负责宏观的、大规模的资源分配，业务压力比较小；第二层调度器负责任务与资源的匹配，因此第二层调度可以有多个，以支持不同的任务类型。
特点：解决了单体调度架构中，中央服务器的单点瓶颈问题；相较于单体调度而言，提升了调度效率；支持多种类型的任务。
两层调度代表：YARN、Mesos 等。
分布式调度架构之共享状态调度：物质文明、精神文明多手协商抓
定义：共享状态调度架构沿袭了单体架构的模式，通过将单体调度器分解为多个调度器，每个调度器都有全局的资源状态信息，从而实现最优的任务调度。
分布式通信之远程调用：我是你的千里眼
本地过程调用（Local Procedure Call, LPC），是指运行在同一台机器上的进程之间的互相通信。
远程过程调用（Remote Procedure Call, RPC），是指不同机器中运行的进程之间的相互通信，某一机器上运行的进程在不知道底层通信细节的情况下，就像访问本地服务一样，去调用远程机器上的服务。
分布式通信之发布订阅：送货上门
分布式通信之消息队列：货物自取
CAP 理论：这顶帽子我不想要
CAP 是指：在一个分布式系统中， 一致性、可用性和分区容错性，最多只能同时满足其中两项。
- 一致性（C：Consistency） - 多个数据副本是否能保持一致
- 可用性（A：Availability）- 分布式系统在面对各种异常时可以提供正常服务的能力
- 分区容错性（P：Partition Tolerance） - 分布式系统在遇到任何网络分区故障的时候，仍然需要能对外提供一致性和可用性的服务，除非是整个网络环境都发生了故障
在分布式系统中，分区容错性必不可少，因为需要总是假设网络是不可靠的；CAP 理论实际在是要在可用性和一致性之间做权衡。
- CP - 需要让所有节点下线成为不可用的状态，等待同步完成。
- AP - 在同步过程中允许读取所有节点的数据，但是数据可能不一致。
分布式数据存储系统之三要素：顾客、导购与货架
数据的生产和消费
数据特征：结构化数据、半结构化数据、非结构化数据
分区和复制
数据分布方式之哈希与一致性哈希：“掐指一算”与“掐指两算”的事
分布式数据存储选型的考量维度：
数据均匀：数据存储、访问尽量均衡
数据稳定：当数据存储集群扩容或缩容时，数据分布规则应尽量稳定，不要出现大范围的数据迁移。
节点异构性：应考虑集群中不同节点硬件配置的差异，将数据承载根据配置尽量均衡
分布式数据复制技术：分身有术
数据复制是指，如何让主备数据库保持数据一致的技术。
复制技术分类
- 同步 - 注重一致性（CP 模型）。数据更新时，主节点必须要同步所有从节点，才提交更新。
- 异步 - 注重可用性（AP 模型）。数据更新时，主节点处理完后，直接提交更新；从节点异步进行数据的同步。
- 半同步 - 采用折中处理。数据更新时，主节点同步部分从节点（通常为一个节点或一半节点）成功后，才提交更新。
很多分布式存储支持通过配置，切换复制策略，以满足不同场景的需要。
分布式数据之缓存技术：“身手钥钱”随身带
分布式高可靠之负载均衡：不患寡，而患不均
负载均衡（Load Balancing）是指将请求或流量均衡地分配到多个服务器或节点上，以实现资源的最优化利用和高效的响应速度。
负载均衡常见策略
- 随机负载均衡
- 策略 - 将请求随机分发到候选服务器
- 特点 - 调用量越大，负载越均衡
- 适合场景 - 适合服务器硬件相同的场景
- 轮询负载均衡
- 策略 - 将请求依次分发到候选服务器
- 特点 - 请求完全均匀分发
- 场景 - 适合服务器硬件相同的场景
- 最小活跃数负载均衡
- 策略 - 将请求分发到连接数/请求数最少的候选服务器
- 特点 - 根据候选服务器当前的请求连接数，动态分配
- 适合场景 - 适用于对系统负载较为敏感或请求连接时长相差较大的场景
- 哈希负载均衡
- 策略 - 根据一个 key （可以是唯一 ID、IP 等），通过哈希计算得到一个数值，用该数值在候选服务器列表的进行取模运算，得到的结果便是选中的服务器
- 特点 - 保证特定用户总是请求到相同的服务器，若服务器宕机，会话会丢失
- 适合场景 - 可以保证同一 IP 的客户端的请求会转发到同一台服务器上，用来实现会话粘滞（Sticky Session）
- 一致性哈希负载均衡
- 策略 - 相同的请求尽可能落到同一个服务器上。尽可能是指：服务器可能发生上下线，少数服务器的变化不应该影响大多数的请求。当某台候选服务器宕机时，原本发往该服务器的请求，会基于虚拟节点，平摊到其它候选服务器，不会引起剧烈变动。
- 优点 - 加入和删除节点只影响哈希环中顺时针方向的相邻的节点，对其他节点无影响。
- 缺点 - 加减节点会造成哈希环中部分数据无法命中。当使用少量节点时，节点变化将大范围影响哈希环中数据映射，不适合少量数据节点的分布式方案。普通的一致性哈希分区在增减节点时需要增加一倍或减去一半节点才能保证数据和负载的均衡。
- 适合场景 - 一致性哈希可以很好的解决稳定性问题，可以将所有的存储节点排列在首尾相接的 Hash 环上，每个 key 在计算 Hash 后会顺时针找到临接的存储节点存放。而当有节点加入或退出时，仅影响该节点在 Hash 环上顺时针相邻的后续节点。
分布式高可靠之流量控制：大禹治水，在疏不在堵
分布式高可用之故障隔离：当断不断，反受其乱
分布式高可用之故障恢复：知错能改，善莫大焉
答疑篇：如何判断并解决网络分区问题？
知识串联：以购买火车票的流程串联分布式核心技术
搭建一个分布式实验环境：纸上得来终觉浅，绝知此事要躬行
特别放送丨那些你不能错过的分布式系统论文
分布式理论基础
Time, Clocks, and the Ordering of Events in a Distributed System
The Byzantine Generals Problem
Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
CAP Twelve Years Later: How the “Rules” Have Changed
BASE: An Acid Alternative
A Simple Totally Ordered Broadcast Protocol
Virtual Time and Global States of Distributed Systems
分布式一致性算法
Paxos Made Simple
Paxos Made Practical
Paxos Made Live: An Engineering Perspective
Raft: In Search of an Understandable Consensus Algorithm
ZooKeeper: Wait-Free Coordination for Internet-Scale Systems
Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore
Impossibility of Distributed Consensus With One Faulty Process
A Brief History of Consensus, 2PC and Transaction Commit
Consensus in the Presence of Partial Synchrony
分布式数据结构
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications
Pastry: Scalable, Distributed Object Location, and Routing for Large-Scale Peerto-Peer Systems
Kademlia: A Peer-to-Peer Information System Based on the XOR Metric
A Scalable Content-Addressable Network
Ceph: A Scalable, High-Performance Distributed File System
The Log-Structured-Merge-Tree
HBase: A NoSQL Database
Tango: Distributed Data Structure over a Shared Log
分布式系统实战
The Google File System
BigTable: A Distributed Storage System for Structured Data
The Chubby Lock Service for Loosely-Coupled Distributed Systems
Finding a Needle in Haystack: Facebook’s Photo Storage
Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
Scaling Distributed Machine Learning with the Parameter Server
Dremel: Interactive Analysis of Web-Scale Datasets
Pregel: A System for Large-Scale Graph Processing
Spanner: Google’s Globally-Distributed Database
Dynamo: Amazon’s Highly Available Key-value Store
S4: Distributed Stream Computing Platform
Storm @Twitter
Large-scale Cluster Management at Google with Borg
F1 - The Fault-Tolerant Distributed RDBMS Supporting Google’s Ad Business
Cassandra: A Decentralized Structured Storage System
MegaStore: Providing Scalable, Highly Available Storage for Interactive Services
Dapper, a Large-Scale Distributed Systems Tracing Infrastructure
Kafka: A distributed Messaging System for Log Processing
Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases