流数据处理对于现今的大数据来说是一件大事，并且有充分的理由。其中： 企业渴望获得更及时的数据，切换到流处理是实现更低延迟的好方法。 现代业务中越来越常见的大量无限数据集使用专为这种永无止境的数据量而设计的系统更容易被驯服。 在数据到达时处理数据，随着时间的推移将工作负载分布得更均匀，从而产生更一致且可预测的资源消耗。 Background 首先，我将介绍一些重要的背景信息，这些信息将有助于构思我想讨论的其他主题。我们将在三个特定的部分完成此操作： Terminology: 精确地谈论复杂的话题需要对术语进行精确的定义。对于一些在当前使用中已经超负荷解释的术语，我会尽力确定我说的时候的意思。 Capabilities: 我会谈谈流媒体系统的常识缺点。我还会提出我认为数据处理系统制造商需要采用的思维框架，以满足现代数据用户的需求。 Time domains: 我将介绍与数据处理相关的两个主要时间领域，展示它们之间的关系，并指出这两个领域带来的一些困难。 Terminology: What is streaming? 问题的症结在于许多应该由它们所描述的东西（例如，无限数据处理，近似结果等）已经通过它们历史上已经完成的方式来口头描述（即，通过流式传输执行引擎）。术语精确度的缺乏决定了流传输的真正含义，并且在某些情况下，流传输系统本身的负担会加重，这意味着它们的能力限于经常被描述为 “流” 的特性，如近似或推测性结果。鉴于精心设计的流媒体系统与任何现有的批量引擎一样能够（技术上更加如此）产生正确，一致，可重复的结果，因此我更愿意将术语 “流” 分离为一个非常具体的含义：一种数据处理引擎设计时考虑了无限的数据集。而已。 （为了完整性，或许值得一提的是，这个定义包括真正的流媒体和微批量实现。） 这里有几个我经常听到的，每个都有更精确的描述性术语: Unbounded data: 一种不断增长的，实质上无限的数据集。这些通常被称为 “流数据”。然而，流应用或批处理术语在应用于数据集时存在问题，因为如上所述，它们意味着使用某种类型的执行引擎来处理这些数据集。所讨论的两类数据集之间的关键区别实际上是它们的有限性，因此最好用描述它们的术语来描述它们。因此，我将把无限的 “流式” 数据集称为无界数据，将有限的 “批处理” 数据集称为有界数据。 Unbounded data processing: 一种持续的数据处理模式，适用于上述类型的无界数据。尽管我个人喜欢使用术语流来描述这种类型的数据处理，但在这种情况下它的使用又意味着使用流式执行引擎，这充其量是误导性的; 由于批量系统首先被构想出来（相反，设计良好的流式系统不仅能够处理超过有界数据的 “批量” 工作负载），所以批处理引擎的重复运行已用于处理无界数据。因此，为了清楚起见，我将简单地称之为无限数据处理。 Low-latency, approximate, and/or speculative results: 这些类型的结果通常与流引擎相关联。事实上，批处理系统传统上没有考虑到低延迟或推测性结果，这是一个历史人为因素，仅此而已。当然，批量发动机如果有指导，完全可以产生近似的结果。因此，与上述条款一样，将这些结果描述为它们（低延迟，近似和 / 或推测）比通过历史流式（通过流式引擎）如何表现要好得多。 从这里开始，任何时候我使用术语 “streaming”，你都可以安全地假设我的意思是一个为无界数据集设计的执行引擎，仅此而已。当我指上述任何其他术语时，我将明确地说出无限数据，无限数据处理或低延迟 / 近似 / 推测结果。这些是我们在 Cloud Dataflow 中采用的术语，我鼓励其他人采取类似的立场。 On the greatly exaggerated limitations of streaming: 接下来，让我们谈一谈流式系统可以做什么和不可以做什么，重点放在能做的上; 我想在这些帖子中看到的最重要的事情之一就是设计良好的流式传输系统的性能如何。流式传输系统长期以来一直处于一个提供低延迟，不准确 / 推测结果的利基市场，通常与更强大的批处理系统相结合以提供最终的正确结果，即 Lambda 架构。 对于那些还不熟悉 Lambda Architecture 的人来说，其基本思想是，您可以在批处理系统旁边运行流式处理系统，两者执行基本相同的计算。流式传输系统为您提供低延迟，不准确的结果（或者因为使用近似算法，或者因为流式传输系统本身不能提供正确性），并且一段时间后，批处理系统会一路滚动并为您提供正确的输出。最初由 Twitter 的 Nathan Marz（Storm 的创始人）提出，它最终取得了相当的成功，因为它实际上是一个很棒的想法。流媒体引擎在正确性部门中有点令人失望，批量引擎如你所期望的那样固有地笨重，所以 Lambda 给了你一种方法来让你的谚语蛋糕也吃掉。不幸的是，维护 Lambda 系统非常麻烦：您需要构建，配置和维护两个独立版本的管道，然后以某种方式合并最后两条管道的结果。...

