论文名称：
LogMine: Fast Pattern Recognition for Log Analytics
3。快速的日志挖掘模式
我们的日志挖掘方法背后的关键直觉是，日志是自动生成的消息，不像故事书中的句子。应用程序源代码中有一些特定的行可以生成日志，因此，来自同一应用程序的所有日志消息都是通过一组有限的格式生成的。标准的聚类和合并方法不考虑数据集中对象之间的任何依赖关系。在日志中，消息之间的依赖关系是很自然的，正如我们在本文中所展示的，这种依赖关系有助于加速集群和合并过程。
3.1标记化（Tokenization）和类型检测（Type Detection）
我们假设所有日志都存储在一个文本文件中，每一行都包含一条日志消息。我们对每个日志都进行简单的预处理。我们使用空格分隔来标记（tokenize）每个日志消息。然后我们检测一组预定义的类型，例如：日期（date）、时间（time）、IP和数字（number），并用字段的名称替换每个字段的实际值。
例如，我们将2015-07-09替换为date，将192.168.10.15替换为IP。
用户可以根据自己对字段类型内容上的兴趣来配置这组预定义的类型。
图3显示了日志消息中的标记化和类型替换例子。
由于下一节描述的聚类算法的一次传递特性，标记化和类型检测嵌入到聚类算法中，而不会增加任何开销。虽然这个步骤不是强制性的，但是我们使用它可以使两个日志之间的相似性有意义。如果没有进行类型检测，则相同模式生成的两个日志可能具有较低的相似性，这只是因为它们对相同的字段具有不同的值。因此，如果不进行标记（tokenize），我们可能最终会产生大量不必要的模式（模板）。
3.2快速的、内存高效的聚类（Clustering）
我们的聚类算法只是日志消息的 friends-of-friend聚类的一次性版本。我们的算法利用多种优化技术来提高聚类性能。
3.2.1距离函数
我们首先通过下面的方程定义两个日志消息之间的距离。
Pi是日志P的第i个字段。
len(P)是日志P的字段的数目。
k1是一个可调的参数。我们在默认的日志距离函数中设置了k1=1，但是这个参数可以更改为对两个日志消息中匹配的字段增加或减少权重。
由于我们希望在框架的后续迭代中对模式进行聚类，因此还需要一个用于模式的距离函数。两个模式之间的距离的定义非常类似于两个日志消息之间的距离，只是使用了一个新的评分函数。
在我们默认的模式距离函数中，我们再次设置k1=k2=1.我们的距离函数是非负的，对称的，自反的，它满足三角形不等式。因此它是一个度量。由相同格式生成的日志消息的距离非常小(大多数情况下为零)，而由不同格式生成的日志消息的距离更大。对于快速和内存高效的日志聚类算法来说，这是一个可取的属性。在高维空间中，日志信息形成完全分离且高度密集的区域。因此，使用上述距离函数查找集群是一项简单的任务。
3.2.2寻找聚类簇
首先，我们定义一个名为MaxDist的内部参数，它表示聚类簇中任何日志条目/消息与聚类簇代表之间的最大距离。因此，聚类簇中任意两个日志之间的最大距离为2×MaxDist。我们从第一个日志消息开始，逐个处理所有日志消息，直到到达最后一个消息。每个聚类簇都有一个代表性的日志消息，它也是聚类簇的第一个成员。对于任何新的日志消息，我们只有当日志和代表之间的距离小于MaxDist时，才将消息插入到一个现有聚类簇中。否则，当消息不和任何代表类似时，我们创建一个新的聚类簇，并将日志消息作为新聚类簇的代表。
上述过程可以在非常小的内存占用中实现。我们需要在内存中为每个集群只保留一个代表性日志，并输出后续日志消息，而不将其保存在内存中。这使得我们的算法可以用少量的内存处理大量的日志。事实上，我们的集群算法的内存使用量是O(集群的数量)。
在决定集群成员关系时忽略大量日志消息并只使用一个有代表性的日志消息不会降低集群的质量。主要原因是任何给定集群中的所有日志消息几乎都是相同的，因为它们很可能是由相同应用程序的相同代码段生成的。因此，上述一遍聚类算法在开始时使用一个非常小的MaxDist，可以生成高度密集(即一致)的日志消息集群，在这种情况下，保持一个有代表性的消息是充分且高效的。
我们最终得到了一组稠密的簇，每个簇有一个代表。如前所述，该算法也用于聚类和合并模式。在对模式进行聚类的情况下，与上面的方法不同，我们将所有模式保存在每个集群中，因为我们将在模式识别组件中使用它们。在大多数系统中，第一次迭代后生成的模式集适合内存。这种算法的速度和效率来自这样一个事实:密集集群的数量不会随日志消息的数量而增加，因为应用程序不可能生成大量的独特模式。换句话说，即使在包含数亿条日志消息的数据集中，也不可能找到一百万个惟一模式。
一遍聚类算法对消息的顺序有很强的依赖性，通常是时间顺序。最糟糕的情况是，来自每个集群中每个模式的一条消息出现在日志的非常早的位置，并且必须将所有剩余的消息与所有唯一的代表进行比较。在实际应用中，来自同一应用程序的日志消息表现出时间上的协同，这使得它们更适合于聚类算法。
3.2.3早期放弃（Early abandoning）技术
早期放弃是在欧几里得距离下加速相似性搜索的一种有效方法。
当比较一个新的日志消息和聚类簇代表时，如果距离小于MaxDist，我们可以将新的日志添加到该聚类簇。由于两个日志之间的距离是通过在一次扫描中将非负数累加来计算的，因此可以采用早期放弃的方法。当我们一个字段一个字段地比较两个日志时，我们可能发现累计的距离已经超过了阈值，MaxDist，尽管许多字段还没有进行比较。在这种情况下，我们不需要继续计算完整的完的距离，因为我们确定这两个日志不是在彼此的MaxDist半径内。由于日志中的字段数量可能很大，因此这种技术可以帮助我们跳过大量的计算，特别是在MaxDist很小的时候。
3.2.4通过map-reduce实现规模化
我们之前提到过，我们的one-pass聚类算法的内存使用率是O(聚类簇的数量)。one-pass聚类算法非常适合通过map-reduce方法进行并行执行。对于数据集中的每个日志，我们创建一个key-value键值对。键是一个固定的数字(在我们的例子中是1)，值是一个包含给定日志的 singleton list。我们还将基于长度的索引添加到每个元组（tuple）的value中。在reduce函数中，我们可以合并每一对列表。具体来说，我们总是将较大的list作为基list，并更通过向里面添加更小的list的所有元素（如果需要的话），来更新这个基list。这使得合并的过程更快。在向基list添加较小list的元素时，我们只添加那些在基集中没有任何类似代表的元素。如果基list中已经存在一个非常接近的代表，则忽略该日志。同时，我们还更新了基于长度的基list索引。最后，基list将是两个给定列表合并的结果。reduce函数的伪代码如下图算法1。
3.3日志模式识别（Log Pattern Recognition）
在我们对日志进行聚类之后，我们需要为每个聚类找到一个模式（模板）。因为我们在第一轮密集的聚类簇中保持一个代表，这个代表本身就是这个的模式，但在随后的回合中，在我们聚类模式后，我们需要一个这样一个算法：在一个聚类中，为一组日志/模式来生成一个模式。我们从一对模式的模式生成过程开始，然后概括为一组模式。
3.3.1成对模式生成（Pattern Generation from Pairs）
不管模式识别算法是什么，我们总是需要在算法的某个点上合并两个日志。因此这里说一下合并（Merge）算法。给出要合并的两个日志，我们首先需要找到它们的最佳对齐（alignment）方式。两个日志的最佳对齐方式是在合并后生成最小数量的通配符和变量。在对齐的过程中，每个日志的字段之间可能会插入一些间隙。对齐算法确保插入间隙后两个日志的长度相等。一旦我们有了两个相同长度的日志，我们将逐个字段处理它们并生成输出。图4显示了一个示例。
请注意，上图align步骤在第二个消息中引入了间隙。字段检测步骤需要直接扫描两个日志。
在算法2中可以找到详细的伪代码。
有不同的算法来对齐两个序列。我们使用Smith-Waterman算法。
3.3.2序列模式生成（Sequential Pattern Generation）
要为一组模式生成一个模式，我们从第一个日志消息开始，将它与第二个日志合并，然后将结果与第三个日志合并，直到最后一个。显然，这种方法的成功很大程度上取决于模式在集合中的顺序。然而，如前所述，每个密集聚类中的日志几乎是相同的。这就是为什么在实践中，合并排序与最终模式的质量没有关联。换句话说，我们会得到相同的结果，如果我们用逆序或者任意顺序来做合并。如果要合并的日志不相似，顺序合并可能会产生一个带有许多通配符的模式，这不是我们想要的。目前存在为一组模式寻找最优合并排序的技术。我们在第4节中提供了详细的实验，以经验证明顺序合并不会失去质量。
3.3.3通过map-reduce实现规模化
如3.3.2节所述，在聚类中合并日志以创建最终模式的顺序对输出没有影响。这样的顺序模式生成可以非常容易地并行化。
3.4层次结构的模式（Hierarchy of Patterns）
前面说的寻找密集聚类的方法可能太具体太笼统，不能满足管理员的需求。
相反，模式的层次结构可以提供日志消息的整体视图，管理员可以在层次结构中选择具有正确特性的级别来监视异常情况。
为了创建层次结构，我们迭代地使用聚类和模式识别算法，如图2所示，并以自底向上的方式生成层次结构。
在第一次迭代中，我们在给定的日志集上使用一个非常小的MaxDist运行聚类算法。这是最严格的聚类条件。聚类的输出是一组密集集群(可能很大)，每个聚类都有一个代表性日志。在不调用模式识别模块的情况下，将代表的日志简单地分配为密集聚类的模式。我们将这些模式视为模式层次结构的叶子(最低层)。为了生成层次结构的其他层次，我们将聚类算法的MaxDist参数增加一个因子，并在生成的模式上运行聚类算法。换句话说，我们在模式上运行一个更宽松的聚类算法，它将产生新的聚类。然后，我们将聚类在一起的所有模式上运行模式识别模块，以查找更通用的模式。这些新模式集将作为新级别添加到层次结构中。在此方法的每次迭代中，都会向层次结构中添加一个新级别。随着我们在层次结构中越往上走，添加的模式数量就越少，这些模式比较低层次中的模式更普遍。这种结构使我们能够灵活地选择层次结构中的任何级别作为所需的模式集。
3.4.1层次结构模式识别
为了生成模式的层次结构，我们从具有最具体模式的叶子层开始，而且聚类也是密集的。当我们在层次结构和合并模式中上升时，聚类的密度会降低。由于MaxDist参数被放宽，我们允许较大距离的模式组合在一起。如果我们使用顺序模式识别算法，这就有可能在层次结构的更高级别出现错误。幸运的是，每个聚类中模板的数量，更高的层级结构中比较低的层级结构中要少的多，我们可以使用一个选择性的合并顺序，而不是传统的UPGMA(算术平均的非加权对组方法)方法所发现的顺序。UPGMA是具有平均链接的层次聚类，当集群在高维空间中呈球形时，它是最优的，我们推测当集群包含大量消息时，这对于日志模式渐近正确。
我们最终的模式识别算法是一个混合了UPGMA、顺序识别和map-reduce的算法。算法3展示了如何为每个日志聚类选择最佳选择。th1和th2分别是一个集群中模式的密度和数量的阈值。
3.4.2一个层级的成本
给定一组日志的模式层次结构，用户可能对具有特定属性的级别感兴趣。一些用户可能更喜欢获得最少数量的模式，而其他用户可能对非常具体的模式感兴趣，而不关心模式的数量。有许多不同的标准可以衡量一个水平是否令人满意。我们引入一个直观的成本函数来选择层次结构的最佳描述层次。我们还提出了一个适合我们的数据集的代价函数。这个成本函数可以很容易地作为一个通用模板来计算层次结构某个级别的成本。
Sizei是聚类i中日志的个数。WCi，Vari，FVi分别是聚类i中通配符（wildcards）、变量字段（variable fields）和固定值字段（ fixed value fields）的个数。a1、a2和a3是可调参数，可按用户要求进行设置。
如果用户没有首选项，我们可以在cost函数中设置a1 = 1、a2 = 0和a3 = 0，并选择模式数量最少但没有通配符的级别作为最终的模式集。例如，在图5中，我们发现级别2生成了两个没有通配符的模式，因此我们从级别2中选择这两个模式作为最终的模式集。在我们的实验中，我们假设用户不会提供任何首选项。用户还可以通过指定预期模式的最大数量来提供首选项。例如，用户可能希望生成最多4个模式。在本例中，我们从图5中的级别2中选择两个模式，因为它将生成最小的通配符数量，同时不会超过给定的最多4个模式的用户。
