分布式无序数据集的排序页

• 下载源代码 - 11.8 KB

问题陈述

最近在实际工作中，我遇到了以下问题。

有几个位于不同工作机器上的数据存储，每个存储都有一个相同类型的未排序对象集合。这些集合很大且是易失性的，意味着项目经常被插入/删除（我们控制插入/删除过程）。系统应响应以下查询：*在另一个聚合器机器上，呈现来自所有集合合并排序列表的p个对象的页面，该页面距离此组合排序列表的开头具有一定的偏移量。*

例如，当用户想要查看（按页面或可滚动表格）分散在不同计算机上的频繁更改对象的已排序合并列表时，就会出现此类问题。

该问题的直接解决方案是：

• 将所有数据存储的集合复制并合并到聚合器机器上，
• 对合并后的集合进行排序，形成全局排序列表，并且
• 从第offset个对象开始，获取p个对象。

这种朴素的解决方案由于每次查询都需要从数据存储大量传输对象，因此不适用于我们大型且频繁更新的数据存储。更好的解决方案应尽可能减少传输的对象数量。

尽管上述问题看起来相当普遍，但我未能找到其文档化的解决方案，更不用说代码实现了。

解决方案

提出的解决方案如下。所有数据存储中的对象根据一些简单的规则被归类到特定的存储桶中。将对象放入存储桶的规则对所有数据存储都是统一的。分类过程应该相对简单且成本低廉。例如，如果我们的对象是单词，那么按存储桶划分可以按单词的第一个字母或前两个字母进行。为了解决我们的问题，我们

• 临时冻结所有数据存储，
• 聚合器收集所有数据存储中每个存储桶的长度，
• 聚合器计算所有数据存储中每个存储桶的总对象数，并且

           S_k - 所有数据存储中前k个存储桶（编号介于0到k - 1之间）中的对象总数。

• 找到满足以下条件的存储桶编号x和y：

                 S_x  ≤  offset  &  S_x+1  >  offset                   (1)

                 S_y  ≤  offset + p   &  S_y+1  >  offset + p     (2)

• 从所有数据存储中加载编号介于x和y（包括）之间的存储桶的内容到聚合器（此时可以解除数据存储的冻结）
• 分别对来自所有数据存储的每个存储桶的对象进行排序，并且
• 将所有存储桶组合成最终的排序列表，并从列表中从第a个对象开始获取p个对象的页面，其中

                 a = offset - S_x                                            (3)

下图说明了上述算法。

图中，数据被插入/删除到z个数据存储0, 1, ..., z - 1中。数据存储中的对象被归类为n个编号为0, 1, ..., n - 1的存储桶。红色框包围了由条件(1)和(2)定义的介于x和y之间的存储桶，这表示传输到聚合器的内容。红色矩形“结果”显示了聚合器中合并排序列表的最终结果页面，包含从第a个对象开始的p个对象。数字a由(3)计算得出。

软件实现

该算法用纯C#在程序集（DLL）AggregatedSortedPage中实现。该程序集包含接口IDataStoreBucketsContainer<T>，其中T是要排序的对象类型，以及类DataStoreBucketsContainer<T>（实现该接口）、Aggregator和Query。接口IDataStoreBucketsContainer<T>提供了获取存储桶长度GetBucketsLength()和内容GetBucketsContent()的方法。类DataStoreBucketsContainer<T>实现了接口IDataStoreBucketsContainer<T>，处理实际的数据存储并将其存储桶保存在其字典中。它还能够向其存储桶添加/删除对象。为了获取存储桶的长度和内容，Aggregator必须调用IDataStoreBucketsContainer<T>接口的方法。如果Aggregator和DataStoreBucketsContainer<T>位于同一进程中（如我们相当说明性且不太现实的示例中），则Aggregator直接调用DataStoreBucketsContainer<T>的方法。但实际上，Aggregator从不同进程查询数据存储。为此，需要实现接口IDataStoreBucketsContainer<T>的适当代理（在此代码示例中未显示）。代理能够从Aggregator进程调用远程DataStoreBucketsContainer<T>对象的方法。应提供适当的基础设施来支持这些进程间调用。

Aggregator是一个无状态的静态类。其唯一的公共方法GetPage<T>()接受IDataStoreBucketsContainer<T>（代理或实际DataStoreBucketsContainer<T>）的实例、实现System.Collections.Generic.IComparer<T>接口用于比较T类型对象的类（以便排序），以及类型为Query的查询对象作为参数。