introduction As we all know, python is a dynamic language and dynamic typing can be flexible, powerful, convenient and easy. But with your project growing, dynamic typing is not always the best approach. As an opposite, static typing can make programs easier to understand and maintain. Type declarations can serve as machine-checked documentation. This is important as code is typically read much more often than modified, and this is especially important for large and complex programs....

gRPC example protocol buffers; As we all know, gRPC service is defined using protocol buffers; If you want to know how to define a .proto file, you can go to [protocol buffer Developer Guide]（https://developers.google.com/protocol-buffers/docs/overview）, Here is our stream_algorithm.proto defination: syntax = "proto3"; // Interface exported by the server. service MyAlgorithmBrain { //get the rank of the item in real time rpc MyRankOfStream(stream ItemRequest) returns (ItemResponse){} //get the structure of the sketch maintained in server rpc SketchOfStream(stream ItemRequest) returns (ItemResponse){} } message ItemRequest { int32 id = 1; int32 value = 2; string timestamp = 3; } message ItemResponse { float rank = 1; } Generate gRPC code Next we need to update the gRPC code used by our application to use the new service definition....

Bloom Filter introduction 首先，我们假设有四种存储设备，分别是 Tape, HDD, SSD, Memory．当然，我们知道，这四种设备的响应速度是按顺序递增的，也就是说 Memory 的速度最快，当然，我们都希望所有的程序都可以跑在 Memory 中，但是这四种设备的存储大小即容量也是不一样的，价格也是随之递增的．Ex .g 当我们在 Java 中使用 Set 类型去存储数据的时候，数据越多，查询所需的时间越长，同时 Jvm heap 也越大．实际生产环境中的数据量极大，在一些实时性要求比较高的应用当中，不可能将所有的数据都放在 Memory 中，当允许一定的误差的情况下，（即使用准确性去换取实时性，这是一种 tradeoff）这里就提出了，一种　Probabilistic　data structure，它可以在一定程度上去接受一定的误差，从而使响应速度加快，所要存储的数据也大大缩小． Bloom Filter 的概念提出的比较早，早在１９７０年就由一个叫 Bloom（真的叫这个名字）的人在一篇名为＂Space / Time trade-offs in hash coding with allowable errors＂ structure Initial the structure Add an element to this structure query 判断存在还是不存在 If one hash function map to 0, It means NO!（　有一个 map 到０　就不行） But if all hash functions map to 1, it means maybe YES(即使　所有的 hash 函数都能 map 到１，　也不能说明就一定存在，　这里有一定的 false positive，　即认为是正确的，但实际上不是正确的概率)...

