Tachyon在Spark中的作用（Tachyon: Reliable, Memory Speed Storage for Cluster Computing Frameworks 论文阅读翻译）

摘要：

Tachyon是一种分布式文件系统，能够借助集群计算框架使得数据以内存的速度进行共享。当今的缓存技术优化了read过程，可是，write过程由于须要容错机制，就须要通过网络或者是磁盘进行复制操作。Tachyon通过将“血统”技术引入到存储层进而消除了这个瓶颈。创建一个长期的以“血统机制”为基础的存储系统的关键挑战是失败情况发生的时候及时地进行数据恢复。Tachyon通过引入一种检查点的算法来解决问题，这样的方法保证了恢复过程的有限开销以及通过资源调度器下进行计算所须要的资源获取策略。我们的评审展示了Tachyon的write性能超过HDFS达到100X。也将现实工作流的端到端的负载提升了4X。

（补充）：

Tachyon是Spark生态系统内高速崛起的一个新项目。本质上。 Tachyon是个分布式的内存文件系统。它在减轻Spark内存压力的同一时候，也赋予了Spark内存高速大量数据读写的能力。Tachyon把内存存储的功能从Spark中分离出来，使Spark能够更专注计算的本身，以求通过更细的分工达到更高的运行效率。

Spark平台详细问题主要有下面几个：

当两个Spark作业须要共享数据时，必须通过写磁盘操作。比方：作业1要先把生成的数据写入HDFS，然后作业2再从HDFS把数据读出来。
在此，磁盘的读写可能造成性能瓶颈。
因为Spark会利用自身的JVM对数据进行缓存，当Spark程序崩溃时，JVM进程退出，所缓存数据也随之丢失。因此在工作重新启动时又须要从HDFS把数据再次读出。
当两个Spark作业需操作同样的数据时，每一个作业的JVM都须要缓存一份数据。不但造成资源浪费，也极易引发频繁的垃圾收集，造成性能的减少。

介绍：

尽管如今有非常多程序框架和存储系统用来改善大规模数据的并行处理性能。可是，这些系统的瓶颈都是I/O操作过程，眼下的解决方法是通过cache进行数据缓存。

可是随之而来的问题就出现了，cache能够显著改善read性能，可是由于容错的须要，必须通过节点之间的数据传递对“写的数据”进行复制备份。可是。由于节点之间数据复制的过程中网络的延迟以及吞吐率性能的低下，导致即使数据被复制存储在内存中。write过程的性能也非常差。

write性能低下会严重影响到job工作流的性能，由于job之间会彼此影响。

为了改善写性能，我们提出了Tachyon（一个基于内存的存储系统）来实现write和read的高吞吐率，同一时候没有牺牲容错机制。

Tachyon通过利用“血统“绕开了反复复制带来的吞吐率的局限性。採用的方法是通过再次对task之上的操作进行计算来恢复出错或者丢失的数据（跟Saprk的容错机制是一样的，仅仅是在Tachyon进行存储的阶段也是採用“血统”机制）而无需进行数据备份。

然而。将“血统机制”引入连续不断的分布式存储系统中也是有一定挑战的。

（1）第一个挑战是，怎样限制一个长期运行的存储系统的反复计算（容错操作）的开销。该挑战对于一个单一的计算job是不存在的。比方一个Mapreduce job或者是一个Spark job，由于在这样的情况下反复计算的时间被job的运行时间所限制。相反，Tachyon的运行过程是不确定的。这意味着反复计算的时间可能无法被限制。有一些框架比方Spark Streaming通过周期性（能够自己设置时间间隔）地设置检查点（checkpoint操作,设置checkpoint文件夹进行数据备份以及运行位置的标记）能够避开这个问题，但不幸的是，Tachyon中基本不能照做，由于存储层不能感知到job当前的运行语义。job的计算特性的分类也十分广泛复杂。

尤其是，当可用的带宽无法满足数据的写速度，固定时间间隔的检查点操作可能会导致无限制的数据恢复操作（由于job的运行情况是透明的。所以checkpoint设置的合理性至关重要）。相反，基于“血统图”进行数据检查点设置的选择反而能够对反复计算过程进行限制。

（2）第二个挑战是怎样为反复计算过程获取资源。

比方，假设job之间有优先级的话。Tachyon在一方面必须确保反复计算获取到足够的资源。在还有一方面，反复计算不能影响到当前具有高优先级的正在运行的job的性能。

解决上述挑战的方法：

（1）第一个挑战：Tachyon在后台通过异步运行某种算法不断的对对应文件设置检查点（文件信息备份）来解决第一个挑战。我们也提出了一个新鲜的算法来决定何时以及选择哪一个文件来检查，这个算法叫做边沿算法（Edge algorithm）。这样的算法对反复计算的开销进行了较好的限制。

（2）对于第二个挑战，Tachyon提供了一种资源申请方案，该方案能够做到：准守严格的job优先级并依照权重进行资源分配。

论文终于得到的结论是：Tachyon的write性能超过HDFS达到100X。也将现实工作流的端到端的负载提升了4X（相对基于内存的HDFS）。另外，Tachyon能够将复制备份引起的网络传输降低高达50%。

