Preventing Lost Update

昨天講的快照隔離優雅的解決了 read-skew 的問題，除了 read-skew ，今天要來聊聊另一個常發生的狀況：2 個 transaction 同時做寫入該怎麼辦！？其中最為人知的寫入衝突就是 更新遺失 (lost update)，如前幾天有看過的圖 7-1 就是一個典型的並發計數器更新遺失問題。

這最常發生在應用程式需要進行 讀取-修改-寫入 (read-modify-wite) 的 transaction 迴圈中，就像上圖 7-1 ，勢必有一個 transaction 的更新將會遺失；因為這是一個很常見的問題，所以我們有以下幾種解決方式可用：

原子寫入操作 (Atomic wrtie operations)

許多資料庫提供原子寫入操作 (Atomic write operations)，這就代表了我們不用在應用程式端進行 讀取-修改-寫入(read-modify-write) 迴圈操作，舉例來說，下面這段 SQL 就是執行緒安全 (concurrency-safe) 的更新：

UPDATE conuters SET value = value + 1 WHERE key = 'foo';

不只 RDB，document 類型的資料庫和 Redis 都有提供類似的原子寫入操作。

原子操作通常使用全域唯一物件鎖來實作，當物件被讀取時沒有其他 transaction 可讀取，除非它的寫入被 commit，這技術也稱 cursor stability；另一個方式是強迫所有的原子操作只被執行在單一執行緒上。

外部鎖 (Explicit locking)

如果資料庫內建的原子寫入操作無法滿足需求，另一個避免更新遺失的方式就是應用程式來指定我該鎖哪裡。

例如下面這段 SQL 就是來檢查機器人跟玩家不能同時走到同一個地圖點，(1) 的 FOR UPDATE 語法就是指示資料庫要取得所有被查詢結果的物件鎖。

BEGIAN TRANSACTION;

SELECT * FROM figures
WHERE name = 'robot' AND game_id = 222
FOR UPDATE; --(1)

UPDATE figures SET position = 'c1' WHERE id = 12345;

COMMIT;

這個方法很需要釐清資料更新的邏輯，若在哪邊忘記加鎖，又會重蹈競爭寫入的覆轍了。

比較並交換 (Compare-and-set)

在一些沒有提供 transaction 的資料庫中，你有時會找到有支持原子操作的 比較並交換 (compare-and-set)，這種操作只允許當資料從你讀取後從未被變更，才能更新，否則會更新無效並重試，用個 SQL 來舉例可能比較好懂：

UPDATE wiki_page SET content = 'new content' WHERE id = 1234 AND content = 'old content';

當 wiki 頁面不是你以為的舊資料時，該更新會無效。

請留意各資料庫針對 比較並交換 (compare-and-set) 是以什麼來實做的！例如這個 wiki 頁面的例子，若資料庫允許在 update 時的 where 語句能讀取舊的快照資料，此做法還是不能避免 更新遺失 (lost update)。

解決衝突和副本 (Confict resoution and replication)

在副本型資料庫中 (2020 Day 21~26)，更新遺失的處理需要多一些額外步驟才能避免，因為同一份資料會被複製到多台節點上，所以資料很有可能會並發的在不同節點上一起被更新。

最常見的方法是允許並發寫入建立多個版本的資料 (也被稱為 siblings），然後依靠應用程式或其他特殊資料結構來解決衝突，細節可回頭看 2020 Day 26 - Capturing the happens-before relationship 小節 。

原子寫入操作同樣也可在副本型資料庫裡運作良好，尤其是累加型的操作（如計數器或對個 list 加元素），此概念是來自 Riak 分散式資料庫 2.0 的資料型態，它能避免跨節點的 更新遺失 (lost update)，Riak 能自動合併並發寫入且不需要建立 siblings 資料。

最後一個方法，依舊是 2020 Day 26 Detecting Concurrent Writes 中提過的 最後寫的最大 (last write wins - LWW) ，這也是很多副本型資料庫的預設解衝突方法。

Write Skew and Phantoms

除了 Day 3 有講到的 dirty writes 和今天的 更新遺失 這 2 種 競爭條件 (race condition) 寫入外（多個 transaction 操作同一個資料物件），今天要講講多個資料物件版本的競爭條件寫入。

假設一下這個場景：你正在寫一個應用系統管理醫生的排班，醫生可同時值班，但最少一定要留一個醫生 oncall，醫生們可以選擇不值班，想像一下有 2 位醫生 Alice 和 Bob 都有同一段時間的值班 (shift_id=1234)，2 位都很不舒服想 翹班 請假，所以上系統操作，很不幸的，他們幾乎同時點了按鈕，此時會發生如下圖的事情：

現在好了，每一個 transaction 都是符合系統業務邏輯規則，但現在 shift_id=1234 的班表上沒有醫生值班了。

Write skew

這種異常情況稱為 write skew，因為他們是同時修改 2 個不同物件，所以不歸類在 dirty writes 或 更新遺失 裡，這個解法看起來很簡單對吧！？讓某個 transaction 慢一點執行就好了，但現實世界總會 Surprise 媽的發科 一下，就是有某個時間點會並發一下。

怎麼解決？我們來看一下：

• 使用資料庫的 constrains，例如 uniqueness, foreign key constrains 或者 完整限制 (Integrity Constraints)。

• 使用明天會講的最強隔離等級 序列化隔離 (serializability isolation)。

• 使用 顯示鎖定 (Explicit Locking)，如下方 SQL，FOR UPDATE 語句會告訴資料庫要鎖住查詢結果（不作用在要新增資料的場景上，因為沒資料可鎖定）。

  BEGIN TRANSACTION;
  	SELECT * FROM doctors
  		WHERE on_call = true
  		AND shift_id = 1234 FOR UPDATE;
  
  	UPDATE doctors
  		SET on_call = false 
  		WHERE name = 'Alice' AND shift_id = 1234;
  
  COMMIT;
  

Phantoms 導致 write skew

write skew 通常符合以下模式：

1. 查詢資料。
2. 判斷是否要繼續執行。
3. 寫入資料（insert, update 或 delete）。

有些業務埸景可能會有不同的順序，舉例來說你可以先寫入，然後查詢，最後在決定要 commit 或中止。

當一個 transaction 的寫入改變另一個 transaction 的查詢結果的效果，稱為 幻影 (phantom) ，Day 4 講的快照隔離能避免 read-only 查詢，但 read-write 就無法了，phantom 會讓你遇到一些很弔詭的 write skew。

明天就來介紹解決 write-skew 的最完美方法，序列化隔離 (serializability isolation) 啦。