分布式数据存储与聚合排序查询解决方案

在现代分布式系统中，数据常常分布在不同的工作机上，每个机器上都存储着大量且频繁变化的数据集。当需要对这些分布在不同机器上的数据进行排序并查询时，传统的解决方案往往因为数据传输量大、处理时间长而变得不适用。本文提出了一种优化方案，通过将数据分类到不同的桶中，并在查询时仅传输必要的数据，从而减少了数据传输量和提高了查询效率。

问题描述

假设有多个数据存储分布在不同的工作机上，每个存储中都包含大量未排序的同类型对象。这些对象集是庞大且易变的，意味着对象经常被插入或从集合中移除（可以控制插入/移除过程）。系统需要响应以下查询：在聚合器机器上展示一个页面的对象，这些对象是从所有集合中合并排序后的列表中，从某个偏移量开始的p个对象。

解决方案

为了解决这个问题，提出了以下解决方案：

1. 所有数据存储中的对象根据一些简单的规则被分类到特定的桶中。所有数据存储中对象的分类规则是统一的。
2. 分类过程应该相对简单且成本低廉。例如，如果对象是单词，那么可以根据单词的第一个字母或前两个字母来分配桶。
3. 临时冻结所有数据存储。
4. 聚合器收集所有数据存储中每个桶的长度。
5. 聚合器计算所有数据存储中每个桶的总对象数。
6. 找到满足以下条件的桶编号x和y：

7. 从所有数据存储中加载编号在x和y之间的桶的内容到聚合器（此时可以解除数据存储的冻结）。
8. 分别对每个桶中的对象进行排序。
9. 组合所有桶的最终排序列表，并从列表中取出从对象编号a开始的p个对象，其中a = offset - Sx。

软件实现

该算法使用C#语言实现，并通过一个名为AggregatedSortedPage的动态链接库(DLL)来提供。该库包含一个名为IDataStoreBucketsContainer的接口，其中T是要排序的对象类型。

IDataStoreBucketsContainer接口提供了获取桶长度GetBucketsLength()和内容GetBucketsContent()的方法。DataStoreBucketsContainer类实现了这个接口，处理真实的数据存储，并且在其字典中包含桶。它还能够向桶中添加/移除对象。为了获取桶的长度和内容，聚合器需要调用IDataStoreBucketsContainer接口的方法。

聚合器是一个无状态的静态类。它唯一的公共方法GetPage()接受IDataStoreBucketsContainer的实例（可以是代理或真实的DataStoreBucketsContainer），用于比较T类型对象的System.Collections.Generic.IComparer接口的实现，以及查询对象的Query类型。

上述软件不强制要求可排序对象的类型T。将对象分配到桶中、对象比较和查询的规则与对象的类型和算法实现是分离的。为了在每个索引（标准）上提供查询，需要提供两个外部实体，即按桶分类对象的方法（在DataStoreBucketsContainer的构造函数中作为参数的System.Func类型的委托），以及比较两个对象的方法（作为System.Collections.Generic.IComparer接口的实现，作为静态Aggregator.GetPage()方法的参数）。

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

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

代码示例

为了测试AggregatedSortedPage程序集，使用了一个名为TestApp的控制台应用程序。Item类表示要排序的对象类型。它根据其公共字符串属性Word的字母顺序进行排序。ComparerItem类包含了将Word属性分类到桶中的方法，以及实现System.Collections.Generic.IComparer接口的比较两个单词的方法。桶大致遵循单词的第一个字母，尽管有些字母被合并到一个桶中，而有些字母被分成两个桶（在后一种情况下，分析了前两个字母）。

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

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