最后，基于对Facebook和Bing的跟踪。能够发现Tachyon的反复计算开销占用的集群资源不超过1.6%。

更为重要的是，因为复制备份操作的固有带宽限制。未来。一个基于“血统”的容错模型可能是让集群存储系统可以匹配内存计算的唯一方法。

背景：

（待改善的）目标的工作负载属性

数据的不变性。数据一旦进行write就不可变了，存储系统仅仅是提供数据之上的扩展操作。
确定性的工作任务。MapReduce和Spark等框架都要求用户代码确定的情况下运行“血统”机制。
对于工作任务不具有确定性的框架。就採用复制备份进行容错处理。
基于位置的调度。MapReduce和Spark等框架都是基于位置进行调度的，这样能够尽可能地降低网络传输的开销。
应用的工作区必须在内存，数据能够在磁盘。
尽量进行程序操作的复制，而尽量避免数据的复制。由于操作的复制开销要更小。
（比方：同样的操作在大量数据之上重复被运行，代码书写的过程中，要选择让操作程序进行多次复制，而不是让数据进行复制）

避免复制操作（避免memory与其它媒介进行数据交换）的情景

一些基于内存的计算框架比如Spark确实加速了一些特定job的运行速度。可是，不同种类的job之间可靠的数据共享却成为瓶颈。

从上图能够看出，如今主流系统使用的媒介，HDD、SDD以及网络传输所支持的带宽都远远小于内存支持的带宽。

大数据处理过程中的数据共享开销往往会主导流水线端到端的时延。

现实中的数据表明有34%的job，其输出的数据量至少等于输入的数据量，在集群计算的过程中。这些job就会限制write的吞吐率。

硬件的改进无法解决上述问题。

一个节点之上，内存的带宽比disk整体带宽要高出1~3个数量级。

SDD的出现也没有太大作用，毕竟它相对磁盘的主要优势是随机訪问的性能提升。而不是连续的I/O带宽的提升（表中可见）。后者才是关键。

设计综述：

系统架构

Tachyon由两层组成：“血统”和持久化存储。

“血统”层级提供非常高的I/O吞吐率而且会追踪job运行的连续过程。持久化层主要被用于异步检查，持久化层能够是不论什么以数据备份为基础的存储系统，HDFS，S3等。

Tachyon採用了标准的master/slave架构：为了管理元数据。master必须包括一个workflow manager，该管理器的作用就是跟踪“血统”信息，计算检查点操作的顺序（相应第一个挑战）以及与集群资源管理器进行交互来为又一次计算申请资源（第二个挑战）。

每个worker上都跑着一个守护进程用来管理本地资源而且定期将worker状态报告给master节点。另外，每个worker节点都会用RAMdisk来存储内存映像文件。用户的应用能够绕过守护进程直接和RAMdisk进行交互，这样，一个具有数据本地性的应用能够避免不必要的数据拷贝，以内存速度进行数据交互。【内存文件管理系统】

举例

须要注意的是，“血统”信息是存储在Tachyon的持久化层的。

我们都知道。Tachyon会通过避免复制备份来改善write性能。然而。复制备份对于非常多job同一时候read读取同样的数据的情况有明显的优化作用。尽管，Tachyon使用“血统”机制避免了数据的复制备份。可是Tachyon并非全然没有数据备份的。

Tachyon也使用clientcache技术来对频繁读取操作的情况进行优化：当一个文件不在当前机器时，该文件会被从远程机器上读取过来而且缓存在Tachyon本地的cache里面，这是Tachyon中的数据备份现象。

API总结

须要特别说明的是。Tachyon本身就是一个标准的文件管理系统。支持全部标准的文件管理操作，除此之外还提供了获取job操作过程的“血统”信息的API接口。而且，使用者假设只将Tachyon作为传统的文件管理系统来用，而不使用Tachyon的“血统”的API接口，这样的情况下。write性能将不会得到改善，读写性能与其它文件系统比方HDFS差点儿相同。

Lineage Overhead（“血统”开销）

从存储的方面来说，“血统”信息被累积存储在二进制文件其中，可是，依据微软的数据统计：一个典型的数据中心平均每天运行1000个job，而且花费1TB大小的容量来存储一年下来全部job运行生成的未压缩的二进制文件，这种数据量对于一个非常小的数据中心来说都是微不足道的。

此外，Tachyon会对“血统”信息进行回收。

Tachyon在检查完输出文件之后会删除“血统”记录。这样会明显降低“血统”信息的大小。另外，在运行的过程中，那些定期运行的job任务一般会变换參数多次运行，在这样的情况下。仅仅有一份程序的拷贝会被存储。

Data Eviction（数据回收）

当数据量不超过内存大小的时候，Tachyon的运行性能非常好，所以，问题就出现了：当内存占满的时候，数据怎样回收呢？（有些数据使用率太低，须要移除内存，或者说从内存中删除）对于那些数据密集型的应用，我们在数据回收的时候考虑下面两个因素：

（1）訪问频率

（2）訪问的暂时本地性（75%的二次訪问都发生在6个小时之内）

