Lazy loaded image
CMU-15-440
📖Lecture 5 Latency
Words 3433Read Time≈ 9 min
2025-7-19
2025-7-19
type
status
date
slug
summary
tags
category
icon
password
原文

Abstract Concept of a Queue

请求数据包和响应数据包 可能走不同的路线。
Applies to any shared resource
  • wireless network
  • server CPU core
  • server GPU
  • Internet router
  • restroom
  • …
一旦资源被共享，排队延迟便随之产生。避免排队，资源私有。
分布式系统中，几乎所有的资源都涉及某种共享(硬件资源：CPU、GPU、内存、磁盘等等，软件资源：有状态的)。
排队规则不止先进先出（优先级队列等）。(这里可以参考操作系统资源调度策略)
Utilization = fraction of time (percentage) resources is in use 利用率 = 资源使用时间的百分比
Latency = (time from arrival to reach position 1 + service time) 延迟 = 到达时间+服务时间
大多式分布式系统是 FIFO , 不支持抢占式调度。
 
Arrival pattern can take many forms 抵达模式有多种形式
  • uniformly spaced interarrivals 均匀间隔到达
  • Poisson distribution (memoryless) 泊松分布（无记忆）
  • many other possibilities 其他多种可能性
 
Service time distribution can also vary 服务时间的分布也会有所不同
  • constant time 常量时间
  • exponential distribution 指数分布
  • normal distribution 正态分布
  • many other possibilities 其他多种可能性
 
服务时间分布描述的是完成单个请求或任务所需时间的概率分布（如处理一个 API 调用、数据库查询等）
造成的原因有很多：服务器性能、CPU/IO 竞争、网络、代码、负载均衡策略等等…
 
 
Many real-world complications 许多现实世界的复杂情况
  • finite memory for queue - 有限的队列内存
  • flash crowds (spikes)
  • non-stationary distributions 非稳态分布
  • diurnal variations 昼夜变化
      • 负载周期可能有变化
  • pricing-dependent variability 定价相关可变性
  • differential service(aka priority queues) 差异服务
  • …

Relevant SCS Faculty & Courses

相关 SCS 教师和课程
Professor Mor Harchol-Balter
Professor Weina wang
Courses
  • 15-259 “Probability and Computing” 概率与计算
  • 15-857 “Analytical Performance Modeling” 分析性能建模
同为 CMU 的课程
 

Iron Law of Queueing Theory

排队理论的铁律
for any shared resource
  1. Utilization(利用率) (aka ”efficiency”: % use of CPU , network ,disk , etc.)
  1. Latency（延迟）（aka “response time” or “agility”: user experience） 响应时间
  1. Freedom (自由度) (arrival discipline : orchestrated or un-ochestrated )
      2. 这里的 Freedom 应该是到达模式，但是教授将其称为自由度，它表达的是请求资源所受的限制程度。
      📑
      1. 利用率趋近于 100% 时，响应时间趋向无穷大当系统利用率接近满负荷（ρ → 1）时，排队等待时间会急剧增加，导致整体响应时间趋向无穷大。这意味着即使系统的处理能力很强，只要利用率过高，延迟就会显著上升。
      1. 服务时间是响应时间的下限在理想情况下（利用率为 0），响应时间等于服务时间。但随着利用率增加，排队时间会使总响应时间远超服务时间。
      1. 高利用率与低延迟不可兼得分布式系统中，要同时实现高吞吐量（高利用率）和低延迟是不可能的。必须在两者之间做出权衡。
如何用数学方法的去论证这些理论，可选修15-259、15-857
Alas, in real life
  • accountants and CFOS demand high utilization(efficiency)
  • freedom is non-negotiable 自由无条件
  • so ,latency falls victim → long queues and high queueing delays 因此，时延下降 → 长队列和高队列延迟
 
要在不牺牲自由度的前提下实现低延迟，唯一的方法是保持低利用率。

Latency and Bandwidth

延迟和带宽
Delay-Bandwidth product ≈ max number of bits in flight
High value leads to Buffer Bloat
缓冲膨胀
📑
缓冲膨胀是指网络设备（如路由器、交换机）中因过度缓冲（Over-Buffering）而导致的数据包延迟激增和网络性能下降的现象。这种现象虽然能减少丢包率，但会引发严重的排队延迟，尤其在拥塞的网络环境下，会导致交互式应用（如视频通话、在线游戏）的体验急剧恶化。
在分布式系统的所有误解中，最大的误解是：当带宽是问题时却试图改善延迟。而当延迟是问题时，却试图改善带宽。
高带宽 ≠ 低延迟 低延迟 ≠ 高带宽
 

