作者：丁维龙,等
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
Storm：大数据流式计算及应用实践试读：
前言
信息技术行业在过去的不长时期内，经历了多种概念的出现、发展和消亡。而当今，最火热的IT词汇，无外乎“大数据”、“云计算”和“物联网”；而相应的支撑技术，诸如Hadoop、HDFS和Cassandra等，均得到了广泛关注和研究。特别是以Hadoop生态系统为代表的大规模数据处理技术，已经成为业界事实上的标准之一。Hadoop/MapReduce 这类数据处理技术和所构建的分布式系统，针对数据边界清晰的数据进行批处理操作，涉及作业的启动、中间结果写盘缓存和基于共享存储的数据传输，使得数据处理结果存在较长延迟，无法提供持续处理的能力。基于Hadoop/MapReduce 计算框架的系统，可针对海量数据实现批处理，但在高速并发的环境下，无法满足实时、连续处理的需求。于是，针对实时数据处理，缺少编程标准化、可靠和可伸缩的计算模型和框架，成为一个巨大缺失，Twitter公司开源的Storm，恰好填补了这个空白。
Storm作为开源的实时数据处理系统，针对流式数据较之Hadoop，不仅降低了数据处理的并行编程的复杂度，也提供了数据不丢失的保证和集群节点动态部署的特性。具体来说，Storm的关键特性如下。
1.编程语义的简化和跨编程语言的集成。通过 Storm 的核心编程抽象，如Topology，Spout 和 Bolt，可以便捷地接入和接收数据、更新数据和追踪数据，并可以灵活地指派数据在组件之间的分片方式。特别是由于采用了 Apache Thrift 接口，Storm仅要求组件间遵循同一套接口描述，而不绑定两端具体的实现语言。因此，Storm有着广泛的适用场景，可在异构环境下，集成处理数据流和更新持久化数据，并行化地连续查询指定数据流。
2.数据处理的可靠性保障。在可用性要求高的场景下，数据是不允许丢失的，要求系统必须保证所有的数据被成功地处理。Storm 通过配置消息反馈策略，可保证到达系统的数据被最终处理，而节点的故障会被及时捕获并使得业务计算自动重新分配，保证数据处理的连续性和可靠性。同时，在数据正确性要求高的场景下，为了避免数据冗余和保证数据仅被处理一次，Storm 给出了事务型处理的概念和模型，可在用户业务逻辑不改变的情况下，通过配置编程组件实现。这类因素也是相对于早先Yahoo开源同类系统的S4最重要的优势。
3.计算节点的可伸缩性和集群配置简便易行。Storm集群管理只需要通过维护有限数量的配置文件完成，保证集群中节点可管可控，其节点的动态接入和作业自动重分配也是一大亮点。若当前的计算资源成为瓶颈，可以通过水平扩展节点实现数据处理的伸缩，即增加机器和提升计算的并行度。官网的实验结果表明，10个节点的Storm集群下，应用的吞吐量可达每秒1000 000个消息，其中还包括每秒100多次的数据库存取调用。
正是由于上述特点，Storm 获得了业界的广泛关注与赞誉。同时，由于活跃的社区贡献，其代码日趋成熟与稳定，在开源后的两年内，已经在数十个企业中实现了商业级应用，如Groupon、The Weather Channel、Twitter、Yahoo、淘宝和阿里巴巴等。
本书全面介绍了Storm的理论基础、溯源发展、核心概念和集群配置、可靠性保障关键技术、常用的并行流模型编程范式、关键数据结构和源码解析等。本书的一大特色是，书中所有实例均来自编者所在团队的实际应用，是一个在智能交通背景下的分布式实时车牌流监控系统。希望通过理论结合实践，本书能为当前火热的大数据背景下的分布式系统开发，贡献一点微不足道的力量。
本书在撰写过程中，得到了许多同仁和朋友的帮助。云计算中心的硕士生张帅、卢帅参与了本书的校稿和整理，电子工业出版社的董亚峰和吴长莘两位编辑为本书的面世也付出大量心血。在此，对他们表示衷心的感谢！
由于时间和水平有限，书中的不妥之处在所难免，衷心希望广大读者能够批评指正，以便我们再版时修订。
编者
2014后3月
作者简介
丁维龙
博士，2013年1月毕业于中国科学院计算技术研究所，现任教于北方工业大学，在大规模流数据集成与分析技术北京市重点实验室从事实时数据处理与分布式系统方向的研究，已在SCI检索期刊和领域知名国际会议发表多篇学术论文，主持并参与多项科研课题。中国计算机学会（CCF）、ACM（Association for Computing Machinery）会员，目前是旗舰期刊IEEE Transaction on Service Computing、IEEE Transactions on Industrial Informatics和计算机学报审稿人，同时担任第七届中国传感器网络学术会议（The 7th China Conference on China Wireless Sensor Networks，CCF CWSN2013）、IEEE SDPI workshop的程序委员会成员。
赵卓峰
博士，2005年1月毕业于中国科学院计算技术研究所，现任北方工业大学云计算研究中心副研究员、副主任，中国计算机学会高级会员、服务计算专委会委员，IEEE/ACM会员。作为负责人，作者承担多项国家和省部级课题，目前从事云计算、物联网等环境下新型应用系统的架构设计及开发方面的研究与工程实践，在公安应急、智能交通、科技信息服务、电子政务、先进制造等应用领域完成10余项应用实践，申报专利及软件登记等知识产权40余项，向华为、东方通科技、神州数码、万方等公司输出多项技术。
韩燕波
博士，毕业于柏林工业大学，现任北方工业大学教授、北方工业大学云计算研究中心主任。中国计算机学会服务计算专业委员会副主任、中国计算机学会大数据专家委员会委员、中国电子学会云计算专家委员会委员、计算机学报编委。曾就职于德国国家计算机研究中心、德国弗郎霍夫软件技术研究所和美国大规模分布系统实验室等机构，归国后2000年被聘为中科院计算技术研究所研究员，入选中科院海外杰出人才计划（百人计划），任网络重点实验室研究员、博士生导师、中科院研究生院教授。主要研究领域包括分布式系统、互联网服务、业务流程管理和协同等，在多个领域主持完成了多项863、973和自然基金重点项目，发表论文140余篇，出版专著4部。申报或合作申报发明专利和软件登记50项，其中5项已向工业界转化。第一篇基础篇 流式数据处理概论第1章 大数据环境下的云计算与物联网
根据维基百科的定义，大数据是指无法在一定时间内用常规软件工具对其内容进行抓取、管理和处理的数据集合。数据已成为与自然资源、人力资源一样重要的战略资源，隐含巨大的价值，已引起学术界和工业界的重视。大数据的有效组织和使用，将对社会发展产生巨大推动作用，孕育着前所未有的机遇。O’Reilly公司断言：“数据是下一个Intel inside未来属于将数据转换成产品的公司和人们。”
大数据的繁荣，离不开云计算和物联网技术的发展。一方面，以云计算为代表的资源虚拟化为数据处理提供了高效、健壮的基础设施，以物联网为代表的网络形态产生了规模庞大的原始数据，逐步积累了大数据；另一方面，大数据的相关研究和技术，必将影响现有的云计算和物联网的发展趋势。云计算、物联网等信息技术的发展使得物理世界、信息世界和人类社会已融合成一个三元世界（the ternary human-cyber-physical universe），大数据是形成统一的三元世界的纽带。
本章主要与大数据相关的云计算、物联网的发展和兴盛，分析大数据来源、特征和数据处理的需求。1.1 云计算与物联网1.1.1 云计算
云计算（Cloud Computing）是一种基于互联网的计算方式，通过这种方式，共享的软硬件资源和信息可以按需提供给计算机和其他设备。
云计算为数据的处理提供了便利的基础设施条件，包括更便宜的分布式存储、计算设备和网络。一方面，技术和业务需求的双重推动会让越来越多的政府机构、公司企业和个人意识到数据是巨大的经济资产，将带来全新的创业方向、商业模式和投资机会；另一方面，大数据处理的兴起也将改变云计算的发展方向，云计算正在进入以AaaS（Analysis as a Service，分析即服务）为主要标志的时代。
云计算是大规模计算机系统自客户-服务器的转变之后的又一种巨变：用户不再需要了解基础设施的细节，甚至不必具有相应的专业知识，而是采用一种基于互联网的新的IT服务和交付模式，通常涉及通过互联网来提供动态易扩展而且经常是虚拟化的资源。在软件即服务（SaaS，Softuare as a Service）的服务模式当中，用户能够访问服务软件及数据。服务提供者则维护基础设施及平台，以维持服务正常运作。这使得企业能够通过外包硬件、软件维护及支持服务给服务提供者来降低IT 运营费用。另外，由于应用程序是集中供应的，更新可以实时发布，无须用户手动更新或安装新的软件，使得企业能够更迅速地部署应用程序，并降低管理的复杂度及维护成本，同时允许IT 资源的迅速重新分配以适应企业需求的快速改变。
云计算通过大规模分布式资源的共享形成规模效应，集成大量的资源供多个用户使用。使用者可以请求（租借）资源，而非拥有资源，并可随时调整使用配额，多余资源可被终止收回。这降低了使用者使用的经费，可以更加高效地使用并可按需配置服务提供者的资源。
1.从部署模型的角度分类
从部署模型的角度分类，云计算可以被分为如下四种类型。这个分类标准最初来源于美国国家标准技术研究所（NIST），现在已被广泛采纳。（1）公用云（Public Cloud）。
公用云服务通过网络及第三方服务供应者开放给客户使用。“公用”意味着服务广泛的使用范围，而不一定代表免费和无限制使用。在亚马逊、VMware 和 Ubuntu 社区提供的公用云服务中，云供应商通常会对用户实施访问控制机制。公用云作为资源管理的解决方案，不仅可以保障不同用户（不同付费水平）的服务质量（QoS和SLA），而且使得资源管理具有成本效益。弹性的云服务是公用云的一个显著特征，按需使用服务降低了用户的系统运维成本。国外著名的公用云提供商有亚马逊、IBM和微软等，国内著名的公用云提供商有新浪、百度和阿里巴巴等。（2）私有云（Private Cloud）。
私有云与公用云的差别主要在于提供的服务的管理模式不同。私有云中服务的数据与程序皆在组织内管理，而且往往对资源限制较为宽松（如网络带宽、安全规范、法规影响等）。此外，私有云服务通过机构/公司内部的虚拟化资源，用户更细粒度、高权限地掌控基础架构、安全策略和使用模式的设计与调整。著名的私有云产品主要有开源产品Eucalyptus和OpenStack，以及收费的商业产品WMware vCenter和微软Windows Server产品线。（3）社区云（Community Cloud）。
社区云由众多利益相仿的组织掌控及使用，如特定安全要求、共同宗旨等。社区成员共同使用云数据及应用程序。社区云也可以看成公用云的一种特例，更多的是跨组织的行业视角的云服务应用。社区云虽然不是新概念，但它的发展确实是当前最为新兴的一类。例如，国际赌博科技公司（International Game Technology）最近推出了IGT Cloud，面向赌博公司赌场的业务管理。又如，联合健康集团（United Health Group）推出了Optum Health Cloud（Optum健康云），面向医疗保健行业的公司客户，旨在充分利用全美保险服务的云资源。此外，弗吉尼亚社区学院（VCCS）与企业合作推出的教育社区云，为40个校园、23所高校提供了服务，达到了提高效率和改善服务的双赢效果。（4）混合云（Hybrid Cloud）。
混合云是介于公用云及私有云之间的云服务使用模式，在私有云的私密性和公用云的灵活低廉性之间进行权衡。用户通常将非关键信息外包在公用云上处理，同时将企业关键服务及数据放在机构内部处理。相对而言，混合云的案例较少，但也有相关的商业公司提供了完善的解决方案。例如，Amazon提供的VPC（Virtual Private Cloud，虚拟私有云）将Amazon EC2的部分计算能力接入企业的防火墙内；VMware提供的vCloud，可将自动化业务连续性与支持虚拟化的安全性和合规性相结合，针对IT 服务的访问、安置和成本提供个性化的控制力。
2.从使用模式的角度分类，云计算通常存在如下三种服务模式。
从使用模式的角度分类，云计算通常存在如下三种服务模式。（1）软件即服务（SaaS）。
用户使用应用程序，但并不掌控操作系统、硬件或运作的网络基础架构。这是一种基础服务模式，软件以付费或免费租赁的方式被提供。典型的操作模式是，服务提供商提供一组账号和密码，用户根据用户信息认证和按配额使用。例如，客户资源管理的服务提供商Microsoft CRM与Salesforce.com提供了相关的SaaS服务。（2）平台即服务（PaaS）。
用户使用虚拟平台操作应用程序，掌控运作应用程序的环境，包括部分主机的操作权，但并不掌控操作系统、硬件或运作的网络基础架构。平台通常是指应用程序的管理环境，包括应用服务器和Web服务器等基础环境。例如，Google公司提供的App Engine和新浪公司的Sina App Engine。（3）基础架构即服务（IaaS）。
用户使用一台或数台机器的基础计算资源，如处理能力、存储空间、网络和中间件，但并不掌控整个虚拟化环境。用户部署操作系统，使用存储空间，使用已部署的应用程序及防火墙和负载平衡器等，可以按自己的需求开发配置适合的应用，属于最底层的云服务。例如，Amazon AWS和Rackspace就是典型的这类服务。
用户通常希望商业化的产品能够满足服务质量（QoS）的要求，并且一般情况下要提供服务水平协议。同时，开放标准对于云计算的发展是至关重要的，开源软件可对众多不同需求的客户提供快速、高效的部署和实施过程。自从Google公司提出了著名的三大件，即无共享架构便捷编程的 MapReduce 框架、针对数据极少修改的大文件提供持续存储的分布式文件系统GFS，以及压缩的高可扩展性的非结构化存储Big Table，相关开源相关技术也开始蓬勃发展。自此，出现了Apache社区对应的Hadoop、HDFS和HBase等开源工具，也出现了像Cloudera这样的开源服务提供商，都极大地推动了云计算的发展。
云计算的发展和繁荣，使大数据应用成为可能。借助云计算技术，数据处理应用可以提高系统整体的弹性和灵活性，降低管理成本和风险，提高应用服务的可用性和可靠性。同时，云计算不仅为大数据处理打造了一个高效、可靠的系统环境，而且充分发挥了平台的优势，为大数据发掘更多的应用牵引。总之，云计算可以用于解决大数据带来的问题，而随大数据出现带来的理论与技术趋势，也成为云计算发展的契机。所以，两者殊途同归，云计算与大数据是相辅相成的。1.1.2 物联网
物联网（Internet of Things，IoT）诞生于1999年，旨在把实物通过射频识别等信息传感设备与互联网连接起来，实现智能化识别和管理，是通过传感器和互联网实现物物衔接的新技术。物联网是传感网（Sensor Network）、无线网（Wireless Network）、互联网（Internet）等网络技术和分布式系统（Distributed System）、高性能计算（High Performance Computation）等数据处理技术交叉融合和发展的产物。
物联网体系结构的设计也是分层次的。按照欧盟第七科技框架CASAGRAS工作组的定义，物联网体系结构包括4个层次：感知层、传输层、数据处理层和应用层。
① 感知层是传感器和射频标签（RFID）形成的网络，协同感知环境或自身状态，并初步处理获取的数据和根据既定规则响应状态的变化。该层的主要功能是信息感知与采集，包括二维码标签和识读器、RFID 标签和读写器、摄像头、各种传感器（如温度感应器、声音感应器、振动感应器、压力感应器等），完成物联网应用的数据感知和设施控制。
② 传输层是宽带无线网络、光纤网络、蜂窝网络或各种专用网络，主要融合和传输来自感知层的数据。传输层的核心是各类网络，承担物联网接入层与应用层之间的数据通信任务。它主要包括现行的通信网络，如2G、3G/B3G、4G移动通信网，以及互联网、Wi-Fi、WiMAX、无线城域网（Wireless Metropolitan Area Network，WMAN）、企业专用网等。
③ 数据处理层，处理和存储数据，通常由分布式系统完成数据检索、挖掘和模式识别等功能，为数据分析、局势判断和控制决策等提供服务。该层的数据处理过程可以采用云计算的模式，使用感知数据管理与处理技术，实现以数据为中心的技术。感知数据管理与处理技术包括物联网数据的存储、查询、分析、挖掘、理解，以及基于感知数据决策的技术。
④ 应用层是不同领域中的各种应用，如灾害监测、交通数据分析、物流供应链、智能农业和医疗保健等。应用层由各种应用服务器组成（包括数据库服务器），其主要功能包括对采集数据的汇聚、转换、分析，以及用户层呈现的适配和事件触发等。这些应用服务器根据用户的呈现设备，完成信息呈现的适配，并根据用户的设置，触发相关的通告信息。同时，当需要完成对前端的控制时，应用层还能完成控制指令生成和指令下发控制。此外，应用层要为用户提供物联网应用UI接口，包括用户设备（如PC、手机）、客户端浏览器等。
物联网的应用和业务，可以借助云计算弹性、可伸缩的处理存储和网络带宽能力，达到具有一定性价比的效果。云计算基础设施的服务，不仅可为物联网应用提供海量的计算和存储资源，还可以提供统一的数据存储格式和数据处理方法，更重要的是可为不同的物联网应用提供统一的交付平台。通过云计算，可降低物联网应用的开发、交付和使用成本，并大幅提高处理效率。同时，物联网作为云计算一个重要的落地方案，也促使云计算不断发展和完善，无论是商业层面还是技术层面。
物联网的产生、发展和繁荣，使得大数据的采集、分析和应用变为现实。同时，大数据环境下的物联网面临着如下挑战。
① 物联网的数据处理。产生、接入和处理作为中间结果的大规模数据，事实上并不总是需要传输到数据中心。这种需求，一方面，来源于基础设施的网络带宽的限制，数据中心的网络传输总是有限的；另一方面，也反映了物联网应用的实时性需求，实时响应相邻层次。此外，系统的可靠性也是被更多考虑的因素。当较低层次的设备出现故障时，中继节点的边缘计算能力，可以实现及时的容错控制和补偿反应。这在大规模分布式系统中，都是非常重大的挑战。
② 物联网的中间件。大规模数据被物联网的传感器采集后，经过传输层的网络和边缘计算处理送到数据中心。在这个过程中，物联网中间件是迫切的需求，要对数据及时进行处理与管理，特别是作为最终业务应用的预处理。当然，并不是所有的应用都存在预处理的需求，但是作为中间件适配的特征，数据可以在正确的时间以合适的方式传递到正确的目标，是中间件在物联网中的重要作用。
③ 物联网的管理平台。通过物联网的体系结构可以看到，这是一个物物相连的基础设施，用于实现数据的连网获取、传输和处理。但是，当物联网应用在关乎国计民生的重要行业中时，如电网或者医疗保险，系统本身必须设计得复杂、安全和可靠，必然需要管理平台对物联网基础设施实现管理和监控。
应该看到，当前被研究的大数据，更多的是指互联网中累积的大规模历史数据，在已经产生的数据中去搜索或做关联分析。事实上，物联网中的大数据相比互联网，存在一些自有的特点。例如，在交通、电网及公共安全等智慧城市的各种应用中，物联网的大数据更多的是指实时的甚至预测未来的数据。传感器持续不断地接入数据，这些数据是流式数据，需要在指定的时间阈值内进行处理、分析、存储和分发。所以，相比于传统的互联网，物联网大数据的研究内容往往有着更多的实时性需求。
以智慧城市建设为例，物联网不仅需要在架构和核心技术上取得突破，还需要在旧商业模式基础上进行技术创新，根据新技术建立新的应用/商业模式。在智慧城市的探索中，基础设施投资巨大，可以逐步提供一些服务。例如，美国纽约市开放了部分城市数据，并邀请开发者基于这些数据开发，可以让纽约市民的生活更加便利的应用；爱尔兰的都柏林也提出了类似的计划Dublinked。在国内，目前已有超过180个城市开始以大数据和物联网为依托建设智慧城市，通信网络和数据平台等基础设施建设投资规模接近5000亿元人民币。据分析，研究重点包括智慧公共服务、智慧社会管理、智慧交通、智慧医疗、智慧物流、智慧安居等方面的建设。从中可以看到：
① 智慧城市是城市信息化向智慧化发展的必经阶段，而通过物联网由城市数字化到城市智慧化，关键是要实现对数字信息的智慧处理，其核心是引入大数据处理技术，大数据技术必将成为智慧城市建设的新引擎。
② 从智慧城市的体系结构来看，由于智慧城市的基础在于物联网技术，因此智慧城市的体系架构和物联网的体系结构相类似，可分为四层，分别为感知层、传输层、平台层和应用层。
③ 大数据技术是处理感知层数据的必然选择。感知层是智慧城市体系对现实世界进行感知、识别和信息采集的基础性物理网络，大规模数据在感知层产生并获取。以视频监控为例，北京目前用于视频监控的摄像头有50万个，一个摄像头一个小时的数据量就在GB级，每天北京市的视频采集数据量在3PB左右，而一个中等城市每年视频监控产生的数据在 300PB 左右，这些摄像头实时回传信息，海量数据对数据存储、并发处理的要求是近乎苛刻的。同时，对于海量数据的处理不仅是智能化的必然需求，也是对IT 投资的一种保护，否则非但不能充分挖掘数据的价值，还将为大规模数据所累。
④ 大数据为智慧城市的各个领域提供强大的决策支持。在城市规划方面，通过对城市地理、气象等自然信息和经济、社会、文化、人口等人文社会信息的挖掘，可以为城市规划提供强大的决策支持，提高城市管理服务的科学性和前瞻性。在交通管理方面，通过对道路交通信息的实时挖掘，能有效缓解交通拥堵，并快速响应突发状况，为城市交通的良性运转提供科学的决策依据。在舆情监控方面，通过网络关键词搜索及语义智能分析，能提高舆情分析的及时性、全面性，全面掌握社情民意，提高公共服务能力，应对网络突发的公共事件，打击违法犯罪。在安防与防灾领域，通过大数据的挖掘，可以及时发现人为或自然灾害、恐怖事件，提高应急处理能力和安全防范能力。
物联网的发展和繁荣，为大数据应用积累了应用需求和技术，为数据处理服务提供了目标和背景。借助物联网技术，数据处理应用可以提高数据处理的速度、可靠性和实用性，并且持续改进应用的服务质量。同时，物联网不仅为大数据处理提供实际的、迫切的需求环境、实用技术和最终目标，而且充分发挥现有优势，为大数据发掘更多的应用牵引。总之，物联网可以用于解决大数据的问题，而大数据发展而来的理论与技术趋势，也成为物联网发展的契机。所以，两者也是殊途同归，物联网与大数据也是相辅相成的。1.2 大数据下的新挑战1.2.1 大数据及其特征
随着互联网时代的发展，博客、社交网络、基于位置服务为代表的新型信息发布方式的不断涌现，以及云计算、物联网等技术的兴起，数据正以前所未有的速度在不断地增长和累积，大数据随着IT 系统的发展已经成为当前不可忽视的问题，学术界、工业界甚至政府机构都已经开始密切关注大数据问题。《Nature》早在2008年就推出了Big Data专刊，计算社区联盟（Computing Community Consortium）在2008年发布的技术报告中综述了大数据研究背景下的挑战问题，《Science》在2011年2月也推出专刊探讨科学研究中大数据的问题。麦肯锡（McKinsey）咨询公司于2011年6月发布了对大数据的影响、关键技术和应用领域等进行详尽分析的报告。2012 年 1 月的达沃斯世界经济论坛把大数据确定为主题之一。2012年3月美国政府正式启动“大数据发展计划”，计划在科学研究、环境、生物医学等领域利用大数据技术进行突破。联合国也启动了Global Pulse倡议项目，以适应大数据时代各国的发展需求。
关于大数据的特征，业界有着不同的视角和总结。本书结合现有的学术和技术文献，将大数据的特征总结为如下几点。
1.数据体量大（Ⅴolume）
IDC公司发布的数字宇宙研究报告称：全球信息总量每两年就会增长一倍，2011年全球被创建和被复制的数据总量为1.8ZB，其中75%来自个人。2011年企业创造、采集、管理和储存信息的成本已经下降到2005年的1/6，而同期企业关于数据的总投资反而上升了50%。
数据体量大，不仅指全部互联网累积的数据，也包括某些单个组织的业务数据。例如，Google公司通过大规模集群和MapReduce 软件，每天处理超过20PB 的数据，每个月处理的数据量超过400PB。淘宝网有3.7亿名会员，在线商品8.8亿件，每天交易数千万元，产生约20TB数据。Yahoo的Hadoop云计算平台有34个集群，超过3万台机器，总存储容量超过100PB（按照欧盟的规定，不能存储超过一年的用户数据）。
2.数据类型多（Ⅴariety）
数据被分为结构化数据和非结构化数据。相对于以往的以文本为主的结构化数据，非结构化数据越来越多，包括网络日志、音频、视频、图片、地理位置信息等，这些数据对数据的处理能力提出了更高要求。数据量增大和类型增多源于数据成本的下降，而新的数据源和数据采集技术的出现则大大增加了未来数据的类型，数据类型的增加导致现有数据空间维度增加，极大地增加了当前大数据的复杂度。据统计，企业中80%的数据是非结构化或半结构化数据，只有 20%的数据是结构化数据。当今世界结构化数据增长率大概是32%，非结构化数据增长率则是63%。2012年，非结构化数据达到互联网总数据量的75%以上。大数据的技术挑战主要是指非结构化数据。
即使针对同一组织的业务数据处理，数据也会因为不同的用户、不同来源存在不同的数据类型。大型互联网公司的搜索引擎，除了直观的文本搜索外，大都提供了多模态的搜索方式。例如，针对图片数据，可以采用以图搜图（用户上传图或指定源图 URL）的方式；针对音频数据，可以采取近似音频（用户上传、现场哼唱或指定源音频 URL）的搜索方式，这导致了数据格式的异构性和类型的多样性。
3.数据更新速度快（Ⅴelocity）
这是大数据区分于传统离线数据挖掘的最显著特征。我们从两个方面分析数据更新的速度，包括数据到达的速度和数据处理的速度。
一方面，速度指的是数据到达的速度。这与当前经济、技术的发展和业务需求的增长有关。大型网络平台，每时每刻都有大量新的网络数据发布，网络信息内容变化迅速，导致了信息传播的时序相关性。特别是，有些数据作为社会信息，在传播过程中会在短时间内引起大量新数据与信息的产生和反馈，并使用户形成网络群体，体现出大数据以及网络群体的突发特性。IDC认为，到2020年，全球所有IT部门拥有服务器的总量将会比现在多出10倍，所管理的数据将会比现在多出50倍，全球将总共拥有35ZB的数据量。
另一方面，速度指的是数据处理的速度。这与业务需求直接相关，而正是由于业务的多样性和技术的进步，用户对业务处理速度的需求总是不断提升。大数据的实时分析，往往需要秒级别的速度，甚至要在1秒内完成亿万级数据的处理和分析，在10秒以内给出结果。某些大型互联网公司，如百度，已经把结果的处理时间限制在100毫秒内，而一些金融机构则期望微秒级别的响应时间。
数据接收和处理的速度需求在不断提高，但是当前以数据库为代表的离线处理技术，存在吞吐量上的瓶颈。以流式数据处理为代表的实时处理技术，可以将流动的数据在有限的内存中及时处理，实现更高的吞吐量。相比数据库这种“存储后处理”的模式，流式实时数据处理是典型的“处理后存储”。
4.价值密度低（Ⅴalue）
通常来说，数据价值密度的高低与数据体量的大小成反比。下面从三个方面来分析大数据价值密度低的特征。
首先，价值密度低源于大数据存在大量的冗余。大数据环境中，因为前端设备精度和灵敏度的原因，同一数据项在采集时可能被重复发送，导致数据处理可能要针对同一份数据多次计算。此外，为了能够可靠地保存采集的数据，数据往往被冗余放置在分布式环境中存储，这也势必导致之后的数据冗余处理。通过大规模智能算法在原始数据中快速提取有价值的数据，也成为目前大数据背景下亟待解决的难题。
其次，价值密度低源于业务处理的结果比原始数据本身体量要小数个量级。以交通流式数据为例，7×24小时连续不间断的监控中，每隔指定的时间间隔（如5分钟）会计算一次最近一个小时内的路段旅行时间，而旅行时间的计算结果相比5分钟内积累的数据，体量要小得多。如何权衡计算速度和在有限内存中的计算精度，也是当前学术界和工业界研究的一个热点。
最后，从业务意义上分析，单条数据没有意义，只有在数据达到一定规模后，才可能分析和处理有业务含义的数据结果。例如，监控系统接收单条车牌识别数据，无法判别该车牌是否有套牌嫌疑，只有把这个车牌数据纳入一定的时间窗口内，结合分析其他监测点接收的车牌数据，才能最终做出正确的套牌判定。
5.待挖掘的真实性（Ⅴeracity）
大数据应用不仅可以实施在历史累积的数据上，也可以在当前到达的数据上实时分析，甚至可以用于未来事件和趋势的预测。所谓大数据的真实性，我们认为更多的是指在历史累积和当前到达的大规模数据上的数据预测的正确性和现实意义解读。例如，微软纽约研究院的David Rothschild在2012年美国总统大选中，通过分析社会舆情数据，正确预测了51个选区中50个选区的选举结果，准确性高于98%。此外，这个团队还通过多维度的大数据分析，成功预测了第85届奥斯卡金像奖除最佳导演奖外的其他奖项，如《逃离德黑兰》摘得最佳影片奖等。
对于大数据真实性这个特征，一方面可以通过预测指导和反馈当前的业务处理逻辑，另一方面可以通过将来的结果验证预测方法的准确性。这方面的相关工作，是当前大数据研究中最为火热的话题之一。
以上分析了大数据的5V特征：Volume，Variety，Velocity，Value，Veracity。其中，前三个V是大数据本身的关键属性，后两个V是大数据处理的两大特点。大数据从理念被提出到目前理论、技术的大繁荣，业界已经从对大数据重要性的认识阶段，发展到实践大数据的必要性的战略实施阶段。但是，应当看到，当前的大数据处理，仍然存在着诸多不可忽视的困难和挑战。1.2.2 大数据处理的技术挑战
正是大数据与传统离线数据迥然不同的特点，使得大数据时代的数据处理面临着新的挑战。综合业界的相关工作，我们总结如下。
1.新型的数据模型
单一、固定的数据表示方法，无法直观地展现出数据本身的意义，特别是针对具有多样化特征的大数据。事实上，试图给出大数据的固定模式、因果关系和关联，是不现实的。所以，为不同形态的数据，选择最合适的数据模型是可取的方式。应当说，数据模型与应用的实际业务有着密切关系。针对多元的原始数据，给出特定应用下的模型，有利于减少处理过程中数据识别、分类和分析的困难，而研究既有效又简易的数据模型是大数据处理首先要解决的技术难题之一。例如，面向感知数据的数据流模型，是针对大数据环境下的实时数据处理的一种模型，在实践过程中已经展现了其良好的适应性和有效性。
此外，在高速、动态环境中数据索引的设计也是数据模型研究的挑战之一。传统关系数据库的索引，能够加速离线查询，源于管理的数据是相对静态的，数据的模式更新频率低。因此，在数据库中构建索引主要研究的是索引创建、更新等的效率。然而，大数据的多样性、高速变化的特征，使得数据模式随着数据量、数据源的不断变化可能会不断改变，甚至无法确定固定的模式。这样的实际需求导致索引结构必须开销有界、时空高效，也即能够快速适应接入的数据。例如，针对高速到达的流式GPS数据，可以构建基于R树、B+树及其变种的时空数据索引，在兼顾查询效率的同时，体现最近到达数据的时效性和重要性。索引的设计也存在特定的应用场景，在数据模式变更的环境下设计高效、适应性强的索引方案将是大数据时代的主要挑战之一。
2.高扩展性的数据分析技术
CAP（Consistency，Availability，tolerance to network Partitions）理论说明，分布式系统中的一致性、可用性、分区容错性三者不可兼得。所以，并行关系数据库必然无法获得较强的扩展性和良好的系统可用性。然而，可扩展、高可用是大数据处理系统必要的需求，如何权衡各个因素，成为了技术研究的挑战和热点。
从数据管理的角度，传统的关系数据库面对大数据往往无法胜任，源于数据库处理系统的目标是追求高度数据一致性和容错性。面对这些挑战，以Google的BigTable为代表的NoSQL（not only SQL）数据库发展起来。BigTable是一个多维稀疏排序表，由行和列组成，每个存储单元都有一个时间戳，形成三维结构。同一个数据单元的多个操作形成数据的多个版本，由时间戳来区分。此外，Amazon的Dynamo和Yahoo的PNUTS也是非常具有代表性的系统 NoSQL 数据库。到目前为止，对 NoSQL 数据库并没有一个准确的定义，但一般认为该类数据库应当具有以下特征：模式自由（schema free）、支持简易备份（easy replication support）、简单的应用程序接口（simple API）、最终一致性（或者说支持BASE特性，不支持ACID，也即放松了对数据一致性的要求）、支持海量数据（huge amount of data）。
从数据处理的角度，以Google MapReduce 和Apache Hadoop为代表的非关系数据分析技术，逐渐成为业界事实上的标准。这类分布式的数据处理框架，有着三大特征：简化分布式编程，提供便捷的集群管理，提供一定的可靠性保障。所以，它适合大规模并行处理，在大规模互联网数据的搜索和分析领域得到了广泛应用，已成为目前大数据分析的主流技术。虽然如此，但目前MapReduce 和Hadoop在一些特定场景下的性能还不足以满足需求，如高速并发的数据环境，所以多样化、有针对性、实用的大数据分析和管理技术仍有待研究。
针对实时大规模数据的处理，已成为当前业界的核心需求之一。学术界和工业界很多研究工作均有涉及，综合相关方案可以大致归纳为三类：高性能批数据处理模式、流式数据处理模式和两者混合的模式。其中，批处理模式就是修改以Hadoop为代表的批处理框架，减少中间结果的写盘次数，增加作业间的流水化程度来提高单位时间的吞吐量。流处理模式，是针对流式数据的一种天然适合的处理方法，将到达的数据在维护的滑动窗口内进行处理，这将在下一章详细说明，典型系统如Yahoo S4和 Storm。而两者混合的模式，主要思路是基于MapReduce模型增加或改变其中的某些处理步骤，以实现流处理。例如，DEDUCE 系统扩展了IBM的流式数据处理System S，使其支持MapReduce。此外，Spark Streaming通过引入离散流（discretized streams）编程模型，改进了批处理模式，大幅提高了处理速度，并在Spark系统上实现了集成。
3.数据集成与融合
数据集成和融合本身并不新颖，但是大数据环境下的这个问题却有了新的需求，因此也面临着新的挑战。泛在的数据在当前分布式环境下，越来越多地以不同结构、不同质量、不同管理域的形式散布在不同的数据管理系统。为了完成跨平台、多源数据汇集的综合的业务功能，数据集成和融合的需求便日益凸显。
从数据的异构性角度，大数据环境存在新的特征。首先，数据类型从以结构化为主转向结构化、半结构化、非结构化三者的融合。其次，数据源的多样性，带来数据产生方式的变化。相比传统集成问题针对的产生于服务器或者个人计算机的静态离线数据，大数据环境下的数据更多来源于设备位置不固定的移动终端，如传感器、手机、平板电脑、GPS设备。而且，这些设备产生的数据量呈现爆炸式增长，大都具有明显的时空特性。再次，数据存储需求出现了根本性变化。传统数据主要存储在关系数据库中，但爆炸式增长的数据类型如流式数据，无法以常规的形式存储后处理，所以出现了流式计算这种数据处理模式。
从数据质量的角度，数据量大并不意味着数据价值大，相反更多时候会产生信息冗余（包括褒义的冗余容错和贬义的垃圾泛滥）。单个系统难以容纳不同数据源集成的大规模数据，而且冗余程度高的数据必然干扰后续的数据分析过程。针对大数据环境下的数据集成和融合，数据的去冗余技术应当更加谨慎。既不能粒度过高，导致达不到应有效果；也不能粒度太低，导致关键信息丢失。所以，在质与量之间需要进行仔细的考量和权衡。
4.数据隐私保护
隐私问题伴随IT的发展一直层出不穷，互联网环境下累积的大规模数据，更加容易传播和泄露。这使得大数据处理在当前成为一把双刃剑，在为人们的生活带来便利的同时，也加重了自身隐私暴露的危险。互联网尤其是社交网络的出现，使得人们在不同的地点产生越来越多的数据足迹。这种数据具有累积性和关联性，也许单个位置的信息没有意义，但是若从不同渠道非法获得不同独立位置的信息，进行聚集关联，隐私就很可能会暴露。这种隐性的数据暴露往往是个人无法预知和预防的。
从技术层面来说，数据开放和隐私保护是彼此矛盾的，却又都至关重要。极端情况下，为了保护隐私，所有数据都应当加以隐藏，但是数据的价值无法体现，相关的社会公共服务甚至无法开展。所以，数据开放是必要的，尤其对于政府等关系国计民生的相关部门，可以更好地指导社会的运转。同时，企业也可以从公开的数据中了解客户的行为，推出定向产品和服务，最大化其产品盈利；学术单位则可以利用公开的数据，从社会、经济、技术等不同的角度进行研究。所以，大数据环境下的隐私保护，主要体现在隐匿敏感信息的前提下，进行有效的数据挖掘。从这个意义上，它有别于传统的信息安全领域更加关注文件的私密性等安全属性。
5.服务的易用性
服务是IT应用生成和实践的最常用渠道，在当前大数据环境下有着特别的意义。服务易用性的挑战突出体现在两个方面：结果的多样化和面向最终用户。
一方面，大数据环境下，因为处理的数据量大且分析更复杂，为了能让处理的结果被更多地利用，服务是必要的；同时，为了从不同维度理解处理结果，针对同一数据集甚至同一种业务计算，应该提供形式多样的呈现方式。另一方面，相比专业的数据库处理，大数据往往是领域业务相关的，需要面向业务人员等最终用户。最终用户不是数据分析的专家，甚至不是IT行业的从业者，复杂的理论和技术往往超出了他们可接受的范围。所以，针对大数据，如何设计和提供服务，是一个必须解决却仍处于起步阶段的研究问题。一般意义上，服务易用性至少表现为易见（easy to discover）、易学（easy to learn）和易用（easy to use），所以如下的几个原则应当考虑。
首先是数据可视化原则（Visibility）。可视性要求用户使用服务时，能够了解其初步的业务含义和操作方法，结果呈现也应当清晰和有针对性。除了服务的功能设计，结果的展示也要充分体现可视化。大规模数据的可视化却面临着诸多挑战，有技术层面的，也有业务层面的，还有设备资源层面的。
其次是匹配原则（Mapping）。人的认知中会利用现有的经验来考虑新工具的使用。例如，SQL是操作数据库的实际标准，也是从业人员必备的技术基础。在服务的设计过程中，应当尽可能考虑和利用用户已有的经验、业务知识，使新工具便于最终用户使用。例如，针对已经有Hadoop编程经验的数据分析人员，YARN框架给出了集成和综合的方案，使他们能够尽快适应基于现有知识的批处理、流式处理和互交式处理的开发与实践。
最后是反馈原则（Feedback）。所谓反馈，是指用户通过服务提示和便捷帮助，能够随时自行掌握操作过程。例如，进度条和弹出框都是反馈原则的经典例子。大数据环境下，这方面的研究工作较少，设计和实现带反馈服务，对最终用户掌握和理解大数据至关重要。往往交互程度越高，用户的参与程度和理解程度越高，越能够降低门槛，让复杂和高深的理论深入浅出，提高用户的满意程度。
从技术角度分析，可视化、人机交互以及数据起源技术都可以有效地提升服务易用性，但是这些技术的元数据管理问题，是大数据环境下不能忽视的挑战。所谓元数据，是关于数据的数据。数据之间的关联关系以及数据本身的一些属性大都是靠元数据来表示的，故可视化技术离不开元数据的支持。数据起源技术对数据关系的依赖程度更高，需要利用元数据来记录数据之间包括因果关系在内的各种复杂关联，并通过关联实现决策和推断。1.3 本章小结
本章分析了大数据产生的技术背景，包括云计算、物联网的相关基础和技术。同时，也详细分析了当前大数据环境下数据处理技术面临的新挑战，从多个角度分析了当前技术的优势和不足。第2章 流式计算的理论与技术
流式数据（Data Stream，也称数据流）是大数据环境下的一种数据形态，其理论诞生于20世纪末，并在云计算和物联网发展下逐步成为当前的研究热点。流式数据与传统的数据是相对的。与静态、批处理和持久化的数据库相比，流式计算以连续、无边界和瞬时性为特征，适合高速并发和大规模数据实时处理的场景。当前大数据环境下的许多应用呈现多源并发、数据汇聚、在线处理的特征，所以实时数据处理（real-time data stream processing）的相关研究迅速发展，并在许多关键领域，如传感网络、金融、医疗、交通和军事领域，得到了广泛的应用。
作为本书理论和技术的基础，本章论述流式数据和流式计算的概念与特征、技术的发展和相关的开源工具。2.1 流式数据与流式实时计算2.1.1 流式数据
大数据环境下，流式数据作为一种新型的数据类型，是实时数据处理所面向的数据类型，其相关研究发展迅速。这种实时的流式数据，存在如下几个特征。
① 实时、高速：数据能以高并发的方式迅速到达，业务计算要求快速连续响应。数据处理的速度至少能够匹配数据到达的速度。
② 无边界：数据到达、处理和向后传递均是持续不断的。从全局的角度看，累积数据的规模随时间推移不断扩大；从处理数据的局部的角度看，窗口技术（滑动窗口、标界窗口等）可以限定处理数据的范围，但是这一部分数据是不断变化的：有新数据到达，同时又有数据因为过期而被移除。
③ 瞬时性和有限持久化：通常情况下，原始数据在单遍扫描、处理后被丢弃，并不进行保存；只有计算结果和部分中间数据在有限时间内被保存和向后传递。
④ 价值的时间偏倚性：随着时间的流逝，数据中所蕴含的知识价值往往也在衰减，也即流中数据项的重要程度是不同的，最近到达的数据往往比早先到达的数据更有价值。
数据流作为一种数据模型的研究，起源于1998年Digital Equipment Corporation的技术报告，该报告第一次给出了“data stream”这一名称和定义。2002年之后，随着在ACM SIGMOD、VLDB等数据处理顶级会议上出现了一系列研究工作和学术界发布了一批原型系统，数据流发展成为一个研究方向。特别是在云计算、物联网方兴未艾的当今，许多有影响力的互联网企业，如 IBM、Yahoo、Twitter、Esper、Cloudera 和 Facebook 等公司，纷纷推出了自己的产品，这不仅对工业界而且对学术界也产生了深远的影响。
本质上，流式数据也称数据流，是一类数据项（tuple）以追加递增（append-only）方式形成的无限集合。综合学术界的各种观点，本书将数据流模型定义如下。
定义2-1 数据流模型假设输入数据项a，a…顺序依次到达，数12据流描述了如下一维函数A：[1…∞]→R。依据如何描述其中的A，数i据流模型可以分为如下3个子模型。
① 时间序列模型（Time Series Model）。在这种模型中，A与iA[i]相同，并按照i的增序呈现。这个模型适合描述时间序列数据（Time Series Data），以i表示时间戳，A[i]表示数据项的值。例如，每5s监控得到的室温数值。
② 收银机模型（Cash Register Model）。在这种模型中，A是iA[j]的增量。假设A=（j，I），I≥0，则A[j]=A[j]+I，其中A[j]表示数iiiii-1ii据项j在i时刻的值。数据项A[j]的值随着时间不断增加A[j]，这样单调i递增的变化方式类似收银机，故得其名。例如，统计一段时间内某连接的源IP地址访问服务器的次数，由于同一个IP可以提出多次访问请求，故统计值总是递增的。
③ 转门模型（Turnstile Model）。在这种模型中，A是A[j]的更新i值。假设A=（j，U），则 A [j]=A[j]+U，其中A[j]表示数据项j在i时iiii-1ii刻的值，U∈R。例如，监控某段道路的车辆总数，道路的开放性使i得任意时刻车辆都可以进入或者退出道路，所以监控的数值可以增加，也可以减少。
事实上，收银机模型可以作为转门模型在U≥0时的特例。从理论i分析和实际使用的角度，每一种模型都有自身适用性和在特定问题背景下的优势。所以，数据流的算法设计，通常是显式或者隐式地说明其针对的数据流模型。
注意，由于收银机模型和转门模型都与应用逻辑相关，本书所指流式数据均是时间序列模型描述的数据流，这种模型更适合描述原始的数据序列。
接下来，我们对比两个相关概念——Database与Dataflow，进一步辨析和阐述流式数据这个概念的内涵和外沿。
数据流发展自数据库（Database）的研究领域，源于静态数据处理的传统数据库技术已经不能满足实时数据处理的需求。所以，数据流和数据库这两种数据处理技术，在基本思路和方法路线上完全不同，它们之间的对比见表2-1。
① 面向的数据不同。数据库适合处理静态/离线的数据，而且数据之间满足关系代数的范式。流式数据针对无边界、离散的在线数据，数据项与数据库的元组相比，有时间戳的概念，而且这是处理过程中相当重要的属性。同时，数据流持续不断地到达，更新频率比数据库高数个量级。
表2-1 Data Stream与Database的比较
② 使用模式不同。数据库维护数据，应用提交查询请求，以提取（Pull）的方式获得返回结果。数据流管理系统维护查询，数据不断到达，应用通过系统的推送（Push）获得连续的结果。
③ 查询实现不同。数据库可以多遍扫描，以随机访问的方式获取数据；对给定的查询通常以事务的方式一次性返回；处理结束后原始数据仍然是持久化的（实现删除的delete操作除外）。数据流单遍扫描、顺序访问持续到达的数据（速度也是不可控的因素），根据注册的查询连续返回结果；原始数据只在内存中暂存，扫描完成后丢弃，处理结果往往也是有限的持久化，比如只存储1个月内的结果。
另一个与数据流相关且相似的概念是Dataflow，而且Dataflow也被翻译为“数据流”，这更容易导致概念的混淆。本书梳理了相关概念的内涵，分析了两者的区别与联系，见表2-2。
表2-2 Data Stream与Dataflow的比较
首先，从这两个概念的起源角度分析。上文已经提到，Data Stream 这个概念是与Database相对的，当Database不能满足实时数据处理的需求后，Data Stream发展起来。而Dataflow指的是一种任务（Task）协同模式，且任务之间传递的是内容（数据本身）；这个概念是与Control Flow（控制流）相对的，Control Flow同样是一种任务协同模式，但是任务之间传递的是执行控制权（Execution Right）。但是，绝对的Dataflow并不存在，Dataflow 一定是通过数据主导（Dominate）控制流完成任务的协同，即所谓的数据驱动（Data Driven）；同时，纯粹的数据驱动的方法表达能力有限，所以实际应用都是Dataflow与Control Flow混合的方法。
其次，从两个概念的目标和典型应用分析。Dataflow的目标是实现任务的协同，而传统的任务协同都是通过控制流实现的，例如经典的业务流程管理（Business Process Management，BPM）控制流是需要被建模的首要因素。随着科学工作流等面向最终用户的协同应用的兴起，更容易被用户理解的数据驱动模式受到了研究界的重视，出现了一些著名的e-Science Dataflow工具，如Kelper、Taverna和相关的数据管理方法等。而Data Stream的目标在于面向应用的数据处理，如网络日志分析、道路交通监控等，强调实时性；同时本书认为，当 Data Stream 处理过程中存在多个协同的任务时，也可以被认为是广义的Dataflow。2.1.2 流式实时计算
实时数据处理（Real-time Data Process）也称实时计算（Real-time Computing）或反应计算（Reactive Computing）。相应地，针对流式数据的实时处理，称为流式数据处理或流式计算。
由定义2-1可知，流式数据具有无边界的特征，也即理论上是无穷的数据项序列。而流式实时计算只能使用有限的内存资源，所以数据流的算法一定是某种程度对流的摘要化（summarization of stream）处理。摘要数据结构（synopsis data structure）和窗口（window）都是最常用的摘要化技术。
摘要数据结构的名称和定义最早由Bell实验室的Phil Gibbons 和Yossi Matias提出。
定义2-2 摘要数据结构任何比本身基础数据集（base data set）小得多的数据结构，都拥有如下特点：①可以驻留（reside）内存，使得查询及时响应而避免访问磁盘；②远程传输（transmitted remotely）的代价小；③对系统整体的空间开销（storage cost）影响小；④当访问基础数据集的开销过大（expensive or impossible）时，可以作为基础数据集的小规模代理（small surrogate）被操作。
摘要数据结构的设计和使用都依赖于需要解决的业务需求，而针对不同问题采用的摘要数据结构的差别很大。例如，针对查询评估设计的摘要数据结构在变更的检测（change detection）和分类（classification）方面，与针对流式数据挖掘的摘要数据结构完全不同。又如，直方图（histogram）作为摘要数据结构常常被用于分位数（quantile）、k-均值（k-medians）、计数（count or sum）和关联聚集（correlated aggregation）等计算；而链表（linked list）作为数据结构则可以用于极值聚集和前k项查询等计算。所以，数据流领域的计算，通常都是根据所关注业务问题的特点，实现专用的摘要数据结构。
窗口技术是数据流研究中另一个常用的技术。由于数据流存在实时性的需求，流中最近到达（recent past）的数据比很久之前到达（distant past）的数据对计算来说更有意义。如何描述流中数据的“最近”，是窗口模型的意义所在。
定义 2-3 窗口。数据流的窗口是描述数据流的最近子集组合（combinatorial）的方法。通过设置的窗口边界（bound），使得流中部分数据项位于窗口内，而在窗口之外数据则不被处理计算考虑。窗
试读结束[说明：试读内容隐藏了图片]