README.md

论文笔记

这个repo记录我平时阅读的paper并记录下笔记，希望自己不只是一个会拼凑代码的程序员。

目录(TOC)

• 论文笔记

  • 目录(TOC)

  • [数据结构]

  • 分布式(Distributed System)

    • 存储(Storage)
      • Spanner
    • 一致性(Consensus)
      • raft
      • Zookeeper

  • 系统(System)

    • 文件系统(File System)
      • F2FS
      • LFS

Spanner

• Spanner: Google’s Globally-Distributed Database

// TODO Wait to read

• MapReduce: Simplified Data Processing on Large Clusters
• Finding a needle in Haystack: Facebook’s photo storage
• In Search of an Understandable Consensus Algorithm (Extended Version)
• ZooKeeper: Wait-free coordination for Internet-scale systems
• PacificA: Replication in Log-Based Distributed Storage Systems

Time Series Database

• Gorilla: A Fast, Scalable, In-Memory Time Series Database

F2FS

F2FS: A New File System for Flash Storage

随着NAND Flash被越来越多的应用到各式设备中，传统的文件系统以HDD为设计对象，已经不再适合于NAND flash。 因此论文设计了F2FS文件系统来提高NAND flash性能和寿命。

在flash中，即使写入一个字节，也需要擦除整个BLock,然后在写入数据，同时频繁的擦写容易造成SSD损坏，所以在SSD中采用out­ of ­place来更新，这里有别与HDD的in place。因此每次写操作都会使数据块的地址发生改变。在LFS中，如果leaf data block更新了，需要递归地修改direct index block，indirect index block等都需要改变，引起了Wandering tree问题。因此引入了NAT

同时F2FS引入了Multi-head logging，F2FS利用flash存储的并行性,可以同时操作多个log，来提高效率。F2FS还通过roll-forward recovery来加速fsync。

LFS

The Design and Implementation of a Log-Structured File System

• Large-scale cluster management at Google with Borg
• The Bw-Tree: A B-tree for New Hardware Platforms
• BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory
• High Throughput Compression of Double-Precision Floating-Point Data

数据结构

• The Adaptive Radix Tree:ARTful Indexing for Main-Memory Databases

• The ART of Practical Synchronization

• Orca: A Modular Query Optimizer Architecture for Big Data

• Filter Before You Parse:Faster Analytics on Raw Data with Sparser