Qi Huang 黄琦, Ken Birman, Robbert van Renesse ( 康奈尔 ), Wyatt Lloyd ( 普林斯顿, Facebook), Sanjeev Kumar, Harry C. Li (Facebook) Facebook 照片缓存分析

2500 亿 * Facebook 头像 新闻 相册 1 * Internet.org, 2013 年 9 月 后台存储 多级缓存 Full-stack 分析

我们的发现（预览） 2 现有 Stack 的性能 改进的的机会 浏览器缓存非常重要 ( 负担了 65+% 的访问 ) 照片的访问频度分布每层都在变化 更优秀的缓存算法可以显著地提升命中率 (S4LRU) 协同缓存值得一试 (Collaborative distributed cache)

用户 Facebook 照片服务 Stack 3

基于用户的 Browser Cache 用户 Browser Cache Browser Cache 4 本地 访问

用户 Browser Cache Browser Cache ( 上百万 ) 5 基于用户的 Browser Cache

Stack 路由选择 Browser Cache Browser Cache 用户 多级缓存 存储后台 多级缓存 存储后台 Facebook Stack Akamai 内容分发网络 (CDN) 内容分发网络 (CDN) 关注点： Facebook stack 6 ( 上百万 )

地域分布的 Edge Cache (FIFO) Edge Cache Edge Cache ( 数十个 ) Browser Cache Browser Cache 用户 PoP 7 ( 上百万 )

Edge Cache Edge Cache Browser Cache Browser Cache 用户 PoP 8 目标 1. 降低 cross-country 访问延迟 2. 降低数据中心的带宽消耗 ( 数十个 ) ( 上百万 ) 地域分布的 Edge Cache (FIFO)

9 Edge Cache Edge Cache Browser Cache Browser Cache 用户 PoP ( 数十个 ) ( 上百万 )

10 Edge Cache Edge Cache Browser Cache Browser Cache 用户 PoP ( 数十个 ) ( 上百万 ) 地域分布的 Edge Cache (FIFO)

全局 Origin Cache (FIFO) Origin Cache Origin Cache 数据中心 ( 四个 ) 11 Edge Cache Edge Cache Browser Cache Browser Cache 用户 PoP ( 数十个 ) ( 上百万 )

12 目标 1. 最小化 I/O-bound 操作 全局 Origin Cache (FIFO) Origin Cache Origin Cache 数据中心 ( 四个 ) Edge Cache Edge Cache Browser Cache Browser Cache 用户 PoP ( 数十个 ) ( 上百万 )

哈希 (url) 13 全局 Origin Cache (FIFO) Origin Cache Origin Cache 数据中心 ( 四个 ) Edge Cache Edge Cache Browser Cache Browser Cache 用户 PoP ( 数十个 ) ( 上百万 )

14 全局 Origin Cache (FIFO) Origin Cache Origin Cache 数据中心 ( 四个 ) Edge Cache Edge Cache Browser Cache Browser Cache 用户 PoP ( 数十个 ) ( 上百万 )

Haystack 存储后台 Backend (Haystack) 15 Origin Cache Origin Cache 数据中心 ( 四个 ) Edge Cache Edge Cache Browser Cache Browser Cache 用户 PoP ( 数十个 ) ( 上百万 )

我们如何采集数据 ? 16

数据采集 检测范围 Backend (Haystack) Browser Cache Browser Cache Edge Cache Edge Cache Origin Cache Origin Cache PoP 用户数据中心 (Object-based 采样 ) Request-based: 采集 X% 的请求 Object-based: 采集针对 X% object 的请求 17

如何采样 Power-law 18 Object rank

Req-based: 偏向热门内容, 导致分析出的缓存性能虚高 19 Object rank Req-based 如何采样 Power-law

Object-based 20 Object rank Object-based: 即使不热门的内容也可以被采样覆盖到 如何采样 Power-law

Object-based: 即使不热门的内容也可以被采样覆盖到 21 Object rank Object-based 如何采样 Power-law

检测范围 Resizer R 22 数据采集 Backend (Haystack) Browser Cache Browser Cache Edge Cache Edge Cache Origin Cache Origin Cache PoP 用户数据中心