在上述特性的影响下。我们使用LRU（最近最少使用算法）作为默认的数据回收策略。当然LRU不一定适用于全部场景。所以Tachyon同一时候也支持其它的数据回收策略。

在下一个张章节中。我们会给出这种描写叙述：Tachyon会将最大的文件除外的全部文件存储在内存中，大的文件直接存储在持久层。（就是spill过程）

Master Fault-Tolerance

Tachyon通过master的备用节点进行master的容错处理。主master将自身每一步的操作以日志的形式都持久化存储在持久层之中。当主master节点出错的时候。备用节点通过读取日志（日志的大小微不足道）将自身改变成为与之前的master一样的状态。

Handling Environment Changes

另一类问题Tachyon会遇到，就是假设框架的版本号变了或者是系统版本号变了我们怎样通过“血统”信息的二进制文件来支持重计算进而恢复文件数据。

（1）我们发现，系统变化之后。能够通过之前设置的检查点进行计算恢复操作。

因此。在计算环境改变之前。我们须要做一些工作：

a）全部当前未复制的文件都被设置检查点（备份）。

b）全部的新数据都被同步保存

当然。除了上述操作。我们能够直接简单地将全部数据进行复制就可以。

（2）另一种方法来更加高效地处理这样的情况，用虚拟机映像单独保存所需的计算环境（不做介绍）。

Why Storage Layer（为什么选择存储层）

选择将“血统”机制引入存储层的原因：

（1）多个job在流水线中会形成复杂的“血统”关系；并且，在一个生产环境中，数据的生产者和消费者可能会在不同的框架以下（一个job过程能够会涉及到多个框架之间的交互）。并且。只在job级别或者是框架级别理解“血统”关系并没有什么卵用，我们应该深入到存储层对“血统”信息进行统计。

（2）一些信息仅仅有存储层知道，比方什么时候文件重命名了或者什么时候文件被删除了，在存储层构建的“血统”才是最准确的。

检查点：

该部分事实上是对Tachyon第一个挑战的解决说明。

Tachyon利用checkpoint算法来限制由于出错导致的文件恢复的时间开销。

不像MapReduce或Spark的job那样。生命周期非常短，Tachyon的job的生命周期非常长，也正由于“血统”信息的复杂，假设没有检查点的设置，那么会须要非常长的时间来运行重计算（血统过于复杂）。

还有就是持续运行的像Spark Streaming这种数据流系统，会获取到当前运行的job的动作语义来决定在那些文件上以及何时进行检查点操作。

Tachyon无法获取到job详细的语义动作，可是也要进行检查点的设置。

Tachyon的检查点设置的关键是”血统“同意后台以内存的速度异步运行检查点操作而不用停止写操作，且Tachyon后台的检查点操作具有非常低的优先级。目的是避免影响当前存在的job任务。

理想的checkpoint算法须要满足一下几点：

（1）限制重计算的时间。像Tachyon这样长时间运行的系统。形成的”血统“链也非常长，所以对于失败情况下的重计算操作的耗时要加以限制，须要注意的是，一旦我们限制了重计算的时间就意味着我们须要限制重计算所需的资源。

（2）为”热“文件进行检查点操作

（3）尽量避免为暂时文件进行检查点操作

Edge Algorithm

基于上述特性，我们设计了Edge算法：

首先。Edge将要检查的文件选择的是”血统“图的叶子（边沿）文件；

其次，Edge会结合文件的优先级进行检查点操作，即优先为优先级高的文件设置检查点。

最后，Edge会将能够放入内存的数据集进行内存缓存，那些太大的文件会直接存储在持久层，假设非常大的文件也存储在内存，须要进行checkpoint的时候，就会出现内存与磁盘的数据交换。

目的就是避免同步设置检查点将write的速度减少到磁盘的速度。接下来依次进行分析。

Checkpointing Leaves

Edge算法用DAG表示文件之间的关系，当中，文件是节点，文件之间的关系（B是某job read A之后生成的）形成DAG图的边（A-B）。

这样的算法对DAG图的叶子（边沿）节点进行检查点操作。例如以下图：

上图表示了Edge算法的工作过程。一開始。集群中仅仅有两个job在执行，并生成了A1，B1。Edge算法对A1。B1进行了检查点操作（备份），之后的阶段，A3，B4，B5，B6成为了叶子。并依次被进行检查点操作，之后阶段。A6，B9成为叶子。假设在A6进行检查点操作的时候出现了错误，Tachyon仅仅须要对A4~A6的过程进行又一次计算。

Checkpointing Hot Files

Tachyon分配优先级的策略是基于的是文件被读取的次数，与cache回收的LFU（近期最不经常使用页面置换算法）类似。保证了最频繁被获取的数据最先被进行checkpoint操作，这样显然能够加快数据恢复速度（容错处理）。

Edge算法必须平衡叶子节点和优先级高的节点的checkpoint的操作。

我们通过下表进行分析。

