存档

‘BigData’ 分类的存档

Reed Solomon Erasure Codes

2014年7月12日 没有评论

[latexpage]
上一篇文章《Finite Field Arithmetic》介绍了有限域上的运算,理解有限域上的运算,是理解erasure编码的基础。今天这篇文章就来介绍一下erasure编码。在分布式存储系统中,通常会通过多副本的方式来保证数据的可靠性,但是多副本带来的成本问题也是显而易见的。在类HDFS这样的系统中,通常数据都会保留三副本,三副本可以容有两副本故障的场景,但同时成本也是一副本的三倍。如何在保证同等的数据可靠性的前提下,减少副本数,降低成本,是分布式存储系统中很重要的一个课题。Erasure编码正是用来解决这个问题的,它能将副本降到1.x的同时,保证同等的数据可靠性保证。本文会以最常用的Reed Solomon erasure编码为例来介绍。

基本思想

erasure-codes
如上图所示,我们总共有$n$块盘,其中$k$块用来存放数据,m块用来存储erasure编码($k+m=n$),在上面的$n$块盘中,任意坏$m$块,都可以通过erasure编码将其余的恢复出来。也就是说,通常$k+m$的erasure编码,能容$m$块盘故障的场景,这时候的存储成本是$1+m/k$, 通常$m 阅读全文…

Finite Field Arithmetic

2014年6月28日 没有评论

[latexpage]
在分布式存储系统中,通常通过多副本的方式来保证数据的可靠性。Erasure编码,是分布式系统中用来在保证跟多副本同等可靠性的前提下,减少副本、节约成本的标准做法。有限域(Finite Field)上的四则运算是Erasure编码在分布式存储系统中应用的基础。今天这篇文章介绍一下有限域(Finite Field)及其上面的运算, 后续文章再介绍Erasure编码。

什么是有限域(Finite Field)

大小为$n$的集合,在其上的任何四则运算(加、减、乘、除)的结果仍在这个集合中,表示为$GF(n)$

有限域(Finite Field)有什么样的性质

对于有限域GF(n)中的元素A(0除外), 均存在:
1. $A+B=0$, $B$称之为$A$的加逆, $-A$(Addition inverse, 可以跟相反数据类比)
2. $A*B=1$, $B$称之为$B$的乘逆, $A^{-1}$(Multiplication inverse, 可以跟倒数类比)
由上面的性质可以推论,在有限域上的减法都可以转化为加法,除法都可以转化为乘法

$GF(n)$($n$为素数)有限域上的运算法则

对于$GF(n)$, 如果$n$是素数,可以这样来定义$GF(n)$,及其上的四则运算:
$GF(n) = {0, 1, 2, \dots, n-1}$
加: $A + B = (A + B) \mod n$
减: $A – B = (A + (-B)) \mod n$
乘: $A * B = (A * B) \mod n$
除: $A / B = (A * B^{-1}) \mod n$

阅读全文…

我所理解的Paxos

2014年6月1日 没有评论

Paxos是前段时间刚获得图灵奖的大神Leslie Lamport所提出的,是用来解决分布式系统中的一致性问题的算法。该算法对于分布式系统的重要性,在这里不再赘言。了解过Paxos的朋友应该都知道,要完全理解Paxos不是一件容易的事。本文是笔者在学习Paxos时,用来帮助自己更好的理解Paxos所梳理的一遍文章,希望能够通过通俗易懂的方式,把Paxos理解清楚。

Paxos要解决的问题

我们知道,Paxos要解决的问题,是分布式系统中的一致性问题。到底什么是“分布式系统中的一致性问题”呢?在分布式系统中,为了保证数据的高可用,通常,我们会将数据保留多个副本(replica),这些副本会放置在不同的物理的机器上。为了对用户提供正确的读/写/删/改等语义,我们需要保证这些放置在不同物理机器上的副本是一致,这就是Paxos所要解决的问题。
Paxos-Scenario 阅读全文…

ZooKeeper原理及使用

2013年12月15日 3 条评论

ZooKeeper是Hadoop Ecosystem中非常重要的组件,它的主要功能是为分布式系统提供一致性协调(Coordination)服务,与之对应的Google的类似服务叫Chubby。今天这篇文章分为三个部分来介绍ZooKeeper,第一部分介绍ZooKeeper的基本原理,第二部分介绍ZooKeeper提供的Client API的使用,第三部分介绍一些ZooKeeper典型的应用场景。

ZooKeeper基本原理

1. 数据模型
zookeeper-tree
如上图所示,ZooKeeper数据模型的结构与Unix文件系统很类似,整体上可以看作是一棵树,每个节点称做一个ZNode。每个ZNode都可以通过其路径唯一标识,比如上图中第三层的第一个ZNode, 它的路径是/app1/c1。在每个ZNode上可存储少量数据(默认是1M, 可以通过配置修改, 通常不建议在ZNode上存储大量的数据),这个特性非常有用,在后面的典型应用场景中会介绍到。另外,每个ZNode上还存储了其Acl信息,这里需要注意,虽说ZNode的树形结构跟Unix文件系统很类似,但是其Acl与Unix文件系统是完全不同的,每个ZNode的Acl的独立的,子结点不会继承父结点的,关于ZooKeeper中的Acl可以参考之前写过的一篇文章《说说Zookeeper中的ACL》。 阅读全文…

