网站建筑设计,wordpress 标题空格,沈阳城乡建设工程信息网,金融公司网站方案为什么80%的码农都做不了架构师#xff1f; 之前已经参加过几次QCon峰会#xff0c;不过今年QCon 2014 上海峰会对我来说比较特别#xff0c;不再只是一名听众#xff0c;而是第一次登台演讲。感觉的确不太一样#xff0c;一来是身份从听众变成了讲师… 为什么80%的码农都做不了架构师 之前已经参加过几次QCon峰会不过今年QCon 2014 上海峰会对我来说比较特别不再只是一名听众而是第一次登台演讲。感觉的确不太一样一来是身份从听众变成了讲师二来是因为成了讲师让我接触到更多的业内朋友也遇到了更多的提问、咨询。会后已经有一段时间了还有朋友提出想了解更多的技术知识。看来会上行云流水的半个小时未能把一个技术点讲述明白我想还是总结一下让技术圈朋友们对Bitmap这个技术点加深点理解。 一、背景 a) 历史的困惑 每个技术点背后都有一系列业务的故事透过我这次讲的Bitmap我们可以看到历史上始终困扰营销领域的一个核心问题。著名广告大师约翰•沃纳梅克提出我知道我的广告费有一半浪费了但遗憾的是我不知道是哪一半被浪费了 (翰•沃纳梅克始创第一家百货商店“沃纳梅克氏”被认为是百货商店之父同时也是第一个投放现代广告的商人)。为什么会出现这样的浪费呢我个人觉得还是对营销所面向的人群理解不透彻导致的。因此营销领域一直期待技术系统能够提供一种能力可以高速、灵活的、从海量用户中找出最合适的那一部分。 b) 时代的曙光 需求的背后是技术的不断进步。最近几年信息技术的突飞猛进给解决问题带来了一线曙光。大数据处理技术和系统已经渗透到当今每一个行业和业务职能领域成为重要的生产因素。人们对于海量数据的挖掘和运用预示着新一波生产率增长和消费者盈余浪潮的到来。使用各种各样新型的技术武器Hadoop、Spark、Storm等等开源工具我们近乎完美的捕捉到这个时代的浪潮将人群的属性分析、行为分析、甚至是心理分析深入到相当精深的地步。 相关厂商内容 京东618大促下的数据驱动个性化推荐 如何构建软硬件结合的人工智能产品研发体系 中国创新型互联网企业走向海外的技术机遇与挑战 数据分析与企业架构 安全狗业内首创云端模式保护服务器安全 相关赞助商 全球架构师峰会7月17日-18日深圳大梅沙京基海湾大酒店。马上报名。 c) 业务驱动力 业务需求对技术的要求是永无止境的。我们需要更好的工具 更快速的分析一次任务就需要个把小时甚至需要一天数据的产出无法支持我们业务的快速调整。 更灵活的分析工具应该比Oracle或者IBM的BI系统更好我们需要有多维交叉的计算能力而不只是简单的几种统计数字。 更轻量级的系统动辄几十台服务器组成的Hadoop集群我们真是无法负担啊成本太高昂了。 二、现有技术分析 a) 硬币的两面 我们最初非常仰仗Hadoop不过后来发现Hadoop不是银弹核心的问题不是Hadoop出了错而是我们对Hadoop的本质理解稍显片面。Hadoop是一种高吞吐量系统其设计和实现中采用了小操作合并基于操作日志的更新等提高吞吐量的技术。硬币的两面在使用过程中逐步显现高吞吐量和低延迟是两个矛盾的目标。既然要低延迟上Storm上Redis。在2011年我们在Hadoop的批处理的基础上为我们的统计平台增加了实时计算能力。下面这张图大约反映了一种典型的架构系统如何使用两种流派的计算系统解决计算问题。 看似完美的解决了高吞吐量和低延迟的矛盾但是核心业务问题没有得到解决业务人员需要在海量数据中使用多维交叉的方式不断计算手里的数据。批量处理还是需要几个小时甚至一天才能出一批数据。流式处理只能算当前的数据历史数据无法回朔。 b) 白天鹅传统技术的缺陷 看待硬币的两面是一种视角这也许是一种平庸的视角。如果不看硬币把硬币当做金属寻找、发现、创造一种新的铸造硬币的方法又是另外一种视角。2012年我们跳出了传统的视角例如Hadoop、或者Storm的改造重新观察我们的问题。经过分析我们得到一个结论我们需要做的是创造第三种计算方式而不是继续在两种计算方式中挖潜。 如果我们把传统系统看作白天鹅并把高速的、灵活的多维交叉分析当作飞行的目标我们应该看看白天鹅为什么飞得累飞得慢 第一个技术障碍是高I/O开销包括磁盘I/O和网络I/O两种主要开销。传统的数据存储都是以行的方式存储在磁盘文件中而传统的文件系统又都是为大文件连续读写做优化的。假如我们要做多维交叉分析我们分析一下系统的运作过程 根据查询需求定位到数据在某些文件。 从文件系统中提取文件。这里产生了磁盘开销。 如果是分布式系统例如普遍使用Hadoop这里产生了高昂的网络传输开销。 然后需要按行的方式从文件中提取数据。这里会碰到一个非常隐蔽的问题每行数据中会有大量的信息对本次查询无任何意义可能造成非常巨大且不幸的浪费。 第二个技术障碍是计算相对低效。传统计算中把大量的CPU和内存放到了数据装载数据过滤等等上面的浪费就是例子。 新一代的计算体系的设计重点是降低整体IO并尽量让计算资源用在真正有价值的点上。 c) 从白天鹅到黑天鹅 我们用了三种法宝克服上面的缺陷以提高整体计算效率 预处理尽量降低低效的文件读取在整个计算过程中的比重。 压缩使用高压缩比的压缩算法将需要计算的数据压缩到最小同时不影响计算精度。 内存计算将计算需要的全量数据全部一次性装载入内存这样可以最大程度的将CPU的计算能力用于业务计算。 那么到底是哪只黑天鹅将以上的优点集于一身内它就是Bitmap。 三、Bitmap的秘密 a) Bitmap如何做到多维交叉计算的 Bit即比特是目前计算机系统里边数据的最小单位8个bit即为一个Byte。一个bit的值或者是0或者是1也就是说一个bit能存储的最多信息是2。 Bitmap可以理解为通过一个bit数组来存储特定数据的一种数据结构由于bit是数据的最小单位所以这种数据结构往往是非常节省存储空间。比如一个公司有8个员工现在需要记录公司的考勤记录传统的方案是记录下每天正常考勤的员工的ID列表比如2012-01-01:[1,2,3,4,5,6,7,8]。假如员工ID采用byte数据类型则保存每天的考勤记录需要N个byte其中N是当天考勤的总人数。另一种方案则是构造一个8bit01110011的数组将这8个员工跟员工号分别映射到这8个位置如果当天正常考勤了则将对应的这个位置置为1否则置为0这样可以每天采用恒定的1个byte即可保存当天的考勤记录。 综上所述Bitmap节省大量的存储空间因此可以被一次性加载到内存中。再看其结构的另一个更重要的特点它也显现出巨大威力就是很方便通过位的运算AND/OR/XOR/NOT高效的对多个Bitmap数据进行处理这点很重要它直接的支持了多维交叉计算能力。比如上边的考勤的例子里如果想知道哪个员工最近两天都没来只要将昨天的Bitmap和今天的Bitmap做一个按位的“OR”计算然后检查那些位置是0就可以得到最近两天都没来的员工的数据了比如 再比如我们想知道哪些男员工没来我们可以在此结果上再“And”上一个Bitmap就能得到结果。 b) Bitmap如何做到高速运算的 回忆一下前面浪费的有两个部分其一是存储空间的浪费Bitmap比文件强多了但是仍然有浪费的嫌疑。它需要保存到外部存储数据库或者文件计算时需要从外部存储加载到内存因此存储的Bitmap越大需要的外部存储空间就越大并且计算时I/O的消耗会更大加载Bitmap的时间也越长。其二是计算资源的浪费计算时要加载到内存越大的Bitmap消耗的内存越多位数越多计算时消耗的cpu时间也越多。 对于第一种浪费最直觉的方案就是可以引入一些文件压缩技术比如gzip/lzo之类的对存储的Bitmap文件进行压缩在加载Bitmap的时候再进行解压这样可以很好的解决存储空间的浪费以及加载时I/O的消耗代价则是压缩/解压缩都需要消耗更多的CPU/内存资源并且文件压缩技术对第二种浪费也无能为力。因此只有系统有足够多空闲的CPU资源而I/O成为瓶颈的情况下可以考虑引入文件压缩技术。 那么有没有一些技术可以同时解决这两种浪费呢好消息是有那就是Bitmap压缩技术而常见的压缩技术都是基于RLERun Length Encoding详见http://en.wikipedia.org/wiki/Run-length_encoding。 RLE编码很简单比较适合有很多连续字符的数据比如以下边的Bitmap为例 可以编码为0,8,2,11,1,2,3,11 其意思是:第一位为0连续有8个接下来是2个111个01个12个03个1最后是11个0当然此处只是对RLE的基本原理解释实际应用中的编码并不完全是这样的。 可以预见对于一个很大的Bitmap如果里边的数据分布很稀疏说明有很多大片连续的0采用RLE编码后占用的空间会比原始的Bitmap小很多。 同时引入一些对齐的技术可以让采用RLE编码的Bitmap不需要进行解压缩就可以直接进行AND/OR/XOR等各类计算因此采用这类压缩技术的Bitmap加载到内存后还是以压缩的方式存在从而可以保证计算时候的低内存消耗而采用word计算机的字长64位系统就是64bit对齐等技术又保证了对CPU资源的高效利用。因此采用这类压缩技术的Bitmap保持了Bitmap数据结构最重要的一个特性就是高效的针对每个bit的逻辑运算。 常见的压缩技术包括BBC有专利保护, WAHhttp://code.google.com/p/compressedbitset/ 和EWAH(http://code.google.com/p/javaewah/)。在Apache Hive里边使用了EWAH。 c) Bitmap在大数据计算上的能力 我们用一个TalkingData Analytics中用户留存的例子来看Bitmap如何做到用户回访的统计。比如想知道某个应用昨天新增的用户中有多少人今天又开启了应用次日留存。使用过Hive的工程师不难理解下面语句的含义 同时我们使用Bitmap技术后同样实现上述的计算对比测试显示出效率的差异是巨大的 d) 引入Bitmap技术后分析系统可能的处理流程大体是什么样的 数据收集系统收集设备上传数据然后分发给实时处理系统和批量处理系统 实时系统采用自有计数器程序或者基于Storm之类中间件的计数器程序计算各类简单计数器然后批量比如30s或者1min更新到Redis或者HBase之类的存储前端供应计数器类数据的服务通过访问后台计算器程序或者是计数器存储来给报表系统提供服务 批量系统对该批的数据按用户进行去重生成/修改某天/某个应用的活跃用户Bitmap同时可以根据需要将机型、地域、操作系统等等各种数据提炼成属性Bitmap备用。 报表中针对分析需要提取各种Bitmap用户、属性……Bitmap高效的利用CPU/内存通过组合And/Or/Not等基础计算最终完成多维交叉计算功能反馈客户结果。 四、黑天鹅的未来 TalkingData提供给客户大数据下高速的多维交叉计算能力还只是一个开始。在大数据时代技术的发展必将推动业务的进化。TalkingData的未来在于提供客户更快速、更便捷、更灵活的数据服务。黑天鹅也遇到了更多的问题需要逐一解决。 a) 内存映射文件 比如即便用了优化的压缩技术Bitmap从文件中迁移到内存中的速度相对来说还是短板。例如系统构建初期我们曾经把Bitmap存储在Mysql中感觉还不错不过随着数据量的增加随机读的问题越来越严重大约一次查询中90%的时间全部被Mysql占去某些开销是挺浪费的例如Mysql一次SQL的执行计划怎么都需要1ms左右。下一步我们计划采用“内存映射文件”技术来解决这个问题。 内存映射文件与虚拟内存有些类似通过内存映射文件可以保留一个地址空间的区域同时将物理存储器提交给此区域只是内存文件映射的物理存储器来自一个已经存在于磁盘上的文件而非系统的页文件而且在对该文件进行操作之前必须首先对文件进行映射就如同将整个文件从磁盘加载到内存。 由此可以看出使用内存映射文件处理存储于磁盘上的文件时将不必再对文件执行I/O操作这意味着在对文件进行处理时将不必再为文件申请并分配缓存所有的文件缓存操作均由系统直接管理由于取消了将文件数据加载到内存、数据从内存到文件的回写以及释放内存块等步骤使得内存映射文件在处理大数据量的文件时能起到相当重要的作用。 b) 分布式Bitmap计算 可以预见到的第二个Bitmap计算的难题是我们有可能遇到“需要非常巨大的计算能力才能解决的问题”。举个简单的例子假如一个客户想看几年的数据指标那么有可能需要提取出成千上万个甚至几十万个Bitmap放到内存中进行计算这是相当恐怖的要求。 TalkingData第一代Bitmap计算引擎虽然利用了诸如“Fork-join”技术最大程度的利用CPU/内存但是遇到上面的计算要求肯定还是力不从心。第二代Bitmap计算引擎采用分布式计算把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分然后把这些部分分配给许多计算机进行处理最后把这些计算结果综合起来得到最终的结果。 请大家注意一下Bitmap天生的特性其实一个Bitmap代表了一个集合同时它支持的计算中就是集合计算中的“And/OR/Not”。大家可以在这个wiki上复习一下“集合代数”的知识。 http://zh.wikipedia.org/wiki/%E9%9B%86%E5%90%88%E4%BB%A3%E6%95%B0 这里面有一些给分布式Bitmap计算提供了理论基础下面这张图表达的是分配律 假如我们有三个集合分别是A去过美国的游客B去过中国的游客C使用IOS设备的游客。现在业务人员要求找出既去过美国又去过中国同时又使用IOS设备的游客。最直接的计算是A∩B∪C但是假如我们在分布式系统的视角下我们可以分拆后的计算是A∪C∩B∪C可以在两台计算节点上分别计算再汇总到中心节点获得最后结果。基于这些集合代数计算的原理我们可以把复杂的多维交叉分析分解成很多小单元计算分配到不同的服务器上计算再做汇总计算得到结果。 原理简单但是执行起来还是有很多困难的比如数据倾斜、分拆计算优化、在高并发下解决负载均衡…… 任重道远 总结 当我最近阅读30年前的Paper的时候我发现科学领域的宽广和深度。大约在30年前天体物理学家利用基数计算Bitmap就是一种基数计算来解释恒星数据除此以外还有时间序列分析和频谱分析。我们今天研究某个产品在时间上的规律还有一个人群使用产品的频率特征不就是这些计算科学在商业世界的再实践吗 从历史观的角度来看这些计算科学很早就已经存在而现代多数程序员由于需要学习各种各样的IDE、语言忽视了这些基础算法的学习和实践要持续、有效地发展个人和团队后者恰恰更重要。Bitmap技术不但让我们支持了业务的发展也证明了我们走在一条正确的路上透过现象看本质从基础的算法出发吸收各种技术流派的思想创造属于自己的技术反馈和服务于技术社区。这就是TalkingData的技术底蕴。 转载于:https://my.oschina.net/muou/blog/470815