https://datasketches.github.io/docs/Research.html 来源与雅虎的开源项目，翻译ｂｙ Titanssword 结合自己研究方向，可合并摘要，分位数, k 均值聚类的流式算法, 有关图流处理算法, 有关滑动窗口流算法 Introduction 在分析海量数据集时，即使对数据进行非常基本的查询，也可能需要巨大的计算资源（内存和计算时间）。这种查询的例子包括识别频繁项目，唯一计数查询，分位数和直方图查询，矩阵分析任务（例如主成分分析和潜在语义分析）以及更复杂的下游机器学习任务。一旦数据量大了之后，这些计算任务将变得十分困难。也达不到实时性的要求。 然而，在许多情况下，只要近似误差被仔细控制，近似的答案是可以接受的。例如，如果数据是嘈杂的，那么比数据中已经存在的噪声更少的错误的答案与确切的算法一样有用。即使数据是无噪声的，许多高层次的商业决策也不需要对数据有精确的了解：在特定的时间内，有多少唯一身份用户访问某个网站时，可以知道多达 1％的错误，这通常与确切的答案一样有效。 当大致的答案是可以接受的，系统设计人员已经掌握了关于流算法的大量文献。这些算法一次处理海量数据集，并计算数据集的非常小的摘要（也称为草图），从中可以得出准确（但近似）的查询答案。许多流式传输算法甚至对 PB 级大小的数据集也只用了几千字节的空间，并且能够对每个数据进行定时处理，从而实现实时分析。 Mergeable Summaries 理想情况下，数据流算法将生成可合并的摘要，这意味着可以独立处理许多不同的数据流，然后可以快速组合每个数据流计算出的摘要，以获得各种数据集组合的精确摘要（联合，交叉等）。可合并摘要使大量数据集能够以完全分布式和并行的方式自动处理，通过在许多机器上任意分割数据，汇总每个分区，并无缝结合结果。除了与精确的方法相比，大大减少了内存使用量，计算时间和延迟，可合并的摘要也极大地简化了系统架构。它们允许非加性查询（如唯一计数查询）被视为加法，两个草图的 “总和” 是它们的合并。这意味着数据可以分割成片段，每个片段分别勾画，草图存储在简单的数据集市架构中，并在查询时合并。 合并摘要的最终重要应用是在外围设备较弱的情况下节能。例如，物联网（IoT）的主要优势之一是它可以监控和聚合物联网设备（如传感器和设备）的数据。这样的设备往往是功率受限的，所以必须最小化必须从每个设备发送到聚合中心的数据量。可合并摘要启用了这一点：每个设备可以自己计算自己数据的摘要，并只将摘要发送给聚合中心，聚合中心将所有接收到的摘要合并，以获取所有设备数据集的全局摘要。 Agarwal 等人在其 Mergeable Summaries 可合并摘要论文 中讨论了不同类型的可合并摘要 The Data Sketches Open Source Library 该库从一开始就被设计为高性能和高质量的产品，适用于需要处理海量数据的大型数据处理系统。该库是用 Java 编写的，包含了各种基本查询类的最新算法，包括识别频繁项目，唯一计数查询，计算分位数和直方图以及采样。它很快将包含像 PCA 这样的矩阵分析任务的算法。库中的所有算法都会生成可合并的摘要，并对返回的答案的准确性提供正式的保证。 目前，该库的核心贡献者是 Lee Rhodes，Kevin Lang，Jon Malkin 和 Alex Saydakov（全部来自 Yahoo / Oath），Justin Thaler（乔治敦大学计算机系助理教授）和 Edo Liberty（首席科学家在亚马逊网络服务和亚马逊 AI 算法组的经理） 该库已经在整个行业和政府进行了调整。例如，在雅虎被设计和创建的地方，该库在内部被广泛使用，以减少许多任务的处理时间从几天到几秒。在 SpliceMachine 中，它用于数据库查询计划和优化。它也深深嵌入到一个叫做 Druid 的低延迟开源数据存储中，还有一个由英国情报机构 GCHQ 维护的叫做 Gaffer 的开源图形数据库。 除了在部署系统中的实用性之外，开发数据草图库的开发过程导致了有趣的研究。这既涉及流算法的理论，也涉及解决真实世界流引擎中至关重要的问题，但在学术文献中经常被忽略。这些问题包括可合并性，以及处理加权流更新（即每个数据片带有相关重要性度量的数据流）。 特别是在数据草图库上的工作已经导致了新颖的算法实现用于识别数据流中频繁项目的最新实用性能 [ABL + 17] 和用于唯一计数查询的可合并摘要 [DLRT16]。在理论层面上，该库的工作导致了分位数查询的流近似算法的空间复杂度的解决，这是一个长期以来的开放性问题 [KLL16]Optimal quantile approximation in streams，也是解决识别频繁项集的问题 [LMTU16]Space lower bounds for itemset frequency sketches。*...