Friday, November 16, 2018

Data Storage Systems

My presentation from from PiterPy Meetup #10 Hardcore about the data structures used in databases for storing and retrieving data.
Two approaches to data processing are considered: OLTP and OLAP.
SQL, NoSQL and New SQL databases are discussed.
The tradeoffs that the developers face when creating storage systems are shown.
Also the methods of data storage and interaction with the database provides CPython are considered.
The presentation and the list of references and books helps more easily navigate the data storage engines and understand which tool is better suited for a particular task.

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.

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

Monday, September 17, 2018

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems by Martin Kleppmann

Finally I've finished reading this awesome book by Martin Kleppmann. It is one of the best technical books I have read. A Lot of useful information with great explanations and schemes.
Special thanks for references after each chapter and of course beautiful maps between chapters :)
This book sparked my interest in databases even more. Thank you Martin for such a good reading! Can't stop to recommend it to everyone!

Thursday, September 13, 2018

LSM tree, Memtable and SSTable

LSM tree (Log-structured merge-tree) is a data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume, such as transactional log data. LSM trees, like other search trees, maintain key-value pairs. LSM trees maintain data in two or more separate structures, each of which is optimized for its respective underlying storage medium; data is synchronized between the two structures efficiently, in batches [1].
LSM trees are used in data stores such as Bigtable, HBase, LevelDB, RocksDB, ScyllaDB, Apache Cassandra, MongoDB, SQLite4, Tarantool, WiredTiger, InfluxDB, etc.

Memtable is in-memory data-structure  that holds the data before it flushed to the SSTables.
In LevelDB, RocksDB and Cassandra the implementation of Memtable is based on skiplist [2] data-structure [3, 4, 5].

SSTable (Sorted Strings Table) is a key-value based persistent, ordered immutable storage [6].
The SSTable contains a sequence of blocks (typically 64 KB in size). At the end of the SSTable an index block is stored.

[1] Log-structured merge-tree
[2] Skip list
[3] Reviewing LevelDB: Part V, into the MemTables we go
[4] MemTable
[5] Apache Cassandra Github: SASIIndex
[6] Bigtable: A Distributed Storage System for Structured Data

Monday, August 20, 2018

PEPFS - Writing file system in CPython

Writing file system in CPython

On last PiterPy meetup I've made a talk about writing simple file system PEPFS in CPython using FUSE (File System In Userspace).

The PEPFS project is available on github:
PEPFS is a simple read-only file system where files are CPython PEPs.
To build file system a fusepy module was used.

Slides are available here and here