分类: Zookeeper 标签: ,

From MapReduce To YARN

2013年11月5日 2 条评论

Google MapReduce

MapReduce是由Google提出的一种软件架构,用于大规模数据的并行计算。Map和Reduce这两个概念,是从函数式编程语言中借鉴过来的。正如Google MapReduce Paper中所描述,MapReduce是这样一个过程:输入是Key/Value对A,用户指定一个Map函数来处理A,得到一个中间结果Key/Value集合B,再由用户指定的Reduce函数来把B中相同Key的Value归并到一起,计算得到最终的结果集合C,这就是MapReduce的基本原理,可以简单的表达为:
map (k1, v1) -> list (k2, v2)
reduce (k2, list(v2)) -> list (v2)

MapReduce的原理本身比较简单,但开发一套完备、易用性好的MapReduce系统,不是一件容易的事。这里会涉及分布式系统的故障容错、负载均衡等一系列复杂的问题。下面就结合在Google MapReduce Paper所讲的MapReduce的执行流程,来介绍一下MapReduce系统的基本工作原理: 阅读全文…

分类: BigData, MapReduce, YARN 标签: , ,

Distributed System Prerequisite List

2013年10月27日 1 条评论

bigdata写在前面:不知不觉,来帝都已经一年整了,这也意味着从search转向分布式系统真正一年了。当初选择这个方向,也考虑到过会有很多不容易,但是既然决定了、选择了,就要努力去做好。过去的一年,也曾迷惘过,也曾沮丧过,但好在努力坚持了下来。总得来说,对所目前的状态,以及所做的事还是充满了信心。一直以来,都坚信只要是自己喜欢的事情,努力去做了,就一定能做好,这是支撑我不断努力、奋斗的信念。最近一直在考虑一个事情,过去的一年,在工作之余,陆陆续续零零散散看了不少分布式相关的资料,打算把这一块好好梳理一下,希望在接下来一年左右时间,通过系统地、深入地学习,对这个领域的理解能够更加全面、透彻。这也是今天写下这篇文章的一个初衷,一方面是给自己接下来的学习理清一个思路,另一方面,也是希望能够与有同样需求的朋友共勉。

接下的内容按几个大类来列: 阅读全文…

分类: BigData 标签:

HDFS ZKFC手记

2013年6月13日 6 条评论

1.基本原理

zk的基本特性:
(1) 可靠存储小量数据且提供强一致性
(2) ephemeral node, 在创建它的客户端关闭后,可以自动删除
(3) 对于node状态的变化,可以提供异步的通知(watcher)

zk在zkfc中可以提供的功能:
(1) Failure detector: 及时发现出故障的NN,并通知zkfc
(2) Active node locator: 帮助客户端定位哪个是Active的NN
(3) Mutual exclusion of active state: 保证某一时刻只有一个Active的NN

2. 模块

(1) ZKFailoverController(DFSZKFailoverController): 驱动整个ZKFC的运转,通过向HealthMonitor和ActiveStandbyElector注册回调函数的方式,subscribe HealthMonitor和ActiveStandbyElector的事件,并做相应的处理
(2) HealthMonitor: 定期check NN的健康状况,在NN健康状况发生变化时,通过回调函数把变化通知给ZKFailoverController
(3) ActiveStandbyElector: 管理NN在zookeeper上的状态,zookeeper上对应node的结点发生变化时,通过回调函数把变化通知给ZKFailoverController
(4) FailoverController: 提供做graceful failover的相关功能(dfs admin可以通过命令行工具手工发起failover) 阅读全文…

分类: BigData, HDFS 标签: , , ,

说说Zookeeper中的ACL

2013年6月2日 没有评论

Access Control在分布式系统中重要性是毋庸置疑的,今天这篇文章来介绍一下Zookeeper中的Access Control(ACL)。

  • 1. 概述
    传统的文件系统中,ACL分为两个维度,一个是属组,一个是权限,子目录/文件默认继承父目录的ACL。而在Zookeeper中,node的ACL是没有继承关系的,是独立控制的。Zookeeper的ACL,可以从三个维度来理解:一是scheme; 二是user; 三是permission,通常表示为scheme:id:permissions, 下面从这三个方面分别来介绍:

    (1)scheme: scheme对应于采用哪种方案来进行权限管理,zookeeper实现了一个pluggable的ACL方案,可以通过扩展scheme,来扩展ACL的机制。zookeeper-3.4.4缺省支持下面几种scheme:

    • world: 它下面只有一个id, 叫anyone, world:anyone代表任何人,zookeeper中对所有人有权限的结点就是属于world:anyone的
    • auth: 它不需要id, 只要是通过authentication的user都有权限(zookeeper支持通过kerberos来进行authencation, 也支持username/password形式的authentication)
    • digest: 它对应的id为username:BASE64(SHA1(password)),它需要先通过username:password形式的authentication
    • ip: 它对应的id为客户机的IP地址,设置的时候可以设置一个ip段,比如ip:192.168.1.0/16, 表示匹配前16个bit的IP段
    • super: 在这种scheme情况下,对应的id拥有超级权限,可以做任何事情(cdrwa)
    • 阅读全文…

