网络模型

• 电路交换
  • 不灵活 成本高 需要专有物理线路 需要建立专有连接 线路利用率低 没有转发机制
  • 容易受网络中断影响
• 包交换
  • 更灵活 成本低 不需要专用线路 可以线路复用 线路利用率高
  • 不容易受网络中断影响
• 我们的网络：**统计复用包交换网络 ** 统计复用=排队
  • Internet:不可靠网络 IP-service model / IP best-effort network /最大努力网络
    • 包可以丢失重复重排 packets may lose, duplicate, reorder
    • 无连接最大努力目的地转发 connectionelss best-effort destination based forwarding.
  • 可靠：保证包能够不丢失 不重复 按序到达 无差错

传输过程和基本术语

• 包在每个网络节点传输方式：上至下层层封装header 下至上层层解包
  • Message “报文” 应用层的名称
  • Segment “报文段” 起始于传输层的信息单元
  • Datagram “数据报 ” 使用udp等无连接服务的网络层信息单元
  • Packet “分组/包” 起始于网络层的信息单元
  • Frame“帧” 起始于链路层的传输单元
  • bit “比特” 物理层单元
• Links: 链路 连接节点的物理介质
• 服务/接口: 不同层之间
• 协议：平级的peer之间
• 端对端 Client to Server 点对点 otherwise | 应用和传输层端对端
  • E2E总时延 = 排队时延 + 处理时延 + 传输时延 + 传播时延
  • P2P总时延 = 传输时延 + 传播时延
• 连接建立断开：通常需要多次握手/挥手
• 两个port+ip 定义一个tcp stream / udp message
• 流量控制：保证接受者buffer能承受住 拥塞控制： 保证网络不过于堵塞
• 可靠：保证包能够不丢失不重复按序到达无差错 重发丢失/损坏的包
• 根据信息在传输线上的传送方向，分为以下三种通信方式：
  • 单工通信Simplex：单向传输
  • 半双工通信Half-duplex：双向交替传输
  • 全双工通信Duplex：双向同时传输
• 局域网：多种不同结构
  • 局域网是一种典型的广播信道，主要特点是网络为一个单位所拥有，且地理范围和站点数目均有限。有多种局域网技术，其中以太网占主导地位。可以按照网络拓扑结构对局域网进行分类：星 环 直线
• 以太网：星形结构局域网 中间使用集线器或交换机连接
• MAC地址 链路层地址 48位 设备网卡的唯一标识 有多少个适配器=多少个mac地址 os可更换
• 网络设备
  • Hub 集线器 [layer 1 物理层] 作用于物理层的 能使多个主机 创建一个广播频道(only floods)的设备 具备多个网口，专门实现多台计算机的互联作用。
  • Repeater 中继器**[layer 1 物理层]** 接收并重复信号
  • Switch 交换机 [layer 2 数据链路层] 收处理转发以太网帧到网络中的其他设备 会维护一个<mac link/接口> 表 “交换表” 表类似一个LRU缓存 因此能够实现mac地址识别=说它具有“学习能力”. 支持同时存在多个点对点连接。
  • Bridge 网桥**[layer 2 数据链路层]** 连接两个局域网
  • Router 路由 [layer 3 网络层] 根据routing table提供转发和路由两种功能 转发：将数据包移送到合适输出端 路由：决定数据包的路由路径。
  • Gateway 网关 [layer 3 物理层] 两个不同网络之间的关口设备

网络IO模型

• 同步
  • 阻塞IO 更高CPU利用率 进程被阻塞 内核代替进程完成操作后返回状态码 进程恢复
  • 非阻塞IO 浪费cpu 轮询 不可用则内核返回错误代码
  • IO复用: 让单个进程具有处理多个 I/O 事件的能力。又被称为 Event Driven I/O
    • 早期的实现
      • select 等待固定数量的fd中1个或多个成为就绪状态 适用于实时性要求高的情况
      • poll 等待一组描述符中1个成为就绪状态 适合实时性要求相对宽松情况
    • 更现代的事件驱动实现
      • epoll linux的io事件通知机制 监视多个fd等待任意一个可用 使用红黑树管理监视中的fd 适用于linux上管理大量长连接情况
        • epoll_create创建一个epoll实例 epoll_ctl把一个事件添加到epoll列表 epoll_wait等待一个io事件就绪 否则阻塞calling thread
        • 默认level triggered: epoll_wait监测到事件发生通知进程 进程可以不处理 下次调用时再处理
        • edge triggered发生事件立即通知 进程要立即处理
  • 信号驱动 使用较少 非阻塞等待创建signal handler 数据就绪后 os 发信号代表可以开始io 比非阻塞cpu利用率更高
• 异步: 进程调用aio_read后立即返回 当io完成后os内核向进程发信号

分层架构

• OSI architecture 7层协议 注重通信协议必要功能
  • 应用层：e2e 用户服务 HTTP FTP DNS DHCP 远程登录 邮件
    • 表示层：数据表示, 压缩, 加密
    • 会话层：建立及管理会话 SSL RPC
  • 传输层：e2e 为应用进程提供端对端通信+在应用层网络层之间multiplexing和demultiplexing TCP UDP
  • 网络层：p2p 无连接通讯，寻址，路由 控制数据在子网中的运行. IP ICMP RIP OSPF BGP ARP
  • 数据链路层： p2p 相邻网络节点/主机的数据的格式化与传输控制 LAN WAN LLC MAC ARP MTU
  • 物理层：点对点比特流传输 01=电流强弱 数模转换 模数转换
• TCP/IP architecture 4层协议 计算机上实现应关心的 除了传输层 网络层 其他上下合并
  • 应用层：应用+表示+会话
  • 传输层，网络层
  • 链路层：数据链路+物理

数据链路层

Data Link Layer 点对点相邻网络节点/主机的数据的格式化与传输控制 e.g. LAN WAN LLC MAC ARP MTU

• 包装成帧Framing 把网络层传下来的包封装成帧 加个开始和结束
• 点对点传输控制P2P transmission control: Logical link control (LLC)
  • Error Detection CRC checksum
  • Flow Control " only used in wireless networks
• 广播控制Broadcast: Media access control (MAC)
  • Frames synchronization 帧的同步 clock based, character counting, byte stuffing. STX ETX
  • Channel sharing 信道共享方法:
    • 信道复用：时分，频分，码分
    • 交替：轮询，令牌传递
    • 随机访问 主要例子：Aloha, Ethernet
      • Ethernet MAC采用CSMA/CD协议 (Carrier Sense Multiple Access / Collision Detection) 载波监听多点接入/碰撞检测
        • 线路空闲立即发送 (Carrier Sense 载波监听)
        • 如果繁忙等待 “inter-frame gap” = 96 bit time
        • 冲突发现，发送 jam signal, 进行二进制指数后退{1,2,4,8,…}, 然后延迟k*51.2 μs" collision domain 冲突域 = 1 RTT

网络层

点对点无连接通讯，寻址，路由 控制数据在子网中的运行. 涉及协议： IP, ARP, ICMP, RIP, OSPF, BGP IP是个不可靠的协议因为无连接 它的可靠性需要通过上层如TCP实现

