通过约束条件分析塑造大数据

阅读数:1025 2015 年 7 月 23 日

计算系统的设计其实就是在玩约束条件的游戏。一个设计良好的系统就像是个定制化的运输箱:它的外部有锁扣和手柄,但从里面装的东西来看其内部设计,却往往给人印象不佳。如果要设计一个优雅简洁的容器,你应该聚焦在那些最重要的因素上:尺寸、重量、;平衡和移动。这些因素以及它们之间的相关影响就构成了设计中的有效约束条件。

在这篇文章中,我将描述了一种对系统数据的形状和流的约束条件进行分析的方法,并将它应用在真实世界的例子中。基于约束条件的方法和物流领域中的格德拉特(Goldratt)理论相似。根据我的经验,最成功的系统设计师和容量规划师倾向于依据具体的约束条件来思考计算系统,即使他们可能没有说出声来。

相比从基准(benchmark)外推,或者争论“并发用户”的定义,使用约束条件方法要有用的多。它能在编码之前揭示可能的系统瓶颈及其相互的依赖关系。这些知识对于理性地选择设计方案至关重要。通过实践你甚至可以对别人,比如竞争对手的系统做出敏锐的猜测,而这也很简单,只需要你观察它是如何运行的。

这个技巧在于先建立数据的尺寸和重量,然后聚焦于它是如何流动的。计算机其实只做两件事情:读入数据和写出数据。性能决定了多少数据可以移动,以及它们移动到哪里来完成任务。说起来似乎很容易,但这需要掌握基础的计算理论。每个计算机等同于一个图灵机(Turing Machine),而所有图灵机做的事情就是在磁带上移动符号,所以它的吞吐量取决于符号移动的速度。从小的微米级的 CPU 内部到大的横跨世界的分布式数据库,这个推论仍然成立。幸运的是,这里的数学方法简单明了。

可以迅速丢弃坏的方案,而无需实际创建它们,这种能力对于好的系统编程有决定性的意义。它部分是靠直接,还有一些经验,但最主要的是算法。

— Keith Adams

我认为描述系统最有用的八个因素如下:

  1. 工作集尺寸(Working set size):这是系统在正常操作时需要处理的一组数据。复杂系统通常会有多个不同的工作集,但其中一至两个是最主要的。在类似邮件或者是新闻馈入的流应用中,当前处理的工作集要比总体的工作集小得多。人们几乎很少会去访问几周前的消息,所以把它们考虑成由另一个系统处理也许更好。更多时候,情况并不如此简单,很难在“热”数据和“冷”数据之间画一条清晰的界限。所以,用概率带(probability band)来思考这个问题会很有帮助:比如过一段给定的时间后,不同部分的数据被使用的概率会是多少?会有多少个概率带?它们是如何分布的?在初始分析中,你可以只关注工作集的大体尺寸,而不是它的细节特征。然而,这些细节会在后面主动找你的。
  2. 平均事务尺寸(Average transaction size): 这个可以理解为系统执行单个事务时的工作集。那么系统完成一个事务要接触到多少数据呢?下载一个图片和运行一个网络搜索,其发送到客户端的回答包括同等规模的数据。但是,它们在后台处理时接触到的数据却差别很大。注意我使用了“事务”这个词来表示不相同的工作,这个观点同样适用于大的分析作业。
  3. 请求速率(Request rate): How many transactions are expected per hour / minute / second? 每个小时 / 分钟 / 秒会有多少个事务发生呢?会有峰值时间,或者比较稳定的需求? 如果是搜索引擎,每分钟每个人可能会有 5 到 10 次的查询需要处理。如果是在线电子书,它可能是一个持续但较低的流量。如果是游戏,那每个人每秒种可能会有多个事务要处理。简单说,这些都是预期的并发量。并发量和事务尺寸的结合 决定了系统数据流的主要因素。
  4. 更新速率(Update rate): 这是来衡量数据增加、删除和编辑的频率。邮件系统有高的增加速率,低的删除速率和几乎是零的编辑速率。而广告拍卖的用例在这三种速率上都异乎寻常的高。衡量更新速率是否值得担心有个有用的方法,就是把它和读取的并发量做一个对比。

    数据增长的速率和工作集大小或数据保留策略也是相关的。0.1% 的增长速率意味着数据要保留大概三年(365 * 3 大约是 1,000)),反之亦然。而 1% 的增长率则意味着数据保留 100 天。
  5. 一致性(Consistency): 一次更新必须在多快的时间内传播到整个系统? 对于关键字广告报价,几分钟的传播时间是可以接受的,而股票交易系统必须在毫秒级完成. 一个评论系统通常期望在一两秒内显示新的评论, 这需要后台疯狂的工作,以给评论者产生即时性的错觉。当更新速度是请求速度中最主要的部分时,一致性就是个关键因素。当传播的更新对于业务特别重要时也同样如此,比如账号注册或者价格和存货发生了变化。
  6. 位置(Locality): 一个请求需要访问工作集中的哪些数据? 这部分的数据如何去定义? 不同请求是否有重叠的部分?极端情况下会使用搜索引擎来回答这些问题: 即用户可以从系统中任何地方来查询到想要的数据。在邮件应用中,用户被确保只能访问他们的收件箱,相对整体数据,这是个小的且定义良好的数据片段。在另一个实例中,你可能需要无重复数据的存储来保存邮件附件,并让其成为热点。
  7. 计算(Computation): 你需要用什么样的数学方法来运行数据? 数据可以预先计算和缓存吗?你会在大数据集上进行交叉吗?你是将计算贴近数据, 还是相反?为什么?
  8. 时延(Latency):事务多快 可以返回成功或失败呢?用户在搜索航班或者进行信用卡交易时,似乎可以接受几秒钟的处理时间。网络搜索必须要在几百毫秒内可以返回;而系统调用外部依赖的API 时则希望可以在100 毫秒或更少的时间内返回结果。除了时延,考虑方差也是很重要的。正如论证的那样,90% 的查询在0.1 秒以内,剩余的在2 秒以内的情况要比所有请求都在0.2 秒内完成的情况要差。

