Tag Archives: 云计算

HFile存储格式

HBase中的所有数据文件都存储在Hadoop HDFS文件系统上,主要包括两种文件类型:

1. HFile, HBase中KeyValue数据的存储格式,HFile是Hadoop的二进制格式文件,实际上StoreFile就是对HFile做了轻量级包装,即StoreFile底层就是HFile

2. HLog File,HBase中WAL(Write Ahead Log) 的存储格式,物理上是Hadoop的Sequence File

下面主要通过代码理解一下HFile的存储格式。

HFile

下图是HFile的存储格式:

HFile由6部分组成的,其中数据KeyValue保存在Block 0 … N中,其他部分的功能有:确定Block Index的起始位置;确定某个key所在的Block位置(如block index);判断一个key是否在这个HFile中(如Meta Block保存了Bloom Filter信息)。具体代码是在HFile.java中实现的,HFile内容是按照从上到下的顺序写入的(Data Block、Meta Block、File Info、Data Block Index、Meta Block Index、Fixed File Trailer)。

KeyValue: HFile里面的每个KeyValue对就是一个简单的byte数组。但是这个byte数组里面包含了很多项,并且有固定的结构。我们来看看里面的具体结构:

开始是两个固定长度的数值,分别表示Key的长度和Value的长度。紧接着是Key,开始是固定长度的数值,表示RowKey的长度,紧接着是 RowKey,然后是固定长度的数值,表示Family的长度,然后是Family,接着是Qualifier,然后是两个固定长度的数值,表示Time Stamp和Key Type(Put/Delete)。Value部分没有这么复杂的结构,就是纯粹的二进制数据了。

Data Block:由DATABLOCKMAGIC和若干个record组成,其中record就是一个KeyValue(key length, value length, key, value),默认大小是64k,小的数据块有利于随机读操作,而大的数据块则有利于scan操作,这是因为读KeyValue的时候,HBase会将查询到的data block全部读到Lru Block Cache中去,而不是仅仅将这个record读到cache中去。

private void append(final byte [] key, final int koffset, final int klength, final byte [] value, final int voffset, final int vlength) throws IOException {

this.out.writeInt(klength);

this.keylength += klength;

this.out.writeInt(vlength);

this.valuelength += vlength;

this.out.write(key, koffset, klength);

this.out.write(value, voffset, vlength);

}

Meta Block:由METABLOCKMAGIC和Bloom Filter信息组成。

public void close() throws IOException {

if (metaNames.size() > 0) {

for (int i = 0 ; i < metaNames.size() ; ++ i ) {

dos.write(METABLOCKMAGIC);

metaData.get(i).write(dos);

}

}

}

File Info: 由MapSize和若干个key/value,这里保存的是HFile的一些基本信息,如hfile.LASTKEY, hfile.AVG_KEY_LEN, hfile.AVG_VALUE_LEN, hfile.COMPARATOR。

private long writeFileInfo(FSDataOutputStream o) throws IOException {

if (this.lastKeyBuffer != null) {

// Make a copy.  The copy is stuffed into HMapWritable.  Needs a clean

// byte buffer.  Won’t take a tuple.

byte [] b = new byte[this.lastKeyLength];

System.arraycopy(this.lastKeyBuffer, this.lastKeyOffset, b, 0, this.lastKeyLength);

appendFileInfo(this.fileinfo, FileInfo.LASTKEY, b, false);

}

int avgKeyLen = this.entryCount == 0? 0: (int)(this.keylength/this.entryCount);

appendFileInfo(this.fileinfo, FileInfo.AVG_KEY_LEN, Bytes.toBytes(avgKeyLen), false);

int avgValueLen = this.entryCount == 0? 0: (int)(this.valuelength/this.entryCount);

appendFileInfo(this.fileinfo, FileInfo.AVG_VALUE_LEN,

Bytes.toBytes(avgValueLen), false);

appendFileInfo(this.fileinfo, FileInfo.COMPARATOR, Bytes.toBytes(this.comparator.getClass().getName()), false);

long pos = o.getPos();

this.fileinfo.write(o);

return pos;

}

Data/Meta Block Index: 由INDEXBLOCKMAGIC和若干个record组成,而每一个record由3个部分组成 — block的起始位置,block的大小,block中的第一个key。

static long writeIndex(final FSDataOutputStream o, final List<byte []> keys, final List<Long> offsets, final List<Integer> sizes) throws IOException {

long pos = o.getPos();

// Don’t write an index if nothing in the index.

if (keys.size() > 0) {

o.write(INDEXBLOCKMAGIC);

// Write the index.

for (int i = 0; i < keys.size(); ++i) {

o.writeLong(offsets.get(i).longValue());

o.writeInt(sizes.get(i).intValue());

byte [] key = keys.get(i);

Bytes.writeByteArray(o, key);

}

}

return pos;

}

Fixed file trailer: 大小固定,主要是可以根据它查找到File Info, Block Index的起始位置。