• 寻址
  • 
  • IP: 沙漏结构的中点，连接异构网络，使之看起来统一
    • 地址系统
      • Class-based addressing (过去版本): lead to problem of large# networks in routing table
      • Subnetting and supernetting 子网与超网
        • 子网 方便管理和路由效率 subnet ip = subnet mask & host ip address
        • 超网 用于跨网路由 CIDR 无分类跨网地址系统
          • ip地址=网络前缀+主机号 128.14.35.7/20 表示前 20 位为网络前缀。
          • 意义：减少了路由表项 查找时采取最长前缀匹配原则选择哪一个
• 路由
  • ARP：Broadcast & Responds路由器确定设备MAC
    • routers and hosts maintain an dynammic <IP, MAC> LRU cache called ARP table. For unkown IP, router broadcast ARP request, hosts with that IP address reply its MAC
  • Routing types and protocols
    • 网内路由Intra-domain
      • RIP Routing Information Protocol: rely on local computation in all nodes
        • Distance Vector Protocol (based on Bellman-ford)
      • OSPF Open Shortest Path First Protocol: no local computation faster nonegative edge weight-loop-free convergence
        • Link state Protocol (based on Dijkstra’s shortest path)
    • 跨网路由Inter-domain: BGP Border Gateway Protocol
• 报文的拆分重组 Fragmentation/Reassembly: 使得异构网络能够以最大传输大小传输包
  • 和tcp合作 tcp负责mtu discovery
    • TCP MTU Discovery: 不断增大发送数据包大小直到获得数据包过大的ICMP响应得出mtu
  • 和数据链路层合作 mtu协议定义链路支持最大传输大小
• 错误报告和控制 ICMP
• - **封装在 IP 数据报中**，但是不属于高层协议。
• ping 用来测试两台主机之间的连通性 通过icmp echo实现
• Traceroute 追踪一个数据包路径: 封装一个无法交付的udp包, 利用IP协议的**“ttl”字段**，尝试从每个网关到某个主机的路径引发ICMP 超时响应。

传输层TCP/UDP

端对端为应用进程提供端到端的通信服务 在应用层和网络层之间multiplexing和demultiplexing e.g. TCP UDP

• UDP: bare-bone protocol
  • 无连接 不可靠 无流量拥塞控制 无时限吞吐量安全保证
  • 但更可控更自由 可以在应用层实现可靠传输: RUDP
  • UDP header：src port, dest port, header length, checksum
