关键词: 云计算, 双层索引, 并发跳表, 范围查询, 乐观并发控制

Abstract: Cloud data processing plays an essential infrastructure in cloud systems. Without efficient structures, cloud systems cannot support the necessary high throughput and provide services for millions of users. However, most existing cloud storage systems generally adopt a distributed Hash table (DHT) approach to index data, which lacks to support range-query and dynamic real-time character. It is necessary to generate a scalable, dynamical and multi-query functional index structure in cloud environment. Based on the summary and analysis of the double-layer index systems for cloud storage, this paper provides a novel concurrent skiplist based double-layer index (referred as CSD-index) for cloud data processing. Two-layer architecture, which can breakthrough single machine memory and hard drive limitation, is used to extend indexing scope. Online migration algorithm of skiplist’s nodes between local servers is used to make dynamic load-balancing. The details of the design and the implement of the concurrent skiplist are discussed in this paper. Optimistic concurrency control (OCC) technique is introduced to enhance the concurrency. Through concurrent skiplist CSD-index improves the load bearing capacity of the global index and enhances the overall throughput of the index. Experimental results show the efficiency of the concurrent skiplist based double-layer index and it has viability as an alternative approach for cloud-suitable data structures.

Key words: cloud computing, double-layer index, concurrent skiplist, range query, optimistic concurrency control