该表展示了来自雅虎的3000个节点的mapreduce集群的文件使用次数统计。基于这个表，我们觉得仅仅要文件的訪问次数查过2次，该文件就属于高优先级的文件。且基于该数据统计，发现86%的checkpointed文件都是叶子节点。因此。我们能够得到这种结论：优先级高的文件最先被运行checkpoint操作（优先级高的文件本身就少。大概仅仅有14%，可是仍然在checkpointed文件里占领14%的比例）。

一个以复制备份为基础的文件系统必须复制每个文件，即使是job直接使用到的暂时文件（也须要进行备份）。

可是Tachyon非常对会对暂时文件进行checkpoint（备份）操作，由于checkpoint操作针对的数据都比較靠后（叶子文件、优先级较高的文件），这样就使得暂时文件在被运行checkpoint操作之前就会被删除掉（nice啊。）。

Dealing with Large Data Sets（大型数据集的处理）

job过程中除了非常大的文件之外的差点儿全部文件都被存储在内存中。

由于96%的活跃jobs能够同一时候将自己的整个数据集保存在集群的内存中去。同一时候Tachyon的master节点配置为能够同步地将上述数据集一次性写入磁盘。

须要注意的是。系统框架可能会遇到高丛发性（爆发性）的数据请求，在请求爆发期间。Edge算法会将内存中差点儿全部的叶子节点以及非叶子节点都进行checkpoint处理（爆发性的数据请求会提升非叶子节点优先级，终于导致差点儿全部的文件都checkpoint）。

假设内存中的文件都是没有被运行checkpoint的（特殊情况），那么Tachyon会同一时候对这些文件进行checkpoint操作来避免产生较长的”血统“链。

Bounded Recovery Time

我们将对DAG图上特定叶子文件i上运行checkpoint操作所花费的时间用Wi表示。将通过祖先转换成叶子文件i的操作过程所花费的时间表示成Gi，能够得到：

定理一：Edge算法能够保证不论什么文件（错误发生）在3*M的时间被恢复。当中，M=maxi{Ti}，Ti=max(Wi, Gi).

上述定理表明，反复计算与DAG图的深度是无关的（当数据集在内存中的时候。cache的表如今反复计算的过程中是一样的）。

上述对反复计算限制的定理无法应用到checkpoint算法对优先级的考虑因素中去。可是我们能够非常easy地得到优先级下checkpoint操作对反复计算的限制：假设对叶子文件进行checkpoint的时间花费是c（在总的反复计算的时间中占用的比例），那么，优先级的checkpoint操作占用的时间就是1-c。

推论二：已知。对叶子文件进行checkpoint的时间花费是c（在总的反复计算的时间中占用的比例）。Edge算法能够保证不论什么文件（错误发生）在(3*M)/c的时间被恢复，当中，M=maxi{Ti}，Ti=max(Wi, Gi).

Resource Allocation资源申请

该部分事实上是对Tachyon第二个挑战的解决说明。

尽管Edge算法已经对重计算进行了限制，Tachyon还须要一种资源分配策略用于调度job的重计算。此外，Tachyon还必须遵守集群汇总现有的资源分配策略，比方均分或者是依照优先级分配。

在非常多情况下会有空暇的资源能够用于重计算，由于大部分计算中心计算资源的利用率唯独30%~50%。当集群资源用完的时候。就须要考虑到相关的资源的分配问题。举一个样例，假如一个集群资源被三个job J1，J2。J3占领，同一时候有两个丢失的文件F1，F2，须要运行 R1，R2两个job进行再计算才干够恢复。

J2只须要F2。Tachyon怎么在考虑优先级的情况下安排重计算过程？

Tachyon的一个解决方式是进行集群资源的静态分配，比方将集群资源的25%分配给重计算过程。

非常显然。假设没有重计算任务这样的方法限制了集群的利用率。另外，採用静态资源分配的策略。就会出现非常多因素的影响，比方。上述情况，假设更高优先级的jobJ3须要文件F2，Tachyon应该怎样调整R2的优先级呢？因此，我们须要明白三个目标：

（1）优先级的配合度。假设一个低优先级的job须要文件。针对该过程的重计算过程应该尽可能小地影响更高优先级的job。

可是，假设该文件后来被一个更高优先级的job所须要。用于运行数据恢复工作的job的优先级应该提升。（也就是说文件的恢复job的优先级会随着获取文件的job的优先级来决定）

（2）资源共享。没有重计算任务。集群就运行正常任务（不是静态资源分配）。

（3）避免重计算的串联操作。

出错情况发生的时候，同一时候可能不仅仅是一个文件会发生丢失，假设不考虑数据的依赖关系就对这些文件进行重计算可能会引起递归的重计算job的产生。

我们现提出能够满足前两个目标的策略，再来讨论怎样实现最后一个目标。

Resource Allocation Strategy

资源申请策略依赖于Tachyon所使用的调度方法。

Priority Based Scheduler

在优先级的调度器中，举一个类似的样例。假如一个集群资源被三个job J1。J2。J3占领，三个job各自的优先级是P1，P2，P3。

方法是，默认情况下全部的重计算job都仅仅有最低的优先级。所以他们对其它的job有最低限度的影响。然而。这样会导致“优先级反转”：比如。文件F2的重计算job R2比J2有更低的优先级。此时当J2占用集群中全部的优先级的时候对F2文件进行获取。R2是得不到运行资源的。J2由于得不到F2也会因此被堵塞。

