文章归档

cpeh: a scalable, high-perormance distributed file system

  1. system architecture
  2. system overview
    1. the ceph file system has three main components:
      • client: each instance of which exposes a near-POSIX file system interface to a host or process
      • osd cluster: sotres all data and metadata
      • mds cluster: manages the namespace(file names and directories) while coordinating security, consistency and coherence.
    2. primary goals
      • scalability: to hundreds of petabytes and beyond, considered in a variety of dimensions, including the overall storage capacity and throughput of the system.
      • performance: out target workload may include such extreme cases as tens or hundreds of thousands

        »» 继续阅读全文

The Design of a High-Performance File Server

老论文了,Bullet file Server,文献原址:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.5481&rep=rep1&type=pdf

key point:

  1. to do away with the traditional file server's block model. In fact, we have chosen the extreme, which is to maintain files contiguously throughout the system. That is, files are contiguously stored on disk, contiguously cached in RAM, and kept contiguously in processes’ memories. This dictates the choice for whole file transfer.
  2. Another design choice, which is closely linked to keeping files contiguous, is to make all files immutable. That is, the only operations on files are creation, retrieval, and deletion; there are no update-in-place operations. Instead, if we want to update

    »» 继续阅读全文

Haystack

文献原址:Finding a needle in Haystack: Facebook's photo storage 

一:简介:

  1. 2600亿照片,20PB数据量
  2. 每周60TB,10亿照片
  3. 每秒100w张图片的检索速度
  4. 对象存储,我们的图片只写,不修改,很少删除
  5. 传统POSIX文件系统成为瓶颈

论文中提到瓶颈是由于传统的POSIX文件系统是基于目录和metadata来管理文件的,通常取一张图片都会涉及好几个IO操作:

  1. 从文件名得到inode号
  2. 将inode信息从磁盘读取出来
  3. 读取文件。

对于一些稍微复杂的架构,1步骤可能会更频繁些。 Haystack设计的目标:

  1. 高吞吐量和低延迟
  2. 分区容忍性
  3. 低成本。通过两个维度来控制,每TB可用数据的利用率和每TB可用数据的读速率(这里的可用考虑到底层文件系统,磁盘阵列,冗余等各种因素)
  4. 简单。

二、背景

  1. 典型设计,存储集群 + cdn
  2. NFS文件系统

 

CDN通常是用来缓存热数据的,但是对于像facebook这样的互联网站,通常需要产生大量的非热数据内容,而恰恰是这些不太热的数据内容,大量地升高了CDN回源的压力,facebook引用了长尾理论来解析这一效应。在NFS卷里,facebook最初默认是每个目录存储上千个文件,但是由于NAS设备对目录metadata的管理方式,导致在一个目录里存放上千个文件相当困难,因为目录的blockmap太大了。这种情况下读1张图片最少也要10个IO,就算让目录存放的文件数降低到100,也仍然会有3个IO才能读到一张图片。 为了减少磁盘操作的次数,facebook还在Photo Store servers上缓存NAS设备返回的file handle,这个是通过增加内核API(open_by_filehandle)来实现的。facebook从NAS上学到的经验就是:通过缓存来降低磁盘IO的操作是很有限的。 也许有人会说,可以使用memcache来缓存所有的file handles。对此facebook坦言,也许这是一个解决方案,但是只能解决这里部分的问题,因为这么做的话需要NAS设备缓存所有的inodes信息,只不过是一种昂贵的传统存储方案罢了。 

三、设计与实现 

方案:CDN解决热数据问题,Haystack解决长尾效应。 Haystack的主要目的就是为了解决NFS存储方案中高磁盘IO的问题。Haystack的做法是:降低文件系统的metadata的内存占用,因此尽可能的将所有的metadata放在内存里,例如它将多个小文件存在一个大文件里。

1)三个核心组建:Haystack Directory, Haystack cache, Haystack store 

 

Store是由物理卷组成的,容量由物理卷的数量来控制,100个物理卷可提供10TB的存储空间。物理卷还会组合成一个逻辑卷,单个逻辑卷中的所有物理卷数据是相同的,冗余。Directory主要保存应用方面的数据信息,例如每张图片存放在哪个逻辑卷上,还有逻辑卷到物理卷的映射以及逻辑卷的剩余空间。Cache相当于一个内部的CDN。 

2)URL规格

»» 继续阅读全文

SILT: small index and Large table

SILT's multi-store design

The most common approach to build a hign performence key-value storage system uses two components:logstore and sortedstore. But in the implementation of SILT, it add a HashStore for sloving the high write amlication problem when merge logstore into sortedstore by traditional way. how to manage the sortedstore isn't key to performance, i think, just a little infulence.