Latency

Latency is the killer , not bandwidth
  • fundamentally more difficult to improve 从根本上更难改进
 
Bandwidth improved through parallelism 通过并行性提高带宽
  • fatter pipes , more lanes on highway ,more checkout clerks at store , …
  • does cost money , but not fundamentally difficult
 
Latency is much , much , much harder to improve
  • typically requires deep structural changes 通常需要深度结构改变
  • e.g shorten distance , increase max speed tolerated , reduce path length 例如，缩短距离，提高最大容忍速度，减少路径长度
 
Many software and systems trends increase latency
  • increased use of layers ( middleware , external libraries (DLLs),VMs,…) 更多层次的使用（中间件、外部库 (DLL)、虚拟机......）。
  • security technologies ( firewalls ,overlay net works ,middle boxes,…) 安全技术（防火墙、覆盖网、中间盒......）。
  • energy savings (buffered packet delivery by access points) 节能（接入点的缓冲数据包传输）
 
延迟比带宽更难改善
在多核服务器上增加更多的核心，实际上提升了服务器的所谓“带宽”，因为它能够并行处理更多的进程，但是其中任何一个进程的执行都需要提高时钟的频率，而时钟频率近来却停滞不前，你可以购买更多的核心，却无法获得更快的时钟频率。如果无法提升时钟的频率，那就必须回头优化程序，减少执行的指令数量，这是一个更棘手的任务。

Impact of Long Latency

Synchronous of RPC becomes intolerable
RPC 同步变得难以忍受
Coast-to-coast Us ≈ 16 ms at speed of light
  • round-trip RPC > 30 ms 往返 RPC
  • large distances (e.g. trans-Pacific) will make matters worse 远距离（如跨太平洋）会使情况更糟
实际上远大于理论值，光在光纤中的传播速度仅为真空的三分之二，实际部署的系统速度远不及光速，这两部分已经增加了延时。
 
30ms is a long time in terms of lost processing opportunity 就损失的处理机会而言，30 毫秒是很长的时间
  • 3 million instructions on an early 1990s processor (100 MIPS)
      • much higher on faster processor and multi-core machines
  • a modern 3GHZ single-core x86 processor is ~1000-1500 MIPS
      • so 30 ms is ~15-45 million instructions(or more, with multicore)
 
Can’t afford to hide real-world asynchrony 无法隐藏现实世界的异步
  • RPC is synchronous abstraction RPC 是同步抽象
  • inadequate for many emerging use cases
  • more complex , asynchronous models needed 需要更复杂的异步模型
  • more difficult to program and get correct 更难编程和保证正确性
 

Takeaway for Public Networks

公共网络的要点
  1. End-to-end latency is Not shrinking 端到端延迟没有缩短
      2. significantly inflated over speed of light
  1. Latency sacrificed to increase capacity (bandwidth) 牺牲延迟以增加容量（带宽）
      2. video delivery is the driver for profitability 视频交付是盈利能力的驱动力
      video传输恰好是一种仅依赖带宽而与延迟无关的工作负载。

Inflation in Fiber Length

忽略……

HF-Trading Fiber(Chicago-NYC)

在金融交易领域，1ms 足以决定胜负。
延迟可以转换成巨额利润。

How Do We Overcome Long Latency?

Solution 1: “Trust but Verify” (optimistic methods) “信任但验证”（乐观的方法）高度针对特定应用;需要应用程序修改
highly application-specific; requires app modifications
 
Solution 2: Cache data (replace remote ops by local ops) 缓存数据（用本地操作取代远程操作） 应用程序透明；不修改应用程序
application-transparent; no app modifications
 
These are complementary solutions 这些都是互补的解决方案
 

Trust But Verify

aka Optimistic methods
optimistic methods of control , 教授使用 Trust But Verify 来描述它
所谓的谓词校验 就是检查前置条件。如果符合就执行。
📑
乐观控制方法通过“信任优先，验证兜底”的哲学，在分布式系统中实现了性能与一致性的平衡。其本质是用事后冲突处理的成本，换取常态下的高吞吐与低延迟。