我们通过优先级的继承关系来解决。当J2获取F2的时候。Tachyon添加R2的优先级到P2。当J3获取F2的时候，再将R2的优先级升至P3。例如以下图所看到的：

Fair Sharing Based Scheduler

在共享调度中。J1，J2，J3各自分享W1，W1。W3的资源（最小的分享单位是1）。

在我们的解决方法中，重计算的jobs一起共享分配的资源。被Tachyon分配好的的默认的资源Wr。当发生错误的时候，全部丢失文件的重计算job能够共享到Wr中的“1个资源”。

此时，当一个job须要上述丢失的文件的时候，请求数据的job的一部分资源会被转移到那些针对这些文件的重计算job上去。比方，当J2须要F2的时候，J2会分到（1-a）*W1的资源，而R2会分到a*W1的资源。

例如以下图所看到的；

上述的方法满足了我们的目标。

由于重计算的job的资源来自须要该缺失文件的job，所以，该过程不会对其它正常的job产生影响。

Recomputation Order

假设运行重计算的过程中没有对重计算的操作限定顺序，那么程序递归地对丢失的文件调用重计算操作就会有非常低的性能。比方，假设job的优先级非常低的话，该job非常一直等待资源。假设改job的优先级非常高。那么针对一个将来注定丢失的文件的前期计算就显得徒劳无功了。所以工作流管理器提前决定好文件重计算的顺序进而能够对他们进行调度。

为了决定哪些文件须要进行重计算。工作流管理器维护了一个DAG图。DAG图中的每个节点代表一个须要进行恢复的文件。在这个DAG图中，存在窄依赖和宽依赖（概念和Spark的一致）。这些依赖关系形成的DAG图是总的DAG图的子图。

为了构建这种DAG图，工作管理器会对目标文件进行DFS，假设当前文件节点在存储层可用的时候，DFS过程会停止。

DFS訪问到的节点必须是须要被重计算的。DAG图中的节点的计算顺序是逆序的，就是说。仅仅有孩子节点都变为可用的时候当前节点才干够開始计算。

上述计算过程是资源管理器运行的。

Implementation（实现）

Tachyon使用已经存在的存储系统来作为自己的持久化层。且Tachyon还使用 Apache ZooKeeper来主导master的错误容忍。

Lineage Metadata

（1）Ordered input ﬁles list

由于文件名称可能会发生变化，可是每一个文件在顺序表中都有一个独特的不可变的文件ID，这样就能够保证应用在将来可能会出现重计算的情况，假设发生的话，重计算的时候就能依照程序第一次运行时候的顺序来读取同样的文件进行兴许操作。

（2）Ordered output ﬁles list

该列表与 input ﬁles list原理一样。

（3）Binary program for recomputation

非常多种方法实现一个重计算程序。

一种天真的方法是为每个应用写一个有针对性的程序。一个略微有点素质的程序猿都不会这样做的。

还有一种方法是写一个类似于“装饰器”的程序，该程序既能“读懂”Tachyon的“血统”信息，又能理解应用的逻辑关系。尽管这种程序貌似非常灵活。可是也仅仅能在一些特殊的框架（兼容这种“装饰器”）下实现。

（4）Program conﬁguration

关于所需的配置文件，Tachyon使用“装饰器”程序读取配置文件：在“血统”提交的时候使用”装饰器“对配置文件进行序列化，之后在重计算阶段解序列化。

（5）Dependency type

宽依赖和窄依赖。

Framework Integration（框架整合）

程序执行的过程中，在它写文件之前会将一些信息提交给Tachyon，然后，当程序写文件的时候，Tachyon会推断该文件是否在”血统“之中，假设在。该文件就能够被写入内存（说明要採用”血统“机制进行容错处理）。

假设文件须要进行重计算。Tachyon会使用之前的”装饰器“程序将文件的”血统“信息以及丢失的文件列表提交给重计算程序来又一次生成相关的数据。

Recomputation Granularity（粒度）

关于重计算的粒度选择问题。

首先，我们能够选择的粒度是job。比方。一个map job产生了10个文件。可是有一个文件丢失了，对于job级别的恢复。Tachyon会恢复10个文件。其次，假设我们选择的粒度是task，这样。运行过程会变得复杂，可是效率会提升非常多。MapReduce和Spark的层级是task级别的。

Evaluation

基础平台：

Amazon EC2 cluster with 10 Gbps Ethernet. Each node had 32 cores, 244GB RAM, and 240GB of SSD. We used Hadoop (2.3.0) and Spark (0.9).

（1）Tachyon

（2）in-memory installation of Hadoop’s HDFS (over RAMFS), which we dub MemHDFS. MemHDFS的writes操作的重计算数据的恢复仍旧会借助network，可是没有了disk的性能限制。

比較结果例如以下：

性能：

Tachyon的write速度比MemHDFS快100X；
对于 multi-job workﬂow而言Tachyon的处理速度是MemHDFS的4X；在出错的情况下。大约花费了1分钟的时间进行数据库的恢复。Tachyon要比快3.8X。
Tachyon帮助基于内存的框架，通过将虚拟机存储转移至堆外内存（直接受操作系统管理）来改善的延迟。
Tachyon恢复master的失败只须要不到1秒。

