在现实生活中应用教科书数据结构取胜

这篇博客文章讲述了我们如何在核心平台中利用教科书上的数据结构，并在关键的数据处理步骤中实现了15倍的速度。在简要解释Union-find的工作原理之后，我们将深入了解Heap的身份如何使用它来提供用户行为的完整视图。

我们还将通过散列描述联合，这是一种比传统方法更适合分布式环境的新型启发式方法。最后，我们将介绍如何利用这些知识在我们的产品中创建临时替代产品，从而将数据导出过程从大约4小时减少到大约10分钟。

当网页或移动应用程序加载Heap SDK时，SDK会生成该Cookie或移动设备唯一的半永久随机标识符。所有事件和用户数据都与该用户ID相关联。为了让产品经理完整地了解用户在其产品中的过程，我们还提供了一个API来连接不同设备上的行为。该接口名为Identity。

如果最终用户登录，Heap客户可以用规范的身份标记该用户。现在“已标识”，跟踪器将其ID设置为该规范标识的散列，并将该标识记录在我们的后端中。来自该用户的所有未来数据都与用于分析的规范身份相关联。此外，先前跟踪的附加到匿名用户ID的数据被映射到规范标识符，从而创建用户交互的统一视图。

单个标识的用户可以很容易地由多个跟踪实例组成。让事情变得更复杂的是，身份可能会改变！可以将各自由一组1个或多个跟踪ID组成的两个标识的用户合并为单个组合用户以供分析。因此，我们需要维护一个非常复杂、动态变化的用户映射。输入Union-Find。

“[UNION-FIND]是存储非重叠集合…的集合的数据结构。[和]提供添加新集合、合并集合以及查找集合的代表性成员的操作。“。

我们使用Union-Find来存储和检索属于同一规范用户的跟踪ID集，这一功能对于支持Heap中的身份至关重要。名为“UsersDB”的数据库存储UNION-FIND数据结构，并允许两个指定的操作：

Find(User_Id)，它返回与user_id所属的ID集相对应的规范ID。

标识用户后，UsersDB会将新的跟踪ID添加到数据结构中，并将旧的ID与新的ID合并以保持关联。UNION-FIND可确保将来使用FIND进行的查找为两个ID返回相同的值。也就是说，find(Old_Id)==find(New_Id)应该始终为true，这表示old_id和new_id现在都引用同一个规范用户。

出于性能原因，我们的主分析数据库基于规范用户(而不是原始用户)共享所有数据。我们将传入事件持久化在它们的规范用户(使用find找到)下。因此，分析查询作用于已识别的用户，而不是原始用户-它们不需要在查询时做任何工作来解析身份并相应地调整数据。

出于所有实际目的，UNION-FIND对于N个UNION和FIND操作序列的运行时为O(N)[1]。这意味着单个操作的分期运行时实际上是恒定的！那件事怎么可能？

让我们更仔细地看看Union-Find的内部结构，探索两个关键的优化(按等级和路径压缩的UNION)，并介绍我们用来代替传统方法的一种新的启发式方法。

UNION-FIND在内部由一组有向树表示，其中边指向每棵树的根。每个用户ID都是树中的一个节点，每个节点树代表映射到一个规范用户的一组ID。树的根节点是集合的规范用户。UNION操作合并两个树，Find返回规范标识符。

单个UNION操作必须执行两个查找操作，每个参数一个。这些查找结果用于确定这两个节点是否已在同一树中。如果不是，UNION将通过将一个树的根节点连接到另一个树来合并这些树。因为向图中添加边是一个恒定的时间操作，所以并集运行在O(Find)中。

查找操作的运行时由节点及其根之间的边数(称为路径长度)确定。

如果不进行优化，最坏情况图可能包含长度为N/2的路径，并导致O(N^2)运行时间[2]，这在这里是不希望的。改善运行时的关键因素是缩短任何给定节点与其树根之间的路径长度。

第一个优化，按等级合并，是选择新树根的启发式算法。其目标是通过始终如一地将较小的树连接到较大的树来限制路径的增长。为此，需要为每个节点计算分数-称为其“排名”。根节点的等级近似于树中最长路径的长度。

每个节点从等级0开始。当两个节点连接时，排序较高的根成为新树的根。如果两个根的排名相等，则任意选择新树的根节点，并将其排名增加1。这种简单的轻量级启发式算法有效地跟踪了树的大小，并限制了增长。

仅按秩进行联合并不能确保O(N)运行时的路径长度足够短。我们还必须利用查找操作通过路径压缩来缩短路径长度。每个查找遍历从查找元素(find(X)中的x)到根(find(X)中的y=y)的整个路径。因为我们知道从x到其根的路径中的所有元素也属于同一集合，所以一旦找到根，我们就可以将这些元素直接连接到根。之后，对这些元素的任何后续查找都将只遇到长度为1的路径。您可以将此视为通过修改树结构来缓存查找操作的结果。

按等级合并会减慢树的生长速度，而路径压缩会主动缩短经过的每条路径。路径长度(因此为O(查找))变为常量，并导致N个联合查找操作的运行时间为O(N)。

