IDEA中的物理索引与逻辑索引：具备倒排去重功能的索引

《ACM Transactions on Storage》：Physical vs. Logical Indexing with IDEA: Inverted Deduplication-Aware Index

针对去重存储系统中传统关键词索引效率低的问题，本文提出IDEA索引机制。通过将术语映射到物理数据块而非逻辑文件，结合白空间对齐的分块技术，显著减少索引大小（最高73%）和查询延迟（单次查询降低82%）。实验表明，IDEA在去重比率高（78%-95%）的Linux内核数据集上效果最佳，同时支持文档排名和精确位置查询等高级功能。

　　在当今信息检索领域，随着在线数据量的不断增长，保持可靠的数据索引变得尤为重要。这些数据不仅被用于数据挖掘和自然语言处理，还被大量的搜索引擎用户进行搜索。与此同时，越来越多的主存储系统采用数据去重技术，将重复的逻辑数据块替换为指向唯一物理副本的引用。然而，传统的索引机制并未考虑数据去重，这可能导致严重的效率问题。具体而言，索引的大小会随着逻辑数据量的增加而增加，与去重比例无关，从而消耗大量存储和内存资源，并且使得查找操作变慢。此外，逻辑上的连续访问在创建索引时会变成对物理数据块的随机且冗余访问，这会显著影响性能。目前，据我们所知，没有任何去重存储系统支持完整的关键词索引。

本文提出了一种面向数据去重的关键词索引设计，称为IDEA。IDEA通过将关键词映射到包含它们的唯一数据块，以及将每个数据块映射到它所归属的文件，来解决上述挑战。这一基本设计概念不仅提升了索引性能，还支持诸如实时索引、结果排序和邻近搜索等高级功能。我们的原型实现基于Lucene（Elasticsearch的核心搜索引擎），展示了IDEA在减少索引大小和创建时间方面的能力，以及在单个和多个关键词查询中降低关键词查找延迟的潜力。

数据去重的引入改变了数据存储的方式，使得存储系统需要处理逻辑数据和物理数据块之间的差异。这种差异给数据管理带来了新的挑战，例如垃圾回收、卷之间的负载均衡、缓存和计费等问题。此外，去重数据的碎片化问题也会影响数据访问的效率，因为逻辑上的连续数据访问会转化为物理存储上的随机I/O操作。为了解决这些问题，IDEA的设计确保了关键词索引的高效性，减少了存储和访问延迟。

在设计IDEA时，我们采用了白空格感知的去重数据块分割方法，以确保数据块边界与单词边界对齐，从而避免关键词被分割在不同的数据块中。这种方法可以显著提高索引的准确性和效率。IDEA的索引过程通过直接处理物理数据块来实现，而不是按照逻辑文件顺序进行处理。这种方法减少了随机访问和冗余处理，提高了整体性能。IDEA还引入了两个映射结构：关键词到数据块的映射，以及数据块到文件的映射。前者用于快速查找关键词的出现位置，后者则用于确定这些数据块属于哪些文件。

在实现IDEA时，我们使用了Lucene作为关键词索引的核心引擎，并将Lucene的文档存储结构用于数据块到文件的映射。此外，我们还使用了Berkeley-DB作为文件到路径的映射结构，以提高查找效率。IDEA的实现过程涉及多个步骤，包括读取去重系统的数据块，处理这些数据块以创建关键词索引，以及通过映射结构将数据块与文件关联。这一过程确保了索引的准确性和高效性，同时减少了存储需求和查找延迟。

为了评估IDEA的性能，我们进行了多组实验，涵盖了Linux内核版本和英文维基百科存档等数据集。实验结果显示，IDEA在索引时间和查找延迟方面都显著优于传统的去重不敏感索引。具体而言，IDEA可以将索引大小减少高达73%，索引时间减少高达94%，并且在单个和多个关键词查询中分别将查找延迟减少高达82%和59%。此外，IDEA还支持实时索引、结果排序和邻近搜索等高级功能，这使其在实际应用中更加灵活和高效。

IDEA的设计还考虑了不同数据存储介质对性能的影响。例如，在使用SSD和NVRAM等高速存储设备时，IDEA可以进一步优化性能，减少查找延迟。此外，IDEA还支持不同的索引变体，包括IDEA-indirect、IDEA-offsets和IDEA-rank，这些变体分别支持实时索引、关键词偏移量查找和结果排序等功能。通过这些变体，IDEA能够适应不同的应用场景和需求。

总体而言，IDEA为数据去重存储系统提供了一种高效且灵活的关键词索引方案。它通过将关键词映射到数据块，以及数据块映射到文件，解决了传统索引方法在处理去重数据时所面临的效率问题。IDEA的实现过程不仅减少了存储需求和查找延迟，还支持多种高级功能，如实时索引、结果排序和邻近搜索。这些特性使得IDEA在实际应用中具有广泛的应用前景，特别是在需要高效数据检索的场景中。