异步检查点的设置：

Edge算法超过不论什么固定间隔的检查点设置方法，分析表明Tachyon能够将数据复制备份引起的网络交互降至50%。

重计算的影响：

重计算对其它的job差点儿没有影响；另外。通过对Facebook和Bing的跟踪。重计算对集群资源的消耗不会超过1.6%。

接下来是详细的性能比較过程。

性能

Raw Performance

实验中。集群中的每个节点会开启32个进程，每个进程读/写1GB的数据。结果例如以下图：

对于写而言，Tachyon实现了15GB/sec/node的吞吐率。

然而，虽然使用的是10Gbps的带宽。MemHDFS的写吞吐率仅仅有0.14GB/sec/node，原因就是因为须要数据备份带来的网络瓶颈。我们同一时候能够看出，理论上在硬件之上採用一次备份的最大的性能也仅仅有 0.5GB/sec/node。平均来看，Tachyon的write速度比MemHDFS快100X。而理论上以复制为基础的write速度极限是MemHDFS的30X。

对于读而言。Tachyon实现了38GB/sec/node。我们通过增加cache缓存以及 short-circuit reads（数据的本地性）的方法优化了HDFS读性能。可是MemHDFS也只实现了17 GB/sec/node的速度。

像这样速度上2倍的差距的原因就是，HDFS API由于调用了java I/O streams 仍然须要额外的内存数据备份。

另外，Tachyon读的性能要好于写的性能，由于硬件的设计为read留了很多其它带宽。

Realistic Workﬂow

实验中我们測试Tachyon的工作流是基于一个媒体信息分析公司在一小时内运行较多job来进行的。

包括周期性的提取、转换、载入（ETL过程：用来描写叙述将数据从来源端经过抽取（extract）、转换（transform）、载入（load）至目的端的过程。）过程以及针对job进行測量的相关报告。

实验执行的环境是拥有30个节点的EC2（亚马逊弹性计算云）集群上面。整个工作流分为20批次的作业，共包括240个job（当中每一个批次有8个Spark job以及4个MapReduce job）。每批作业读1TB的数据并产生500GB的数据。我们使用Spark的Grep job来仿真ETL应用，用MapReduce的WordCount来仿真測试分析的应用。且每批次的作业，我们执行两个Grep应用来提前处理数据，之后我们执行WordCount作业来读取处理之后的数据并计算终于的结果，得到终于结果之后，数据就会被删掉。

我们測量了Tachyon以及MemHDFS上面执行的工作流的端到端的延迟。为了模仿真实的场景，元数据一旦写入系统我们就開始进行測量。对Tachyon而言，我们还測量了一个node失败的时间消耗。

上图展示了相关性能：

能够看出Tachyon上的运行时间大约为16.6min，而MemHDFS则用时67min。

加速比大约为4倍关系。当Tachyon上发生失败情况的时候，时间也只多耗费了1min。加速比仍旧有3.8倍。

对Tachyon而言，基本的负载是序列化和反序列化（空间开销和时间开销）。这个实验使用的是 Hadoop TextInputFormat（主要用于描写叙述输入数据的格式,功能：数据切分和为Mapper提供输入数据）。假设使用更加高效的序列化模式。性能会有所提升。

Overhead in Single Job（单个job的负载）

当我们执行一个单独的job的时候，能够发现Tachyon能带来更小的负载而且能够通过降低无用的负载来改善内存框架的性能。

我们使用Spark的一个worker节点（不要Tachyon）来执行Word Count job。通过两种方式进行缓存，一种是解序列化的java对象，一种是序列化的字节数组。

相比較使用Tachyon进行缓存，当数据量小的时候。两者是类似的。

当数据量变大的时候，Tachyon更快，由于Tachyon避免了使用java的内存管理机制。Spark1.0.0已经将Tachyon作为默认的堆外存储方法。

Master Fault Tolerance

Tachyon使用热门线路备份（之前的等待master节点）来实现更快的master节点恢复。时延发现热门线路备份能够在0.5s之内代替当前出错的master节点，且在标准误差0.1s之内。

上述实现的性能是可能的。由于代替的过程是备用master不断通过当前master的日志文件数据来获取更新自己的数据信息。

Asynchronous Checkpointing（异步检查点的设置）

Edge Checkpointing Algorithm

我们通过比較Edge算法和固定时间间隔的检查点设置的算法来终于对Edge算法进行评估。我们用100个jobs模拟一个迭代的工作流，整个过程的运行时间遵从高斯分布（正态分布），平均来看每一个job用时为10s。

每一个job的数据输出过程（write）都须要固定的15s的总时间来进行检查点的设置。操作过程中，随意时刻node都可能出错。

从上图能够看出。Edge算法优于固定时间间隔的算法。

对固定时间间隔的策略而言，假设时间间隔设置的太小，检查点的设置就跟不上程序运行速度。

