LSM-индекс с общими компонентами для индексации хронологических данных
Аннотация
Современная эпоха характеризуется взрывным ростом объема хранимых и обрабатываемых данных. В таких условиях особенно важными становятся производительность хранения и индексации данных во внешней памяти. Существует множество приложений, требующих доступа к истории изменения данных, таких как приложения резервного копирования, информационные системы в банковской сфере, медицине и т. д. Данные с историей, т. е. объекты, имеющие время жизни в определенной шкале времени, называются хронологическими.
Предлагается новый алгоритм индексации хронологических данных, LSM с общими компонентами, который сочетает в себе возможность хранения части индекса во внешней памяти, эффективность операций записи во внешнюю память (запись всегда выполняется в последовательном режиме), не зависящее от количества версий объектов время выполнения запросов по диапазону ключей при фиксированном времени, а также возможность разделения "исторических" ("холодных") данных и их хранения на отдельных носителях.
Алгоритм был теоретически проанализирован, реализован и протестирован. Его поведение было изучено в сравнении с известными подходами для нескольких вариантов использования.
Литература
2. Leavitt N. Will NoSQL Databases Live Up to Their Promise? Computer. 2010; 43(2):12-14. (In Eng.) doi: https://doi.org/10.1109/MC.2010.58
3. O'Neil P., Cheng E., Gawlick D., O'Neil E. The Log-structured Merge-tree (LSM-tree). Acta Informatica. 1996; 33(4):351-385. (In Eng.) doi: http://dx.doi.org/10.1007/s002360050048
4. Lomet D., Salzberg B. Access Methods for Multiversion Data. ACM SIGMOD Record. 1989; 18(2):315-324. (In Eng.) doi: https://doi.org/10.1145/66926.66956
5. Segev A., Shoshani A. Logical Modeling of Temporal Data. ACM SIGMOD Record. 1987; 16(3):454-466. (In Eng.) doi: https://doi.org/10.1145/38714.38760
6. Jensen C.S., Clifford J., Gadia S.K., Segev A., Snodgrass R.T. A Glossary of Temporal Database Concepts. ACM SIGMOD Record. 1992; 21(3):35-43. (In Eng.) doi: https://doi.org/10.1145/140979.140996
7. Tsotras V.J., Kangelaris N. The Snapshot Index: An I/O-optimal Access Method for Timeslice Queries. Information Systems. 1995; 20(3):237-260. (In Eng.) doi: https://doi.org/10.1016/0306-4379(95)00011-R
8. Bertino E., et al. Indexing Techniques for Advanced Database Systems. The Springer International Series on Advances in Database Systems. Vol. 8. Springer, Boston, MA; 1997. 250 p. (In Eng.) doi: https://doi.org/10.1007/978-1-4615-6227-6
9. Anderson D., Dykes J., Riedel E. More Than an Interface ‒ SCSI vs. ATA. Proceedings of FAST ’03: 2nd USENIX Conference on File and Storage Technologies. San Francisco, CA: USENIX Association; 2003. p. 245-257. Available at: https://www.usenix.org/legacy/events/fast03/tech/full_papers/anderson/anderson.pdf (accessed 17.05.2022). (In Eng.)
10. 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
11. Picoli I.L., Pasco C.V., Jónsson B.Þ, Bouganim L., Bonnet P. uFLIP-OC: Understanding Flash I/O Patterns on Open-Channel Solid-State Drives. Proceedings of the 8th Asia-Pacific Workshop on Systems (APSys'17). Mumbai, India: Association for Computing Machinery; 2017. Article number: 20. p. 1-7. (In Eng.) doi: https://doi.org/10.1145/3124680.3124741
12. Hu X.-Y., Eleftheriou E., Haas R., Iliadis I., Pletka R. 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
13. Bayer R., Mccreight E.M. Organization and Maintenance of Large Ordered Indexes. Acta Informatica. 1972; 1(3):173-189. (In Eng.) doi: https://doi.org/10.1007/BF00288683
14. Comer D. The Ubiquitous B-Tree. ACM Computing Surveys. 1979; 11(2):121-137. (In Eng.) doi: https://doi.org/10.1145/356770.356776
15. Graefe G. Modern B-Tree Techniques. Foundations and Trends® in Databases. 2011; 3(4):203-402. (In Eng.) doi: http://dx.doi.org/10.1561/1900000028
16. Ang C.-H., Tan K.-P. The Interval B-tree. Information Processing Letters. 1995; 53(2):85-89. (In Eng.) doi: https://doi.org/10.1016/0020-0190(94)00176-Y
17. Becker B., Gschwind S., Ohler T., Seeger B., Widmayer P. An Asymptotically Optimal Multiversion B-tree. The VLDB Journal. 1996; 5(4):264-275. (In Eng.) doi: https://doi.org/10.1007/s007780050028
18. Elmasri R., Wuu G.T.J., Kim Y.-J. The Time Index: An Access Structure for Temporal Data. Proceedings of the 16th International Conference on Very Large Data Bases (VLDB'90). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 1990. p. 1-12. Available at: https://www.vldb.org/dblp/db/conf/vldb/ElmasriWK90.html (accessed 17.05.2022). (In Eng.)
19. Goh C.H., Lu H., Ooi B.-C., Tan K.-L. Indexing Temporal Data Using Existing B+-trees. Data & Knowledge Engineering. 1996; 18(2):147-165. (In Eng.) doi: https://doi.org/10.1016/0169-023X(95)00034-P
20. Gottstein R., Goyal R., Hardock S., Petrov I., Buchmann A. MV-IDX: indexing in multi-version databases. Proceedings of the 18th International Database Engineering & Applications Symposium (IDEAS'14). Association for Computing Machinery, New York, NY, USA; 2014. p. 142-148. (In Eng.) doi: https://doi.org/10.1145/2628194.2628911
21. Shen H., Ooi B.C., Lu H. The TP-Index: A Dynamic and Efficient Indexing Mechanism for Temporal Databases. Proceedings of 1994 IEEE 10th International Conference on Data Engineering. Washington, DC, USA: IEEE Computer Society; 1994. p. 274-281. (In Eng.) doi: https://doi.org/10.1109/ICDE.1994.283041
22. 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
23. 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 17.05.2022). (In Eng.)
24. Dong S., Callaghan M.D., Galanis L., Borthakur D., Savor T., Strum M. Optimizing Space Amplification in RocksDB. Proceedings of the 8th Biennial Conference on Innovative Data Systems Research (CIDR 2017). Chaminade, CA, USA; 2017. p. 1-9. Available at: https://www.cidrdb.org/cidr2017/papers/p82-dong-cidr17.pdf (accessed 17.05.2022). (In Eng.)
25. Petrov A. Algorithms Behind Modern Storage Systems. Communications of the ACM. 2018; 61(8):38-44. (In Eng.) doi: https://doi.org/10.1145/3209210
26. Qader M.A., Cheng S., Hristidis V. A Comparative Study of Secondary Indexing Techniques in LSM-based NoSQL Databases. Proceedings of the 2018 International Conference on Management of Data (SIGMOD'18). Houston, TX, USA: ACM; 2018. p. 551-566. (In Eng.) doi: https://doi.org/10.1145/3183713.3196900
27. Wang P., Sun G., Jiang S., Ouyang J., Lin S., Zhang C., Cong J. An Efficient Design and Implementation of LSM-tree Based Key-value Store on Open-channel SSD. Proceedings of the Ninth European Conference on Computer Systems (EuroSys'14). Amsterdam, The Netherlands: ACM; 2014. Article number: 16. p. 1-14. (In Eng.) doi: https://doi.org/10.1145/2592798.2592804
28. Yang F., Dou K., Chen S., Hou M., Kang J. -U., Cho S. Optimizing NoSQL DB on Flash: A Case Study of RocksDB. 2015 IEEE 12th Intl Conf on Ubiquitous Intelligence and Computing and 2015 IEEE 12th Intl Conf on Autonomic and Trusted Computing and 2015 IEEE 15th Intl Conf on Scalable Computing and Communications and Its Associated Workshops (UIC-ATC-ScalCom). IEEE Computer Society; 2015. p. 1062-1069. (In Eng.) doi: https://doi.org/10.1109/UIC-ATC-ScalCom-CBDCom-IoP.2015.197
29. Lersch L., Oukid I., Lehner W., Schreter I. An Analysis of LSM Caching in NVRAM. Proceedings of the 13th International Workshop on Data Management on New Hardware (DAMON'17). Association for Computing Machinery, New York, NY, USA; 2017. Article number: 9. p. 1-5. (In Eng.) doi: https://doi.org/10.1145/3076113.3076123
30. Muth P., O'Neil P., Pick A., Weikum G. The LHAM Log-structured History Data Access Method. The VLDB Journal. 2000; 8(3-4):199-221. (In Eng.) doi: https://doi.org/10.1007/s007780050004
31. Singhal M. Update transport: a new technique for update synchronization in replicated database systems. IEEE Transactions on Software Engineering. 1990; 16(12):1325-1336. (In Eng.) doi: https://doi.org/10.1109/32.62441
Это произведение доступно по лицензии 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.