In fact, SILT isn't a generic key-value store because of its keys are uniformly distributed 160bit hash value(e.g., pre-hashed key with SHA-1), but doing it fixed length as SILT have done here is so much convenient for compressing

»» 继续阅读全文

猜解leveldb写性能

如题,猜测。

我们知道leveldb的很出色,随机读写的性能可以分别达到 164,000 ops/sec 和 129,000 ops/sec,这是官方的Benchmarks数据。

leveldb最关键的核心技术在于基于level思想的sstable文件compact策略,因为这种设计,大大的改善了Random Writes的性能。levledb的memtable/immutable是一个skiplist链表,而skiplist insert的时间复杂度是O(logn),也就是说,insert的时间复杂度是随着问题规模的增长而线性上升的,呵呵,不知到大家注意到没。

高性能kv的实现现在跑的比较火的就数lsm-tree,主要的思路就是先在内存里cache到某个阀值然后dump到磁盘,再由其他线程或者进程来进行compact操作,于是首先会引出的第一个问题是:

1、sstable文件的管理以及如何执行compact的操作,这个地方直接影响到读性能,这也是为什么采用lsm-tree的key-value存储引擎读性能一直提升不上去的原因,尤其是一些老旧数据的检索。

我当初也主要没考虑过在skiplist这一部分做过优化,毕竟skiplist主要还是内存操作。

但是leveldb的作者可不是这么想的,这种想法可真是so easy但是又很难引起大家的注意:就是靠缩小问题的规模来达到提升insert性能的目的。我今晚在食堂吃饭,想到这点的时候就没差点笑喷了,有意思,哈哈 ^_^

但是如果这样做的话会导致sstable文件会非常的多,而且会产生大量的小文件,所以如果没有一套非常优秀的compact策略的话只有傻子才会这样做,我当初在研究lsm论文后,采用的思想是直接dump大sstable文件,sstable文件量小,容易管理,查询性能也比较好,当然后来也意识到很多问题,这是后话了。

所以Jeff Dean和Sanjay Ghemawat设计了一种基于level的compact策略,然后让memtable达到一个非常小的阀值后直接dump成小文件,由后台进程来进行compact管理。memtable的阀值由 write_buffer_size(include/leveldb/options.h)控制,默认是4mb左右,假设key是20bytes,value是80bytes,这个阀值可以容纳4w个entries左右。

根据skiplist的查找时间复杂度O(logn),我在本机上做了一个简单的测试,主要计算随着规模的增长每随机插入一条数据的开销。

测试环境:

Date: Tue Apr 17 23:45:07 2012 CPU: 2 * Pentium(R) Dual-Core CPU T4400 @ 2.20GHz CPUCache: 1024 KB System: Centos Linux 2.6.32-220.el6.i686 #1 SMP Tue Dec 6 16:15:40 GMT 2011 i686 i686 i386 GNU/Linux

实际上只使用了一个CPU,测试结果

测试代码:https://github.com/pipul/coutune/tree/master/skiplist

很明显,随着skiplist的cardinality不断变大,插入每条数据的开销越来越多,不过当n趋向无穷大的时候,这种变化会渐趋不明显。而在刚开始的时候,insert开销抖增。所以,想要获得最好的random writes性能,skiplist的cardinality尽量控制到百万级别以下

The Log-Structured Merge-Tree

LSM-tree 是一种相当优秀的思想。它本身是为了优化B树在更新插入时的性能而被提出来的,所以要彻底理解LSM-tree,就要清楚B树的难处。

B树中的update性能

完全不考虑缓冲的情况下,举例一个可以存储10亿关键字的B树,深度为2,那么每次update事务,至少需要四次IO操作才能完成,三次读,一次写。如果根结点常驻内存的话,最少也需要三次IO。如果是插入(插入也算是update的一种)操作,遇到结点满状态,需要对结点分裂,还需要更多的IO才能完成。

即便是到了今天普通PC的磁盘IOPS也就150左右,可以想象,根本无法处理得了大量的并发操作,尤其在海量存储难题面前

LSM-tree 的核心思想

LSM-tree 最原始和质朴的思想,就是在内存里对B树的update操作进行缓存。使用cache的做法似乎不值一提,但在当时来说哪怕1MB的闪存价格都非常昂贵,大部分的数据还是通过磁盘来处理,如果你有这方面的经验,就能理解B树这种传统的数据结构实践起来是多么的困难。而且,The Log-Structured Merge-Tree 这篇论文在提出的时候是1996年,当时的内存容量我猜在5MB左右。

五分钟法则的由来

