Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила

Гоц Грейф
Пересказ: Сергей Кузнецов

Оригинал: Goetz Graefe. The Five-minute Rule: 20 Years Later and How Flash Memory Changes the Rules, ACM QUEUE, July/August 2008

Назад Содержание

Резюме и выводы

Правило пяти минут двадцатилетней давности для основной памяти и дисков продолжает действовать, но для гораздо более крупных дисковых страниц. Кроме того, его следует дополнить двумя новыми правилами пяти минут: одно для небольших страниц, перемещающихся между основной памятью и флэш-памятью, и другое – для крупных страниц, перемещающихся между флэш-памятью и традиционными дисками. Для небольших страниц, перемещающихся между основной памятью и дисками, Грей и Пуцолу поразительно точно предсказали появление через двадцать лет пятичасового интервала равнозатратности.

Исследования флэш-памяти и ее места в системной архитектуре являются неотложными и важными. Через несколько лет флэш-память будет использоваться для ликвидации разрыва между традиционной основной памятью и традиционными дисковыми устройствами во многих операционных системах, файловых системах и системах баз данных.

Флэш-память можно использовать для расширения основной памяти или персистентного хранилища. В данной статье эти модели называются «расширенным буферным пулом» и «расширенным диском». Обе модели кажутся жизнеспособными в операционных системах, файловых системах и системах баз данных. Однако из-за особенностей характеристик этих систем в них будут применяться разные модели использования.

В обеих моделях содержимое основной памяти и флэш-памяти будет управлять алгоритмами замещения в стиле LRU, которые направлены на то, чтобы удерживать более полезные страницы в основной памяти, а менее полезные страницы – на традиционных дисках. Связанный список или другая структура данных, реализующая политику замещения для флэш-памяти, будет поддерживаться в основной памяти.

В операционных системах и файловых системах флэш-память будет, главным образом, использоваться как временное хранилище (например, как быстрая резервная копия виртуальной памяти или как дополнительный кэш файловой системы). Оба эти вида применения относятся к модели расширенного буферного пула. При выполнении запланированного останова системы содержимое флэш-памяти могло бы записываться в персистентное хранилище. Однако при отказе системы описание содержимого флэш-памяти, сохраняемое в основной памяти, будет утрачено, и его потребуется реконструировать путем анализа содержимого способом, очень близким к тому, который применяется при восстановлении традиционных файловых систем. В качестве альтернативы содержимое флэш-памяти можно было бы аннулировать и загружать по требованию.

С другой стороны, в системах баз данных флэш-память будет использоваться как персистентное хранилище на основе модели расширенного диска. Текущее содержимое будет описываться персистентными структурами данных (например, родительскими узлами индексов на основе B-деревьев). Традиционные механизмы поддержки долговечности данных (в частности, журнализация и контрольные точки) обеспечивают согласованность данных и их эффективное восстановление после отказов системы. При запланированном останове системы нет потребности в переписи содержимого флэш-памяти на диск.

Имеются две причины использования разных моделей флэш-памяти. Во-первых, системы баз данных полагаются на регулярное выполнение операций установки контрольных точек, во время которого измененные страницы выталкиваются из буферного пула в персистентное хранилище. Перемещение измененной страницы из основной памяти в расширенный буферный пул во флэш-памяти приводит к существенным накладным расходам при выполнении следующей операции установки контрольной точки. Необходимо найти свободный буфер в основной памяти, прочитать в основную память содержимое страницы из флэш-памяти и затем записать эту страницу на диск. Совершенно ни к чему добавлять такие накладные расходы к операции установки контрольной точки, которая в системах баз данных выполняется довольно часто. С другой стороны, в операционных системах и файловых системах контрольные точки не используются, и поэтому в них флэш-память можно использовать как расширенный буферный пул.

Во-вторых, в основных персистентных структурах данных баз данных – B-деревьях – обеспечиваются механизмы отображения и отслеживания местоположений, требующие выполнения частых перемещений и замещений страниц. Следовательно, для отслеживания местоположения страницы данных при ее перемещении между диском и флэш-памятью можно использовать ту же структуру данных, которая поддерживается для обеспечения эффективного поиска в базе данных. Кроме того, что удается обойтись без описателей буферного пула и т.д. для страниц во флэш-памяти, отсутствие косвенности при адресации страницы позволяет максимально ускорить поиск в базе данных.

Наконец, поскольку у флэш-памяти и дисков существенно отличаются соотношения времени задержки доступа и скорости передачи данных, для них являются оптимальными разные размеры узлов B-дерева. О’Нейл в своей работе о SB-дереве показывает, что в многоуровневой иерархии памяти требуются два разных размера узлов. Для перемещения отдельных страниц требуются недорогие механизмы, точно такие же, как те, которые нужны для перемещения страниц между флэш-памятью и диском.

