集群环境下分布式索引的实现
摘 要：
针对分布式存储系统上使用非主键访问数据带来的性能问题，探讨在分布式存储系统上实现索引的相关关键技术。在充分分析分布式存储特征的基础上，提出了分布式索引设计和实现的关键点，并结合分布式存储系统的特点及相关的索引技术，讨论了索引的组织形式、索引的维护和数据一致性等问题；然后基于如上的分析，选择在分布式数据库系统OceanBase开源版本上，设计和实现分布式索引机制，并通过基准测试工具YCSB进行性能测试。实验结果表明，虽然辅助索引会对系统性能产生影响，但因为充分考虑了系统特征及存储特点，在不同数据规模下，该索引都能够将性能影响控制在5%以内。另外，使用冗余列的方式，能进一步将该索引的性能提升100%。
关键词：
分布式存储；分布式索引；辅助索引；索引维护；OceanBase
0 引言
为了能够响应和处理互联网级的访问负载，越来越多的应用开始使用基于分布式存储的数据库系统。这些系统的一个共同特征是将数据分片后冗余存储在集群中的多个节点上，从而保证系统的扩展性、可靠性和可用性。按记录主键划分数据是数据分片的主要方式。通过主键属性能够快速定位数据所在的分片，而通过非主键属性往往需要对所有数据分片进行扫描。出于性能的考虑，很多分布式存储系统不建议使用非主键的方式访问数据。
当无法避免使用非主键属性来访问数据时，分布式存储系统的性能成为开发人员需要面对的问题。创建辅助索引是数据库系统改善访问性能的重要手段，在传统关系数据库和分布式数据库领域已经有相当成熟的索引技术。在将这些索引技术应用于新的分布式存储系统时，必须充分考虑每个系统的架构特点，设计和实现能够满足应用场景需求的索引结构。这一领域的研究工作也是近年来的一个热点。
本文对分布式存储系统的特点及相关的索引技术进行了分析，探讨了在分布式存储系统上实现辅助索引需要考虑的问题，包括索引的组织形式、索引分布和索引的维护。同时，本文在对分布式数据库系统OceanBase的开源版本进行介绍的基础上，根据以上的分析，为该系统设计和实现了辅助索引机制，并且通过基准测试工具YCSB（Yahoo Cloud Serving Benchmark）进行了性能测试。测试结果表明，虽然增加辅助索引会对系统的性能产生影响，但这种影响是在可接受范围内并且是稳定的；同时，辅助索引能够极大地提高非主键访问的性能。
1 背景和相关工作
1.1 分布式存储系统
分布式存储系统已经广泛应用于工程实践中，例如Google BigTable[1]、Amazon Dynamo[2]、Windows Azure Storage[3]等，很多大型互联网企业都采用成熟的分布式存储系统方案，以实现对大规模数据的存储、计算以及价值信息的提取。同时，围绕HBase[4]、Cassandra[5]等的开源分布式存储系统展开的相关设计、优化和研究成为备受关注的课题。
相比传统的单点存储系统的部署需要高端服务器来提供高性能数据处理和存储支持，分布式存储系统通常由数量众多、成本较低的普通服务器组成，集群中每个服务器节点都会存储并管理系统的部分的数据。分布式系统中，数据一般采用多副本冗余存储，当某个节点出现故障时，该节点上的数据可以在其他节点上找到相应副本，仍然可以被访问。分布式存储系统一般都具有良好的线性可扩展性，通过增加存储节点可以线性增加系统的处理与存储能力。
按记录主键对数据进行划分，将数据分布存储在多个节点，是数据分布的主要手段。大多数分布式存储系统将数据组织成一个分布式Hash表，或者实现分布式平衡树（如B+树）。例如采用基于Hash存储引擎的Amazon Dynamo[2]，可以看作是哈希表的持久化实现，通过一致性哈希机制[6]将数据项以key（主键）、value（内容）为主要形式分片到不同的数据节点，这样的设计实现只能提供基于指定主键的数据库基本操作（Create，Retrieve，Update，Delete， CRUD）功能。而在Google BigTable[1]的实现中，系统以表格为单位组织数据，每个表上的数据按照主键（row key）有序，组成一个B+树，一个叶子节点包含表的一个前开后闭的主键的范围，每个计算节点可以看成存储了分布式B+树的一个或几个叶子节点，支持根据主键的CRUD以及范围查找。
通过维护数据分片以及集群节点的信息，分布式存储系统能够很好地处理客户端的主键查询请求。根据数据分布情况及集群负载，系统会选择合适的存储节点进行访问，并发地向它们发送对应主键（主键范围）的查询请求，最后将从每个节点读取到的本地数据整合后返回给客户端；但是，对于非主键的查询请求，系统无法根据主键确认数据位置，只能对所有节点的数据进行全部扫描，访问性能极受影响。
1.2 分布式索引
创建辅助索引，是提高访问性能的重要手段。传统的单点存储系统，已经拥有很成熟完善的索引机制，但由于系统架构、数据存储的根本改变，单点存储系统的辅助索引技术不能直接运用在分布式存储系统当中。二者的主要区别在于，对于分布式系统，海量数据上的辅助索引极可能拥有与原数据相仿的规模，这就意味着辅助索引也需要分布式存储。在庞大的数据规模下，分布式存储系统的辅助索引管理，组织形式的设计，以及访问和维护的机制，都存在传统单点存储系统未曾有过的新问题。
目前已有许多围绕不同分布式存储系统展开的辅助索引研究工作。对于如Cassandra[5]、Riak[7]等，不依赖中心节点管理集群，拥有环状结构的系统，基于P2P（PeertoPeer）的索引实现有益于高可扩展性，LSH（LocalitySensitive Hashing）[8]是在Chord[9]的基础上实现的分布式索引，通过位置敏感的哈希算法来获得属性值区间标识与存储节点的位置。对于Master/Slave模式的分布式存储系统，也有很多构建辅助索引的研究工作：Hindex（HuaweiIndex）[10]、IHBase（Index_Hbase）[11]实现了对于每个节点数据维护局部索引的方案，这种索引的设计适用于范围扫描查询，不适合随机读取的场景；CGIndex（Cloud Global Index）[12]是基于亚马逊云计算平台（Amazon Elastic Computing Cloud， Amazon EC2）[13]的一个二级索引实现机制，其基本思想是每个节点不仅维护一个局部B+树，还维护全局的CGIndex，通过访问CGIndex可以确定需要在哪些节点上查询局部索引，支持高性能的随机读取；CCIndex（Complemental Clustering Index）[14]将索引看作另一种形式的数据并存成表，使用可靠的互补校验表（Complemental Check Table， CCT）来代替这些表的备份实现了索引容错和恢复，大幅度减少了索引的存储开销；DiffIndex（Differentschemes Index）[15]考虑了不同场景和需求下的索引数据表的同步机制。