五分钟法则是从经济学的角度为降低IT企业运营成本而被提出来的,用术语的话来说,就是 COSTp/COSTm,在今天的说法就是,当页面达到每超过300秒就被访问一次的频率后,就应该将这块页面加载到内存以提升性能。而过去的说法,是指页面没有被频繁使用的话,就不应该将其加载到内存中来,87年的今天是5分钟,96年是1分钟,到了今天可能是十几秒。

COSTm = cost of 1 MByte of memory storage COSTp = disk arm cost to provide 1 page/second I/O rate, for random pages

COSTm和COSTp非物理设备的价值那么简单,涉及很多因素,尤其是COSTp,比如Google说,每0.5秒的延迟就会有20%的流量损失,你可以想象一下COSTp值多大。

所以,Patrick O'Neil (LSM论文的作者)们要解决的问题,就是怎么有效利用缓存的策略,Patrick O'Neil 的做法是,在内存里维护一个相同的B树,当内存中的B树达到阀值时,然后批量进行 rolling merge

NoSQL运动里的LSM实践

NoSQL运动里谈到的LSM相当于复杂的 Multi-Component LSM-trees,只是存储组件不再使用B树,而是习惯了另一种更加漂亮的数据结构 Skiplist,Google的Bigtable理论模型里用到的就是这个东西,可以看看levelDB的实现,而且mencached,redis,nessDB等也不乏使用。相比传统的B树,Skiplist 最大的特色就是完全平坦化的存储模型,O(logn)的时间复杂度

LSM与skiplist的结合,带来了一种新的存储架构策略,我自个的话说就是:swap和merge-split

以levelDB为例,C0是memtable,是内存中的LSM组件,C2 ~ Ck就是sstable,是常驻磁盘的LSM组件,关于存储的设计可以看看这篇文章 >> KeyValue存储层文件结构的设计 或者 HFile。而C1实质上是sstable在内存中的cache,通常是一个LRU链表。

所谓swap,就是将memtable中的数据直接dump到磁盘形成新的sstable,而meger-split则是删除sstable中过期的数据。这种设计的好处是,无论是插入,更新,还是删除,都可以很轻松的抽象成一个put操作,大大简化了DB的实现逻辑。

但是,这种实现的策略有两个地方限制了其自身可应用的场景,就是update的频率要远大于读取,才能体现出顺序写的性能优势,因为

  • sstable间是无法保证严格有序的,因此查询一个key就不得不在所有的sstable中进行,然后返回最新的数据。用迂回折中的办法,可以对sstable按照timestamp排序,查到最近的一个key并返回。所以bigtable这种模型很可能无法满足精确,实时的海量查询需求
  • 此外,merge-split 还隐藏了另外一个很重要的因素,就是数据文件要达到GB甚至TB级才会有显著的merge-split效果。

要解决这个问题,可以适当改变swap和merge-split的策略。nessDB是个很好的例子。nessDB同样采取LSM的思想,但是不同与上述模型,nessDB确保sstable之间是有序的,对查询操作比较友好。

nessDB是通过牺牲部分写性能来提升查询的效率。memtable在swap的时候并不直接dump成sstable文件,而是合并到现有的sstable文件中去。

LSM的持久化

如果要确保数据不能丢失,为了应对服务器遇不可抗拒外力因素造成的宕机的情况,通常LSM有两次持久化过程,一次是log,,以append形式对所有的update操作先进行日志记录,一旦出现意外情况,即可以恢复log中的内容到memtable,这里实际上相当于重新redo了一系列的事务,除了增加少量的disk存储开销不会带来其他任何影响。第二次是swap,在memtable达到阀值的时候直接dump到磁盘上形成新的sstable,这个过程叫做最终持久化。

 

LSM的论文洋洋洒洒30多页,也算是我看过的最长的一篇论文了,前前后后花了不少时间才算弄明白。其实LSM并不复杂,反而可以说是出奇的简单,Patrick O'Neil在文中列举了很多例子来计算LSM所带来的性能的提升,也许在今天这种情况下是不足论道的,但是Patrick O'Neil迈出了一小步,却是存储难题的一个重大突破。

»» 继续阅读全文

KeyValue存储层文件结构的设计

主要参考了一下HFile存储格式的设计,也可以说完全是HFile的一个简约版。我去除了一些目前暂时可能用不上的结构,毕竟HFile作为HBase数据库底层存储的文件结构,融合了过多的通用特性,比如Meta,另外我还做了一下稍微的修改,比如trailer块中的某些字段。

数据文件主要由四部分组成,连续的Data Block,一块File Info,一块的Index Block,最后是 Trailer 块

 

Data Block 数据块

DATA_BLOCK_MAGIC 主要的作用是数据校验,避免数据损坏带来的意外情况。Block中所有的数据其实整个数据文件的keyvalue都是有序的。Block的大小可以自定义,主要是针对IO性能和解析的粒度。