找到瓶颈

找到一个你想分析的系统,然后填写出上述的那些约束条件,并且草拟一个方案能满足这些条件。下来问自己最后一个问题:决定性的操作是什么?换句话说,最基本的瓶颈在什么地方?哪些部分必须仔细考量?

当你大声说出来答案时,虽然听起来可能平淡无奇,但是确定一个系统的真正瓶颈对于 认知事物有极大的帮助。偶发性的瓶颈往往会形成堆积,修正一个会激活另一个,但是它们不会对你设计的基本前提形成颠覆性的威胁。基础性的瓶颈则难于修复,也很难识别,因为它们是由创建系统时基于的一些自然事实或者一个强假定引起的。一个无穷快的网址仍然受限于光的速度,火箭也会受限于提升自身燃料重量的需求。保持这种思考性的实验直到你完全理解最基础的瓶颈是什么?以及为什么?

我们可以打个比方,你有个披萨店,想赚更多的钱。如果购买的人排长队,你可以把订单登记的数量增加一倍。如果是披萨送货时迟到,你可以规划一个更好的工作节奏,或者为送货员配备车辆。甚至你可以尝试提高烤箱的温度。但从根本上说,披萨店的瓶颈是烤箱的尺寸。即使你把其他事情都做好,如果烤箱容量不扩张,你也无法生产出更多的披萨。当然你也可以再购买一个烤箱,不过你必须事情想清楚,把这个新家伙放到什么地方。

如果你不能清晰地发现系统的基本瓶颈,那么就去改变系统的约束条件,看看它的响应有什么变化。比如你必须将延迟降低 10 倍,看看会发生什么?比如你只用一半数量的计算机?如果放松一致性的约束,又要靠什么样的技巧才能侥幸成功?通常认为初始约束是真实和静止的,但实际中它们很少如此。问题中的创造力远比答案中的创造力更有利用价值。

如果你想了解某件事情,把它放在极端条件下观察或者检查它的对立面。

——Col. John Boyd

影视流用例