上述软件对类型为T的可排序对象没有施加任何要求。将它们分布到存储桶的规则、对象的比较以及查询都与对象类型和算法实现分离。要对每个索引（标准）执行查询，应提供两个外部实体，即：

• 用于按存储桶对对象进行分类的方法（作为DataStoreBucketsContainer<T>构造函数中的委托类型System.Func<T, int>），以及
• 用于比较两个对象的方法（作为静态Aggregator.GetPage<T>()方法的参数，实现System.Collections.Generic.IComparer<T>接口）。

这些方法在不同地方使用，因为在实际生活中，类DataStoreBucketsContainer<T>和Aggregator运行在不同的进程中。

类DataStoreBucketsContainer<T>提供方法GetInfo()用于检查其存储桶。它返回一个元组，包含数据存储中每个存储桶的长度列表、平均对象数以及存储桶长度与平均数的比率。尽管此方法不直接用于解决问题，但它可能有助于优化存储桶分配规则。

代码示例

为了测试程序集AggregatedSortedPage，使用了控制台应用程序TestApp。类Item代表排序对象类型。它按其公共字符串属性Word的字母顺序排序。类ComparerItem同时包含将Word属性分类到存储桶的方法和比较两个单词的方法，实现了接口System.Collections.Generic.IComparer<T>。存储桶大致遵循单词的第一个字母，尽管某些字母被合并到一个存储桶中，而另一些字母则被分成两个存储桶（在后一种情况下，分析前两个字母）。

文本文件t8.shakespeare.txt包含威廉·莎士比亚的所有著作，从这里下载，用作单词来源，并移除了逗号、撇号等辅助符号。测试只使用不重复的单词（没有单词重复）。空字符串也从列表中移除。进行这些修改后，列表中剩下29541个单词。文件应被下载并放置在TestApp.exe所在的文件夹或TestApp.csproj所在的文件夹中。文件名在Program.cs中硬编码（当然，可以使用任何其他足够大的文本文件进行测试 - 只需在代码中更改文件名）。为了方便后续检查查询的正确性，列表中的所有项目都按字母顺序排序，并且它们的序列号和数据存储被放入用于测试的目的的适当属性中，并将在下面描述。

类Item有两个仅用于测试目的的辅助属性。属性DataStore指示包含此项目的Data Store，属性Num表示项目在完整排序列表中的序列号（即文件中所有不重复单词按字母顺序排序的列表）。这两个属性使我们能够有效地检查查询执行的结果。请注意，在实际生活中，这些属性没有用处。

为了测试，我们将所有单词平均分配到三个数据存储中，并执行查询，其中offset = 15000，p = 25。此查询首先针对未更改的单词集执行，然后通过向一个数据存储添加单词和从一个数据存储中删除单词来执行。未更改的单词集的查询结果如下（如您所见，有些单词拼写不正确，因为像撇号这样的符号已被删除）

Data Stores Lists Aggregator

start: 15000, num: 25

COMBINED SERIAL NUM.   NUM. IN PAGE  DATA STORE   WORD
     15000                  0            2        loaf
     15001                  1            0        loam
     15002                  2            1        loan
     15003                  3            1        loath
     15004                  4            2        loathd
     15005                  5            0        loathe
     15006                  6            1        loathed
     15007                  7            0        loather
     15008                  8            0        loathes
     15009                  9            1        loathing
     15010                  10            0        loathly
     15011                  11            2        loathness
     15012                  12            2        loathsome
     15013                  13            1        loathsomeness
     15014                  14            2        loathsomest
     15015                  15            1        loaves
     15016                  16            0        lob
     15017                  17            2        lobbies
     15018                  18            1        lobby
     15019                  19            1        local
     15020                  20            0        lochaber
     15021                  21            0        lock
     15022                  22            1        lockd
     15023                  23            2        locked
     15024                  24            0        locking

我们通过Item类的辅助属性获得了COMBINED SERIAL NUM.（合并序列号）和DATA STORE（数据存储）列的内容。从上面的结果可以看出，我们的查询已正确完成，并且单词来自所有数据存储。

讨论

为了提高算法的效率，每个存储桶应包含相对少量的对象（当然，存储桶的数量应是合理的）。这使得系统能够从数据存储传输更少的对象到聚合器，并由聚合器对更少的对象进行排序以生成最终的合并列表。另一方面，对象分配到存储桶的规则应简单且成本低廉，以减少对象大量添加情况下的计算和锁定时间。