大数据日知录读书笔记(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结构中,如果误判也就多次磁盘读而已