netcache

NetCache[SOSP2017] 笔记

Posted by chinaljr on July 1, 2018

论文

关键词

  • KV
  • 可编程交换机
  • Caching

motivation

  • Load balance for performance guarantee
    • N个T吞吐的机器，吞吐量N*T
    • service level agreements SLA
  • Fast small cache for load balancing
    • nlogn cache [有论文可证明]
  • In-network caching for in-memory KV store
  • programable switch

overview

  • switch
    • 正常路由功能
    • Cache
      • match-action tables 匹配判断命中
      • register arrays 储存信息
    • Cache一致性
      • light-weight write-through
    • query statistics
      • per-key counter for the cached items
      • heavy hitter detector
        • Count-Min sketch
        • Bloom filter
  • Controller
    • receives HH reports
    • compare cache的 和 没cache的
    • cache updates
  • storage server
  • client
    • Get Put Delete

NetCache Design

network Protocol

  • Packet format
    • OP SEQ KEY VALUE
  • network routing
    • get 经过缓存
    • put 和 delete 不经过

Query Handling

  • Handling read queries
    • cache hit and valid
      • 计数
      • 更改 pkt.value
      • 交换源和目的
    • cache miss
      • HH detector
      • if hot 通知 controller
  • Handling write queries
    • hit 标记非法
    • 转发到 storage server

Cache Coherence and Cache Update

  • Cache Coherence
    • cache 有非法位，修改的时候置位非法，转发给server，并通过header告知server，当前这个询问是cached
    • server
      • 根据packet header判断是否已经cached，对于put 和 delete 然后更新switch的内容
      • 直接返回给client 成功的消息，不必等待cache更新完毕
    • 非法位有效，直接转发query到server
    • 不同于标准的write-through，不必等cache更新，就可以继续进行别的任务
    • Trick
      • 更新长度不大于原来的value的KV不需要经过Control Plane
  • Cache Update
    • Hot enough based HH detection

Swtich Data Plane Design

  • Data Plane
    • P4
    • Barefoot Tofino
  • Variable-length On-Chip KV (4.4.2)
    • stateful memory
      • register arrays
      • ASIC 有很多 strict resource and timing requirements
    • exact-match table 找到匹配项
      • index
      • bitmap
    • 需要优化的花费
      • the number of entries in match-action tables
      • the size of action data given by a table match
      • the size of intermediate metadata
  • Query Statistic
    • per-key counter
    • Count-min
      • some hashing function
      • 多个function 降低冲突概率 多个 hashing取最小值
    • Bloom filter
      • 保证在 report 给control 之后，每个hash值只被report了一次
    • 说加了一个 sampling component ？？？？？？？？？？？？？？？？？？？？？具体加了啥他妈的能不能写清楚点！！！艹
  • Pipeline layout

Discussion

  • 扩展性，高层switch需要cache
  • Rrstricted KV interface
    • 把大的 value 拆了
    • 把大的key hash 成定长的
  • Write-intensive workloads
    • 表现不好
  • Encryption
    • 不会产生限制
  • Switch
    • 可以专门为cache增加功能
    • 为了适应switch，添加本来没有的cache，麻烦
  • switch可以用到别的集群服务中，如GPU

implementation

见论文

evaluation

具体结果都在论文里

  • Setups
    • Barefoot Tofino
      • 256 25Gbps ports
  • Snake test for switch microbenchmark
    • snake test
      • 0 连 S1
      • 0-1 2-3 4-5 6-7
      • n 连 S2
      • full traffic load
    • demonstrate ：process netcache queries at line rate
    • value size 不受影响
    • cache size 不受影响
  • Server rotation for static workloads
    • server 不够
    • hot items is static
    • 128个服务器，2个服务器分别存1/128 测试64次
      • 把结果aggregation
        • shared-nothing 结构
        • switch 不是瓶颈，算128个和算2个效率没差
    • 求最大效率的吞吐
      • 找到 bottleneck partition
        • 是作为第一次迭代的partition，还是作为一个固定的partition？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
        • ？？咋找啊？？？，是不断提高发送速率？？当throughput趋于稳定就是上限？？？？就不能是client达到上限永远找不到吗？？？？？
      • 生成zifp询问，筛选出指向唯二服务器的询问
      • 调整发送速率，达到瓶颈，这个就是询问的速率，记录当前throughput。
      • 这个速率就是client 在128个机器时候的速率，然后继续接下来的63次实验，client就是这个速率，只不过实际发送的询问是针对唯二server的
      • 累加64次的 throughput 就是 结果
    • 具体实验
      • throughput 和 latancy 表现都很出色
      • write 的比例只要不高过 0.2 表现碾压。超过 0.2差别不大
      • cache size ，达到nlogn的时候吞吐增长就已经足够好了，这实验不就是证明了 nlogn就可以吗？？？，这不是别人的论文结论吗？？
      • scalability 这只是仿真的实验
        • No-cache < Leaf-Cache < Leaf-Spine-Cache
  • Dynamics (Server emulation)
    • 这个更过分，直接每个服务器上64条队列
    • 模拟动态过程
    • ？？不必关注真正的throughput
    • 方法
      • Hot-in 按时选cold 变成 top
      • random cold 随机替代（不一定是top）
      • hot-out 最hot的out

相关工作

  • in-meomory KV stores
  • load balancing
    • switch KV
  • Hardware acceleration