Tuesday, March 13, 2018

Гипотеза RUM

Группа разработчиков из DASlab (Лаборатория систем обработки данных) Гарвардской школы инженерных и прикладных наук Джона А. Полсона (SEAS) разработали гипотезу RUM (Read, Update, Memory, то есть Чтение, Обновление/Запись и Память).

Гипотеза RUM описывает повсеместный компромисс между оптимальным чтением, записью и используемой памятью у методов доступа к современным системам данных.

При построении методов доступа к современным системам, каждый сталкивается с одними и теми же фундаментальными задачами и проектными решениями.
Есть три величины, которые исследователи всегда стараются свести к минимуму:
  • накладные расходы на чтение (R)
  • накладные расходы на обновление/запись (U)
  • накладные расходы на память (оперативная память, диск, и др.) (M)
три этих параметра (накладные расходы RUM) образуют треугольник:
Накладные расходы RUM - на чтение, запись и используемую память.

Гипотеза RUM:
разработка методов доступа, которые устанавливают верхнюю границу для двух (из трёх) накладныех расходов (оверхедов) RUM, приводит к жёсткой нижней границе для третьего (оверхеда), которая не может быть дополнительно уменьшена.

TLDR: Чтение, Обновление/Запись, Память  оптимизация двух за счет третьего.

Накладные расходы на чтение выражаются в усилении чтения (read amplification), то есть отношении объёма фактически прочитанных данных к объему необходимых данных.
Аналогично накладные расходы на обновление/запись выражаются в усилении записи (write amplification), а накладные расходы на память в усилении занимаемой памяти (space amplification).
Здесь усилении записи (write amplification)  это отношение объёма фактически записанных данных к реально изменённому, а усиление занимаемой памяти (space amplification) — отношение объёма данных + объём вспомогательных данных таких как индексы и другие метаданные, к объёму самих данных.

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

Структуры с оптимизацией записи  уменьшают накладные расходы на запись, сохраняя обновления во вторичных структурах данных. Основная идея заключается в объединении обновлений с последующим применением к системе управления данными. Примеры: LSM-tree, Partitioned B-tree (PBT), алгоритм Materialized Sort-Merge (MaSM), алгоритм Stepped Merge и Positional  Differential Tree (PDT), и др.

Способы эффективного использования памяти предназначены для уменьшения накладных расходов на хранение данных. К ним относятся методы сжатия и индексы с потерями, такие как Фильтр Блума, HyperLogLog, Count-min sketch, Bitmap, Zonemap, Sparse индексы, и др.

Ссылки:
[1] The RUM Conjecture - DASlab @ Harvard University
[2] Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, et al.: “Designing Access Methods: The RUM Conjecture,” at 19th International Conference on Extending Database Technology (EDBT), March 2016. doi:10.5441/002/edbt.2016.42

No comments:

Post a Comment