Abstract Concept of a Queue

请求数据包和响应数据包 可能走不同的路线。
Applies to any shared resource
  • wireless network
  • server CPU core
  • server GPU
  • Internet router
  • restroom
  • …
一旦资源被共享，排队延迟便随之产生。避免排队，资源私有。
分布式系统中，几乎所有的资源都涉及某种共享(硬件资源：CPU、GPU、内存、磁盘等等，软件资源：有状态的)。
排队规则不止先进先出（优先级队列等）。(这里可以参考操作系统资源调度策略)
Utilization = fraction of time (percentage) resources is in use 利用率 = 资源使用时间的百分比
Latency = (time from arrival to reach position 1 + service time) 延迟 = 到达时间+服务时间
大多式分布式系统是 FIFO , 不支持抢占式调度。
 
Arrival pattern can take many forms 抵达模式有多种形式
  • uniformly spaced interarrivals 均匀间隔到达
  • Poisson distribution (memoryless) 泊松分布（无记忆）
  • many other possibilities 其他多种可能性
 
Service time distribution can also vary 服务时间的分布也会有所不同
  • constant time 常量时间
  • exponential distribution 指数分布
  • normal distribution 正态分布
  • many other possibilities 其他多种可能性
 
服务时间分布描述的是完成单个请求或任务所需时间的概率分布（如处理一个 API 调用、数据库查询等）
造成的原因有很多：服务器性能、CPU/IO 竞争、网络、代码、负载均衡策略等等…
 
 
Many real-world complications 许多现实世界的复杂情况
  • finite memory for queue - 有限的队列内存
  • flash crowds (spikes)
  • non-stationary distributions 非稳态分布
  • diurnal variations 昼夜变化
      • 负载周期可能有变化
  • pricing-dependent variability 定价相关可变性
  • differential service(aka priority queues) 差异服务
  • …

Relevant SCS Faculty & Courses

相关 SCS 教师和课程
Professor Mor Harchol-Balter
Professor Weina wang
Courses
  • 15-259 “Probability and Computing” 概率与计算
  • 15-857 “Analytical Performance Modeling” 分析性能建模
同为 CMU 的课程
 

Iron Law of Queueing Theory

排队理论的铁律
for any shared resource
  1. Utilization(利用率) (aka ”efficiency”: % use of CPU , network ,disk , etc.)
  1. Latency（延迟）（aka “response time” or “agility”: user experience） 响应时间
  1. Freedom (自由度) (arrival discipline : orchestrated or un-ochestrated )
      2. 这里的 Freedom 应该是到达模式，但是教授将其称为自由度，它表达的是请求资源所受的限制程度。
      📑
      1. 利用率趋近于 100% 时，响应时间趋向无穷大当系统利用率接近满负荷（ρ → 1）时，排队等待时间会急剧增加，导致整体响应时间趋向无穷大。这意味着即使系统的处理能力很强，只要利用率过高，延迟就会显著上升。
      1. 服务时间是响应时间的下限在理想情况下（利用率为 0），响应时间等于服务时间。但随着利用率增加，排队时间会使总响应时间远超服务时间。
      1. 高利用率与低延迟不可兼得分布式系统中，要同时实现高吞吐量（高利用率）和低延迟是不可能的。必须在两者之间做出权衡。
如何用数学方法的去论证这些理论，可选修15-259、15-857
Alas, in real life
  • accountants and CFOS demand high utilization(efficiency)
  • freedom is non-negotiable 自由无条件
  • so ,latency falls victim → long queues and high queueing delays 因此，时延下降 → 长队列和高队列延迟
 
要在不牺牲自由度的前提下实现低延迟，唯一的方法是保持低利用率。

Latency and Bandwidth

延迟和带宽
Delay-Bandwidth product ≈ max number of bits in flight
High value leads to Buffer Bloat
缓冲膨胀
📑
缓冲膨胀是指网络设备（如路由器、交换机）中因过度缓冲（Over-Buffering）而导致的数据包延迟激增和网络性能下降的现象。这种现象虽然能减少丢包率，但会引发严重的排队延迟，尤其在拥塞的网络环境下，会导致交互式应用（如视频通话、在线游戏）的体验急剧恶化。
在分布式系统的所有误解中，最大的误解是：当带宽是问题时却试图改善延迟。而当延迟是问题时，却试图改善带宽。
高带宽 ≠ 低延迟 低延迟 ≠ 高带宽
 

