大数据日知录读书笔记(1):大数据基础理论

1.大数据概览

1.1 定义

最广为接受的定义为4V定义

  • 数据量大(volumn):google一天处理数据量25PB
  • 多样性(variety):结构化数据(数据库中的表)、非结构化数据(图片、音频、视频)
  • 高速性(velocity):数据产生速度快,比如各种实时传感器数据
  • 价值性(value):价值密度低

1.2 大数据基本处理流程

图片说明

1.3 大数据技术架构

图片说明

1.4 大数据相关公司

第一类:基础架构与平台

第二类:完善分布式计算生态系统的技术型公司

  • Cloudera
  • MapR
  • HortonWorks

第三类:其他

  • 免费网络文件同步工具:DropBox
  • 大数据算法分析和工具:ZillaByte
  • 大数据实时商业分析服务:decide.com

2.数据分片与路由

数据分片:将数据切分后存储在各个节点
数据路由:从各个节点找到所有数据分片

2.1 分片(shard)抽象模型

总体上分两种

  • 哈希分片:key-value形式的,只支持点查询

  • 范围分片:支持点查询和范围查询(给定键值范围即可查到所有符合的值)

2.2 哈希分片

  • 哈希取模法(Round Robin):用k表示,机器的台数,H(key)表示存储数据的物理机编号,用这种方式将数据分配到各个物理机上,公式为

H(key)=hash(key)mod k 缺点是缺乏灵活性,增加机器就要重新分配,本质上他是将key->partition和partition->machine两个映射合二为一了。

  • 虚拟桶:(Membase)couchbase提出的一种方法。设计一个桶的数据结构在内存和key进行映射,然后桶在和外部物理机器的存储对应。key->bucket之间由一个映射表维护,当增加物理机器的时候只要修改这张表即可。这种思路在数据库的一些连接算法也经常用到。

图片说明

  • 分布式哈希(DHT):一致性哈希是DHT实现方法中的一种,key->partition和partition->machine采用同一个哈希函数,哈希空间解耦,具备较高灵活性,用于P2P网络,由于P2P网络本身复杂性,这种方式虽然灵活,但是维护也麻烦

2.3 范围分片

就是把一组键空间对应一个分区 keys->partitions

3.数据复制与一致性

3.1数据存储的基本理论模型之:CAP模型

  • 强一致性(consistency):分布式系统中不同副本之间一致
  • 可用性(Availability):任何时刻对数据系统的读写操作在一定时间内完成
  • 分区容忍性(Partition Tolerance):分区的机器无法通信,整个系统仍然能够继续工作

已经证明的规律:CAP只能同时被满足两个,架构师应在AP和CP之间进行权衡和选择,有所强调和放弃。分布式必然满足P。一致性和可用性是有所矛盾的。NoSql更加关注AP

改进:在没有分区的时候可以考虑同时满足A和C

3.2数据存储的基本理论模型之:ACID模型

主要是RDBMS遵循的模型

  • 原子性(Atomicity):一个事务要么执行要么不执行
  • 一致性(consistency):一个事务的执行如果对别的数据造成影响,那么也要一起改动。和CAP里面的C不同
  • 独立性(Isolation):事务之间序列化执行
  • 持久性(Durabilitity):运行成功后对系统的更新是永久的

3.3 数据存储的基本理论模型之:BASE模型

主要是nosql采用的原则

  • 基本可用性(Basically Available):绝大多数时间内可用,允许偶尔失败
  • 轻状态或者柔性状态(soft state):数据不要求任意时刻保持同步
  • 最终一致性(Eventual Consistency):弱一致性,最终能达到一致性即可

现在即使nosql也开始借鉴acid特性,融合是趋势,例如google的megastore

4.大数据常用算法和数据结构

4.1布隆过滤器(bloom filter)

m=位数组长度 k=哈希函数个数

流程伪代码:

注意:每个要存放的数据,要经过所有的hash函数处理

图片说明

判断是否在集合中的伪代码:

图片说明

优点:极大的节约空间,表征集合数据。具有极好的空间和时间效率

缺点:有误判率(不在集合的认为在集合内),但是不会漏判(在集合内的肯定不会认为不在),无法删除数据(要数据可以采用计数BF,多个比特位当作一个单元,需要删除的时候通过减1即可)

给定误判率和集合大小设置m位数组大小的计算公式:

图片说明

应用:

  • google chrome 恶意url判断
  • 网络爬虫对已经爬过的url判断
  • 海量数据查找,例如bigtable,将key值保存在bf结构中,如果误判也就多次磁盘读而已