Промоделируй восстановление key-value хранилища по write-ahead log (WAL,
журнал упреждающей записи) после краша.
Перед тем как менять данные на диске, СУБД и файловые системы сначала
дописывают запись об изменении в журнал. Если процесс упал, при старте журнал
«проигрывают» заново и восстанавливают согласованное состояние. Ключевое
правило: применять можно только то, что было закоммичено. Изменения,
которые не успели получить запись commit (их оборвал краш), отбрасываются —
иначе мы получили бы半-применённую транзакцию.
Журнал — это срез записей Record{Op, Key, Val}, где Op ∈ {"set", "commit"}:
set — изменение значения ключа в рамках текущей (ещё не зафиксированной)
транзакции;commit — фиксация: все set-записи, накопленные с предыдущего commit,
становятся видимыми.
Реализуй функцию:
func Replay(log []Record) map[string]int
Она должна проиграть журнал и вернуть итоговое состояние хранилища, применив
только изменения транзакций, у которых есть commit. Незакоммиченный хвост
(set без последующего commit) игнорируется. Повторный set того же ключа
перезаписывает значение.
Примеры:
Replay([]Record{
{Op: "set", Key: "x", Val: 1},
{Op: "commit"},
{Op: "set", Key: "x", Val: 99}, // оборвано крашем — не было commit
{Op: "set", Key: "z", Val: 5},
})
// → map[string]int{"x": 1}
Replay([]Record{
{Op: "set", Key: "a", Val: 1},
{Op: "commit"},
{Op: "set", Key: "a", Val: 2},
{Op: "set", Key: "b", Val: 7},
{Op: "commit"},
})
// → map[string]int{"a": 2, "b": 7}
Краевые условия:
- пустой журнал → пустая (непустая по len, но без ключей)
map[string]int{};
- весь журнал закоммичен → применяются все транзакции;
- последняя транзакция оборвана (нет
commit) → её set-записи отбрасываются.
Тип Record уже определён (поля Op, Key, Val). Подробнее про долговечность
записи и fsync — в главе «fsync и долговечность».