public void close() throws IOException {

trailer.fileinfoOffset = writeFileInfo(this.outputStream);

trailer.dataIndexOffset = BlockIndex.writeIndex(this.outputStream,

this.blockKeys, this.blockOffsets, this.blockDataSizes);

if (metaNames.size() > 0) {

trailer.metaIndexOffset = BlockIndex.writeIndex(this.outputStream,

this.metaNames, metaOffsets, metaDataSizes);

}

trailer.dataIndexCount = blockKeys.size();

trailer.metaIndexCount = metaNames.size();

trailer.totalUncompressedBytes = totalBytes;

trailer.entryCount = entryCount;

trailer.compressionCodec = this.compressAlgo.ordinal();

trailer.serialize(outputStream);

}

注:上面的代码剪切自HFile.java中的代码,更多信息可以查看Hbase源代码。

参考:http://www.searchtb.com/2011/01/understanding-hbase.html

http://th30z.blogspot.com/2011/02/hbase-io-hfile.html

 

分布式文件系统Ceph调研1 – RADOS

Ceph是加州大学Santa Cruz分校的Sage Weil(DreamHost的联合创始人)专为博士论文设计的新一代自由软件分布式文件系统。自2007年毕业之后,Sage开始全职投入到Ceph开 发之中,使其能适用于生产环境。Ceph的主要目标是设计成基于POSIX的没有单点故障的分布式文件系统,使数据能容错和无缝的复制。2010年3 月,Linus Torvalds将Ceph client合并到内 核2.6.34中。

Ceph中有很多在分布式系统领域非常新颖的技术点,对解决分布式文件系统中一些常见的问题的研究非常有指导意义。所以值得研究。

RADOS简介

1 RADOS概述

RADOS (Reliable, Autonomic Distributed Object Store) 是Ceph的核心之一,作为Ceph分布式文件系统的一个子项目,特别为Ceph的需求设计,能够在动态变化和异质结构的存储设备机群之上提供一种稳定、可扩展、高性能的单一逻辑对象(Object)存储接口和能够实现节点的自适应和自管理的存储系统。事实上,RADOS也可以单独作为一种分布式数据存储系统,给适合相应需求的分布式文件系统提供数据存储服务。

2 RADOS架构简介

RADOS系统主要由两个部分组成(如图1所示):

1.由数目可变的大规模OSDs(Object Storage Devices)组成的机群,负责存储所有的Objects数据;

2.由少量Monitors组成的强耦合、小规模机群,负责管理Cluster Map,其中Cluster Map是整个RADOS系统的关键数据结构,管理机群中的所有成员、关系、属性等信息以及数据的分发。

图1 RADOS系统架构图示

对于RADOS系统,节点组织管理和数据分发策略均有内部的Monitors全权负责,所以,从Clients角度设计相对比较简单,它给应用提供的仅为简单的存储接口。

3 RADOS详细介绍

3.1 扩展机群

1.Cluster Map

存储机群的管理,唯一的途径是Cluster Map通过对Monitor Cluster操作完成。Cluster Map是整个RADOS系统的核心数据结构,其中指定了机群中的OSDs信息和所有数据的分布情况。所有涉及到RADOS系统的Storage节点和Clients都有最新epoch的Cluster Map副本。因为Cluster Map的特殊性,Client向上提供了非常简单的接口实现将整个存储机群抽象为单一的逻辑对象存储结构。

Cluster Map的更新由OSD的状态变化或者其他事件造成数据层的变化驱动,每一次Cluster Map更新都需要将map epoch增加,map epoch使Cluster Map在所有节点上的副本都保持同步,同时,map epoch可以使一些过期的Cluster Map能够通过通信对等节点及时更新。

在大规模的分布式系统中,OSDs的failures/recoveries是常见的,所以,Cluster Map的更新就比较频繁,如果将整个Cluster Map进行分发或广播显然会造成资源的浪费,RADOS采用分发incremental map的策略避免资源浪费,其中incremental map仅包含了两个连续epoch之间Cluster Map的增量信息。

2.Data Placement

数据迁移:当有新的储存设备加入时,机群上的数据会随机的选出一部分迁移到新的设备上,维持现有存储结构的平衡。

数据分发:通过两个阶段的计算得到合适的Object的存储位置。如图2所示。

图2 数据分发图示

1.Object到PG的映射。PG (Placement Group)是Objects的逻辑集合。相同PG里的Object会被系统分发到相同的OSDs集合中。由Object的名称通过Hash算法得到的结果结合其他一些修正参数可以得到Object所对应的PG。

2.RADOS系统根据根据Cluster Map将PGs分配到相应的OSDs。这组OSDs正是PG中的Objects数据的存储位置。RADOS采用CRUSH算法实现了一种稳定、伪随机的hash算法。CRUSH实现了平衡的和与容量相关的数据分配策略。CRUSH得到的一组OSDs还不是最终的数据存储目标,需要经过初步的filter,因为对于大规模的分布式机群,宕机等原因使得部分节点可能失效,filter就是为过滤这些节点,如果过滤后存储目标不能满足使用则阻塞当前操作。