让我们将上面的方法应用到比披萨店更复杂的案例中,即视频流服务。可以想象它是一个小规模的 Hulu 或 Netflix,视频库容量为十万个,平均 60 分钟的时长,500 kbps 的比特率。在高峰时间,大约会有一百万人观看。

  1. 工作集尺寸: 100 k 视频)*(60 分钟)*(60 秒)*(500 kb / 秒)/( 8 位字节),算出来大约超过 20 TB 的数据。公式中最敏感的数字是比特率,改变比特率可以缩小或膨胀总的数据大小。
  2. 工作集的概率带依赖于视频受欢迎程度的分布,它 (可能) 是个长尾。假设所有视频中,受欢迎程度前100 个的视频占播放总数的10%,排名在前1000 个的视频占20%,排名在前10000 个的视频占35%。而倒数第三的视频的占比很可能已经无足轻重,你甚至不必去留意它。所以,人们很容易完全忽略长尾。然而, 正如我们后面将看到的那样,这将是一个mistake。
  3. 平均请求尺寸(Average request size): 大约是(3600 秒)*( 64 kbps), 或者几百 MB。在实践中,流的平滑取决于能够把数据以略高于其消耗的速度推到客户端去,并且很可能都是以小数据块来完成。为了使问题简化,我们特意忽略了发送到客户端过程中,涉及流量整形的那些繁杂的问题。
  4. 请求速率(Request rate): 和较小请求尺寸的系统相比,其请求速率会相当的低,但是仍会有高并发的请求。可以期望用户浏览是多个短脉冲,而媒体流则是长时间持续的。高峰时段系统每秒排出的数据将达到每秒 0.5TB。
  5. 更新速率(Update rate): 和请求速率相比,更新速率近乎于零,这是因为视频基本上都是专业制作。但如果这是 YouTube,那么将会是一个完全不同的故事。
  6. 一致性(Consistency): 因为在很大程度上这是个只读的系统,所以这一点可以被忽略掉。
  7. 位置:用户可以观看任何一个电影,当然同一时刻只能有一个。从相反的方向来看这个问题,你会发现来自不同的地方的用户会在同一时刻访问相同的电影。
  8. 计算(Computation): 计算量的大小取决于视频是否是动态生成编码。如果不是这样,那么计算的主要工作就是把数据放到管道中。
  9. 延迟(Latency): 这是个有趣的问题。最坏的情况是不停的进行频道切换或者在视频播放时中不停的跳跃播放位置。在实际的影片服务中,您可能已经注意到,切换不同的媒体流或者在一个视频中跳跃播放位置需要在一两秒钟内完成,长于这个时间将是不可接受的。

现在让我们来概述一下可以满足这些约束条件的系统。总共 20TB 需要保存的数据量,看上去不算太大;500Gbps 的请求速率,看上去数据服务量还是挺多。如果我们使用当前(2015 年)16 核的文件服务器,它可以轻松完成 7 Gbps 的有效网络数据吞吐,所以我们需要至少 50 个这样的服务器,每个上面配置 128 GB 的 RAM,还有 2 TB 的存储,这样很容易容纳整个的工作集数据。

虽然我们可以把数据存储起来,但我们可以移动它们吗?让我们再来看看欢迎度曲线,前 100 个视频占了总需求的 10%,所以你会想要在每个服务器存储这 100 个视频的副本。实际中你可能会对前一个视频都这样做,它们占了总带宽的三分之一,但只用掉了 10% 的存储空间。如果有足够的 RAM 和一点运气,那么受欢迎的视频几乎完全可以从内存中提供服务。

这样,还剩下 9 万个视频,处于长尾右端的 3 万个视频观看次数很少,所以无关紧要。但长尾中间的 6 万个视频占了总业务流量的 2/。所以需要考虑如何为它们服务,同时保持延迟条件的约束?由于 RAM 已经被最受欢迎的视频占用,所以接下来就要算算存储层额可以支持多少 500 kbps 的业务流量并发。具体的设计可能要进行测试后才会出来,但最终很可能是几百个磁盘驱动器并行工作来达到好的结果。

从这里我们可以得出结论:视频服务的基本瓶颈是随机寻道时间,在设计上这等同于那些小的金属机械臂可以来回移动的速度。起控制作用的约束条件是人们观看视频的欢迎度曲线,这个是你无法改变的。

还有其他的设计方案可能会解决这个问题。例如,在每个服务器上配置 1 TB 的 RAM,而不是 2 TB 的磁盘。使用今天或明天的 SSD 技术也可以圆满的解决这个问题。这里用到的数字可能不是很准确,而且肯定会随着时间的推移而改变。关键是发现那些最重要的具体细节,并重点讨论它们。

人脸识别用例

