构建大数据系统的前沿技术概述
第一部分存储模型之前,先抛两个问题:
1)这些存储的数据结构,主要是来优化什么操作的?
2)SSD对于这些存储结构有什么样的影响?
一. 存储模型--读和写的取舍
一个好的存储结构,我们希望的是更新数据快,查找特定的数据也快,最好占用空间还小,一般来说,这算得上是对存储的终极要求了。
终极要求,这东西一般都是YY,但是,加上一定的限制条件,在特定的时期,数据大爆炸之前,单机时代,B树这个结构,可以算得上是银弹。基本上所有的关系型数据库系统都采用这种结构。SqlServer和Oracle都采用B树,Mysql,Db2还有informix采用的B+树,
磁盘读数据和写数据的过程,1)移动磁头到对用的扇区,2)然后磁头接触磁道,写或者读数据,3)通过总线传输到内存或者寄存器。
磁头移动时间,十分之一秒的级别,读写的时间,按照普通磁盘,7200转的,差不多在百分之一秒级不到,还有一个耗时就是总线传输时间,这个基本可以忽略,在10的8次方分之秒。
另一个背景知识是,文件系统, 读写是有最小操作单位的块,每次I/O操作,都是整块操作。块大小,跟文件系统的格式有关,fat32,ext3/4等等,常见的块大小4096个字节,块大小可以调整,块,对应到物理的扇区。
通过上面的分析,有效的优化是降低磁头定位的次数;B树就是综合读写两方面的需求,提出的对磁头定位操作优化的结构。隐含的数据特征是:重查询,轻新增,并发写要求不高。总的数据量优先,单挑记录会被反复更新,这刚好就是单机时代的数据特征。在做关系型数据库表设计的时候,知道这点会比较有用。
B+树和B*树是B树的两种变形,B+树降低了中间节点的数据大小,同样的块大小,可以存储更多的数据,检索上更有效率,但是,实际数据读取上有妥协。B*树,相对于B数在节点的分裂,旋转,平衡方面有增强。
进入互联网时代,数据的特征有了变化,写多读少,数据具备热点时间。有效期之后的数据,就相当于传统数据库的归档。另外一个有利的变化,是内存变得很便宜,可以用足够低的成本hold住热点数据。这种前提下,顺序写做持久化,热点数据保持在内存中,并且在内存中进行排序,保证顺序写入的数据是有序的。
基于这样的思路,就有了LSM-Tree和COLA-Tree两种改进。区别在于LSM的MemTable保持固定大小,持久化数据的索引都有compaction阶段完成。COLA的思路,是Memtable就按照固定的逻辑完成索引更新。COLA里面是没有Memtable这个名称的。
基本上现存所有的NoSQL都是采用LSM-Tree的思路,除了TokuDB。
Cassandrda和LevelDB,需要特别提一下,他们两个在Compaction阶段的实现,是参考了COLA的做法的,sstable做了分层合并。COLA在层之间,还引入了分形树(Fractal Tree)的实现,改进索引性能,Cassandra和LevelDB是没有,单层上数据检索,还是采用的BloomFilter和二分法。
二.实时计算-精度和速度的权衡
纯粹从性能对比,COLA跟B树算是公平对决,数据如下:块大小4098字节
查询Cola比B树慢12倍,插入速度是B树的340倍。
LSM不具备可比性,更多靠cache命中的效率。
之前提到的问题,SSD的影响,这么看起来,SSD对B树和Toku的影响要比LSM大(只是相对的),这些算法,对于ssd来说,算法对性能的影响并不重要,比较重要的反而是,通过算法降低,flash的读写次数,达到延长ssd使用寿命和减少损坏率。
除了需要保存检索数据,还需要对数据进行计算,流计算,实时计算的框架,已经是大数据里面到处可见,Storm,Spark Stream等等,这些流行框架更多是调度系统,真正的计算还需要自己来实现。
在我现在的实际工作中,常见的有点难度的计有exist是否存在,distinct count 去重计数,top n 等等在 window内部。
所有这些计算,对于内存都是很巨大的挑战。可行的做法,就是引入精度,接受概率。
这些做法,在数据挖掘的领域,已经是司空见惯的做法,比如关联规则挖掘的Apriori跟Fp-growth等都引入的概率的做法。
很多程序员其实也用过,一说就知道,Bloom Filter做去重,接受一定概率的误差,换来空间的减少,提升性能。
接下来介绍几个,我在实际工作中,用得比较多的方法,实际上是几个概念。
1)Bloom Filter
2)Sketching
3)基数估计
BF略过,大家都知道。Sketching,用于做频率估计,估算数据流中每个数据的出现次数。基本思路也跟BF差不多,通过互相独立的hash函数依次处理输入,接受一定程度的正负错判,估计值在一定概率内正确,这个概率可调整。这类方法的另一个优势是可以很容易实现分布式,能够合并。
Sketch有几个变种,basic sketch, counter sketch和counter min sketch,依次各有改进。
Bf和counter min sketch算是当前最优的top n的方法。Cms对于重复度高的效果较好,重复度不高了,有基于cms基础上的改进,counter-mean-min sketch。
上面在存储模型中间没有提到,cms还能够用在nosql的range query索引上,不追求精确度,在性能方面完爆B树。
基数估计也是类似的思路,用很少的空间,计算集合的势,常见的算法有Linear counter,LogLog counter两类,分别使用在重复情况比较明显和重复情况相对于总量来说较低
Redis在支持bitmap之后,在2.8.9之后,直接提供了hyperloglog的支持,每个 HyperLogLog 键只需要花费 12 KB 内存,就可以计算接近 2^64 个不同元素的基 数。线性的counter也可以直接利用bitmap实现。Hash函数的murmur是比较可以无脑使用的实现。
具体的算法描述,大家可以问百度,不细说了,知道有哪些可用场景就好。我们主要用在风险检测的参数计算方面。
三.分布式持久化-CAP的妥协
对于分布式持久化的内容,也扯两句,我个人很喜欢Dynamo模型的对称结构,BigTable的管理节点实在是不美观。也就是zk和gossip+vector clock的战争,这种选择也就决定了各自在CAP和ACID中间能够达到的水平。
四.日志为中心的基础架构设计
ArchSummit全球架构师峰会 上我也推荐过kafka的作者写的文章,在推荐一次,个人觉得每一个做分布式系统设计的架构师,都应该读几遍才好。
给大家看这样一个图
苏宁现在整体数据系统建设思路,差不多就是这样,通过日志,串行所有操作,避免冲突。基本上满足异地多活的需求。中间过程,分实时计算,批量计算并且在服务层合并数据。
数据分析咨询请扫描二维码
CDA数据分析师在中国航信高科技产业园进行了面向测试度量的数据分析培训课程,培训人数近2 ...
2024-05-01CDA数据分析师走进深圳迈瑞生物医疗电子股份有限公司,在迈瑞总部展开了为期两天的培训,本次课程参训人员线上及线下近百人, ...
2024-05-01CDA数据分析师在合肥市对合肥阳光新能源科技有限公司开展了为期8天的企业内训。 合肥阳光新能源科技 ...
2024-05-01CDA数据分析师走进海尔大学,进行了《数据治理与数据中台建设的道与术》专题培训,培训现场爆满,近百人参加了此次培训。 ...
2024-05-01在中国银行苏州分行培训中心开始数据分析师培训,此次培训课程共10天内容,包括Excel、MySQL、概率论与数理统计、SPSS等内容, ...
2024-05-01从实际的业务需求出发,结合行业的典型应用特点,围绕实际的商业问题,探讨数据挖掘、机器学习模型在金融领域的应用,包括获客、信用评分、细分画像、交叉销售、反欺诈、违规识别、时序预测、运筹优化、流程挖掘九个方面,形成 ...
2024-05-01本次培训课程为线上+线下的模式,由于学员编程能力不一、部分学员没有编程基础,故提供统计学、python基 ...
2024-05-01华夏银行信用卡中心-机器学习培训 1、课程亮点 取材于业界一流企业和顶级咨询公司的行业实践;已经被证明是人人 ...
2024-05-01主 题:数据中台建设及数据分析应用主题分享 1. 数据中台市场洞察 2. 主流数据中台产品比较 3. 某企业数据中 ...
2024-05-01围绕“数据驱动”战略,全力打造我行 300 人数字化人才梯队,着力培养数字化管理人才、大数据专业团队 ...
2024-05-01在当今数据驱动的商业环境中,数据分析成为了企业决策的重要依据。通过对大量数据的收集、处理和分析,企业能够更好地理解市场 ...
2024-04-29在人工智能(AI)的世界里,提示词(Prompt)是一种强大的工具,它能够引导AI按照用户的需求产生特定的输出。本文将深入探讨AI ...
2024-04-29CDA立足未来职场,拓展前沿视野——对外经贸大学保险学院举办“三全育人大讲堂”分享行业最新动态。 ...
2024-04-294月2日,CDA数据分析师创始发起人兼协会理事长赵坚毅博士受邀在浙江万里学院举办了一场以“数字化能力在职场中的作用” ...
2024-04-29随机森林(Random Forests)现在机器学习中比较火的一个算法,是一种基于Bagging的集成学习方法,能够很好地处理分类和回归的问 ...
2022-12-23方差分析是数据分析中常用的一种统计分析方法,接下来让我们简单了解一下方差分析的基本思想和原理吧。 方差分析(Analysis ...
2022-12-23来源:关于数据分析与可视化 关于streamlit-aggrid 数据排序 表格样式的调整 数据 ...
2022-08-03作者:麦叔 定义 「把上面晦涩的概念汇成一句话就是:」 ❝ 回调函数就是一个被作为参 ...
2022-08-03现今,高学历人群日益增多,物以稀为贵的高学历光环淡去。无论本科生还是研究生,甚至博士生,求职竞争力都大不如前,就业压力越来越大。
2022-06-01某家企业10个人面试,有9个本科生……如何脱颖而出,除得体的举止和良好的沟通力外,证书成重要筹码,这也是很多人考证的关键所在。
2022-04-14