Latency

Latency is the killer , not bandwidth
  • fundamentally more difficult to improve 从根本上更难改进
 
Bandwidth improved through parallelism 通过并行性提高带宽
  • fatter pipes , more lanes on highway ,more checkout clerks at store , …
  • does cost money , but not fundamentally difficult
 
Latency is much , much , much harder to improve
  • typically requires deep structural changes 通常需要深度结构改变
  • e.g shorten distance , increase max speed tolerated , reduce path length 例如，缩短距离，提高最大容忍速度，减少路径长度
 
Many software and systems trends increase latency
  • increased use of layers ( middleware , external libraries (DLLs),VMs,…) 更多层次的使用（中间件、外部库 (DLL)、虚拟机......）。
  • security technologies ( firewalls ,overlay net works ,middle boxes,…) 安全技术（防火墙、覆盖网、中间盒......）。
  • energy savings (buffered packet delivery by access points) 节能（接入点的缓冲数据包传输）
 
延迟比带宽更难改善
在多核服务器上增加更多的核心，实际上提升了服务器的所谓“带宽”，因为它能够并行处理更多的进程，但是其中任何一个进程的执行都需要提高时钟的频率，而时钟频率近来却停滞不前，你可以购买更多的核心，却无法获得更快的时钟频率。如果无法提升时钟的频率，那就必须回头优化程序，减少执行的指令数量，这是一个更棘手的任务。

Impact of Long Latency

Synchronous of RPC becomes intolerable
RPC 同步变得难以忍受
Coast-to-coast Us ≈ 16 ms at speed of light
  • round-trip RPC > 30 ms 往返 RPC
  • large distances (e.g. trans-Pacific) will make matters worse 远距离（如跨太平洋）会使情况更糟
实际上远大于理论值，光在光纤中的传播速度仅为真空的三分之二，实际部署的系统速度远不及光速，这两部分已经增加了延时。
 
30ms is a long time in terms of lost processing opportunity 就损失的处理机会而言，30 毫秒是很长的时间
  • 3 million instructions on an early 1990s processor (100 MIPS)
      • much higher on faster processor and multi-core machines
  • a modern 3GHZ single-core x86 processor is ~1000-1500 MIPS
      • so 30 ms is ~15-45 million instructions(or more, with multicore)
 
Can’t afford to hide real-world asynchrony 无法隐藏现实世界的异步
  • RPC is synchronous abstraction RPC 是同步抽象
  • inadequate for many emerging use cases
  • more complex , asynchronous models needed 需要更复杂的异步模型
  • more difficult to program and get correct 更难编程和保证正确性
 

Takeaway for Public Networks

公共网络的要点
  1. End-to-end latency is Not shrinking 端到端延迟没有缩短
      2. significantly inflated over speed of light
  1. Latency sacrificed to increase capacity (bandwidth) 牺牲延迟以增加容量（带宽）
      2. video delivery is the driver for profitability 视频交付是盈利能力的驱动力
      video传输恰好是一种仅依赖带宽而与延迟无关的工作负载。

Inflation in Fiber Length

忽略……

HF-Trading Fiber(Chicago-NYC)

在金融交易领域，1ms 足以决定胜负。
延迟可以转换成巨额利润。

How Do We Overcome Long Latency?

Solution 1: “Trust but Verify” (optimistic methods) “信任但验证”（乐观的方法）高度针对特定应用;需要应用程序修改
highly application-specific; requires app modifications
 
Solution 2: Cache data (replace remote ops by local ops) 缓存数据（用本地操作取代远程操作） 应用程序透明；不修改应用程序
application-transparent; no app modifications
 
These are complementary solutions 这些都是互补的解决方案
 

Trust But Verify

aka Optimistic methods
optimistic methods of control , 教授使用 Trust But Verify 来描述它
所谓的谓词校验 就是检查前置条件。如果符合就执行。
📑
乐观控制方法通过“信任优先，验证兜底”的哲学，在分布式系统中实现了性能与一致性的平衡。其本质是用事后冲突处理的成本，换取常态下的高吞吐与低延迟。
 
上一篇
Lecture 4 Semantics
下一篇
Lecture 6 Cache Part 1
Comments
Loading...
Catalog