HDFS datanode阅读手记

2013年1月28日 没有评论

1. Hign Level Module View

datanode modules

  • HttpServer: 提供http service, 展示内部状态信息
  • IPCServer: Rpc service framework, 模块间的交互都通过rpc来完成(Block数据传输除外)
  • DataXceiverServer: 数据传输server, 提供Block数据的读写修改等功能
  • BlockPoolManager: 提供管理BlockPool的相关API。其中,BlockOfferService为每个Namespace下每个BlockPool一个实例,提供BlockPool对它所对应的Namespace的操作的相关API, BlockServiceActor为指定Namespace中每个namenode一个实例,自已持有线程,定时向它所对应的namenode发heartbeat, blockreport, 并执行namenode通过heartbeat/blockreport response传回来的command
  • FsDataset: 封装了datanode所管理的所有的block相关数据,提供相关的API,其中FsVolume封装了对单块盘的相关的操作
  • 阅读全文…

分类: BigData, HDFS 标签: , ,

Hadoop, Hbase, Zookeeper安全实践

2012年12月31日 19 条评论

过去的一个月,一直在折腾Hadoop, Hbase, Zookeeper的安全,中间碰到各种坑,在这里做一个简单的总结,希望能够抛砖引玉,与感兴趣的朋友交流一些实践经验。说到安全,这里主要包括两个方面,一个是Authentication,一个是Authorization:

  • Authentication要做的事情,是认证用户的身份,即你说你是A用户, Authentication要确保你真的是A,而不是B;
  • Authorization要做的是权限控制,就是对A用户只能操作它自己有权限的实体(比如HDFS的文件,Hbase的表),对于他没有权限的他不能操作。

有了Authentication和Authorization,总体上算是比较安全了,基本上不会出现,像A用户误删了B用户的数据的事情。在Hbase/Hadoop/Zookeeper中,Authentication是通过Kerberos是实现的,Authorization有各自的实现,相比而言,Authentication的实现相对复杂一些,里面的坑也比较多,因此本篇文章的大部分篇幅会以Authentication为主。对Kerberos之前没了解的同学,可以看一下这篇文章:[Hadoop Kerberos安全机制介绍][1],里面介绍Kerberos认证原理的部分讲得比较清楚。下面就我在实践过程中遇到的一些坑做一个总结。

在实践开始之前,先安装好Kerberos服务器,kerberos的安装比较简单,也不是本文要讨论的内容,直接在google搜索,相关的tutorial应该比较多,照着一步步做下来一般都不会有问题,需要注意的就是区分OS发行版,比如Ubuntu和CentOS,会有一些细微的差别。 阅读全文…

Hadoop/Hbase配置集成Ganglia

2012年11月11日 3 条评论

Hadoop/Hbase是开源版的google Bigtable, GFS, MapReduce的实现,随着互联网的发展,大数据的处理显得越发重要,Hadoop/Hbase的用武之地也越发广泛。为了更好的使用Hadoop/Hbase系统,需要有一套完善的监控系统,来了解系统运行的实时状态,做到一切尽在掌握。Hadoop/Hbase有自己非常完善的metrics framework, 里面包种各种维度的系统指标的统计,另外,这套metrics framework设计的也非常不错,用户可以很方便地添加自定义的metrics。更为重要的一点是metrics的展示方式,目前它支持三种方式:一种是落地到本地文件,一种是report给Ganglia系统,另一种是通过JMX来展示。本文主要介绍怎么把Hadoop/Hbase的metrics report给Ganglia系统,通过浏览器来查看。

介绍后面的内容之前有必要先简单介绍一下Ganglia系统。Ganglia是一个开源的用于系统监控的系统,它由三部分组成:gmond, gmetad, webfrontend, 三部分是这样分工的:

  • gmond: 是一个守护进程,运行在每一个需要监测的节点上,收集监测统计,发送和接受在同一个组播或单播通道上的统计信息
  • gmetad: 是一个守护进程,定期检查gmond,从那里拉取数据,并将他们的指标存储在RRD存储引擎中
  • webfrontend: 安装在有gmetad运行的机器上,以便读取RRD文件,用来做前台展示

简单总结它们三者的各自的功用,gmond收集数据各个node上的metrics数据,gmetad汇总gmond收集到的数据,webfrontend在前台展示gmetad汇总的数据。Ganglia缺省是对系统的一些metric进行监控,比如cpu/memory/net等。不过Hadoop/Hbase内部做了对Ganglia的支持,只需要简单的改配置就可以将Hadoop/Hbase的metrics也接入到ganglia系统中进行监控。 阅读全文…