Благодарности

Эта статья посвящается Джиму Грею, который посоветовал выполнить данное исследование и много раз в разных обстоятельствах помогал как автору, так и многим другим исследователям. Барб Питерс (Barb Peters), Лили Джоу (Lily Jow), Харуми Куно (Harumi Kuno), Хосе Блейкли (José Blakeley), Мехул Шах (Mehul Shah) и рецензенты DaMoN 2007 внесли несколько предложений по улучшению статьи после прочтения ее раннего варианта.

Литература

1. Gray, J., Putzolu, G.R. 1987. The 5-minute rule for trading memory for disk accesses and the 10-byte rule for trading memory for CPU time. SIGMOD Record 16(3): 395-398.
2. Gray, J., Graefe, G. 1997. The five-minute rule ten years later, and other computer storage rules of thumb. SIGMOD Record 26(4): 63-68.
3. Larus, J.R., Rajwar, R. 2007. Transactional Memory. Synthesis Lectures on Computer Architecture. Morgan and Claypool.
4. Hamilton, J. 2007. An architecture for modular data centers. CIDR (Conference on Innovative Data Systems Research).
5. Gray, J., Fitzgerald, B. Flash Disk Opportunity for Server-Applications.
6. Härder, T., Reuter, A. 1983. Principles of transaction-oriented database recovery. ACM Computing Surveys 15(4): 287-317.
7. Chen, P.M., Lee, E.L., Gibson, G.A., Katz, R.H., Patterson, D.A. 1994. RAID: High-performance, reliable secondary storage. ACM Computing Surveys 26(2): 145-185.
8. See reference 7.
9. Ousterhout, J.K., Douglis, F. 1989. Beating the I/O bottleneck: A case for log-structured file systems. Operating Systems Review 23(1): 11-28.
10. Woodhouse, D. 2001. JFFS: the Journaling Flash File System. Ottawa Linux Symposium. Red Hat Inc.
11. See reference 1.
12. See reference 1.
13. See reference 2.
14. See reference 1.
15. See reference 5.
16. See reference 1.
17. See reference 2.
18. Graefe, G. 2007. Master-detail clustering using merged indexes. Informatik – Forschung und Entwicklung 21 (3-4): 127-145.
19. Carey, M.J., DeWitt, D.J., Richardson, J.E., Shekita, E.J. 1989. Storage management in EXODUS. Object-Oriented Concepts, Databases, and Applications: 341-369.
20. Stonebraker, M. 1981. Operating system support for database management. Communications of the ACM 24(7): 412-418 .
21. Graefe, G. 2004. Write-optimized B-trees. VLDB: 672-683.
22. See reference 21.
23. See reference 2.
24. Bayer, R., McCreight, E.M. 1970. Organization and maintenance of large ordered indexes. SIGFIDET Workshop: 107-141.
25. Bayer, R., Unterauer, K. 1977. Prefix B-trees. ACM Transactions on Database Systems 2(1): 11-26.
26. O’Neil, P.E. 1992. The SB-Tree: An index-sequential structure for high-performance sequential access. Acta Informatica 29(3): 241-265.
27. Lomet, D.B. 2001. The evolution of effective B-tree page organization and techniques: A personal account. SIGMOD Record 30(3): 64-69.
28. Bender, M.A., Demaine, E.D., Farach-Colton, M. 2005. Cache-oblivious B-trees. SIAM Journal on Computing 35(2): 341-358.
29. Graefe, G. 2006. Implementing sorting in database systems. ACM Computing Surveys 38(3).
30. Nyberg, C., Barclay, T., Cvetanovic, Z., Gray, J., Lomet, D.B. 1995. AlphaSort: A cache-sensitive parallel external sort. VLDB Journal 4(4): 603-627.
31. Rivoire, S., Shah, M. Ranganathan, P., Kozyrakis, C. 2007. JouleSort: A balanced energy-efficiency benchmark. SIGMOD.
32. Shatdal, A., Kant, C., Naughton, J.F. 1994. Cache-conscious algorithms for relational query processing. VLDB: 510-521.
33. DeWitt, D.J., Naughton, J.F., Burger, J. 1993. Nested loops revisited. PDIS: 230-242.
34. Graefe, G. 2003. Executing nested queries. BTW: 58-77.
35. See reference 24.
36. See reference 18.
37. Härder, T. 1978. Implementing a generalized access path structure for a relational database system. ACM Transactions on Database Systems 3(3): 285-298.

Назад Содержание