2023-nosql-lsm

Проект курса "NoSQL"

Этап 1. In-memory (deadline 27.09.23 23:59:59 MSK)

Fork

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

$ git clone git@github.com:<username>/2023-nosql-lsm.git
Cloning into '2023-nosql-lsm'...
...
$ git remote add upstream git@github.com:polis-vk/2023-nosql-lsm.git
$ git fetch upstream
From github.com:polis-vk/2023-nosql-lsm
 * [new branch]      main     -> upstream/main

Make

Так можно запустить тесты (ровно то, что делает CI):

$ ./gradlew clean test

Develop

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

ВНИМАНИЕ! При запуске тестов или сервера в IDE необходимо передавать Java опцию -Xmx64m.

Сделать имплементацию интерфейса DAO, заставив пройти все тесты. Для этого достаточно реализовать две операции: get и upsert, при этом достаточно реализации "в памяти".

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

Report

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

Этап 2. Persistence (deadline 2023-10-04 23:59:59 MSK)

Приведите код в состояние, удовлетворяющее новым тестам. А именно: при конструировании DAO следует восстановить состояние, персистентно сохраненное в методе close(). Нужно реализовать метод get(key), который будет возвращать Entry, сохраненной в памяти или в хипе.

В DaoFactory.Factory появился конструктор createDao(Config config), который нужно переопределить в своей реализации. Config Содержит в себе basePath - директория для сохранения состояния DAO.

В новых тестах не предполагается использование полноценной реализации метода get(from, to).

Report

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

Этап 3. Merge Iterator (deadline 2023-10-18 23:59:59 MSK)

Приведите код в состояние, удовлетворяющее данным запросам:

• Бинарный поиск по файлу теперь является обязательным для реализации.
• Метод get(from, to) должен работать полноценно и полностью поддерживаться DAO даже при наличии в ней данных, записанных в файл.
• Стоит учитывать, что в диапазоне от from до to, некая часть данных может уже находиться в файле на диске, в то время, как другая часть будет все еще InMemory. Несмотря на это, необходимо уметь последовательно отдавать все данные в правильно отсортированном порядке.
• Запрошенный диапазон значений может быть слишком велик, чтобы держать его полностью в памяти, нужно динамически подгружать лишь необходимую в данный момент часть этого диапазона.
• За один тест метод close у конкретного инстанса DAO может быть вызван только один раз, однако после этого имеется возможность создать новый инстанс с тем же config(т.е будет произведено переоткрытие DAO). В отличие от прошлого этапа, в этот раз в DAO можно будет писать новую информацию, а не только читать старую из него. Количество таких переоткрытий за один тест неограниченно. Следовательно, должна поддерживаться возможность создания соответствующего количества файлов, содержащих данные нашей БД - по одному на каждый close, а так же возможность поиска значений по всем этим файлам.
• После использования метода close, Entry с уже записанным до этого в файл ключом может быть добавлено в последующие DAO еще несколько раз, т.е текущее значение, соответствующее этому ключу, будет таким образом перезаписано, однако старые значения, соответствующие этому же ключу, все еще будут находиться в более ранних файлах. База данных должна суметь выдать самое свежее для запрошенного ключа значение при поиске из всех имеющихся.
• На данный момент метод flush будет вызываться только из метода close. Таким образом, flush будет гарантированно выполняться однопоточно, также на данном этапе можно рассчитывать на то, что get и upsert в процессе выполнения метода flush вызываться не будут, однако во все остальное время get и upsert могут работать в многопоточном режиме - старые тесты на concurrency никуда не пропадают, но могут появиться и новые. Считаем, что поведение get и upsert после отработки метода close - undefined
• upsert с value == null подразумевает удаление: такие записи не должны возвращаться в get.

Report

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

Этап 4. Compact (deadline 2023-11-01 23:59:59 MSK)

Требуется реализовать метод compact() в DAO:

• Все SSTable'ы должны быть слиты в один, включая как таблицы на диске, так и таблицу в памяти
• Старые должны быть удалены
• Должна сохраниться только самая свежая версия, старые записи должны быть удалены
• Удалённые записи (upsert с null-значением) не должны сохраняться при сompact()
• В рамках данного задания гарантируется, что сразу после compact() будет вызван метод close(), а значит работа с этим DAO больше производиться не будет. Но в последствии может быть открыто новое DAO c тем же конфигом. И на нём тоже может быть вызван compact.
• close() обязан быть идемпотентным -- повторный close() не должен приводить к отрицательным последствиям, включая потерю производительности. На текущем этапе можно считать, что конкуретных вызовов close() нет.
• Тесты будут появляться и дополняться

Report

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

Этап 5. Thread safety (deadline 2023-11-22 23:59:59 MSK)

Требуется обеспечить потокобезопаность всех методов Dao, т.е. любые методы могут вызываться одновременно из разных потоков и поведение должно быть корректным, включая итерирование по данным (кроме как после вызова close(), о чём см. ниже). NB! Под "не блокирует" ниже понимается отсутствие блокировок длительностью более нескольких миллисекунд.

flush()

• В классе Config появился порог flushThresholdBytes
• При превышении размера таблицы в памяти указанного порога должен запускаться автоматический фоновый flush (не блокирующий другие методы Dao)
• В случаях, когда flush не поспевает за вставкой данных (одна полная таблица всё ещё пишется на диск, в то время как заполнилась следующая таблица), параллельные upsert()ы должны бросать исключение -- тем самым мы сигнализируем клиенту о перегрузке и избегаем падения по OutOfMemory
• Запускается в фоновом режиме (не блокирует другие методы Dao)
• В процессе flush все данные должны быть доступны на чтение

compact()

• Вызывается вручную, но из любого потока и сколько угодно раз на протяжении жизни Dao
• Компактит данные только на диске (в отличие от предыдущего этапа)
• Запускается в фоновом режиме (не блокирует другие методы Dao)
• В процессе compact все данные должны быть доступны на чтение

close()

• Блокируется до окончания фоновых операций flush()/compact(), если таковые имеются
• Корректно освобождает все ресурсы, в т.ч. пулы потоков
• Обязан быть идемпотентным -- повторный close() не должен приводить к отрицательным последствиям
• Поведение всех других методов Dao после вызова close() не определено, включая итерирование по предварительно полученному Iterator

Report

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

Бонусные задания (deadline 2023-12-06 23:59:59 MSK)

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

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

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

Feedback

Развёрнутая конструктивная обратная связь по курсу: достоинства и недостатки курса, сложность тем, предложения по улучшению.

Autocompact

Регулярный автоматический фоновый compaction.

Durability (WAL)

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

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

Reverse Iterator

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

Expiration

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

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

Compression

Необходимо реализовать блочную компрессию в файлах на диске (используя готовые реализации LZ4, Snappy или zstd) и не забыть про 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

• Поддержка файлов больше 2ГБ
• Модульные тесты для ключей/значений больше 2ГБ