• TCP: 面向连接 可靠 流量拥塞控制 基于字节流 全双工 差错校验
  • TCP header:
    • SRC，DST ports (16-bit each)
    • Sequence #序号, Ack #确认号(32-bit each) 序号：当前数据段第一个字节编号 tcp要用序号拼接数据 确认号：期望下个数据段第一个字节编号
    • Header length(data offset), reserve
    • Flags(indicate pkt types): SYN FIN ACK URG(紧急指针) PSH(不在接受者缓冲区等待) RST重制连接标志
    • Receive window (16-bits 发送者接收窗口的大小) 用于流量控制flow control
    • Check sum: for error detection
    • Urgent Ptr: 优先级
    • Options
  • 全双工：建立连接后可以双向收发数据
  • 以连接为导向： 意味着需要主动建立连接
  • TCP提供包级别的可靠传输 (IP最大努力网络不能保证)
    • UDP只提供位级别的可靠传输 由checksum实现 只能进行简单的检测看看数据是否污染
  • 如何实现可靠传输：不丢失 不重复 按序到达 无差错
    • 不丢失
      • 确定包收到了：ack机制
      • 确定包没收到：计时器/超时检测机制Retransmission Timeout 制定了超时标准要比RTT稍微多一点尽量接近RTT, RTO新= RTO旧*2 by karn’s algorithm
      • 丢包补救：快重传+urgent ptr
    • 不重复 按序到达
      • 滑动窗口
    • 无差错
      • Check sum
  • 提供流量控制：确保接收方的buffer不会overflow
    • receiver发送的ack报文中的receiver window表示自己仍可缓存的容量 若超过这个限制 sender必须等待receiver的ack和更新。将窗口字段设置为 0，则sender停止发送数据。这实际上调整了sender发送窗口大小和发送速率。
  • 提供拥塞控制：与整个网络有关, 网络比较拥挤的时候控制发送方的窗口。增加一个congestion window CWND
    • send window (#unacknowledge pkts in flight) = min(CWND, RWND) 当cwnd更小时，我们就进入了一个拥塞控制的模式
      • 慢开始与拥塞避免
        • cwnd := 1, cwnd++ for each ack == cwnd*=2 each RTT 慢慢探测网络容量 指数增长 但是又被临界值限制 到达临界值后线性增长避免拥塞
        • cwnd >= ssthresh do congestion avoidance: cwnd++ for each RTT;
      • 快重传和快恢复： 快重传解决丢包重发问题（3个重复包=包丢失），快恢复临界值减半后线性增长拥塞窗口：适应性的避免网络拥塞 on dupack (pkt loss) fast retransmit the next sequence from receiver side. Fast recover it by setting ssthresh = cwnd/2, cwnd = ssthresh, do congestion avoidance

三次握手 四次挥手

• 为什么三次握手：TCP是一个全双工通信协议，也就是说它是双向收发的。初始序号是两边都要随机选择:因为安全问题要避免TCP sequence prediction attack。所以双方都要告诉对方自己的初始序号 = 也就是通信双方数据原点的位置，所以至少要4次握手。SYN ACK SYN ACK, 然后因为tcp header里reserve flags部分SYN ACK是可以同时为1的 中间两个步骤可以合并 所以3次就够。

• 第三次握手过程中sender可以piggypack data而receiver只能在这次握手结束才可以。

• 在linux socket编程中，客户端执行connect()时，将触发三次握手。
  

• 为什么四次挥手因为tcp全双工+tcp半关闭造成的。假如client主动关闭，那么直到client收到server的ack前，数据传输仍然可以从server—>client进行，tcp是半关闭的client-server关了但server-client方向还没关，这也是为什么有close-wait状态的原因，服务器端要等待最后这一波数据传输的完成。所以这也解释了中间两次为什么不能像建立连接一样合并。当服务器没有数据要传时他就可以通过fin来释放自己方向的连接了。

• TIME_WAIT / 2MSL等待状态:

  • 确保server收到ack
    • server接受了ack不需要TIME_WAIT，因为它已经完成同步了可以释放资源了。
    • client必须等待确定server收到ack，否则client直接关闭server会可能收不到ack无法正常关闭。
    • ack最久要1MSL到达server或者最坏情况没收到。取上界=1MSL
    • 等待server回复的超时重传消息=最坏情况又1MSL
    • 最坏要2MSL client才知道ack有没有到达
  • 避免新旧连接混淆

• 在linux socket编程中，任何一方执行close()操作即可产生挥手操作。

滑动窗口

• TCP使用滑动窗口实现流量控制和乱序重排和去重 (虽然tcp byte-oriented 以下为了方便说明 改为包/sequence 而不是字节)
  • 流量控制：
    • Receive window用于接收方通知发送方自己还有可用缓冲区大小，发送方据此调整发送数据多少, 从而保证流量控制
  • sender缓存：已发送但未确认的包
  • receiver缓存：未按序到达的包
  • sender发送流水线化 提高信道利用率
  • receiver回复cumulative ack:
    • receiver只对窗口内最后一个按序到达的包进行确认 = 之前全部按序到达窗口向右滑动
    • 对于按序未到达的包 sender收不到ack超时重传
    • receiver收到该包，如果【该包+已缓存的未按序到达的包 】构成一段连续有序的segment 那么他们可以被交付给应用进程，窗口向右滑动
• sender

• receiver

拥塞控制

如果网络出现拥塞，分组将会丢失，此时发送方会继续重传，从而导致网络拥塞程度更高。因此当出现拥塞时，应当控制发送方的速率。这一点和流量控制很像，但是出发点不同。流量控制是为了让接收方能来得及接收，而拥塞控制是为了降低整个网络的拥塞程度。

慢开始与拥塞避免

• Slow start: 初始 cwnd = 1，每收到1个ack cwnd++，cwnd指数增长：2、4、8 …
• 为cwnd避免过快，设置一个慢开始门限 ssthresh，当 cwnd >= ssthresh 时，进入拥塞避免-每个轮次cwnd++ 线性增长
• 若超时: 令 ssthresh = cwnd / 2，重新执行慢开始。

快重传与快恢复

• 如何确定报文丢失：接收方只对最后一个收到的有序报文段进行确认。在发送方，如果收到三个重复确认，那么可以知道接收方下一个报文段丢失，此时执行快重传
• 只是丢失个别报文段而不是网络拥塞：执行快恢复，令 ssthresh = cwnd / 2 ，cwnd = ssthresh，直接进入拥塞避免cwnd线性增长
  
• SYN flood: client发第一个syn后下线server没收到ack不断尝试直到超时 linux:5次 1+2+…+32=63秒才断开连接，可被恶意利用
  • 防护:linux提供tcp_syncookies的参数 当syn队列满了 server通过该参数回发SYN cookie 若client非恶意会回复SYN cookie 直到连接成功建立

应用层

• 2种架构: Client Server / Peer to Peer平级
• Socket = 门, 传输层 = 走廊
• 主机和进程可以被ip+端口定义
• 远程登录： SSH TELNET
• 邮件： 发送协议常用 SMTP，读取协议常用 POP3 和 IMAP。
• 不同情况下应用有不同需求 数据丢失 vs 实时性 vs 吞吐量

常用端口

FTP

• 服务器主动(客户端配置服务端firewall) 服务器被动(只需开放端口号 不安全)

• 2个TCP连接： TCP数据连接端口20, TCP控制连接端口21.

DHCP

只适用于动态ip分配的情形，如进入一个新的移动网络。 主机不知道自己ip地址 ask dhcp server, 配置好IP地址,子网掩码,网关 IP 地址.

• client使用udp同子网内广播discover报文
• dhcp server返回offer 包括多种选择
• client选择一个ip 发送request
• dhcp server返回ack

DNS

• 如果返回的响应超过 512 字节（UDP 最大只支持 512 字节的数据）。
• DNS zone transfer

DNS 负载均衡

同一主机在dns服务器里配置多个主机记录=多个不同服务器ip，dns服务器解析域名时会轮询，这就完成了简单的负载均衡。

HTTP HTTPS

• URI 包含 URL 和 URN。
• HTTP是无状态的
  • 请求互相独立， 类似事务
  • 编程，本地储存，cookie，session是用来提高用户体验的
• HTTPS 并不是新协议，而是让 HTTP 先和 SSL（Secure Sockets Layer）通信，再由 SSL 和 TCP 通信，也就是说 HTTPS 使用了隧道进行通信。
  • SSL使用RSA算法 public key加密 private key解密
• API
  • Get 从服务器获取数据
  • Post 提交数据给服务器
  • Head 获取报文头部
  • Put/Delete 上传文件/删除文件 不安全没有验证机制
  • Patch 部分修改资源
• 状态码
  • 200 OK
  • 3XX 重定向
  • 4XX 客户端错误 如 404 NOT FOUND
  • 5XX 服务端错误

Get Post比较

• get将请求信息放url里 post放报文体中
• get符合幂等性和安全性(只读) post不符合(因为是修改操作)
• get可被缓存 绝大多数get请求都被cdn缓存 减少web服务器压力 可被储存到浏览器记录和书签中 而post不行

cookie session

• cookie: 存在于client边的保存用户状态信息的文本文件，由浏览器储存到client本地。 方便未来向服务器查询用户信息使用。渐渐被淘汰，现在新的浏览器直接支持将数据储存在client本地。存在浏览器中不加密会不安全。但可以减少服务器负担。
  • http request - http response & set-cookie
  • http request & cookie - http response
• session：存在于server边，用于维护用户登录状态，关闭浏览器 一定时间后会失效
  • 由cookie实现
    • server分配给每个session唯一的jsessionID server从redis缓存中验证用户信息密码 key=session id
    • 返回http response set-cookie包含session id client收到后将cookie值存入浏览器 之后对sever的请求会包含该cookie值 = session id

Web页面请求过程

• DHCP配置基本信息(假设主机最开始没有 IP 地址及其它信息)
  • DHCP udp broadcast - DHCP server offer - select IP - ack(assigned ip, dns server ip, 网关ip, 子网掩码)
  • 因为我们广播过了 ethernet learning switch knows host’s <MAC, link>
  • DHCP ack到达主机，主机得到ip地址 DNS服务器地址 网关IP 子网掩码 完成配置
• 需要知道域名IP地址, 先看DNS缓存(browser-os-router-isp), 如果缓存没有, DNS根服务器查询IP 迭代或递归的 从顶级域名到次级域名
• 得知ip地址，主机通过浏览器和服务器三次握手生成一个 TCP socket，向服务器发送HTTP GET
• 层层路由 (通过IP获取设备MAC-ARP broadcast & responds) 路由取决于要不要跨网 涉及不同协议
• 到达服务器，服务器从socket读取 HTTP GET 报文，回复 HTTP 响应报文，将 Web 页面内容放入报文主体中，发回给主机。
• 浏览器收到 HTTP 响应报文后，抽取出 Web 页面内容，之后进行渲染，显示 Web 页面。

缓存

• 使用代理服务器或client浏览器进行缓存
• http 1.1 使用cache-control字段控制缓存 no-store no-cache(使用缓存先验证有效性) private public
  • max-age: 可在server缓存最大时间 expires 过期时间
• 验证缓存是否有效：If-none-match: + etag: 资源的唯一标识 备用方案：last modified

OS

进程线程

1. 进程是资源分配的基本单位：正在执行中的指令和上下文。实体：pcb
2. 上下文：pcb里的内容 对应着 用户堆栈 内核堆栈 代码段 寄存器
3. 进程切换=上下文切换成本高 IPC通信成本高且困难 故引入线程
4. 线程同进程内一个执行单元/可调度实体 共享同进程资源：代码段，堆，pid, open fds, 当前目录, 用户和用户组id
5. 线程独立内容：tid, 寄存器(pc, ip, esp)，本地栈
6. 用户内核线程管理取决于内核支不支持内核级线程：多对1，1对1
7. 并行parallelism强调多核和硬件支持是并发的子集: 并发concurrency仅表示多线程/多进程交替执行，不要求同时，也不限定cpu数量 = 同时处理多任务 vs 轮流处理多任务
8. fork COW
   • 实现：把页表里某些页标记为
     只读，count references 只有当write实际发生才分配新页进行拷贝
     其他例子：内存的获取：弄一页对应全0的物理内存共享给所有malloc但还没写的引用，使得系统有更多可用虚拟内存

6种IPC方式

Pipe ⾮非命名管道，⽣命周期属于对应的⽗⼦进程

Named Pipe 命名管道(FIFO)不同于无名管道之处在于它提供了一个路径名,与之关联， 以 FIFO 的⽂件形式存在于文件系统中，这样，即使与 FIFO 的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过 FIFO 相互通信，因此，通过 FIFO 不不相关的进程也能交换数据。 常用于客户**-**服务器应用程序中，FIFO ⽤作汇聚点，在客户进程和服务器进程之间传递数据。

1
2

int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

Message queue 消息队列列，主要是提供⼀一种异步通信方式，消息被保存到队列里，接受者有需要就取回 有很多开源的实现:Apache activeMQ rocketMQ 但是异步的缺点是 接受者要进行polling 轮询操作才能接受到最近消息。 优点:⽐信号传递更多信息， ⽐管道 可以提供有格式的消息 不需要同步。
Semaphore
Shared Memory 实现困难 要os层面支持 而且要同步不同进程对内存的访问
Socket 不同机器

调度

• 合作机制：中断interrupt
  • 硬件设备中断：异步的到来 但会被同步 timer / io设备等
  • 软件中断：同步的 系统调用或异常(trap实现)。均有handler处理
• cpu虚拟化：公平，高效，安全的分配计算资源
• 安全机制：用户内核双态转换 通过系统调用作为interface 涉及cpu上下文切换
  • 系统调用由trap机制实现 通过索引syscall table呼叫对应trap
• 调度: 在io的时候充分利用cpu 快速响应=RR=高周转时间 tradeoff 可调度进程在ready queue里
  • 批处理：需求-高吞吐量/短周转时间
    • FCFS 非抢占 护送效应“短等长”
    • SJF 非抢占 长作业饥饿
    • SCTF 抢占 贪婪 较优
  • 交互式系统：快速响应
    • RR 抢占 低响应时间 高周转时间 时间片太小 上下文切换开销大 太大 不能保证实时性
    • MLFQ 可抢占 同时保证吞吐量和响应性 多级队列 高级有先同级RR 用完demote 周期性boost防饥饿
  • 实时系统： 一个确定时间段内响应
    • 多用抢占式保证及时响应

并发控制

• cpu pipeline有效提高性能 但有pipeline hazards问题:

  • 数据依赖hazards | 分支hazards

• 解决方式：cpu指令重排序/乱序执行 | 分支预测

• 缓存不一致：多核cpu上多级缓存不同步

• 内存可见性/一致性问题：缓存内容未同步至主存 cpu编译器指令重排 内存乱序访问

• 内存屏障: 编译时防止指令重排 运行时保证内存可见性

• 锁实现

  • 软件：困难 peterson算法 过时 现代处理器会乱序执行
  • 硬件:
    • 原子操作：
      • TestAndSet xchgl 更新并返回旧值供外层循环检测
      • CompareAndSwap CAS 满足期望值则更新。返回旧值供外层循环检测 cmpxchgl
      • FetchAndAdd xaddl 加上1个数 返回旧值共外层循环检测
    • 内存屏障

• 锁类型：公平=无饥饿

  • 自旋忙等待：需搭配抢占式调度 适合多核短持锁时间 饥饿
  • yield自旋：自旋很短时间然后yield 减少了响应时间 饥饿
  • 排号自旋锁: 使用faa，新来拿号，不到回合自旋，fifo公平 饥饿 | 改进：排号yield
  • 队列锁: os支持 饥饿者扔到waiting queue挂起 锁可用再放回ready queue 公平
  • 混合锁: 定时自旋+队列 linux futex 公平

条件变量，管程，信号量，协程

• cv: 条件等待队列

  • wait(mutex,cv) 放锁挂起caller，醒后拿锁返回
  • signal(cv) 唤醒一个挂起的线程

• sv：用于检测状态变化 从而进行wait/signal

• monitor: mutex + cv + sv 任何时刻只有1个线程进入管程 属于高级同步原语

  • mesa: 唤醒和线程恢复执行非原子 sv可变 需while检测
  • hoare: 原子唤醒+恢复执行 sv不变 if检测即可
  • java在语言层级上支持通过管程机制同步 同步方式有两种：互斥lock sychronized 合作cv Object.wait( ) Object.notify( ) 每个java对象都有一个锁和cv
  • 2 cvs [empty + fill] + 1 mutex 解决pc问题
    • p wait(empty, mutex) put(i) signal(fill)
    • c wait(fill, mutex) get() signal(empty)

• semaphore: 初始非负的同步计数器 power(sem) = power(cv + lock)

  • –wait: sem-- <0挂起 >=0通过
  • signal: sem 唤醒一个挂起的线程
  • 0=占用 正=最多几个线程同时访问 负=等待中线程数量
  • sem(1) = mutex, sem(0) = cv, sem(可用资源量) = 共享资源访问控制
  • 3 sem 解决pc问题

• 2 sem read lock + write lock + reader_counter 实现读写锁
  - 读锁：拿起rl, [若reader_counter=0,拿起wl], 放下rl 同理释放
  - 写锁：拿起wl，同理释放

• 协程：用户态特殊函数 可挂起恢复 threadlocal不需要同步 多协程-串行执行

死锁

• 哲学家就餐：不可同时拿左手叉子 会造成环形等待 只让最后一个哲学家先拿右手叉子即可破解环形等待 | 原子化吃饭
• 条件与预防 | os调度预防：银行家算法
  • 互斥: 获得资源的独占控制 | 预防：不使用锁
  • 占有且等待： 拿着这个还等别的 | 预防：2 phase locking或大粒度锁
  • 不可抢占 | 预防： 得不到锁就释放资源
  • 环形等待 | 预防：决定好锁获得顺序
• 解决：
  • 鸵鸟策略
  • 检测 | 恢复：抢占，回滚，kill，重启系统
    • 单个资源：资源waits-for图环判断(拓拓扑排序/dfs)
    • 多个资源：超时检测 标记清除[满足所有可满足+释放资源 长时间不可满足=死锁]

内存管理虚拟化

• 动态加载: 调⽤时加载 lazy loading | 动态链接: 函数执行时lazy定位和链接

• 静态重定位: 进程装⼊入内存前一次性完成逻辑/物理地址的变换 固定的不可变不安全

• 动态重定位：内存虚拟化 访问内存前转换

• 内部碎片： 分配单元内部的浪费 如padding | 外部碎片：对于os的无法被分配的小内存洞

• 虚拟化内存：物理内存通过分页分段 + on-demand paging映射为更大逻辑内存

• 页表：映射关系 + 元信息

• 分页：逻辑和物理空间分为固定大小页 4KB=blocksize of disk

  • 消除物理内存外部碎片，造成逻辑内存空间连续的假象
  • 按需置换提供更多可用虚拟内存

• 分段：地址空间分段code, stack,heap 每个段分配一些固定大小页，每段都有对应页表

  • 模块化方便共享保护

• 分页分表合用好处：段自由生长，模块化方便共享保护，稀疏地址空间有效减少页表大小

• TLB: cpu上缓存 mmu组件 含最近访问页表项翻译内容 减少内存访问

• MMU: cpu上负责逻辑物理地址转换的部分 table walk unit + 多个tlb

• 页置换策略：按需加载：代价page fault 提前加载：只适用于sequential workload 可与用户暗示结合advise

  • OPT: 未来最⻓长时间不不⽤用的 理论最优不实际
  • FIFO: 进入内存最久的 可能把最常用的踢掉
  • LRU: 若workload合适 近似opt 但实现困难 要维护一个所有页面链表
  • Clock: LRU近似 遍历环形buffer ref_bit=0停 清除经过的1

文件系统和Linux

• 硬连接/实体链接: 两路径同inode号 不可链接⽬录/跨文件系统 ln file hardlink

• 软连接/符号链接: data block指向路径 ln -s file softlink

• fd_table - file table(各种访问模式read/write/r&w) - inode table | stdin out err 0 1 2

• sigchld: 供父进程用wait/waitpid等子进程的信号

• 孤儿进程：父进程先退出 子进程仍在运行

• 僵尸进程：⼦进程先退出 子进程资源未释放。处理：kill⽗进程使之成为孤⼉ init会回收资源。

• 

数据库架构

• 储存管理storage manager： 将数据库文件以数据库pages形式表示 管理pages读写 pages内可用空间使用 数据库的一页通常和os虚拟内存中的页或硬件的页不同 大小取决于数据库设置
  • 文件的表示形式：heapfile sortedfile 说的是pages内记录有序或无序
  • pages的管理：链表 或 page directory（一个包含所有pages元信息的特殊page）
  • 不同数据类型的表示 固定长度的整数浮点数 不定长度的VARCHAR TEXT BLOB。 数据库系统元信息表
  • 储存模型：row-store适合OLTP workloads, column-store适合OLAP workloads
• 缓存管理 buffer manager 管理数据库缓存池(磁盘中读来的数据库页)
  • 实现：使用哈希表维护当前内存中的页 每个页被修改了就要标记为脏, 此外还有pin counter计数正在使用他的线程数量 正在使用中的页不可以被淘汰
  • 策略：LRU-k 普通的LRU和clock会存在sequential flooding问题：顺序扫描冲掉缓存中所有内容
  • 优化：顺序读取情况下根据query plan预读
• 解析引擎SQL parser：创建语法树 制定logical query plan & physical query plan(如各种join算法block nested join, hash join)
• 优化器衡量不同plan的优劣: cost-based search, 抽样统计, 大的策略是尽量走索引。
• 执行引擎: 按照query plan从上到下执行
• 锁管理： HashMap<obj_name, <granted_set_txns, lock_mode, wait_queue> + lock upgrade等多粒度锁控制
• 日志管理：UNDO log: 未完成/aborted事务 REDO log：
  • 失败-事务失败 系统失败
  • 策略：
    • shadow paging(COW)
    • Write-Ahead Logging 每个log entry:<txn_id, obj_id, before_val, after_val>
      • 周期性设置检查点将内存中内容flush到disk 作为redo undo操作新起点
      • physical logging 记录在数据库页的位置 logical logging 记录高层的操作如insert delete update和元数据
• 容灾机制 ARIES: analyze WAL records + redo starting from a check point + undo uncommitted txns
• 索引管理
• 权限管理

Workloads: OLTP OLAP

• OLTP online transaction processing （最常见）例如亚马逊购物车界面 只以事务方式简单查询语句访问/更新数据库的一 小范围数据 较少读 较多写 简单查询
• OLAP analytical 已经通过oltp取得了数据 通过复杂查询语句在大范围内 进行数据分析 通常不涉及更新数据 kept query by oltp通常以只读方式提供 大范围数据 较多读 较少写 复杂查询
• HTAP hybrid transaction analytical 中间位置， 混合workload
• oltp at frontend => extract&transform&load => olap at back end with datawarehouse
• htap db: oltp and olap at same side complicated not easy to build

关系数据库设计理论

函数依赖,异常,范式

• X函数依赖于Y 意味着Y独特的决定X Y是当前表的候选键

• X完全函数依赖于Y意味着X不函数依赖于Y的任何子集

• X部分函数依赖Y = Y的一部分可以决定X Y作为键存在冗余

• X->Z，Z->Y，X->Y是传递函数依赖

不符合范式的关系，会产生很多异常，范式可以解决异常：

• 冗余数据栏目：例如某个信息在不同行出现了多次 该schema设计有问题
• insert异常：因为冗余信息的存在 我们想插入一条记录 就要包括/编造这些无关冗余信息 这往往不现实
• delete异常：删除一个含冗余信息的行，导致丢失同行其他关键信息。
• update异常：只改了一条记录中的信息，其他记录中相同的信息忘了改。

通过无损分解消除没必要的函数依赖 产生更合理的schema 高级别范式依赖于低级别范式

• 1NF：原子属性不可分。
• 2NF：1NF+消除部分函数依赖 （每个非主属性完全函数依赖于主键）
• 3NF：2NF +消除传递函数依赖（非主属性不存在“传递函数依赖”）

数据库并发控制

事务管理中的ACID原则

• Atomicity 原子性 “all or none”: 事务所做操作要么全部提交要么全部失败回滚
  • 实现： 日志undo log, Shadow paging(COW)
• Consistency 一致性 “looks correct”
  • 数据库一致性 仍遵循完整性约束 未来事务能看到过去事务造成的后果
  • 事务一致性 事务前后数据库内容一致 一致意味着多个事务访问相同数据得到相同结果
• Isolation 隔离性 “lives alone”: 事务所作修改commit前对其他事务不可见
  • 两种类别的并发控制协议来保证隔离性
  • 悲观 从最初就避免问题的发生
  • 乐观 设定某种事务执行顺序，假设冲突发生不常见，发生后再处理 lazy
• Durability 持久性 “survives failure”: 事务提交的修改应被持久化，即便系统崩溃也不受影响 redo log

串行情况下 原子性=>一致性 并行情况下 原子性+一致性=>一致性

一致性冲突

• 读写冲突：
  • 不可重复读 “non-repeatable read” 两个读的中间数据被另一个事务覆写并提交 导致第二次读的同一行值不同
    • transaction reads committed UPDATES from another transaction. The same row now has different values than it did when your transaction began.
    • A non-repeatable read occurs, when during the course of a transaction, a row is retrieved twice and the values within the row differ between reads.
  • 幻读 “phantom read” 两个读的中间被另一个事务插入/删除行并提交 导致第二次读返回的行不同
    • Phantom reads are similar but when reading from committed INSERTS and/or DELETES from another transaction. There are new rows or rows that have disappeared since you began the transaction.
    • A phantom read occurs when, in the course of a transaction, two identical queries are executed, and the collection of rows returned by the second query is different from the first.
  • 避免不可重复读锁行就足够，避免幻读需要锁表
• 写读冲突： 脏读 “dirty reads” Reading uncommitted data 读了另一个事务没有提交的数据
• 写写冲突：丢失修改 “lost updates” overwriting uncommitted data 一个事务覆盖另一个事务没有提交的数据

隔离级别

• RU: 事务中的修改，即使没有提交，对其它事务也是可见的。
• RC: 一个事务只能读取已经提交的事务所做的修改。
• RR: 保证在同一个事务中多次读取同一数据的结果是一样的。
• S: 强制事务串行执行，这样多个事务互不干扰，不会出现并发一致性问题。从MVCC并发控制退化为基于锁的并发控制。不区别快照读和当前读，所有的读操作都是当前读，读加读锁（S锁），写加写锁（X锁）。在该隔离级别下，读写冲突，因此并发性能急剧下降，在MySQL/InnoDB中不建议使用。
• 冲突可串行：一个调度是冲突可串行的意味着可以将其转换为串行调度
  • 依赖关系图一定无环
  • 这就是SERIALIZABLE隔离级别：将事务完全调度为串行执行

悲观并发控制

二段锁

• Pessmistic 悲观的 假设事物存在高度竞争 使用锁 因此安全程度高 但并发能力会有所限制 (not allow all serializable schedules)

• 写锁互斥 X 读锁共享

• 2PL 总是保证冲突可串行调度 always gurantee conflicts-serializable schedule = grantee serializable schedule

• 二个阶段 “/\”

  • 生长期 只允许拿锁
  • 收缩期 一旦释放第一个锁 进入收缩期
    • 只允许放锁 或不放锁
    • 不允许拿锁

• 问题: 脏读情况下cascading abort例如t1写 t2读 此时t1还没commit便abort 此时t2不得不abort…如果t2也写了还没来的及提交后面还有读的那这个反应会连锁下去

  • 解决: Strong Strict 2PL (SS2PL) 一个事务提交/abort后才允许放锁 一次放完

• 死锁处理:

  • 检测:
    • 后台周期性在waits-for graph中判环 / 超时检测
    • 选择一个victim回滚打破环，选择标准和rollback程度取决于具体设计
  • 预防:
    • 通过时间戳赋予优先度 FCFS
    • 一个人得到锁后其他所有人进入等待队列 直接严格避免死锁发生

锁粒度和层次

MySQL 中提供了两种封锁粒度：行级锁以及表级锁。
应该尽量只锁定需要修改的那部分数据，而不是所有的资源。锁定的数据量越少，发生锁争用的可能就越小，系统的并发程度就越高。
但是加锁需要消耗资源，锁的各种操作（包括获取锁、释放锁、以及检查锁状态）都会增加系统开销。因此封锁粒度越小，系统开销就越大。
在选择封锁粒度时，需要在锁开销和并发程度之间做一个权衡。

• 一个事务想要更新1billion tuples = ask for locks 1 billion times VERY SLOW
• 我们需要锁的层次来展现 行级表级处分别发生了什么

如何更方便的进行多粒度封锁： 意向锁

• 意向锁Intention lock: 表示想要对表加锁，与"锁提升机制"结合，细粒度锁太多时动态的分配可用的粗粒度锁 大大减少lock manager需要处理的锁的请求数量

• 意向锁在高层如表级告诉我们下面有什么样的锁 通过兼容矩阵 可以从hierarchy高处快速判断能不能读/写下层具体行的数据

• Intention-Shared (IS):下面某个地方有读锁

  • Intention-Exclusive (IX):下面某个地方有写锁

• Shared+Intention-Exclusive (SIX): 整个子树可共享读，下面某个孩子有写锁

• 表级锁兼容矩阵：
  | | X | IX | S | IS |
  | ---- | ---- | ------ | ---- | ------ |
  | X | | | | |
  | IX | | OK | | OK |
  | S | | | OK | OK |
  | IS | | OK | OK | OK |

• 表和表：任意 IS/IX 锁兼容: != 真正加锁 | S 和 IS 兼容

• 表和行：表级 IX 和行级 X 兼容：两个事务先对同表加IX锁，然后可以对同表两个不同数据行加 X 锁

Mysql事务四级封锁: 强2PL+读写锁

Mysql InnoDB引擎采用强2PL，根据当前隔离级别自动加锁=隐式锁定

• 一级 修改加写锁，事务结束放写锁 = Read Uncommited级别
• 防止写写冲突问题Lost updates
• 二级 一级 + 读加读锁，读完放读锁 = Read Commited级别
• 防止脏读问题Dirty Reads
• 三级 二级 + 读加读锁，事务结束放读锁 = Repeatable Reads级别
• 防止不可重复读问题unrepeatable reads
• 四级 全表锁，事务结束放锁 = Serializable级别

显式锁定：

1
2

获取读锁： SELECT ... LOCK In SHARE MODE; 
获取写锁： SELECT ... FOR UPDATE;

乐观并发控制

• 不使用锁：对common case的一种优化, 大部分情况下事务只需持续很短时间，冲突没有那么容易发生。所以我们可以使用比较懒的策略，假设冲突不会发生，检测到发生再进行补救 如选择abort

根据ACID原则 并发情况下实现一致性需要原子性和隔离性, 原子性通过CAS等原子操作解决, 隔离性通过时间戳机制赋予事务执行顺序

目前有三种主流乐观并发控制策略

• 基于时间戳的 事务用时间戳编号排序 最早OCC论文内容
  • 读写阶段：将更改存在私有空间
  • 验证阶段：验证是否和其他事务冲突再提交
  • 写阶段：验证成功 将私有空间更改同步至主空间 否则abort
• snapshot isolation: 朴素mvcc
• CAS: 不仅是一种策略 也是一种实现
  • 满足期望值(没有被占用)则更新。返回旧值供外层循环检测
  • 外层while CAS(flag, 0, 1) == 1: Old value is 1, lock held by someone else, spin and wait. Otherwise go ahead do modification
  • 硬件支持：x86架构下指令为cmpxchgl

MVCC多版本并发控制

• 当前最常见的数据库并发控制方法. 非常适合读多写少的OLTP workload 朴素MVCC解决了在REPEATABLE READ和READ COMMITTED两个隔离级别下读同一行和写同一行的两个事务的并发问题。

• 朴素的MVCC在数据库领域可以说是乐观的 是不用锁的 单纯使用快照方式实现读写分离 类似COW

mysql默认隔离级别为RR， InnoDB的mvcc是mvcc的改进版 引入(next-key lock]解决了朴素mvcc的幻读问题 能够实现RC RR S三个隔离级别

• 即便是改进版MVCC也只是处理读写或写读的冲突属于整个四种Isolation level处理的问题。写写冲突 lost updates 一般通过first commiter/first updater win 解决

• 读=不加锁的非阻塞读 读旧版本快照 | 写(插入删除更新)=加锁更新一个最新的版本快照

• 系统版本号SYS_ID：通过时间戳机制单调递增分配

• 事务版本号TRX_ID：事务开始时的系统版本号

• 每个事务都有这两个版本号并被记录在undo日志中

• RC RR隔离级别下使用版本链 多个版本的快照存在undo日志中，日志通过回滚指针把一个数据行的所有快照连起来

• MVCC 维护一个read view结构 当前未提交事务列表trx_min_id…trx_max_id 一个数据行快照的trx_ID <min则可用 >max则不可用 位于中间取决于当前隔离级别 若该快照不可用则要沿undo日志中版本链找前一个可用快照

• 快照读select…不需要锁，当前读（数据修改insert/update/delete）操作需要锁

• innodb为了解决rr级别下当前读(数据修改)的幻读问题，使用了next-key lock

  • 本质上是gap lock+ record lock
  • record lock锁定记录上的索引相当于一个单点锁 (使用unique index访问的情况)
  • gap lock锁定record lock单点之前的开区间(使用non-unique index / no index访问的情况)
  • (10, 15] 每一个next-key lock锁定一个左开右闭区间

索引和储存

B,B+,Hash,Bit Map

• 哈希索引高效等值查询 位图索引适合静态low cardinality数据

• B树平衡多路查找树 m度=m指针 m-1个键值(实际数据记录) 叶子层并非包括全部数据记录 节点半满压缩高度 节点内有序 叶子结点位于同层

• b+树 叶子层(节点内外均有序)fixed-size数组的链表保存全部数据记录+非叶子层有序索引只存搜索键值 (储存指针多一个)

• b+树与b树区别：

  • b+叶子层有序fixed-size数组链表同时支持高效等值查询和范围查询 （节点内有序可以2分搜索）和bulk-loading (每个固定gap选最小值作为搜索键值 从下到上建树)
  • 单叶子储存节点更多 高度压缩更明显 IO次数更少
  • 所有查询都要找到叶子结点 查询性能更稳定

• 为什么适合储存：非平衡树可以直接排除-skew情况下退化为链表 红黑只有2叉不适合高度太高io次数太多文件系统 b+结合b树优点节点半满多路平衡查找树 高度低IO次数少 同时叶子层支持外排序后bulk-loading 更适合文件系统和数据储存 更好利用磁盘预读性质

索引

为什么要使用索引？避免全表扫描，使用更好的索引-减少数据访问量

• 索引键=索引项 搜索键：我们要查找的栏目名称
• clustered index / primary index / sparse index 主索引：记录顺序和索引键相同 整个文件要按索引键排序 indexed-sequential file 只能有1个主索引。例子：有序文件/hash表上的索引
  • primary index指用含主键的集合作索引键的索引 一般情况下将primary index和clustered视为相同
  • 无论索引键是否有重复 可以是dense(trivial)也可以sparse 因为完全有序 可以每个disk block建一个索引指向第一个anchor record即可 找到合适位置后顺序扫描 因此一般默认为sparse
    • 有序= 高效的范围查找 IO次数少
    • 因为有序 插入删除更新 维护成本高：有空间直接插入 否则维护overflow chain 时间长了性能下降严重 因此多数数据库会定期重新组织记录结构将overflow chain展开 但这也要开销
• non-clustered index / secondary index 辅助索引：索引键和记录顺序不同
  • must only be dense !
  • 索引有序 按辅助索引键排序 不给记录排序 那是主索引的事！！！
  • 可能涉及到不同磁盘区块 = 更多io + 寻道时间 更慢
  • 通常使用间接索引的方式避免重复key问题 这样最底层索引相同key有序排列 底层之上高层实现稀疏索引
  • sparse辅助索引没有意义 因为数据记录无序 什么都找不到 最后依赖全表扫描或主索引
  • 例：mysql中当查询列上没有辅助索引 就走主索引
• dense index: 索引键出现在每个含搜索键值的记录上,
  • 有序情况下支持范围查询 二分查找
  • 有序情况下非常高效：1 disk IO = load everything into memory until exceed range
  • 无序情况：需要全表扫描 不适用 现在的索引尤其是b+tree都是有序索引
• sparse index: 索引键出现在部分含搜索键值的记录上 必须是主索引 记录要按索引键顺序排序
  • 1 key - ptr pair per disk block 1st record = anchor record
  • 有序情况下 可用二分查找 MORE space-memory effcient
• 多列联合索引
  • 通常策略：按最左边建立b+树有序索引 索引按优先级左到右字典序排序

Mysql索引

InnoDB支持 B+树 哈希 全文索引 MyISAM支持全文索引 空间数据索引

• DDL部分 声明的key会自动创建辅助索引 主键会创建主索引
• 联合索引匹配遵循最左匹配原则 idx1(a,b,c,d)
  • 从左向右匹配直到遇到范围查询<,>,between,like e.g. a=3,b=4,c>5,d=2 d会用不到索引
  • 若查询均为等值查询 = , in 则可以乱序 如查询 a=1, c=3,b=2 (a,b,c) 甚至可以省略前面部分 直接查询c = 3 查询优化器会自动修改
• 原因：B+树有序索引会建在a上 剩余内容b,c,d在前者基础上依次排序 叶子层记录以有序数组形式存在叶节点内 有序查询找到a后依次向后按序匹配
  • b的有序是基于a的有序 因此等值查询不受影响
  • 当a为范围查询时,e.g. a>1 的结果是一个多条记录的范围 此时b相对于这个范围是无序的 无法使用索引
• 索引是建立越多越好吗？
  • 数据量小的表不需要索引 增加额外开销
  • 数据修改要维护索引 = 更多维护成本

Mysql引擎

SQL调优

索引调优基本heuristics

• 修改sql尽量全走索引（覆盖索引）没索引的情况下考虑建合适的辅助索引
  • innoDB辅助索引 不覆盖会 访问主索引
  • myisam只缓存索引 不覆盖会 额外读文件-全表扫描-系统调用 page replacement
• 选择性强的索引放前面，索引全覆盖的情况下尽量将范围查询移到末尾 遵循最左匹配原则的原理 避免查询不走索引
• 不要把想走索引的搜索码放表达式里 如actor_id + 1 = 5; 是错误的 不会走索引
• 性能： 1个多列索引>多个单列索引
• 较长类型如blob, text, varchar 应使用前缀索引 只索引前几个字符

需要注意的

• mysql optimizer会消除没有必要的数据行访问 因此不一定会走主索引或副索引

• 找慢的query show variables找到系统变量long_query_time slow_query_log(默认off)

  • long_query_time 超过则加入slow query log, set slow_query_log为on

• 查看query plan, explain query显示栏目

  • id=子查询执行顺序 type=找到数据行/join的方式: all全表扫描 index扫了index树
  • extra里面有各种状态比如using index = 索引完全覆盖了查询 using index for group-by部分使用索引等 using file-sort用了外排序（比如order by） using temporary 用了临时表

• explain xxx force index(primary) / force index(xxx) 尝试使用别的索引

• 加索引 alter table xxx add index idxname(字段名); 或者在ddl里create index xxx

查询优化

• 切分大的事务(查询) 避免小的饥饿 或使用多粒度意向锁
• 大连接查询切分为 单表查询 + 关联 更好利用已有缓存 提高自身缓存可用性 减少锁竞争

分布式和系统设计

模型和概论

• 重要假设: 容错模型 假设我们可以相信节点(we write them)（若不相信需要使用拜占庭容错协议 blockchain）
• 基本架构
  • shared everything: 单点
  • shared memory: no one does this, need OS support 多用于HPC超算中心
  • shared disk: common for cloud DBMS
  • shared nothing: most common. better performance, hard to manage ex. most nosql sys
  • 同构vs异构：集群内节点可否执行相同任务
• 两种设计monolith vs microservice 组件耦合程度
  • monolith: 单机负责多种功能
    • 适合小团队
    • 简单： 更少解耦，维护
    • 快：少/无 RPC
    • 部署复杂
    • 单点故障波及范围大
  • microservice：单机负责单一功能 + 小型分布式缓存数据库 适合大型系统
    • easy to scale (easy for new team member)
    • decoupled : easy to reason about
    • hard to design: s1 only talks to s2 = they need to be merged
• 两种拓展模型

• 优化方法

  • 优化单点能力：vertical scaling
  • 解决单点故障 horizontal scaling - 备用服务器转换 / replication
  • 多节点集群负载均衡 减少单点负荷: load balancer responsible
  • 微服务架构提高可拓展性: 解耦系统组件, 各司其责
  • 日志和评估系统

• 事件驱动模型: ex. git, game server csgo headshot

  • publisher-subscriber: relies on message queues to pass events
    • Good: decoupled, easy to identify failure ONLY SPOF, easy to add / remove
    • Bad: extra level of indirection = slow, does not gurantee strong consistency, cost for learning and maintaining message queues

原则和协议

• CAP： 分布式系统不能同时满足一致性 可用性 分区容忍性

  • Consistency一致性：保持数据一致和最新 Linearizability
  • Availability可用性：系统可用时间占总时间的比值 All up nodes can satisfy all requests
  • Partial tolerant分区容忍性：局部网络故障消息丢失时能否继续提供一致性和可用性服务 still operates despite message loss
  • 分区容忍性一般必不可少 CAP实际上是在一致性和可用性CA间进行权衡
    • 不可以cp 因为存在k-safety限制 不得不放弃可用性

• BASE理论 CAP的拓展 CA的协调结果 Basically avaiable, Soft State, Eventually Consistent

  • ACID要求强一致性(数据更新后 用户能够读取到最新值) 用于单机传统数据库
  • BASE要求最终一致性 中间软状态可以看情况适当妥协 保证始终提供核心基础服务即可

• 分布式死锁检测 周期性union所有waits-for-graph

• 如何实现共识 agree on commit abort ? quorum (voting)

• 分布式事务协调 原子性提交相关协议2PC, Paxos, Raft, ZAB

  • 中心化: global traffic cop as middleware / coordinator route query as needed to partitions
    • 2PC: 相当于paxos的弱化版

      • prepare phase: 协调者询问参与者事务是否准备好提交 参与者投票Y/N 全票=提交

      • commit phase: 协调者决定结果 如果可以就都提交-否则回滚 参与者回复ack

      • 可以和 2PL结合

      • 问题

        • 不能解决dead coordinator问题 paxos 可以解决
        • 同步过程中阻塞问题 要等待其他参与者响应
        • 网络问题导致只有部分参与者commit ？
        • 一个节点失败=失败 容错率低
  • 去中心化: 节点自行组织产生分布式共识
    • 没有协调者
    • 服务器和master node交流 如果是同构架构 所有节点都可以是master node
    • query request发送到master node / partition
    • 提交时master node和其他节点交流safe to commit？ 投票选择
      • paxos 分布式共识算法 无需全票 多数投票通过即通过 如果多数存活non-blocking 高容错 解决dead coordinator问题
        • proposer 提议提交 OK? 1个或多个proposer
        • acceptor reply 只需多数即可提交 see n+1 reject n
        • learner: 被告知投票的结果，不参与投票过程。
        • 持续处理新来的proposal 即便之前的已经同意 也当即拒绝之前的proposal和commit请求
        • 解决饥饿问题：multi-paxos 选择1个leader, 规定若如果只有一个proposer propose阶段可以跳过 周期性选举当前leader

• raft 选举主节点

组件和机制

• 异步消息机制： message/task queue

  • 接受任务后分配给不同服务器，若花时间太长=dead，assign to next server to avoid duplication

• 分布式缓存

  • 缓存：avoid network calls, repeated computation, db load
    • 置换策略不好或缓存太大都会导致缓存无用
    • thrashing: constantly input & output withhout using the result = sequential flooding ?
    • server-side, client-side : fast but cache consistency?
    • 全局缓存global cache (redis): 解耦！微服务！
      • consistently accurate but slightly slower
      • can scale independently
    • write through: …on hit, update cache & database keep db always consistent but slow
    • write back: write to cache, mark dirty(inconsistent). lazily update db when dirty-cache entry is evicted db can be temporarily inconsistent but fast
    • hybrid: 重要的更新write through, 批缓存不重要的更新到cache, 低峰时间一次性同步到db

• 分区 usually logical

  • 垂直切分/naive table partitioning ：如果查询分布不均匀集中到一个点 单点计算能力可能扛不住
  • 水平切分/round-robin sharding / load balancing ：query fragment分布到集群不同节点上作相同处理最后合并 有效缓解单数据库压力 多采用哈希取模方式划分
    • 可拓展 无重复的 一致性哈希：集群增删一个节点后如何避免rehash&trash our caches？
      • 绕环线性探测到下一个节点
      • 节点少数据倾斜？每台服务器做多个虚拟节点replication 实现相对均匀分布
      • 哈希函数不好 服务器分布不均not uniformly distributed：
        • 完美哈希 使用哈希函数族（嵌套一致性哈希 + multilevel sharding ）
  • 数据库的分库分表：大连接慢 可与主从复制结合提高分片容错 可与和索引结合 consistency is hard 建议优先使用nosql等其他系统再考虑这种primritive
    • 表的垂直切分：一张表按列切分成多个表 分到不同库里
    • 表的水平切分：同一个表中的记录拆分到多个结构相同的表中 可以分布到集群不同节点上 配合服务器的负载均衡 减少单库压力

• 复制 Replication

  • 创建冗余备用节点储存相同信息提高系统可用性

  • k-safety: 最少k可用复制品 #replicas < k DBMS halts go offline

  • 主从架构

  • 更新集中到master

  • master更新内容到replica

    • 更新方式
      • 同步： 主等待从完成日志并回复ack 保证强一致性strong consistency 数据是即时的
      • 异步：不等待 主直接返回ack给client 保证最终一致性eventual consistency 数据snapshot
    • 更新timing
      • 连续的：生成日志=》直接发送
      • 提交时
    • 从者主动被动？
      • 主动：事务在从处自行执行 需要检测不同从的结果匹配
      • 被动：事务在1处执行后传递给所有replicas

  • 可允许只读事务访问replica

    • 可实现读写分离: 主服务器处理写操作以及实时性要求比较高的读操作，而从服务器处理读操作。从服务器可以分布到离用户较近的地方 降低延迟 提高用户体验
    • 采用快照隔离能保证弱一致性, 增加冗余提高可用性

  • master故障 选举新master

  • 多主人

    • replica和主人平级（没有主人=多主人）- 事务可在任何replica处更新 replica们自行使用原子性提交/分布式共识协议2PC/Paxos互相同步

  • 网络故障包丢失 分区paxos选主后 split-brain双主如何在网络恢复后同步?

    • 传统/newsql dbms：多数节点连接完好才允许更新 不存在这个问题
    • nosql：需要某种形式上的中心化处理
      • 乐观：选择可用性，牺牲部分一致性，之后在合适的时间自动或人为处理 hazelcast
      • 悲观：选择一致性，牺牲部分可用性，投票下线存在问题的网络分区 mongoDB

• 总结：分区和复制通常一起使用：如水平切分的数据库分布到集群不同单点上 并作复制 复制品可以是slave(主从结构)也可以是master (distributed-consensus based).

No-sql & in-memory DB

• NoSQL: not-only relation: k-v, document(json, csv), graph cassandra redis mongodb

  • 优点
    • 插入删除涉及所有相关数据 此时使用nosql开销较低
    • schema比较灵活 方便更改
    • 内部支持水平切分 scales well
    • built for OLAP
  • 缺点
    • no acid guarantee
    • not read optimized join is hard 涉及大量扫描相关对象
    • no relation no constriants

• In-memoryDB: very modern, lack durability support from ACID, store things in volatile meory. e.g. Oracle IMDB