分析 缓存的访问负载效果 (traffic sheltering) 照片的访问频度分布 (popularity distribution) 缓存大小、算法、协作 (collaborative Edge) 文章中 – 照片的时间属性对系统性能的影响 – 照片拥有人的社交属性对系统性能的影响 – 照片请求访问的路由分析 23

负载效果 Backend (Haystack) Browser Cache Browser Cache Edge Cache Edge Cache Origin Cache Origin Cache PoP 用户数据中心 R 24

照片的访问频度分布和对系统的影响 25

访问频度分布 Browser 符合 power-law 分布 26

“ 火爆 Viral” 的照片在 Edge 上依然访问量巨大 27 访问频度分布

分布斜率 (Skewness) 在经过多极缓存后会减少 28

访问频度分布 Backend 符合 stretched exponential 分布 29

绝对访问频度 存储 / 缓存的设计取决于部署的层次位置 30

访问频度分布对缓存的影响 31 High Low M Lowest 每个类别包括 25% 访问

访问频度分布对缓存的影响 Browser 的访问负载逐渐减少 32

访问频度分布对缓存的影响 Edge 除 ”lowest” 组外负载稳定 33

访问频度分布对缓存的影响 Origin 对 “low” 组的贡献最多 34

访问频度分布对缓存的影响 Backend 服务长尾 35

我们如何能够提升缓存性能 ? 36

模拟 重放采集数据 (25% 用来预热缓存 ) 估算当前缓存大小 分析两种命中率 (object-wise, byte-wise) 37

Edge Cache ＋ 缓存空间 选择 San Jose edge ( 高访问量, 中值命中率 ) 38

Edge Cache ＋ 缓存空间 “x” 代表当前缓存尺寸 (59% 命中率 ) 39

Edge Cache ＋ 缓存空间 “ 无限 ” 命中率需要 45x 当前缓存尺寸 40

Edge Cache ＋ 缓存算法 LRU 和 LFU 仅比 FIFO 提高少许 41

S4LRU 42

S4LRU 43

S4LRU 44

S4LRU 45

Edge Cache ＋ 缓存算法 S4LRU 提升最大 46

Edge Cache ＋ 缓存算法 Clairvoyant (Bélády) 意味着还有大量的提升空间 47

Origin Cache S4LRU 对于 Origin 的效用超过 Edge 48

该缓存那种照片 Recency & frequency 导致了 S4LRU 的有效性 照片的年龄、社会属性也会影响性能么 ? 49

照片年龄 50 年轻的照片更加热门，曲线符合 Pareto 分布

照片的社交网络 51 更多的朋友 /followers 给每张照片带来更多的访问

Edge 协作式缓存 52

Edge 的地域覆盖范围 53

Edge 的地域覆盖范围 54

Edge 的地域覆盖范围 55

Edge 的地域覆盖范围 56

Edge 的地域覆盖范围 57 Atlanta 80% 的访问由远程 Edges 服务的

Edge 的地域覆盖范围 58 全局范围内也存在大量的远程访问

Edge 的地域覆盖范围 59

协作式 Edge 60

协作式 Edge “Independent 独立 ” 情况下所有 Edges 的命中率 61

协作式 Edge “Collaborative 协作式 ” Edge 能提高 18% 的命中率 62 Collaborative

相关工作 63 存储系统分析 内容分发分析 Web 访问模式分析 BSD file system (SOSP ’85), Sprite ( SOSP ’91), NT (SOSP ’99), NetApp (SOSP ’11), iBench (SOSP ’11) Cooperative caching (SOSP ’99), CDN vs. P2P (OSDI ’02), P2P (SOSP ’03), CoralCDN (NSDI ’10), Flash crowds (IMC ’11) Zipfian (INFOCOM ’00), Flash crowds (WWW ’02), Modern web traffic (IMC ’11)

结语与贡献 64 量化了现有 stack 内缓存的性能 量化了各层缓存间照片访问频度分布的改变 Recency, frequency, age, social factors 都会影响缓存策略 指出了协作式缓存的潜在作用