###### tags: `memo` `systems`
# LEC 15 Logging

Slide URL: http://web.mit.edu/6.033/www/lec/s17-partial.pdf

## 前回の話
- 以下の機能を提供するトランザクションを実装する方法を検討
- 原子性
- 分離
- shadow copies で原子性を実現してみた
- ただし、パフォーマンス面は…

## 今回の話
- 原子性を実現する別の方法、logging

## Logging
### :one: 基本
以下の一連の処理をログに記録する

begin
write(A, 100)
write(A, 50)
commit

begin
write(A, read(A) - 20)
write(Bm read(B) + 20)
commit

begin
write(A, read(A) + 30)
crash!

ログは以下の通り

|No|TransactionID|Type|OldValue|NewValue|
|-|-|-|-|-|
|1|T1|UPDATE|A = 0|A = 100|
|2|T1|UPDATE|B = 0|B = 50|
|3|T1|COMMIT|||
|4|T2|UPDATE|A = 100|A = 80|
|5|T2|UPDATE|B = 50|B = 70|
|6|T2|COMMIT|||
|7|T3|UPDATE|A = 80|A = 110|

そして、ログから特定の値を再現するコードは以下の通り

def read(logs, var):
    commits = []
    
    # ログを逆順にスキャン（新しいログから見ていきたいため）
    for log in reversed(logs):
        if log.type == "COMMIT": # コミット済みトランザクションの tid を記録
            commits.append(log.tid)
        elif log.type == "UPDATE" # 目的の変数が最後に更新された値を探す
            and log.var == var
            and (log.tid in commits or log.tid == current_tid):
            return log.new_value

コミット前にクラッシュすると、COMMIT ログが残らないので read() では引っかからない

**欠点: read が遅くなる場合がある**
- 例えば、以下の場合は遅い
- ログが膨大、かつ
- 目的変数の最後の更新がログの比較的先頭部分にある

### :two: cell storage を使った read() のパフォーマンス改善
ログに加えて、on disk に各変数の最新値を書くこと read() のパフォーマンスを改善できる。ただし、今回は cell storage の値の正しさを保証するために cell storage に対して recover 処理を実行する必要がある

def read(var):
    return cell_read(var)
    
def write(var, value):
    logs.append(Log(current_tid, "UPDATE", var, read(var), value))
    cell_write(var, value)
    
def recover(logs):
    commits = []
    
    # 未コミットの処理を破棄する (undo)
    for log in reversed(logs):
        if log.type == "COMMIT":
            commits.append(log.tid)
        if log.type == "UPDATE" and log.tid not in commits:
            # コミットされていないログであれば、古い値に復元する
            cell_write(log.var, log.old_value)

**利点: read が早くなった**

**欠点: write, recover が遅くなる場合がある**
- write: ログの記録 + cell storage への書き込みが増えたため
- recover: 必ずログ全体を操作するため、ログが膨大だと遅くなる

### :three: cache を使った write() のパフォーマンス改善
cell storage に加えて、on memory なキャッシュを用意する。最新値は cache に記録するようにする。ここで大事なことが 2 つあって、

1. cache の値を定期的に cell storage に書き出す必要がある
- recover() は cell storage をベースにしているため
2. cache が cell storage に書き出される前にクラッシュした場合も想定する必要がある
- recover() で undo だけではなく、redo の処理も必要になる

def read(var):
    if var in cache:
        return cache[var]
    else:
        cache[var] = cell_read(var)
        return cache[var]
        
def write(var, value):
    logs.append(Log(current_tid, "UPDATE", var, read(var), value))
    cache[var] = value
    
def flush(): # 時々呼び出して、cache を cell storage に書き出す
    for var in all_vars:
        cell_write(var, cache[var])
        
def recover(logs):
    commit = []
    
    # 未コミットの処理を破棄する (undo)
    for log in reversed(logs):
        if log.type == "COMMIT":
            commits.append(log.tid)
        if log.type == "UPDATE" and log.tid not in commits:
            # コミットされていないログであれば、古い値に復元する
            cell_write(log.var, log.old_value)
    
    # コミット済みの値を反映 (redo)
    for log in logs:
        if log.type == "UPDATE" and log.tid in commits:
            cell_write(log.var, log.new_value)

**利点: read, write が早くなった**

**欠点: recover が遅くなる場合がある**
- recover: 必ずログ全体を操作するため、ログが膨大だと遅くなる

## :four: checkpoints とログの truncate による recover() のパフォーマンス改善

recover() が遅いのはログが膨大になるから、であれば以下の方法でログを短くすればいい
- cache の中身を全て flush する
- CHECKPOINT を作成する
- その時点での最新値
- CHECKPOINT 以前のログを削除する

## メモ
- 今回の Logging は Write-Achead Logging （ログ先行書き込み） と言うらしい
- https://ja.wikipedia.org/wiki/%E3%83%AD%E3%82%B0%E5%85%88%E8%A1%8C%E6%9B%B8%E3%81%8D%E8%BE%BC%E3%81%BF
- 実際の変更を加える前に必ずログを残す方式
- よく知られたログ先行書き込みアルゴリズムに ARIES がある
- https://qiita.com/kumagi/items/14b6593a2e8ae0c56546 とか
- https://dl.acm.org/doi/10.1145/128765.128770 を見ると
- 結構今回の話に似ている気がする？
- ファイルシステムではジャーナリングという