SLC-index: A scalable skip list-based index for cloud data processing

Abstract

Due to the increasing number of cloud applications, the amount of data in the cloud shows signs of growing faster than ever before. The nature of cloud computing requires cloud data processing systems that can handle huge volumes of data and have high performance. However, most cloud storage systems currently adopt a hash-like approach to retrieving data that only supports simple keyword-based enquiries, but lacks various forms of information search. Therefore, a scalable and efficient indexing scheme is clearly required. In this paper, we present a skip list-based cloud index, called SLC-index, which is a novel, scalable skip list-based indexing for cloud data processing. The SLC-index offers a two-layered architecture for extending indexing scope and facilitating better throughput. Dynamic load-balancing for the SLC-index is achieved by online migration of index nodes between servers. Furthermore, it is a flexible system due to its dynamic addition and removal of servers. The SLC-index is efficient for both point and range queries. Experimental results show the efficiency of the SLC-index and its usefulness as an alternative approach for cloud-suitable data structures.

Keywords

cloud computing / distributed index / cloud data processing / skip list

References

[1] ArmbrustM, FoxA, GriffithR. A view of cloud computing [J]. Communications of the ACM, 2010, 53(4): 50-58

[2] Ben-YehudaO A, Ben-YehudaM, SchusterA, TsafrirD. Deconstructing Amazon EC2 spot instance pricing [J]. ACM Transactions on Economics and Computation, 2013, 1(3): 16

[3] WangL-z v, LasxewskiG, YoungeA. Cloud computing: A perspective study [J]. New Generation Computing, 2010, 282137-146

[4] CalderB, WangJ, OgusA W. Windows Azure storage: A highly available cloud storage service with strong consistency [C]. ACM Symposium on Operating Systems Principles, 2011, Cascais, ACM: 143157

[5] LiuA-f, LiuX, LiHe. MDMA: A multi-data and multi-ACK verified selective forwarding attack detection scheme in WSNs [J]. IEICE Transactions on Information and Systems, 2016, E99-D(8): 2010-2018

[6] DingY S, HaoK R. Multi-objective workflow scheduling in cloud system based on cooperative multi-swarm optimization algorithm [J]. Journal of Central South University, 2017, 24(5): 1050-1062

[7] ChangF, DeanJ, GhemawatS. Bigtable: A distributed storage system for structured data [J]. ACM Transactions on Computer Systems, 2008, 26(2): 1-26

[8] GhemawatS, GobioffH, LeungS T. The Google file system [C]. ACM Symposium on Operating Systems Principles, 2003, 37(5): 29-43

[9] VavilapalliV K, MurthyA C, DouglasC. Apache hadoop yarn: Yet another resource negotiator [C]. ACM Annual Symposium on Cloud Computing, 2013, 5: 1-16

[10] DecandiaG, HastorunD, JampaniM. Dynamo: Amazon’s highly available key-value store [C]. ACM Symposium on Operating Systems Principles, 2007, 41(6): 205-220

[11] LakshmanA, MalikP. Cassandra: A decentralized structured storage system [J]. ACM SIGOPS Operating Systems Review, 2010, 44(2): 35-40

[12] DittrichJ, QuianeruizJ, JindalA. Hadoop++: Making a yellow elephant run like a cheetah (without it even noticing) [J]. Proceedings of The VLDB Endowment, 2010, 3(12): 515-529

[13] YangH C, ParkerD S. Traverse: Simplified indexing on large map-reduce-merge clusters [C]. International Conference on Database Systems for Advanced Applications, 2009, Brisbane, Springer: 308322

[14] LinJ, RyaboyD, WeilK. Full-text indexing for optimizing selection operations in large-scale data analytics [C]. The Second International Workshop on Map Reduce and Its Applications, 2011, San Jose, ACM: 5966

[15] LuP, ChenG, OoiB C. ScalaGiST: Scalable generalized search trees for mapreduce systems [innovative systems paper] [J]. Proceedings of the VLDB Endowment, 2014, 7(14): 1797-1808

[16] RichterS, QuianeruizJ, SchuhS. Towards zero-overhead static and adaptive indexing in Hadoop [J]. Proceedings of the VLDB Endowment, 2014, 23(3): 469-494

[17] ChangB R, TsaiH F, HsuH T. Secondary ındex to big data NoSQL database–ıncorporating solr to HBase approach [J]. Journal of Information Hiding and Multimedia Signal Processing, 2016, 7(1): 80-89

[18] AguileraM K, GolabW, ShahM A. A practical scalable distributed B-Tree [J]. Proceedings of the VLDB Endowment, 2008, 1(1): 598-609

[19] HuangB, PengY-xing. An efficient two-level bitmap index for cloud data management [C]. IEEE International Conference on Communication Software and Networks, 2011, Xi’an, IEEE: 509513

[20] ZhouW, LuJ, LuanZ-zhi. SNB-index: A SkipNet and B+ tree based auxiliary Cloud index [J]. Cluster Computing, 2014, 17(2): 453-462

[21] WangJ-b, WuS, GaoHong. Indexing multidimensional data in a cloud system [C]. ACM SIGMOD International Conference on Management of Data, 2010, Indianapolis, ACM: 591602

[22] ChengC-l, SunC-j, XuX-long. A multi-dimensional ındex structure based on ımproved VA-file and CAN in the cloud [J]. International Journal of Automation and Computing, 2014, 11(1): 109-117

[23] LuP, WuS, ShouL-dan. An efficient and compact indexing scheme for large-scale data store [C]. IEEE International Conference on Data Engineering, 2013, Brisbane, IEEE: 326337

[24] DinariH, NaderiH. A method for improving graph queries processing using positional inverted index (PII) idea in search engines and parallelization techniques [J]. Journal of Central South University, 2016, 23(1): 150-159

[25] HeJ, WuY, DongY-yun. Dynamic multidimensional index for large-scale cloud data [J]. Journal of Cloud Computing Advances Systems & Applications, 2016, 5(1): 1-12

[26] PughW. Skip lists: A probabilistic alternative to balanced trees [J]. Communications of The ACM, 1990, 33(6): 668-676

[27] JESI G. P. Peersim HOWTO: Build a new protocol for the PeerSim 1.0 simulator [EB/OL]. [2011-08-04] https://doi.org/peersim.sourceforge.net/.