2020-db-lsm

Курсовой проект 2020 года курса "Использование баз данных" в Технополис.

Этап 1. In-memory (deadline 2020-04-21)

Fork

Форкните проект, склонируйте и добавьте upstream:

$ git clone git@github.com:<username>/2020-db-lsm.git
Cloning into '2020-db-lsm'...
...
$ cd 2020-db-lsm
$ git remote add upstream git@github.com:polis-mail-ru/2020-db-lsm.git
$ git fetch upstream
From github.com:polis-mail-ru/2020-db-lsm
 * [new branch]      master     -> upstream/master

Make

Так можно запустить интерактивную консоль:

$ ./gradlew run

А вот так -- тесты:

$ ./gradlew test

Develop

Откройте в IDE -- IntelliJ IDEA Community Edition нам будет достаточно.

В своём Java package ru.mail.polis.<username> реализуйте интерфейс DAO, используя одну из реализаций java.util.SortedMap.

Возвращайте свою реализацию интерфейса в DAOFactory.

Продолжайте запускать тесты и исправлять ошибки, не забывая подтягивать новые тесты и фиксы из upstream. Если заметите ошибку в upstream, заводите баг и присылайте pull request ;)

Report

Когда всё будет готово, присылайте pull request в master со своей реализацией на review. Не забывайте отвечать на комментарии в PR и исправлять замечания!

Этап 2. Persistence (deadline 2020-05-12)

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

Как и раньше необходимо обеспечить прохождение тестов PersistenceTest, а также приветствуется добавление новых тестов отдельным pull request'ом.

Этап 3. Compaction (deadline 2020-05-19)

На данном этапе необходимо реализовать (блокирующий) метод DAO.compact(), который должен устранять устаревшие версии ячеек на диске, чтобы не занимать лишнее место.

Необходимо обеспечить прохождение тестов CompactionTest.

Референсные реализации:

LSM
Cassandra
LevelDB, но без дополнительных индексов, сжатия и Bloom Filter

Менее очевидные моменты:

Помните о лимите -Xmx128m -- необходимо начинать сбрасывать данные на диск до возникновения OutOfMemoryException
Удаления (a.k.a. tombstone) тоже нужно хранить, иначе это чревато "возрождением" удалённых значений
Необходимо каким-либо образом упорядочивать значения для одного ключа по времени, чтобы возвращать наиболее "свежее"
Эффективность навигации до from элемента при реализации DAO.iterator() -- линейная сложность неприемлема

Этап 4. Bonus (deadline 2020-05-26)

После реализации всех предыдущих этапов, необходимо выбрать одну из незанятых фич, описанных ниже, и обсудить с преподавателем предполагаемый способ реализации.

При реализации фичи допускается изменение API DAO.

Добавление тестов, демонстрирующих работоспособность реализации, является обязательным.

Durability (WAL)

Гарантирует durability (отсутствие потерь подтверджённых записей/удалений) даже в случае "падения" процесса за счёт того, что операции модификации подтверджаются только после того, как попадут в write-ahead-log. При инициализации стораджа обнаруженные записи WAL "проигрываются" перед началом обслуживания новых операций. Устаревшие WAL должны ротироваться, чтобы не занимать лишнее место на диске.

Существуют разные подходы к реализации sync() на диск.

Reverse Iterator

Текущий интерфейс DAO позволяет итерироваться по данным только в лексикографическом порядке. Требуется реализовать возможность корректной итерации в обратном порядке, т.е. добавить метод descendingRange().

Expiration

Операция upsert() должна принимать опциональный параметр Time-To-Live (TTL) или время, после которого ячейка должна "пропасть".

"Протухшие" ячейки не должны отдаваться клиентам и должны вычищаться при compaction.

Compression

Необходимо реализовать блочную компрессию в файлах на диске и не забыть про compaction.

Streaming

Необходимо реализовать механизм для записи и чтения значений больше чем Java Heap, например, принимая InputStream и выдавая OutputStream в качестве значения.

Atomic Batches

Необходимо реализовать возможность атомарного применения набора модификаций (upsert или remove).

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

Transactions

Необходимо обеспечить возможность транзакционного выполнения набора любых операций (upsert/remove/get). При возникновении конфликта (любой другой транзакции, работающей с теми же ключами несовместимым способом, т.е. не read/read конфликта) клиент должен получать ConcurrentModificationException. Пример реализации -- NewSQL.

Bloom Filters

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

Очевидно, что это будет работать только в случае "точечных", а не range-запросов.

Column Families

Поддержка независимых таблиц/keyspace/database/namespace/whatever.

Snapshots

Получение слепка БД на текущий момент времени с возможностью чтения из него вне зависимости от "развития" основной БД.

Здесь могут помочь hard links.

Custom Comparators

Возможность указания клиентом пользовательского Comparator вместо лексикографического.

Real 64-bit

Support for files >2GB
Unit tests for >2G keys

zvladn7/2020-db-lsm