2024.07 blog review

2024-07-01

Database

BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance

https://db.in.tum.de/teaching/ss16/moderndbs/chapter8.pdf

ByteGraph的优化。主要是几点：

  1. 底层存储从KV换为Append-Only的BlobStorage。原因是BlobStorage可以提供与硬件能力接近的吞吐，也可以自行控制数据分布和GC。而KV一般是基于LSM模型，需要预留更多的带宽来做Compaction，性能 也比较un-predictable。其实说白了就是KV更黑盒，这个抽象是有代价的.
  2. 基于BlobStorage构建BW-Tree。其中BW-Tree可以per user，降低写写冲突；并且delta node会包含了先前的所有delta node数据，这样在读的时候就不需要merge所有delta，优化读
  3. 负载感知的Reclamation
  4. 通过Log实现RO节点的强一致读

Hybrid Garbage Collection for Multi-Version Concurrency Control in SAP HANA

https://15721.courses.cs.cmu.edu/spring2019/papers/05-mvcc3/p1307-lee.pdf

SAP HANA关于MVCC垃圾收集的一些优化

  1. 为了避免long-run的OLAP事务导致垃圾回收savepoint水位一 直无法前进，引入了间隔垃圾回收。就是比如说版本链是[1,3,4,10]，活跃事务是[2,100] ，那其实可以直接把3和4给回收掉。跟HyPer一样
  2. 组垃圾回收。给每个版本数据维护一个指针，指向产生它的事务，如果这个版本数据可以被回收，那么这个事务产生的所有数据其实都可以被回收
  3. 表垃圾回收。简单来说就是比如说如果一个活跃事务只会访问表a，那么表b的历史版本gc就不需要受到这个活跃事务影响了。但是只能用在能完全确定事务所读表的场景，比如RC隔离级别的一个statement，或者SI的存储过程

HiEngine: How to Architect a Cloud-Native Memory-Optimized Database Engine

https://dl.acm.org/doi/10.1145/3514221.3526043 Memory DB的一些设计，包括如何快速做数据checkpoint、包括如何缩短RTO

对于第一个问题，提出了一个dataless checkpoint，cp里只记录数据在日志文件中的offset，不记录全量数据，重启后将offset填到heap空间里。读的时候lazy read from log file

对于第二个问题，想缩短RTO，那么所有数据都应该做checkpoint，否则总不能启动时全量扫描来rebuild吧。数据行（指heap空间里的）的cp好做，直接拿个快照事务，然后dataless checkpoint就好。关键是索引的cp，因为索引并不是mvcc的。所以要考虑cp时怎么不阻塞前台请求，做法总结起来就两种，base+immutable delta+mutable delta，或者cow。cow其实也算是一种mvcc了吧

System

Alibaba Pangu

https://www.usenix.org/system/files/fast23-li-qiang_more.pdf

  1. append-only模式
  2. 重量级客户端，要做分发写、元数据缓存（目录树与chunk分布）等。请求元数据时会batch
    1. 三副本，客户端写成功2副本，可以reply client。client维持一个内存副本，进入chasing状态，如果有限时间内无法成功第三个副本，通知master拷数据到其他副本
    2. 如果写入<2个成功，进入non-stop write模式，把原chunk seal掉，通知master换一个chunk写。 (这种分发写模式的长尾应该会比raft 这种强主模型的好一些。但是重客户端，要吃客户端机器的cpu和内存，如果是块存储其实感觉不是很合适，因为客户机的cpu和内存要超卖。)
  3. 目录树实现 InfiniFS

Storage

Overcoming the Memory Wall with CXL-Enabled SSDs

https://www.usenix.org/system/files/atc23-yang-shao-peng.pdf

计算能力增长远远快于内存容量, 所谓内存墙

CXL允许CPU直接访问PCIe设备用作主内存,但使用闪存作为主内存存在三个主要挑战:

  1. 内存请求和闪存的粒度不匹配
  2. 闪存的延迟远远慢于DRAM
  3. 闪存的寿命有限

咋解决？加一层Cache&Buffer，Over

Optimizing Every Operation in a Write-Optimized File System