实际考虑使得为我们的Identity API实现按等级联合方案变得复杂。跟踪排名需要附加元数据：每个节点都有一个排名。取而代之的是，我们选择了一种无状态启发式方法，其效果与从联合减少树生长的效果大致相同。

我们不使用排名，而是比较散列值。也就是说，在我们的Union(A，B)实现中，我们根据Hash(find(A))和Hash(find(B))中较低的一个来选择新的根。每个联合只能减少给定树根的散列。具有较小散列的树很可能是许多联合的结果，每个联合都一致地减少散列。反过来，这棵树越来越有可能成为未来联盟的根，从而最大限度地减少路径长度的增长。该方法在不增加任何状态的情况下，按秩概率地逼近并集。

现在我们已经讨论了Union-Find及其性能优化，让我们回到这篇博客文章的主要内容：我们如何通过部署更高效的Union-Find实现来实现15倍的性能优势。

回想一下，我们将身份信息存储在名为UsersDB的postgres实例中。身份的联合查找图存储为边表，其中每行将一个用户ID映射到另一个用户ID。UNION和FIND操作作为此表上的SQL查询实现。

当我们收到新的用户映射时，这些查询会将新行插入到表中以更新数据结构。作为获取数据进行分析的一部分，我们从UsersDB找到每个传入事件的规范用户，并将事件重新映射到该用户。通过一些Postgres调优和一些智能缓存，这个Union-Find实现已经很好地为Heap服务了几年。

当我们需要横向扩展我们的数据功能Heap Connect时，问题就出现了。此功能允许客户将他们的Heap数据集同步到他们的数据仓库，通常是Snowflake或RedShift。作为每次同步的一部分，Connect需要从UsersDB导出客户的全套用户映射。

随着客户越来越多、规模越来越大，我们在UsersDB上遇到了扩展限制。批量导出被编写为一个复杂但调优良好的SQL查询，该查询对客户数据集中的每个ID运行Find。面对较长的处理时间、超时和较高的故障率，我们尝试了一些策略来改善现状：

这只会推迟不可避免的事情。导出仍然在减速，并且消耗数据库共享资源的比例在不断增加。这开始降低导出和UsersDB的可靠性，导致其他客户端的性能下降。

我们的调查突出了算法和系统的局限性。我们的Find实现没有实现路径压缩，并且查询不断耗尽内存并溢出到磁盘，极大地降低了速度并消耗了宝贵的磁盘I/O。Heap Connect的资源利用模式与分析数据库的摄取从根本上是不一致的。这使得很难找到一个性价比高、性能好的折衷方案。

作为响应，我们在GO中构建了一个专门的服务，并结合了性能良好的联盟-查找实现和工作负载适当的资源。

身份导出服务直接解决了慢查询带来的两个主要瓶颈：缺乏路径压缩和内存分配不足。我们实现了路径压缩并分配了足够的内存来执行整个导出，而不会溢出到磁盘，远远超过了旧的查询。现在，我们不再使用速度慢、不稳定且不透明的SQL查询，而是提供了具有详细日志记录和指标的快速服务。

我们缩小了范围，只重新实现导出的瓶颈：重复查找以评估用户映射。对于每个批量导出，新服务从UsersDB获取完整的边缘列表，这避免了使身份的真实来源复杂化，并极大地简化了实现。通过从SQL中删除查找操作，我们将复杂的聚合查询简化为使用筛选器的简单表扫描。

归根结底，代码本身是简短而简单的。在不到一周的时间里，我们成功地部署了该服务，并显示出比之前的Postgres查询有很大的性能提升。整个项目在2周后交付给Connect客户，将我们每天最慢的出口速度从4小时加快到15分钟。

该项目的交付速度很快，因为我们利用了构建在AWS弹性容器服务(ECS)之上的内部服务平台。一旦我们完成了业务逻辑并将服务连接在一起，部署到生产中就轻而易举了。CI/CD在不配置专用基础设施的情况下构建和部署容器。

我们在黑客周期间发货了身份导出服务。Hack Week是一个Time Heap工程师自组织来处理不一定在路线图上的项目。在过去，项目的重点是对投机性特征的概念证明。今年的活动面向的是那些可以在一周内发货和交付价值的项目，而身份导出服务显然符合这一要求！

你有没有一个很酷的故事，说你曾经用教科书上的算法取得了巨大的实际胜利？在推特上联系吧！如果你对这类工作感兴趣，我们正在招聘。

[^1]从技术上讲，UNION-FIND对于N个UNION和FIND操作序列的运行时为O(𝛂(N)N)。这里，𝛂表示反阿克曼函数，该函数增长极慢，实际上在所有实际用途中都是恒定的。为简单起见，我们将𝛂视为一个常量因子，并将Union find视为具有分期运行时的算法，该算法与UNION和FIND操作的数量呈线性关系。

[^2]我们通过运行N/2个并来创建N/2条边的单链来创建最坏情况树。然后，我们在叶节点上运行N/2个查找，每个查找遍历N/2条边。这将导致O(N^2/4)运行时，或O(N^2)