求知 文章 文库 Lib 视频 iPerson 课程 认证 咨询 工具 讲座 Modeler   Code  
会员   
 
  
 
 
     
   
分享到
海量数据下的分布式存储与计算
 

作者:葑岚 ,发布于2013-1-15,来源:CSDN

 

存储

从理论角度

提到大数据存储nosql是不得不提的一个部分,CAP,BASE,ACID这些原理在过去的一些年对其有着一定的指导作用(近年来随着各种实时计算模型的发展,CAP也被渐渐打破)

CAP:(Consistency-Availability-Partition Tolerance

数据一致性(C): 等同于所有节点访问同一份最新的数据副本;

对数据更新具备高可用性(A): 在可写的时候可读, 可读的时候可写,最少的停工时间

能容忍网络分区(P)

eg:

传统数据库一般采用CA即强一致性和高可用性

nosql,云存储等一般采用降低一致性的代价来获得另外2个因素

ACID:按照CAP分法ACID是许多CA型关系数据库多采用的原则:

A:Atomicity原子性,事务作为最小单位,要么不执行要么完全执行

C:Consistency一致性,一个事务把一个对象从一个合法状态转到另一个合法状态,如果交易失败,把对象恢复到前一个合法状态。即在事务开始之前和事务结束以后,数据库的完整性约束没有被破坏

I:Isolation独立性(隔离性),事务的执行是互不干扰的,一个事务不可能看到其他事务运行时,中间某一时刻的数据。

D:Durability:事务完成以后,该事务所对数据库所作的更改便持久的保存在数据库之中,并不会被回滚

BASE:一般是通过牺牲强一致性,来换取可用性和分布式

BA:Basically Aavilable基本可用:允许偶尔的失败,只要保证绝大多数情况下系统可用

S:Soft State软状态:无连接?无状态?

E:Eventual Consistency最终一致性:要求数据在一定的时间内达到一致性

以云存储为例:目前的云存储多以整体上采用BASE局部采用ACID,由于使用分布式使用多备份所以多采用最终一致性

Nosql常见的数据模型有key/value和Schema Free(自由列表模式)两种,

key/value,每条记录由2个域组成,一个作为主键,一个存储记录的数据(mongodb)

Schema Free, 每条记录有一个主键,若干条列组成,有点类似关系型数据库(hbase)

在实现这些模型的时候基本使用2种实现方式:哈希加链表,或者B+树的方式

哈希加链表:通过将key进行哈希来确定存储位置,相同哈希值的数据存储成链表

基本的hash寻址算法有除法散列法,平方散列法,斐波那契(Fibonacci)散列法等,但是java是这样做的

static int indexFor(int h, int length) {

return h & (length-1);

}

java会用key的hashcode值与数组的槽数-1进行与运算

这里会有一个问题只有当数组的槽数为2的n次方-1,其二进制全是1的(如2的2次方-1=11)的时候哈希值产生碰撞的概率是最小的
所以在java中hashmap的数组的初始大小是16(2的4次方)

hashmap的问题

hashmap的resize:

当不断put数据使数据慢慢变大的时候,刚开始的数组已经不能满足需求了,我们需要扩大数组的槽数
hashmap中有loadFactor属性,该属性默认为0.75,即元素个数达到数组的百分之七十五的时候,数组槽数会进行翻倍,并且之前已存入的数据会重新进行计算。

so:如果我们可以预估我们会在hashmap中存放1000个数据,那么我们就要确保数组的槽数乘上0.75大于1000,我们得到1366,如果我们这样写new HashMap(1366),java会自动帮我们转换成new HashMap(2048)(2的n次方)

B+树:B+树的特点

1.节点中关键字数量与字节点数相同。  

2.所有叶子结点中包含全部指向记录的指针

3.叶子结点按照自小而大顺序链接

5通常在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点(爬虫会有深度优先,广度优先的算法)

来自百度的图

so:hash查找单条非常快

b+树,范围查找很快(深度优先,广度优先的遍历等)

需要一个可以排序的hash结构

空间换时间:跳表+hashtable实现可排序的hash

eg:ConcurrentSkipListMap

跳表结构

so:增,删,改(通过跳表)的复杂度为o(log(n))

查(通过hashtable)的复杂度为O(1)

当然我们不知道有结构化的数据,特别我们存储的数据是需要拿来进行复杂的数据挖掘算法,所以有的时候nosql并不能满足我们的需要

实际的数据

结构化

半结构化(我们的数据)

非结构化

海量(百T级别)

数据偶尔丢掉几条没关系

数据质量差

选择hdfs的原因

hdfs在设计之初考虑到了以下几个方面:

1,hdfs将采用大量稳定性差的廉价pc来做为文件存储设备,所以pc发生死机或硬盘故障的几率极高,应看作是常态,所以hdfs应该提供数据多备份,自动检测节点存活,和故障机器的自动修复

2,hdfs存储的大多是大文件,所以针对大文件的读写会作出优化

3,对于写入数据来说,系统会有很多追加操作,而很少会有随机读写

4,对于读取数据来说,大多数的操作是顺序读,很少有随机读

计算

从理论角度

离线计算 :针对海量的,对实时性要求不是很高的数据

实时流计算 :数据清洗,topn等应用场景

列存储 :大表jion,海量数据实时查找

key-value :对半结构化,非结构化数据的实时查找(结构灵活,适合项目初期的试错阶段)

内存和磁盘计算的区别

寻址

内存是通过电子工作的,所以搜索速度和物理结构无关,进行寻址时只需要微秒级别既可以

磁盘在寻址时需要1,移动磁头2,旋转磁盘 因为磁盘旋转的速度有限,所以寻址消耗毫秒别时间

*操作系统会将一个连续的数据存放在一起(win一般是4KB),这样磁盘旋转一周读取的数据就会多些,从而提高效率

传输速度

内存和硬盘的数据都会被读到cpu的缓存中,但是从内存到缓存和从硬盘到缓存的传输速度是差别很大的

内存到缓存的速度大概有7-8GB/秒,而磁盘到缓存的速度大概只有60MB/秒

so:因此内存计算和磁盘计算的速度差可以达到百万倍以上

离线计算

hadoop现了mapreduce的思想,将数据切片计算来处理大量的离线数据数据。

hadoop处理的数据必须是已经存放在支持的分布式文件系统上或者类似hbase的数据库中,所以hadoop实现的时候是通过移动计算到这些存放数据的机器上来提高效率

ps:针对hadoop我们的使用是开发一个类似pig的mdx框架,与pig的区别是我们的框架会更加的针对业务友好,业务人员只需要了解维度信息和需要的度量即可

实时流计算

storm是一个流计算框架,处理的数据是实时消息队列中的,所以需要我们写好一个topology逻辑放在那,接收进来的数据来处理,所以是通过移动数据平均分配到机器资源来获得高效率

列存储

提出region和Xfile概念(如hbase的HFILE和hive的rcfile以及yuntable的YFile)
根据key将数据分到不同的region,保存log,数据压缩并行列转置后存到Xfile,定期或使用内存到了一定阙值flash到硬盘

列存优点举例-

eg1:通过region和XFile过滤掉大量数据,如果对100g的数据做分析

通过region会过滤掉一大批数据

对于数值类型,每个xfile会有一个预统计(最大最小值)又会过滤掉一部分数据

假设还剩下2.5g的数据

对于频繁使用的数据会在内存中有缓存

假设命中2g

剩下的0.5g会已压缩的方式存放在硬盘(定长字段压缩比更大,当然数字的压缩比最大)

so-100g的查询=》2g的内存查找+0.5g的硬盘查找(内存寻址是硬盘寻址的几百万倍)

eg2:通过动态扩展列来进行大表的jion

google的bigtable进行cookie的join,是将一个几千万的用户行为的表jion到一张100亿行的cookie大表,它只需要将新的表根据cookie重新做一下索引即可,因为数据是列存储所以具体的数据存储不需要实际的硬盘移动,大大减少了jion的时间,尽管这个表有几十万的列但对查找几乎是没有影响的

key-value

存储非结构化数据

-eg:评论,问答

再看下数据

结构化

半结构化(我们的数据)

非结构化

海量(百T级别)

数据偶尔丢掉几条没关系

数据质量差

到目前为止我们的处理方案是:

离线分析(对实时性要求不高-hadoop)-结构化,半结构化,非结构化

实时分析(对实时性要求极高-storm)-结构化,半结构化,非结构化

实时查找(经常性对大量数据进行count等操作-infobright,hbase)-结构化,部分支持半结构化

有时我们需要对非结构化的数据做一些实时搜索的功能keyvalue搞不定怎么办--实时搜索(巧妙设计数据结构)

我们的做法是:

倒排索引

+关键字的前缀冗余

具体关键字的前缀冗余使用redis的zset完成,其本质也是一个hashtable+跳表的所以结构

这样存的时候需要切词,存储,key和关键字映射的存储,前缀和关键字映射的存储

但是读的时候是非常迅速的,如下图当用户输入J 就可以很快的找到关于java等的信息(当然还需要一些评分,权重算法)

服务架构需要考虑的问题:

CPU负载和I/O负载(计算密集型和io密集型)

CPU负载-计算密集型

所谓CPU负载就是通常的web服务等,这些服务基本上只消耗cpu,所以只要增加安装相同服务的服务器,然后就可已通过负载均衡器工作了

I/O负载-io密集型

1.数据的切割和在机器间的分配策略(原则是尽量移动计算而不是移动数据)

2.如何通过多备份来确保数据的可用性(确保多备份的一致性)

3.如何使集群针对性强的响应客户端的读写请求

4.如何实现集群中单台机器的热拔插

5.好的负载均衡策略

6.网络通信延迟,因为计算机运行的速度是微秒甚至纳秒,所以毫秒级别的延迟对程序来说性能损害是极大的

ps:我们平常使用的路由器一般pps(每秒转发数为几十万左右),所以一般的千兆以太网的极限就在几十万/秒

除此之外由于正常的路由器的ARP表上限为900左右

两个原因导致一个子网中机器不能过多,当集群中机器过多时就需要进行网络的层次话

虚拟化优点

1,扩展性-可以动态的迁移和复制,使得服务器增加变得更简单

2,提高资源利用率

3,降低运维成本(远程管理,环境更单一异常行为局部化,使得主机控制更简单)

4,提高可用性(抽象硬件差异)

5, 调整负载(软件层面对负载进行控制,当监测到负载消耗异常可重启进程或者虚拟机)

缺点

1,虚拟机本身的损耗(cpu,内存)

2,网络性能损耗近一半

3,I/O性能略微降低0.5%左右

相关文章 相关文档 相关视频



我们该如何设计数据库
数据库设计经验谈
数据库设计过程
数据库编程总结
数据库性能调优技巧
数据库性能调整
数据库性能优化讲座
数据库系统性能调优系列
高性能数据库设计与优化
高级数据库架构师
数据仓库和数据挖掘技术
Hadoop原理、部署与性能调优
 
分享到
 
 


MySQL索引背后的数据结构
MySQL性能调优与架构设计
SQL Server数据库备份与恢复
让数据库飞起来 10大DB2优化
oracle的临时表空间写满磁盘
数据库的跨平台设计
更多...   


并发、大容量、高性能数据库
高级数据库架构设计师
Hadoop原理与实践
Oracle 数据仓库
数据仓库和数据挖掘
Oracle数据库开发与管理


GE 区块链技术与实现培训
航天科工某子公司 Nodejs高级应用开发
中盛益华 卓越管理者必须具备的五项能力
某信息技术公司 Python培训
某博彩IT系统厂商 易用性测试与评估
中国邮储银行 测试成熟度模型集成(TMMI)
中物院 产品经理与产品管理
更多...