Горизонтально масштабируемый индекс на основе LSM-дерева для логических запросов полнотекстового поиска
Аннотация
Пусть существует набор объектов, где каждый объект характеризуется логическими признаками. Пусть логический запрос или Булевский запрос обозначает запрос на поиск объектов, характеризуемых логической функцией, по признакам, например, "документы со всеми словами...и любыми словами ...и без слов... ". Термины "объект" и "документ" в дальнейшем используются как взаимозаменяемые. Компоненты могут иметь различную семантику, т.е. е. некоторые компоненты могут соответствовать словам документа, некоторые ‒ меткам или категориям, а некоторые ‒ побитовым квантам времени даты документа.
Хотя индексы, использующие логические запросы, хорошо изучены в литературе, общий метод ведения списков рассылки не всегда приемлем. Если объем данных может достигать порядка петабайт, компактная структура индекса становится жизненно важной.
Цель исследования ‒ предложить метод построения эффективного растрового индекса во вторичной памяти, позволяющий обновлять или дополнять индексируемые данные с высокой скоростью записи. Мы предлагаем эффективный индекс на основе LSM для растровых изображений и дизайн элементов для практических приложений. Мы также обсуждаем аспекты построения объединенных индексов для достижения хорошей масштабируемости. В статье описываются архитектура и алгоритмы предлагаемого индекса, а также результаты наших экспериментов, которые показывают устойчивую производительность нашего решения.
Литература
2. Ponte J.M., Croft W.B. A language modeling approach to information retrieval. Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval (SIGIR'98). Association for Computing Machinery, New York, NY, USA; 1998. p. 275-281. (In Eng.) doi: https://doi.org/10.1145/290941.291008
3. Mattmann C.A. A vision for data science. Nature. 2013; 493(7433):473-475. (In Eng.) doi: https://doi.org/10.1038/493473a
4. Marx V. The big challenges of big data. Nature. 2013; 498(7453):255-260. (In Eng.) doi: https://doi.org/10.1038/498255a
5. Chen C.L.P., Zhang C.-Y. Data-intensive applications, challenges, techniques and technologies: A survey on Big Data. Information Sciences. 2014; 275:314-347. (In Eng.) doi: https://doi.org/10.1016/j.ins.2014.01.015
6. Anderson D., Dykes J., Riedel E. More Than an Interface ‒ SCSI vs. ATA. Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST'03). San Francisco, CA: USENIX Association; 2003. p. 245-257. Available at: https://www.usenix.org/conference/fast-03/more-interface%E2%80%94scsi-vs-ata (accessed 13.01.2022). (In Eng.)
7. Chen F., Koufaty D.A., Zhang X. Understanding Intrinsic Characteristics and System Implications of Flash Memory Based Solid State Drives. ACM SIGMETRICS Performance Evaluation Review. 2009; 37(1):181-192. (In Eng.) doi: https://doi.org/10.1145/2492101.1555371
8. Picoli I.L., et al. UFLIP-OC: Understanding Flash I/O Patterns on Open-Channel Solid-State Drives. Proceedings of the 8th Asia-Pacific Workshop on Systems (APSys'17). Association for Computing Machinery, New York, NY, USA; 2017. Article number: 20. p. 1-7. (In Eng.) doi: https://doi.org/10.1145/3124680.3124741
9. Hu X.-Y., et al. Write Amplification Analysis in Flash-based Solid State Drives. Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference (SYSTOR'09). Association for Computing Machinery, New York, NY, USA; 2009. Article number: 10. p. 1-9. (In Eng.) doi: https://doi.org/10.1145/1534530.1534544
10. O'Neil P., et al. The Log-structured Merge-tree (LSM-tree). Acta Informatica. 1996; 33(4):351-385. (In Eng.) doi: https://doi.org/10.1007/s002360050048
11. Chang F., et al. Bigtable: A Distributed Storage System for Structured Data. ACM Transactions on Computer Systems. 2008; 26(2):4. (In Eng.) doi: https://doi.org/10.1145/1365815.1365816
12. DeCandia G., et al. Dynamo: amazon's highly available key-value store. ACM SIGOPS Operating Systems Review. 2007; 41(6):205-220. (In Eng.) doi: https://doi.org/10.1145/1323293.1294281
13. Hassan M.U., et al. A Comprehensive Study of HBase Storage Architecture ‒ A Systematic Literature Review. Symmetry. 2021; 13(1):109. (In Eng.) doi: https://doi.org/10.3390/sym13010109
14. Lakshman A., Malik P. Cassandra ‒ A Decentralized Structured Storage System. ACM SIGOPS Operating Systems Review. 2010; 44(2):35-40. (In Eng.) doi: https://doi.org/10.1145/1773912.1773922
15. Luo C., Carey M.J. LSM-based storage techniques: a survey. The VLDB Journal. 2020; 29(1):393-418. (In Eng.) doi: https://doi.org/10.1007/s00778-019-00555-y
16. Dong S., et al. RocksDB: Evolution of Development Priorities in a Key-Value Store Serving Large-Scale Applications. ACM Transactions on Storage. 2021; 17(4):26. (In Eng.) doi: https://doi.org/10.1145/3483840
17. Alsubaiee S., et al. AsterixDB: A Scalable, Open Source BDMS. Proceedings of the VLDB Endowment. 2014; 7(14):1905-1916. Available at: https://www.vldb.org/pvldb/vol7/p1905-alsubaiee.pdf (accessed 13.01.2022). (In Eng.)
18. Lim H., Andersen D.G., Kaminsky M. Towards Accurate and Fast Evaluation of Multi-stage Log-structured Designs. Proceedings of the 14th Usenix Conference on File and Storage Technologies (FAST'16). Santa Clara, CA: USENIX Association; 2016. p. 149-166. Available at: https://www.usenix.org/system/files/conference/fast16/fast16-papers-lim.pdf (accessed 13.01.2022). (In Eng.)
19. Chambi S., et al. Better Bitmap Performance with Roaring Bitmaps. Software: Practice and Experience. 2016; 46(5):709-719. (In Eng.) doi: https://doi.org/10.1002/spe.2325
20. Lemire D., Ssi-Yan-Kai G., Kaser O. Consistently faster and smaller compressed bitmaps with Roaring”. Software: Practice and Experience. 2016; 46(11):1547-1569. (In Eng.) doi: https://doi.org/10.1002/spe.2402
21. Wang J., et al. An Experimental Study of Bitmap Compression vs. Inverted List Compression. Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD'17). Association for Computing Machinery, Chicago, Illinois, USA; 2017. p. 993-1008. (In Eng.) doi: https://doi.org/10.1145/3035918.3064007
22. Pinar A., Tao T., Ferhatosmanoglu H. Compressing Bitmap Indices by Data Reorganization. Proceedings of the 21st International Conference on Data Engineering (ICDE'05). USA: IEEE Computer Society; 2005. p. 310-321. (In Eng.) doi: https://doi.org/10.1109/ICDE.2005.35
23. Hsu Y.-F., et al. A Novel Automated Cloud Storage Tiering System through Hot-Cold Data Classification. 2018 IEEE 11th International Conference on Cloud Computing (CLOUD). IEEE Press, San Francisco, CA, USA; 2018. p. 492-499. (In Eng.) doi: https://doi.org/10.1109/CLOUD.2018.00069
24. Dayarathna M., Wen Y., Fan R. Data Center Energy Consumption Modeling: A Survey. IEEE Communications Surveys & Tutorials. 2016; 18(1):732-794. (In Eng.) doi: https://doi.org/10.1109/COMST.2015.2481183
25. Liu S., Huang X., Fu H., Yang G. Understanding Data Characteristics and Access Patterns in a Cloud Storage System. 2013 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing. Delft, Netherlands; 2013. p. 327-334. (In Eng.) doi: https://doi.org/10.1109/CCGrid.2013.11
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
