Skip to content

ITMO-MPP/distributed-merge

Repository files navigation

Алгоритм распределённого слияния

В этом задании вы реализуете алгоритм распределённого слияния N отсортированных последовательностей.

Постановка задачи

В файлах DataHolder.kt и Merger.kt находятся описания интерфейсов, которые вам предстоит реализовать. Свой код вы должны писать на языке Kotlin в файлах DataHolderImpl.kt и MergerImpl.kt.

Допустима также реализация на Java. Для этого, как и в предыдущих заданиях, удалите файлы DataHolderImpl.kt и MergerImpl.kt и вместо них добавьте файлы с Java-кодом, в которых реализуйте аналогичные классы.

Описание интерфейса DataHolder

DataHolder-процесс хранит отсортированный список ключей и отдаёт ключи Merger-процессам для слияния.

Передача ключей Merger-процессам

  • fun getBatch(): List<T> — передаёт Merger-процессу пакет ключей размера batchSize. Если ключей осталось меньше batchSize, то нужно вернуть все оставшиеся ключи (в частности, если ключей не осталось вообще, необходимо вернуть пустой список). Во всех остальных случаях необходимо вернуть пакет, размер которого в точности равен batchSize.

Обработка ошибок

Производящий объединение Merger-процесс может в любой момент отказать. В этом случае, объединение необходимо продолжить на новом Merger-процессе. Объединение на новом процессе должно быть продолжено с того же самого места, с которого объединение началось на отказавшем процессе.

  • fun checkpoint() — сохраняет текущее состояние DataHolder-процесса, чтобы его можно было восстановить в случае сбоя Merger-процесса.
  • fun rollback() — вызывается в случае сбоя Merger-процесса и загружает последнее сохранённое состояние.

Окружение DataHolder-процесса

Через ссылку на объект DataHolderEnvironment DataHolder-процесс может узнать batchSize — требуемый размер пакета ключей.

Описание интерфейса Merger

Merger-процесс выполняет операцию распределённого слияния, запрашивая пакеты ключей у DataHolder-процессов.

Реализуемые операции

  • Конструктор класса MergerImpl.kt принимает Map<Int, List<T>>? — отображение из идентификатора DataHolder-процесса в остаток пакета ключей, полученного от этого DataHolder-процесса. Эти пакеты были получены предыдущим Merger-процессом, но не были использованы (так как у предыдущего Merger-процесса закончилось место на диске). Все списки в отображении непусты — если весь пакет ключей, полученных с определённого DataHolder-процесса, был израсходован ранее, то идентификатор этого DataHolder-процесса не будет присутствовать в отображении. Если текущий Merger-процесс является первым, то вместо отображения ему в конструктор передаётся null.
  • fun mergeStep(): T? — возвращает ключ, который должен быть следующим в сливаемой последовательности. Если ключей в сливаемой последовательности не осталось, процесс должен вернуть null.
  • fun getRemainingBatches(): Map<Int, List<T>> — возвращает отображение из идентификатора DataHolder-процесса в остаток пакета ключей, полученного от этого DataHolder-процесса по описанным выше правилам. Заметьте, что в возвращаемом отображении не должно быть пустых списков: если некоторому DataHolder-процессу должен быть сопоставлен пустой список, идентификатор этого DataHolder-процесса не должен присутствовать в отображении.

Окружение Merger-процесса

Через ссылку на объект MergerEnvironment Merger-процесс может:

  • val dataHoldersCount: Int — узнать, сколько DataHolder-процессов существует в системе. DataHolder-процессы системы пронумерованы целыми числами в диапазоне [0; dataHoldersCount - 1].
  • fun requestBatch(dataHolderId: Int): List<T> — запросить пакет ключей у DataHolder-процесса с идентификатором dataHolderId. Заметьте, что запрашивать ключи можно только если вы исчерпали весь запас ключей, полученных от этого процесса ранее.

Тестирование

Тестирования реализации происходит путем запуска теста SolutionTest. Из командной строки: ./gradlew test.

Формат сдачи

  • Выполняйте задание в этом репозитории.
  • Код DataHolder-процесса должен быть реализован в одном файле DataHolderImpl.kt или src/DataHolderImpl.java.
  • Код Merger-процесса должен быть реализован в одном файле MergerImpl.kt или src/MergerImpl.java.
  • Не меняйте остальные файлы в репозитории.

Инструкции по сдаче заданий находятся в этом документе.

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages