January 2016

You are browsing the site archives for January 2016.

注:本文转载至 http://blog.yunnotes.net/index.php/tfs-erasure-code/ TFS发展至今,集群部署总容量已超过50PB,机器数量约2700台。TFS在阿里内部主流部署方式是主集群内数据块2个副本,每个主集群配置两个备集群,分别在同城和异地机房,实际上每份数据6个副本,存储成本非常高,为了降低TFS存储成本,我们将Erasre code引入到TFS系统,本文将详细介绍TFS应用Erasure code的技术方案。

Continue reading TFS纠删码实现

概述 Skip list(也称跳表)是一种随机化数据结构,基于并联的链表,其效率可比拟二叉查找树(对于大多数操作需要O(log n)平均时间)。 基本上,Skip list是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表,因此得名。所有操作都以对数随机化的时间进行。一个基本的Skip list结构如下:

Continue reading SkipList

LevelDB磁盘上的<key, value>数据被存储在sstable中,而数据在sstable内又是按照block为单位索引的,且LevelDB内又以block为单位做了缓存。因此,读取<key, value>的第一步是确定其所在block,这通过查找sstable的index block完成。当读出<key, value>所在data block后,同样需要在该data block内顺序查找。本文的主要目的是搞清楚如何查找index block获得<key, value>所属data block以及查找data block最终获得key对应的value值。

Continue reading LevelDB详解: 如何从Block中读出key

LevelDB基本读流程按照如下顺序: 从内存memtable读; 从内存Immutable memtable读; 从level0的sstable读; 从level1的sstable读; …… 上面的读流程中,如果在上一级命中,就不再进入下一层级去读取,因为上一层级的数据总是比下一层级的数据更新,这也是取名levelDB的原因所在。

Continue reading LevelDB详解: 读过程一

单例模式应该是23种设计模式中最容易理解,也是最容易手写代码的模式了。但是要正确写出单例模式确是对基本功的极大考验。因为其中的坑却不少,所以也常作为面试题来考。本文由浅入深教你写出正确优雅的单例模式代码,带你装逼带你飞。

Continue reading 正确写出单例模式

DBCP中的基本类图关系如下: 工厂方法模式   首先,大量运用了工厂模式:如GenericObjectPool内有一个PoolableConnectionFactory用来为其创建object(对外暴露makeObject()接口)。而 PoolableConnectionFactory又只是PooledFactory接口的一个实现。

Continue reading DBCP中的设计模式

LevelDB是针对大规模Key/Value数据的单机存储库,从应用的角度来看,LevelDB就是一个存储工具。而作为称职的存储工具,常见的调用接口无非是新增KV,删除KV,读取KV,更新Key对应的Value值这么几种操作。LevelDB没有直接支持更新操作的接口,如果需要更新某个Key的Value,你可以选择直接生猛地插入新的KV,保持Key相同,这样系统内的key对应的value就会被更新;或者你可以先删除旧的KV, 之后再插入新的KV,这样比较委婉地完成KV的更新操作。

Continue reading LevelDB专题七: 记录读取

在之前的系列文章中,我们介绍了LevelDB的一些静态文件及其详细布局,从本节开始,我们看看LevelDB的一些动态操作,比如读写记录,Compaction,错误恢复等操作。本节介绍LevelDB的记录更新操作,即插入/删除一条KV记录。LevelDB的更新操作速度是非常快的,源于其内部机制决定了这种更新操作的简单性。 图1 levelDB写入记录  图1是LevelDb如何更新KV数据的示意图,完成插入操作包含两个具体步骤: KV记录以顺序的方式追加到log文件末尾,并调用Sync将数据真正写入磁盘。尽管这涉及到一次磁盘IO,但是文件的顺序追加写入效率是很高的,所以并不会导致写入速度的降低; 如果写入log文件成功,那么将这条KV记录插入内存中的Memtable中。前面介绍过,Memtable只是一层封装,其内部其实是一个Key有序的SkipList列表,插入一条新记录的过程也很简单,即先查找合适的插入位置,然后修改相应的链接指针将新记录插入即可。 log文件内是key无序的,而Memtable中是key有序的。对于删除操作,基本方式与插入操作相同的,区别是,插入操作插入的是Key:Value 值,而删除操作插入的是“Key:删除标记”,由后台Compaction程序执行真正的垃圾回收操作。 LevelDB的写入操作就是如此简单,真正的麻烦在后面接下来介绍的读取操作中。

Continue reading LevelDB专题六: 数据写入