Namaran

Code daily. Without assist.

2026-09-23

CrashRecovery.hs

module Main where

import qualified Data.Map as Map

data Entry = Put String Int | Commit deriving Show

recover :: [Entry] -> Map.Map String Int
recover es = foldl step Map.empty es
  where
    step m (Put k v) = Map.insert k v m
    step m Commit = m

main :: IO ()
main = print (Map.toList (recover
  [Put "a" 1, Commit, Put "b" 2, Put "a" 99]))

WALのエントリ列から、直近のクラッシュ後に復元されるべき状態を求めるrecoverです(最後のCommitより後に続くエントリは、まだコミットされていないトランザクションなので復元の対象外です——クラッシュがディスクへ書き終える前に起きた可能性を保証できないためです)。入力は[Put "a" 1, Commit, Put "b" 2, Put "a" 99]("a" 1をコミットした後、次のコミットに達する前にクラッシュしたログ)。いまの出力は[("a",99),("b",2)]ですが、本来の出力は[("a",1)](最後にコミットされていた状態)です。何が問題で、どう直せばよいでしょうか?

Answer

recoverはログの全エントリを、Commitかどうかに関係なくそのままfoldlで適用しています。しかし障害復旧の目的は「最後に確実にディスクへ書き終えた(コミットされた)状態」を復元することであり、最後のCommitより後に残っているエントリは、クラッシュがそれらの書き込みの途中に起きた可能性がある——つまりディスク上で本当に完了しているかどうか保証されない——ため、復元には使ってはいけません。この例ではPut "a" 1, Commitまでが確定した内容で、それに続くPut "b" 2, Put "a" 99はコミットされる前にログが途切れているので捨てるべきです。ところがいまのコードは最後まで全部を適用してしまうため、本来存在しないはずの"a" 99や"b" 2が復元後の状態に紛れ込み、[("a",99),("b",2)]になってしまいます。直し方は、ログを最後のCommitの直後で打ち切ってから畳み込むことです:

recover :: [Entry] -> Map.Map String Int
recover es = foldl step Map.empty (dropTrailingUncommitted es)
  where
    step m (Put k v) = Map.insert k v m
    step m Commit = m

dropTrailingUncommitted :: [Entry] -> [Entry]
dropTrailingUncommitted = reverse . dropWhile notCommit . reverse
  where
    notCommit Commit = False
    notCommit _ = True