File Info 数据块

File Info Block 主要记录了整个数据文件的一些基本信息。ItemsNum表示File Info Block里记录的数量,AVG_KEY_LEN 表示平均的 key 长度,其他同理,LASTKET保存了整个数据文件的最后一个Key,方便进行key的检索。

Index Block 索引数据

Index Block 主要是连续的entries组成,每个entry对应一个Data Block,包含了各自所对应的Data Block的偏移量 Offset,Data Block的大小 DataSize,KeyLen和KeyData为每块Data Block的第一个Key。

Trailer 块

数据文件被打开时,首先应该被读取的是Trailer块,Trailer块的长度是固定的,当然这个可以自己修改,理所当然的做法就是给Trailer增加一个Version,解决各版本之间数据格式不兼容的问题。Trailer 结构里主要保存了 File Info 和Index Block等其他结构在文件中的偏移量和数据大小,如下

我写了一个c版本的上述设计的实现,仅关注存储形式而不涉及上层DB的实现逻辑。代码未经测试,谨慎使用

https://github.com/pipul/Hfile

浅谈DB的分层索引

HFile是Hbase的底层存储文件结构,目前有两个版本v1和v2,要理解HFile的设计,这里 http://www.slideshare.net/schubertzhang/hfile-a-blockindexed-file-format-to-store-sorted-keyvalue-pairs,这里 https://issues.apache.org/jira/browse/HBASE-3857

HFile在v2里引入分层索引,是很值得研究的地方,对其他key-value db的设计有借鉴意义,此外,还有 compound Bloom filter,同样很值得思考

 

传统keyvalue数据库索引的设计

将索引结构顺序写到磁盘上,形成一个 Data Index Block,Data Index Block 会在数据库文件被打开时全部加载到内存。这样就可以根据内存中的索引数据检查出某个key具体在哪块block上,如果此块Data block IN_CACHE,就直接从内存里返回数据,如果IN_DISK,就lseek到偏移量处,将整块Block加载到内存,通常会使用lru算法来维护内存中的data block块数据,结构如下

在索引文件太大,1GB,数GB这种情况下,对性能会有很大的影响。因为会有频繁的 Data Block 被swaped到磁盘,又cache到内存。

 

分层索引

所以 HFile 在v2中开始引入了分层索引这一尝试,将索引文件分为 root block index 和 non-root block index 两种。root block index 会在数据库文件打开时被加载到内存。而non-root block index 会根据需要加载到内存,non-root block index 可以只有leaf-index block,或者还会有 intermediate level index block,如果Data Block 数据块个数少,leaf-index block 和 root block index足以,否则就需要加入中间层索引,也就是 intermediate level index block,它在 HFile文件里是可选的。实际情况下索引的层级不会超过两层。

root block index 由连续的entries组成,entry的结构如下,entry的个数会被记录在trailer结构里

如果是single level index,那么root block index里的每个entry就对应一个data block,这和 HFile v1是一样的。如果是two level index,那么root block index里的每个entry就指向每个leaf index block,而每个leaf index block则记录了对应的一系列Data block的偏移量。如果是三层,情况就要更复杂一下,root block index 里的entries指向intermediate level index block,而intermediate level index block则指向leaf index block。

»» 继续阅读全文

BLOOM-FILTER 的误报率

先来解决 false-positives 与 false-negatives 的定义

  • false-positives: 将不属于该集合中的元素错误地以为是该集合中的,为误报
  • false-negatives: 将属于该集合中的元素错误地以为不是该集合中的,此为漏报

Bloom-filter 的设计是,漏报不可能发生,误报允许存在,但是概率要控制在一定的范围内。Bloom-filter 的问题实质上是分析 false-positives 的问题

Bloom 是这样计算的:

经过 kn 次 hash 之后,集合 S 中任意一位为 0 的概率是,也可以说是集合中 0 的比率

(1 - \frac{1}{m})^{kn}

可能为 1 的概率是

p = 1 - (1 - \frac{1}{m})^{kn}

而产生误报的条件是,k 个 hash 的结果都为 1,所以 false-positives 的概率应该是,Bloom 说的

f = p^k = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k

我同样认为 Bloom 的论文中关于 false-positives 的估算是不算妥当,有兴趣的请移步:> ON THE FALSE-POSITIVE RATE OF BLOOM FILTERS 虽然这篇论文我只看了前部分,但是仍然觉得很有意思,Prosenjit Bose 等按照 Bloom 的方法讨论了一种较简单的情况,然后通过枚举计算出与实际误报率之间的偏差偏差。我的看法是,Bloom

»» 继续阅读全文