获得log的原始数据，用时序关系为边的自动机构造workflow图，获得workflow的异常。难点在于异步和并发带来的interleaved。 通过fork和join解决异步、通过标识符集解决并行问题。
Intro
CloudSeer主要解决以下几个challenges
处理interleaved logs： 当云基础设施并行地执行多个任务时，来自不同执行的日志信息通常在日志文件中交错出现。 即使在单一的执行中，不同服务之间的异步操作也会以不同的方式交织日志信息。 为了恢复工作流信息，有必要确定日志信息和任务执行之间的对应关系，但这并不简单。
在线监测
检测没有明确错误信息的问题： 执行问题可以以不同的形式表现出来。其中一些可能不容易被注意到，例如，性能下降和没有明确错误信息的无声故障
提供工作流程信息： 作为一种监控方法，仅仅报告一个故障是不够的，管理员还需要诊断故障并采取进一步的行动。 failure的上下文，特别是工作流，对于指导管理员缩小和隔离可能的原因是非常有用的。监控方法应该利用日志信息，在故障报告中包含这些信息。
Overview
Cloud-Infrastructure Example: OpenStack
描述了Openstack是如何启动VM的
Logging Characteristics
我们意识到有两个日志特征使得基于日志的工作流监控并不直接。
首先，除了由同步任务执行引起的消息交错，来自同一执行的日志消息也可能是交错的。这是由异步操作引起的，它通过不同的服务进程创建了多个执行路径。 因此，来自不同路径的日志信息可能交错在一起，没有固定的顺序，使得任务工作流的监控更加复杂。
第二，与任务执行相关的日志信息通常没有单一和独特的标识符。 在云基础设施中，每个服务都管理着自己的资源（例如，用户、虚拟机和图像由不同的服务管理），并根据资源类型用标识符记录它们。 在任务执行期间，这些标识符可能不会在不同的服务之间传播，因为不同的服务不会分享关于不同资源的知识。
Demonstration of CloudSeer
CloudSeer的主要思路包括三个阶段
- The Task Automaton：根据log template建立自动机。为了解决异步问题，增加fork和join两种特殊节点
- Checking Interleaved Sequence：对同一个自动机，可能存在并行运行。为此，通过标识符集来区分并行运行的自动机的状态。
- Interpreting Results：当传入的消息（或缺乏消息）满足分歧标准时，CloudSeer能够报告分歧的自动机实例，表明有问题的执行。
Modeling Task-Based Log Sequences
离线建模过程从正确的任务执行所产生的日志中创建自动机。 对于每个要建模的任务，建模过程从该任务的多次执行中获取日志序列。建模过程包括以下三个步骤。
Preprocessing
使用正则表达式提取信息，并通过出现次数从循环、条件选择和周期性的背景任务中删除了不规则的日志信息。
Mining Temporal Dependencies
为了获得时序关系，定义了两种关系：strong和weak。前者是a总发生在b前面，且中间没东西，后者是a发生在b前面，但是中间可能插了一些东西。
为了获得时序关系，主要就是简单的三步：枚举所有对、获得满足strong/weak的对、迭代。
Constructing Automata
根据上一步构建自动机。
Checking Interleaved Log Sequences
在在线检查阶段，CloudSeer使用之前离线建模阶段的任务自动机来检查叶间的日志序列。 这个检查阶段的输入和输出如下。CloudSeer每次从日志流中获取一条日志消息。输入的消息属于正在生成的一些交错的日志序列中的一个。 基于任务自动机，CloudSeer输出
- 一个接受的自动机实例，如果最后一条消息完成了一个正确的日志序列；
- 一个错误的自动机实例，如果最后一条消息符合问题检测标准；
- 没有输出，表明预期有更多的日志消息。
首先，CloudSeer需要从多个任务自动机中选择一个正确的自动机来检查属于当前日志序列的传入日志消息。 它的主要思想是使用一个自动机组G来跟踪被检查序列的所有可能的自动机。
然后，我们以两种方式扩展算法1中所示的检查算法。 首先，新算法同时保持多个自动机组来跟踪交错序列，其中每个自动机组跟踪一个任务执行的日志消息。 其次，为了避免在所有自动机组上详尽地尝试每一个传入的消息，该算法将一个标识符集与每个自动机组联系起来，这有助于确定即时使用的适当自动机组。
有三种可能
- only one automaton group left;
- multiple automaton groups taking m;
- none of the selected automaton groups to take m
分别有不同的处理方法，这边不仔细介绍了，比较简单，一些brute-force和一些启发式算法。
问题检测。 我们在CloudSeer中实现了两个简单的标准来检测常见的执行问题。 这两个标准是基于执行问题的两种常见表现形式：（1）错误信息的存在，表明任务失败；（2）信息的缺失或延迟，表明任务失败或性能下降。
当错误信息（由其记录级别决定）到达时，错误信息标准生效，算法2中的检查算法导致分歧状态，如第24行所示。 然后，该准则应用计算最大标识符集（ComputeMaxIdentifierSets）和获取自动机群（GetAutomatonGroups）的功能来识别和输出可能与错误信息相关的最可能的自动机群。
超时准则标记任何在指定时间段内没有接收任何信息的自动机组。 标记的自动机组成为算法2的输出。超时值在不同的系统和配置中可能有所不同。确定这样的值不在本文的范围内，我们把它留给未来的工作。