3.Device State

Cluster Map中关于Device State的描述见下表所示。

表1 Device State描述

in out
assigned PGs not assigned PGs
up online & reachable active online & idle
down unreachable unreachable & not remapped failed

4.Map propagate

Cluster Map在OSD之间的更新是通过一种抢占式的方法进行。Cluster Map epoch的差异只有在两个通信实体之间有意义,两个通信实体在进行信息交换之前都需要交换epoch,保证Cluster Map的同步。这一属性使得Cluster Map在通信实体内部之间的更新分担了全局的Cluster Map分发压力。

每一个OSD都会缓存最近Cluster Map和到当前时刻的所有incremental map信息,OSD的所有message都会嵌入incremental map,同时侦听与其通信的peer的Cluster Map epoch。当从peer收到的message中发现其epoch是过期的,OSD share相对peer来说的incremental map,使通信的peers都保持同步;同样的,当从peer收到message中发现本地epoch过期,从其嵌入到message中的incremental map中分析得到相对本地的incremental map然后更新,保持同步。

不是同一个通信对等方的两个OSD之间的epoch差异,不影响同步。

3.2 智能存储

1Replication

RADOS实现了三种不同的Replication方案,见下图3示:

图3 RADOS实现的三种replication方案

Primary-copy:读写操作均在primary OSD上进行,并行更新replicas;

Chain:链式读写,读写分离;

Spaly:Primary-copy和Chain的折中方案:并行更新replicas和读写分离。

2Consistency

一致性问题主要有两个方面,分别是Update和Read:

  1. Update:在RADOS系统中所有Message都嵌入了发送端的map epoch协调机群的一致性。
  2. Read:为避免部分OSD失效导致数据不能从该OSD读需要转向新的OSD,但是read operation的发起方还没有该OSD的失效信息的问题,同一个PG所在的OSDs需要实时交换Heartbeat。

3Failure Detection

错误检测:RADOS采取异步、有序的点对点Heartbeat。(此处的错误检测是OSDs自身检测)

4Data Migration & Failure Recovery

由于设备失效、机群扩展、错误恢复造成的Cluster Map更新使得PG到OSDs的对应关系发生了变化,一旦Cluster Map发生变化,相应的OSDs上的数据也需要做相应的调整。

数据的移植和数据恢复都是由Primary OSD负责统一完成。

(Data Migration & Failure Recovery具体方法待续)

3.3 Monitors

Monitors是Cluster Map主备份存储目标,所有其他位置上的Cluster Map最初都是从Monitors请求得到。Monitors通过对Cluster Map的周期更新升级实现存储机群的管理。

Monitor的工作分两个阶段:

1.首先在多个Monitors中选举Leader,之后Leader向所有Monitors请求Map Epoch,Monitors周期性向Leader汇报结果并告知其活跃(Active Monitor),Leader统计Quorum。这阶段的意义是保证所有的Monitors的Map Epoch都是最新的,通过Incremental updates对已失效的Cluster Map进行更新。

2.Leader周期向每一个Active Monitor授权许可提供分发Cluster Map副本给OSDs和Clients的服务。当授权失效但Leader仍没有重新分发认为Leader died,此时重回第一阶段进行Leader重选;当Active Monitor没有周期向Leader反馈ACK则认为有Monitor died,重回第一阶段进行Leader选举并更新Quorum。Leader周期分发Lease和Active Monitor周期反馈ACK的另外一个作用是同步Monitors的Cluster Map。Active Monitor收到Update请求时,首先验证当前的Epoch是否为最新,如果不是,更新后向上汇报到Leader,Leader分发给所有的Monitors,同时回收授权,重新开始新一轮的Leader选举到Cluster Map服务。

通常Monitor的负载比较小:OSDs上的Cluster Map更新通过OSDs之间的机制实现;OSDs的状态变化比较罕见不会对Monitors的负载造成影响。但是一些特殊情况可能会对Monitors负载带来影响,比如:同时有n OSDs failed,每一个OSD store m个PGs,此时会形成m×n个failure report到达Monitors,对于规模较大的机群这样的数据量比较大。为避免这种情况给Monitor带来的负载压力,OSDs采用伪随机的时间间隔交错安排failure检测(此处是从OSDs到Monitor的检测)向上汇报,另外根据Monitors的并行化和负载均衡分配的特点,扩展Monitors是解决Monitors的负载压力的另一措施。

4 总结

与传统的分布式数据存储不同,RADOS最大的特点是:

1.将文件映射到Objects后利用Cluster Map通过CRUSH计算而不是查找表方式定位文件数据在存储设备中的位置。省去了传统的File到Block的映射和BlockMap管理。

2.RADOS充分利用了OSDs的智能特点,将部分任务授权给OSDs,最大程度的实现可扩展。

5 参考文献

[1]     RADOS: A Scalable, Reliable Storage Service for Petabyte-scale Storage Clusters.

[2]     Ceph: A Scalable, High-Performance Distributed File System.