有时候,系统会被一个特定操作严重主导,以至于几乎其它操作相比它都无足轻重。可以举一个有趣的案例,即人脸识别。记住不是人脸检测,人脸检测仅仅是在图像中找到人脸,而决定在给定照片中的人是谁,则需要和照片库中照片进行比较。

人脸识别首先需要对已知人群的照片进行预处理,以便对每个人的基本特性生成一种抽象描述,这种抽象描述有个非常奇怪的名字,叫“特征脸(eigenface)”。一个特征脸是一个固定大小的数据块,通常小于 100 kB,它可以由一些聪明的算法生成。生成特征脸的主要好处是可以相对低廉的计算任意两个人脸之间的相似度得分。得分越高,两个人脸轮廓特征就越接近,从而你识别出这个人是谁的可能性更高。

假设你有一个对应五千万个体的人脸特征库,它们可能来自国民护照,或者驾照数据库,或者是世界上最大的年鉴。系统每秒会有数百个查询照片流请求进来,这些实时地流请求来自边境机构的护照控制需求。必须在 1 秒或更少的时间内为每张照片找到相似度排名前十的匹配者。好了,我们开始分析:

  1. 工作集尺寸:工作集尺寸为:5 千万 * 100KB,总共 5TB。热数据和冷数据短期内无法区分,并且可能并不存在这样的区分。
  2. 平均请求尺寸: 每个请求系统进来的数据是一张照片,他可以被缩减成 100KB 固定尺寸的特征脸,但每个请求需要访问的系统数据可能会非常高。
  3. 请求速率:每秒 300 个。
  4. 更新速率: 具体情况暂时还不清楚,但是可能次数较低,而且应该是在预处理时的批处理操作。
  5. 一致性:在更新速率低的情况下,这个可以暂时忽略。
  6. 位置:我们必须扫描库中的 5 千万资料,并且给匹配度排名,这个想法有些不切实际。我们需要找到一种方法尽可能多得省略一些工作。
  7. 计算:阅读实际的人脸检测算法是相当迷人的,但对于这个练习却并不是很重要。我们做一个假设即可,即完整的比较两个特征脸需要 10 毫秒的 CPU 时间。
  8. 延迟:必须在1 秒或更少的时间内完成,这是个刚性需求。

满足低延迟需求的唯一方法是在执行在给定的搜索时,大幅减少特征脸全面对比的数量。但正如肠道检查那样,这涉及到可能性的范畴,即在这个问题上是否可以投入足够的计算资源?答案很可能是 No。每秒特征脸对比的次数 =5000 万 * 10 毫秒 * 300,这大约需要每秒 5000 CPU-years 的计算能力。我看过一些大型集群,但都达不到这样的规模要求。

所以我们需要用些聪明的方法来减少工作。这个领域中比较活跃的研究是一种快速搜索【特征脸索引】的方案,但是通过摘要我们知道其加速线性而不是对数的(所以可能无法满足我们的性能需求)。谷歌有一个通用的图像相似度搜索方案,这个理论上也许是可行的,但是不一定是可用的技术。现在我们先停止调查,尝试一下别的东西吧。也许我们可以基于人的眼睛颜色、年龄或性别来消除大部分的候选人。举个例子来说,对比一个 30 岁的女人和一个男孩子的照片是没有意义的。

假设可以通过启发式和低成本的技巧来缩小候选人的数量,比如对于一个给定的查询照片只需要对比 1000 个候选人。这相当于用 10 个 CPU 来解决 10,000 毫秒(译者注:1000 个候选人乘以 10 毫秒)的计算问题以让延迟控制在 1 秒,如果添加更多的资源,完成任务就没有问题。如果每个用 12 个 CPU,那么 300 * 12 意味着我们总共需要 3600 个 CPU 来处理请求,这大约是 250 台服务器或是六个机架。这样的计算机集群其重量大概是三吨,其计算能力以任何标准衡量都是相当高的,但为了这个重要的项目还是值得的。

我们现在可以计算它了,但是我们可以保存数据吗?5TB 对于 RAM 来说是相当多的。但从另一方面来说,我们有服务器集群来提供这些内存。将库中的特征脸数据分布到集群的 RAM 中有点类似 Memcached 的方案。

好了,现在让它动起来吧。噢。它看起来走不了。