假设时间间隔设置太大，检查点的设置间隔时间就会非常长，数据恢复时间就会受到影响。而且，即使採用最优的固定时间间隔方法，性能也比不上Edge算法，由于Edge算法能够依据程序运行的过程以及状态进行检查点设置的时间间隔的调整。

Network Trafﬁc Reduction

那些採用数据复制进行容错的文件系统在数据密集型的集群中差点儿占用了一半的网络通信。

Tachyon能够降低通信的消耗，原因是Tachyon在异步的检查点设置的过程中能够避免对那些会被删除的暂时文件进行检查点的设置。

带宽节省下来了，性能自然会提升。

分析例如以下：

（1）T表示job运行的时间与对job输出的数据进行检查点设置的时间（网络带宽）的比例。比方，測试一个Spark Grep程序，得到T=4.5，说明job执行的速度是网络带宽的4.5倍。事实上，T值的大小主要取决于网络带宽或者说是I/O。

（2）X表示生成数据的job的百分比。

（3）Y表示读取前面job的输出数据（组建“血统”）的job的百分比。假设Y=100。则会形成一个“血统”链，假设Y是0。则“血统”的深度就是1。

因此，我们尝试着将X置为60。将Y置为84，并使用Edge算法来模拟1000个jobs的运行过程。取决于T，通过复制备份操作之后保存下来的网络通信的百分比的情况：当T=4是40%，当T>=10的时候是50%。

（也就是说，X和Y固定的情况下，检查点设置操作的带框越小，T越大。表示网络通信越快 ----Tachyon）

Recomputation Impact

Recomputation Resource Consumption（消耗）

我们会通过计算模型以及对FaceBook和Bing的追踪来计算重计算过程所需的资源。

我们的分析建立在以下的如果之上：

（1）每一个机器的平均失效时间是3年。且假设一个集群包括1000个节点，平均每天会有一个节点出现失败的情况。

（2）能够负担的检查点设置的吞吐率是200MB/s/node。

（3）资源消耗用机器时间（machine-hours）来測量。

（4）分析的过程中。觉得Tachyon只在job级别，使用粗粒度的重计算在最差的情况下进行測试（不用支持细粒度的task级别的重计算）

Worst-case analysis

最坏的情况下，一个节点出错，且其内存中的数据都是没有设置检查点的，须要task用超过200MB/sec的速度进行数据的再生。假设一个机器拥有128GB的内存，那么须要655秒的时间重计算丢失的数据。即使数据是连续存放的，其它的机器在这个过程都是堵塞的，由于这些机器都是须要根据这些数据进行并行计算的。在上述情况下。重计算过程占用了集群执行时间的0.7%。

上述的开销是与集群的大小和内存的大下呈线性关系的，假设集群有5000个节点，每一个节点有1TB的内存，重计算的开销能够达到集群资源的30%。

Real traces

现实的工作流程中。Tachyon的重计算的开销要远远小于上述最差的情况。由于job之间是独立的。差点儿不会影响整个集群，因此一个节点失败不会堵塞其它的节点。

上图依据对FaceBook和Bing的追踪来比較不同内存和不同节点数的集群资源占用情况，能够看出正常情况下Tachyon的性能。

Related Work

Distributed Storage Systems

在大数据分析中，分布式文件系统以及key/value存储系统都是通过将数据拷贝到不同的节点进行容错处理的。这些系统write的吞吐率是受到网络带宽的限制的。

无论这些系统怎样优化。他们的吞吐率与内存的吞吐率相比都查的非常远。

Tachyon在存储层使用“血统”的概念来避开复制备份的操作，且利用内存进行单一的存储来提升性能。 Apache HDFS社区考虑将“血统”引入系统中，此灵感也是来自于Tachyon。

【补充】Batch-Aware Distributed File System（BAD-FS）。该类型的系统有两部分组成：

（1）storage层expose了诸如caching、consistency、replication等通常固定的控制策略；

（2）scheduler层使用这些控制来适应不同的工作流，这样可以针对特定的工作流来处理比如cache consistency、fault tolerance、space management等问题，使存储和计算协调一致。

BAD-FS将传统文件系统的各种控制从File system转到了scheduler。这种优点是：提高性能。优化错误处理；简化实现。

[BAD-FS]为存储过程单独提供了一个调度器，提供额外的控制作用。

用户通过说明式的语言将jobs提交给调度器，系统也因此知道了jobs之间的“血统”关系。然而。为了让上述过程在并行大数据引擎上面成为现实。有两个主要的问题：

（1）确保调度器和存储层之间的交互是正确的，比方避免死锁或者是优先级反转情况的出现。

（2）限制重计算的时间

对于第一个问题（相应论文開始的资源申请的挑战），我们会提供避免死锁或者是优先级反转的机制。同一时候也会考虑到调度器的策略。对于第二个问题（相应论文開始的限制重计算时间的挑战）。我们会提供异步的检查点设置算法，该算法利用“血统图”在后台不停地运行检查点设置来确保优先的恢复时间。

Cluster Computation Frameworks