https://www.usenix.org/sites/default/files/conference/protected-files/fast16_slides_yuan.pdf

文件系统元数据存储方式

  1. 层级inode，优点是rename快，缺点是lookup需要查找多层
  2. full path index。优点是lookup很快，缺点是rename的开销大

论文做了一个折中，子树划分，然后子树内full-path-index，子树间层级索引

Evaluating File System Reliability on Solid State Drives

https://www.usenix.org/system/files/atc19-jaffer.pdf

fs能否面对ssd错误？ ext4表现最佳, inode blocks损坏时会丢数据, 而且用很少的checksum。

btrfs次之，在很多地方用了checksum.

f2fs最次, 不检测ssd的write error， 静默错误会导致严重后果，内核crash

HydraRPC: RPC in the CXL Era

https://www.usenix.org/conference/atc24/presentation/ma

使用CXL type3来做两机之间的share memory，并通过ntstore、clflush等来bypass cpu cache（和之前使用aep类似），然后基于这个shm来做rpc

方法简单来说是在这个shm上划一个payload区，再为每个连接划两个队列，WQ和CQ分别用于请求和响应，里面存着payload的一块引用, 其他好像就没什么了

（感觉CXL 3.0多机cc距离落地还有很长的距离orz

FastCommit: resource-efficient, performant and cost-effective file system journaling

https://www.usenix.org/conference/atc24/presentation/shirwadkar

ext4 data=ordered 日志模式下，fsync() 系统调用会因为无关 IO 操作导致显著的时延,文章做的工作就是优化 ext4 jbd2. jbd2的问题主要有两个:

  1. jbd2采用物理redo日志，size大。相比之下xfs使用逻辑日志，size小但是恢复慢

  2. 因为日志size大，所以写盘时write then flush，不能直接FUA（FUA仅支持一个block）

文章认为直接用逻辑日志替换物理日志不现实，工程量巨大，更倾向做能落地的.

优化方案：

  1. 既然物理和逻辑日志都各有优缺点，那就直接整合，在物理日志之间穿插逻辑日志。物理日志flush后，之前的逻辑日志就可以truncate了，所以逻辑日志只占很小的空间。恢复的时候先按物理日志恢复，再按照逻辑日志恢复。写逻辑日志的那些commit就称之为fast commit

  2. 逻辑日志直接FUA，因为足够小；而物理日志需要单独flush

  3. fast commit不再交由专门的jbd线程来做，因为会引入额外的调度开销，notify+wakeup啥的也会有开销，而是直接由发起fsync的线程来做，自己run to completion（类似）

(韩国人在单机文件系统上真好活跃，包括之前的SpanFS、iJournaling、CJFS

Non-Blocking Writes to Files

https://www.usenix.org/sites/default/files/conference/protected-files/fast15_slides_campello.pdf

写文件的时候page cache miss，会引起一次到存储上的读，然后再修改page，这个过程较block-write。

但实际上这个写可以先buffer起来，直接返回，这样写就是non-blocking的。读的时候再lazy地把page读出来然后apply buffer。大概就讲了这么个东西

Others

jemalloc 引起的 TLB shootdown 及优化

https://blog.csdn.net/ByteDanceTech/article/details/104765810 一次因jemalloc的madvice引起的TLB Shootdown

  1. /proc/interrupts 发现是TLB shootdown
  2. 解决方案：禁用jemalloc的madvice

Don’t shoot down TLB shootdowns!

https://nadav.amit.zone/publications/amit2020tlb.html

减少TLB shootdown的开销

  1. 本地TLB flush和remote TLB shootdown并法执行，省掉一次本地flush的时间
  2. remote TLB shootdown可以在进入中断处理程序后马上ack， 而不需要等到真的flush了

其他看不懂

The RCU-Reader Preemption Problem in VMs

https://www.usenix.org/system/files/conference/atc17/atc17-prasad.pdf

RCU的Grace Period需要等到每个cpu的context switch才会结束，在此之前，旧资源无法释放。虚拟机环境下，cpu在持有rcu read lock的时候可能被抢占，导致Grace Period迟迟不能结束，影响内存释放

Tags: #blog