我们可以存储它,但是我们可以移动它吗?我们忘记更新平均请求尺寸了。如果单个请求访问 1000 个特征脸,这些特征脸数据是随机分布的,这相当于将 100 MB 的数据从它所在的 Memcached 服务器移动到另一个负责特征脸对比的 CPU 所在的服务器上。假如那个时间每秒有 300 个请求,那我们就会面临 240gbps 网络带宽消耗,这是个致命的风险。对于每台服务器来说,这接近于 1gbps 这个令人不安的数据,而且此时 CPU 已经忙于特征脸的比较而无法应对这么高的网络传输负载。

我们需要将计算放在数据存储的地方,而不是将数据传输到计算节点。在开始比较之前,我们准确地知道哪 1000 个特征脸需要对比。Memcached 对特征脸键值采用直接哈希的方式,所以特征脸存储的服务器是很容易得知的,下来就可以将具体的请求路由到这个特定的服务器上。每个服务器基于本地数据会做 4 或 5 次比较,并返回它们的相似度得分。整体的相似度得分的列表可以很容易地组装起来并进行排序。这种方案下,唯一的网络流量将是查询时特征脸照片所占的 100 KB,乘以服务器的数量 250,估算成 300 倍,总共 60gbps,这个数字虽然很高,但是是可行的。进一步,可以使用更聪明的数据分布方案来避免数据查询展开到整个集群中。

系统的基本瓶颈就是扫描那些特征脸,到目前这点可能看得还不是很清晰。这是个比较难的问题,我们几乎没找到一个合理的解决方案,甚至我们还没有考虑识别的准确性是否足够有用。这种人脸识别的分析在重要细节几乎肯定会出错,但从一些懂行的人给出的评论来看,方案大致是正确的。我故意选择了这个我不太了解的用例来演示如何约束分析如何帮助你分析系统,即使(特别)你不是一个专家。

想象一个专家过来告诉你“为什么不利用 GPU 呢?他们可以将特征脸的对比提速十倍!”你可以回答“听上去很有趣,但是它对网络带宽问题有何帮助呢?”(实际上可能会有帮助,如果它能减少机器数量)。如果有人说“我有一个办法来索引特征脸!”你可以回答“这很有趣,但前提是它能帮助我执行不到 1000 次完整的比较。顺便说一下, 你应该和懂 GPU 的那帮家伙聊聊。”你也知道应该密切注意说这样话的一些人,即 “我可以使用比 100KB 更小的尺寸来准确地代表一个人的脸。”

这其是基于约束条件分析方法的真正价值,即帮助你更好理解问题的物理意义,从而揭示出那些需要创造性的地方。像特征脸技巧那样,它允许你通过标准形式来呈现复杂的图片,从而可以在对比中很快地接受或拒绝。

科学不仅仅是探索为什么(Why),而是为什么不(Why not)?

— Cave Johnson

结束语

类似这种大数据系统分析的工作有几个技巧值得去练习。能够通过不完整的数据进行快速评估是至关重要的。例如,谷歌拥有多少台服务器呢?(可以按照电力消耗来估算)。另一个很好的技能是能丢弃推理中那些有缺陷的思路,并及时对大脑中的想法进行刷新。Jeff Dean 有许多非常好的在线谈论包括“你应该知道的数字”以及如何考虑大型系统的设计。

可以在现有系统上进行约束条件分析,然后来查找答案,这对于掌握技能是个很好的方式。在本文中,我回避了那些有高更新速率或高一致性约束条件的案例。但你可以花一个小时左右的时间来分析一些类似的商业系统以增强了解,比如 2004 年左右时的 AdWords、2005 年时的 YouTube 或者 2005 年的 Flickr。关于这些系统都有一些很好的评论和讨论,而且是系统的创建者写的。但是建议你在独立的解答之前先不要看这些文章。

关于作者

Carlos Bueno数据库公司MemSQL 工作,之前他是Facebook、Yahoo 和几个初创公司的性能工程师。Carlos 写了一本计算机科学小说《 Lauren Ipsum 》,深受孩子们喜爱。他还是《 Mature Optimization 》的作者,这是一本 Facebook 性能分析的手册。

查看英文原文: Shaping Big Data Through Constraints Analysis

收藏

评论

微博

发表评论

注册/登录 InfoQ 发表评论