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