Spark在一个单独job的执行过程中使用“血统”信息，且执行在一个单独的JVM里面。Spark中不同的不同种类的查询无法用一个稳定且高吞吐率的方法来共享数据集（RDD），由于Spark是一个计算框架。而不是一个存储系统。我们通过将Tachyon与Spark进行集成，通过进行稳定的数据集共享充分改善了Spark jobs的工作流程处理性能。而且，Spark在Tachyon的异步检查点设置的过程中也会受益。由于它实现了高吞吐率的write过程。

其它的系统比方MapReduce和Dryad（微软的分布式运算框架）也会在一个job的运行过程中跟踪task的“血统”信息。可是这些系统不像Spark能够整合Tachyon。他们无法跟踪文件之间的关系。也因此无法在不同的job之间提供高吞吐率的数据共享。

Caching Systems

【补充】DryadLINQ是一个把LINQ程序（LINQ即Language Integrated Query(语言集成查询)，LINQ是集成到C#和Visual Basic.NET这些语言中用于提供查询数据能力的一个新特性）转化成分布式计算指令，以便执行于PC集群的编译器。

[Nectar]类似Tachyon，Nectar也会使用“血统”的概念，可是。Nectar只服务于特定的程序框架DryadLINQ。而且整合于传统的，复制的文件系统中。Nectar是一个数据复用系统，服务于DryadLINQ查询操作，目标是节省空间且避免多余计算。

（1）节省空间：删除大量无用文件，假设须要再次使用，就会又一次执行产生这些文件的job。可是数据的恢复过程是没有时间限制的。

（2）避免多余计算：标示不同程序里面比較普遍的代码块进而找到那些经过同样计算得到的文件，加以反复利用。作为对照，Tachyon的目标是通过不同的基于内存的以及有限的数据恢复时间的框架来提供数据共享。

[PACMan]是一个基于内存的缓存系统。适用于数据密集型的并行工作。

该系统探索了不同的策略，目的是让数据仓库的缓存效率更加高效。

然而。PACMan没有改善write的性能。也没有改善第一次read的性能。

Lineage

除了上述领域，“血统”已经被应用在非常多其它的领域其中了。比方科学计算、数据库、分布式计算等等，也被应用在提供历史数据的应用中。

Tachyon在不同的环境下使用“血统”来实现内存速度的读写吞吐率。

Checkpoint Research

检查点的设置已经成为了一个非常值得的研究领域。大多数的研究是在当失败情况发生的时候怎样将又一次计算的开销最小化。可是。不像之前使用同步的检查点设置的那些work操作。Tachyon会在后台进行异步的检查点设置。这种话就算一个检查点设置操作没有完毕。也能够通过“血统”来进行丢失数据的重计算。

Limitations and Future Work

Tachyon致力于改善其目标工作多负载的性能。且评估也展示出了令人欣喜的结果。可是我们也从中意识到了Tachyon的局限性，比方CPU密集型或者是网络密集型的jobs的处理。

另外，另一些将来要面临的挑战：

（1）Random Access Abstractions（随机訪问抽象）

执行jobs的数据密集型的应用会向像Tachyon这种存储系统输出文件。通常，这些文件会被DBMS进行再加工来让面向用户的应用使用这些数据。因此。Tachyon提供高层次的仅仅读随机訪问抽象，比方在已有的文件之上提供key/value接口，能够缩短数据管道而且让数据密集型的jobs输出的数据马上变为可用的数据。

（2）Mutable data（可变的数据）

“血统”一般无法进行高效率的细粒度的随机訪问更新也是挑战之中的一个。可是针对这个问题有非常多的方向，比方定向更新一集批量更新。

（3）Multi-tenancy（多重租赁）

对于Tachyon而言，内存公平共享是重要的研究方向。像LRU/LFU这些策略能够提供好的总体性能，可是要以对每个用户进行隔离操作为代价。另外，安全也是处理过程的另外一个有趣的问题。

（4）Hierarchical（分等级） storage

尽管内存的容量每年都是以置数形式增长的。可是相对于内存的替代品而言还是非常昂贵的。

一个早期的Tachyon研究者表示，除了要使用内存这一层级。Tachyon也应该使用NVRAM（非易失随机存取存储器）和SSDs。

将来。我们将会研究怎样在Tachyon中支持层级存储。

（5）Checkpoint Algorithm Optimizations

我们已经提出了Edge算法来提供一个受限的重计算时间。然而。也会有其它的技术考虑到不同的度量标准。比方检查点设置开销，单个文件恢复开销，多有文件恢复开销等。我们将这些改进留给社区来进一步探索。

Conclusion

随着以数据为中心的工作负载開始存在于内存，write的吞吐率就成为了应用的主要瓶颈。因此，我们觉得以“血统”为基础的数据恢复的方法也许是唯一实现集群储存系统加速内存吞吐率的方法。

我们提出了Tachyon，一个基于内存的存储系统，该系统引进了“血统”来加速由决定性的批量jobs组成的工作负载的关键部分的处理。在让Tachyon有实际用途的过程中。我们定位并攻克了一些关键的挑战。

我们的评估展示了Tachyon在眼下的存储方案上提供了可靠的加速。相似的方法也被HDFS社区採纳以便在集群中高效地利用内存。Tachyon眼下已经开源。