Tuesday, October 16, 2018

SPARROW theorem and RUM Conjecture

I've found a post in RocksDB blog about the SPAce, Read Or Write (SPARROW) theorem, which states that:
1. Read Amplification (RA) is inversely related to Write Amplification (WA)
2. Write Amplification (WA) is inversely related to Space Amplification (SA)

Seems like the same, but more detailed principles are described in RUM Conjecture paper.

Sunday, October 14, 2018

Периодическая таблица структур данных

Группа исследователей из Гарварда под руководством профессора Стратоса Идреоса опубликовала интересную работу "The Periodic Table of Data Structures" [1] (Периодическая таблица структур данных или даже Периодическая система структур данных), в которой они пытаются систематизировать существующие структуры данных путём их декомпозиции на части – основные принципы, то есть минимальные структуры данных (например связный список).
Полученная в итоге модель позволяет увидеть какие структуры данных ещё остаются малоизученными или требуют оптимизации, а также получить лучшие результаты производительности путём комбинирования и настройки существующих структур данных.

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

В работе также предлагается понятие design continuums (континуумы дизайна или континуумы проектирования) – часть пространства проектирования структур данных, которое можно рассматривать как единое, потому что оно определяется одним и тем же набором основных принципов. Структурируя пространство проектирования, можно заметить такие континуумы в классах структур данных, которые традиционно считались принципиально разными.

Данная работа тесно связана с другой работой под названием "Data Calculator" [2, 3] (Калькулятор данных), в которой исследователи пытаются разработать интерактивный, полуавтоматический подход для генерации и проектирования структур данных.

Ранее они же предложили гипотезу RUM про которую я уже писал в блоге.

Ссылки:
[1] S. Idreos, et al., “The Periodic Table of Data Structures,” Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, vol. 41, no. 3, pp. 64-75, 2018.
[2] S. Idreos, K. Zoumpatianos, B. Hentschel, M. Kester, and D. Guo. The Data Calculator: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models. SIGMOD, 2018.
[3] S. Idreos, K. Zoumpatianos, B. Hentschel, M. Kester, and D. Guo. The Internals of the Data Calculator, 2018.

Tuesday, October 9, 2018

Epoch protection

Epoch protection is a technique to avoid expensive synchronization between threads.

References:
[1] Keir Fraser: Practical lock-freedom
[2] Faster: A Concurrent Key-Value Store with In-Place Updates