大数据与大数据计算

DBDeveloper2018-12-05 16:41:07


今天听了一场报告会,是清华计算机系60周年系列讲座之一,主讲人是哈工大软院院长李建中教授,主题《计算和数据资源受限的大数据计算的复杂性理论与高效算法研究》,李老师介绍的大数据计算理论体系很完善,由于只有一个小时,很多只能稍微提及,但是还是有很多观点让我受益匪浅,分享一下。


本文预计阅读时间 5 分钟。


什么是大数据?


wiki定义:Big data is data sets that are so big and complex that traditional data-processing application software are inadequate to deal with them.


首先大数据指的是数据集,是纯粹的数据。其次,由于复杂与庞大,传统的数据处理软件无法处理。这样的数据集就可以叫大数据。


这个定义其实很模糊,什么叫传统的数据处理软件无法处理的?也没规定硬件。那超级计算机能处理的算不算?普通的CPU、内存,后面接一个存储柜装个几百 T 数据算不算大数据呢?


因此,个人感觉,应该是普通PC机的配置,256内存,12T硬盘,用传统的数据库Oracle,MySQL不好用了,感觉单机撑不下了,或者单表数据量几百万以上性能急剧下降无法满足要求了。这时候就叫传统的搞不定了,需要考虑大数据解决方案了。


大数据计算问题


输入:大数据 D,问题 P 的参数

输出:问题 P 的解 P(D)


这里重点是输入一个大数据。有一个很容易混淆的场景是拥有的数据量很大,TB、PB级,但是每次用来计算的只有几十或几百MB,这个输入就不能称为大数据,因此这种问题就不是大数据计算问题。


你面临的问题不是大数据计算问题有什么问题吗?没什么问题,如果真碰到了大数据计算问题就麻烦了。


由此也给出大数据计算的定义:


大数据计算:求解大数据计算问题的过程。


大数据计算的挑战


报告的前提是“计算和数据资源受限”,为什么这个很重要呢?因为一般情况下这是搞大数据的都会面临的实际问题,如果一个人说他的大数据场景没这种问题,很有可能他的数据不够大。下面看看受限的两个方面:


1、计算资源的强受限性


先不说最简单的计算,只说遍历一遍数据。


大数据一般指 TB、PB、EB、ZB、YB 级别的数据。以机械硬盘和 SSD 的 IO 速率来考虑。1TB的数据遍历一遍(顺序读取),机械硬盘1G/s,需要17分钟,SSD算5G/s,需要3分钟。


一个精确的算法至少需要将所有数据遍历一遍。因此这个时间可以认为是处理大数据的最少时间,那么 1PB 数据用 SSD 遍历就需要 2 天多,而且 1PB 的SSD 成本相当大,估计没有人这么搞。数据量再大还得继续乘 1024。


多项式时间不再是大数据计算问题易解性的判别标准。对于PB、EB需要至少亚多项式,对于ZB、YB至少需要polylog多项式时间才算易解。


2、数据资源弱可用性


这个特性主要说的是数据质量差。理想中数据应该是整整齐齐的,但是实际上数据很多都会有错误,大概有10%左右的错误数据。人工记录的数据就可能由于脑子进水记错了。数据错误会造成很大经济损失。


既然数据有错的,那么能不能修正呢?修复的复杂度是n^3数量级的,很难修复。因此,修复后的数据也不会100%正确。这个叫弱可用性数据,如何在弱可用性数据上进行计算,使结果的误差满足要求,是另一个重要的研究方向。


一些计算方法


1、小数据近似大数据


所谓大事化小,小事化了。需要发现大数据的内在规律,才能将问题简化,这个就跟具体问题十分相关了,没啥通用方法。类似把123*234*345*0化简为1*0。


2、增量计算方法


将需要计算的数据分成很多小份,一份一份算。不过这个需要计算具有可加性。比如给 1 万个数求和,先分 10 份,每份 1 千个数求和,再给 10 个和求和。


3、直接处理压缩数据


将 100T 数据压缩为1G,在1G数据上直接设计算法就会容易很多。但是如果要达到在 100T 上数据计算的效果,需要压缩方法具有映射完整性,也就是100T数据能完全对应到 1G 上,1G 数据也能完全恢复为 100T 数据。举个例子:1,1,1,1,1,压缩为5,1。


大数据系统


这部分回到我们经常听到的 Hadoop,MapReduce,Spark了。这些是大数据计算框架,但是只有这个是不够的,在面对一个问题时主要需要解决的还是算法问题。


举个例子:大数据计算框架就像高级包工队,他们有盖1万层高楼的能力,这是传统包工队干不了的。但没有图纸是没法盖出楼来的。而图纸就是算法。


总结


大数据是指传统方法处理不了的数据集。大数据计算问题处理的是大数据。计算受限和数据受限是大数据计算中普遍存在的客观现象。这时对于一个大数据计算问题的复杂度分析就很重要,到底能不能计算,多长时间能计算出来,算出来的结果准不准,都需要理论支持。




Copyright © 古田计算器虚拟社区@2017