F1 中在線異步Schema變更
Online, Asynchronous Schema Change in F1
簡介
F1 的主要特性影響到schema變更的地方有：
- 大量的分布
- 關系型schema洲脂，每個F1服務都有schema的一份拷貝痛垛，變更必須讓所有的F1服務更新校仑，相當于一次分布式的變更。
- 共享的數(shù)據(jù)存儲尽超，F(xiàn)1可以訪問所有存儲在spanner中的數(shù)據(jù)。
- 無狀態(tài)服務，F(xiàn)1服務必須容忍機器故障须床，被取代拇泣，丟失網(wǎng)絡噪叙。所以是無狀態(tài)的，客戶端可以隨意連接到任何一個F1霉翔。
- 沒有全局成員關系构眯，F(xiàn)1服務之間沒有通信關系。
在F1上進行Schema變更的要求：
- 所有數(shù)據(jù)的可訪問性早龟，不能因為schema變更而導致系統(tǒng)下線惫霸，哪怕是一部分數(shù)據(jù)庫下線都是不可接受的。（比如鎖住一個列）
- 最小化性能影響葱弟，頻繁的schema 變更壹店，要最小化性能的影響，即對用戶響應時間的影響芝加。
- 異步schema變更硅卢，因為F1之間沒有通信協(xié)議，所以不能通過F1服務之間通信來同步schema藏杖。意味著将塑，不同的F1服務可能使用新的schema在不同的時間點上。
背景
F1提供了一個建立在key-value數(shù)據(jù)上的關系的視圖蝌麸。
key-value store提供三種操作点寥，put,del,get。
put和del insert或者delete一個給定的key来吩。
get獲取前綴符合給定key的數(shù)據(jù)集合敢辩。
F1 提供了樂觀并發(fā)控制蔽莱，會給key-value添加兩個需求。
- Commit timestamps（提交時間戳）戚长。每個key-value對有一個最后修改時間戳盗冷。
- 多個get和put可以被以原子的方式執(zhí)行。
F1 的schema是一系列表的定義同廉，每個表的定義由一組列仪糖、一組耳機索引、一組完整型約束迫肖，和一組樂觀鎖乓诽。列可以是原始類型或者復雜類型，主鍵的類型被嚴格要求只能是原始類型咒程。在每一行中鸠天，列的值可以是缺省的，也可是是必須存在的帐姻。使用required標識稠集。
F1 使用一種基于時間戳的樂觀并發(fā)控制，與Percolator相似饥瓷。F1 的schema包含一個額外的元素在每個表上剥纷，即樂觀鎖。
一個表可能有多個鎖呢铆，每個列關聯(lián)一個確切的樂觀鎖晦鞋。每個行有它自己的樂觀鎖實例基于schema的定義，且這些實例控制了對這些行中的列的事務并發(fā)訪問棺克。
F1實現(xiàn)行級別的鎖悠垛，用戶可以給表添加新的鎖并關聯(lián)它到一個任意的列中。F1的用戶可以選擇鎖的粒度娜谊，可以是行級別的范圍鎖到列級別的鎖确买。
Schema 是一個特殊的k-v對來表示的。通過一個版本來表示當前的schema版本纱皆，當該標本變化的時候湾趾，表示有schema變更發(fā)生了。
不同的服務使用的新schema的時機不同派草，同一時刻可能存在多個版本的schema在是使用搀缠。
當所有的F1服務都加載了新的schema完成的時候，表示schema change已經(jīng)完成近迁。
造成數(shù)據(jù)損壞的主要原因是由于schema變化太過突然了艺普。一部分F1使用舊的，一部分使用新的schema造成了數(shù)據(jù)損壞。
（PS：通常情況下衷敌，一步解決不了問題，就可以拆成若干步來完成拓瞪。一階段不行就兩階段缴罗，三階段，直到問題解決祭埂，每一階段都使問題縮小化面氓，朝著最終的目標前進即可解決）
因此，引入中間狀態(tài)蛆橡，將一次危險的schema變更舌界，拆解成一系列安全的schema變更。
為了簡化正確的實現(xiàn)泰演，F(xiàn)1允許最多不超過2個schema版本在使用呻拌。意味著，存在一個短暫的時間窗口睦焕，有兩個schema版本在使用藐握。超過兩個版本的存在會大大引入復雜性。
Schema變更
F1的schema有表垃喊、列猾普、索引、約束和樂觀鎖本谜。稱為schema項初家。每個schema項目都有與之關聯(lián)的狀態(tài)。有兩種沒有中間狀態(tài)的稱為：absent和public乌助。
- absent：當一個schema項不存在的時候溜在，它是缺省的。
- public：當一個schema項存在他托，并且可以影響或者被所有操作應用的時候炕泳，它是public的。
F1也存在兩種內(nèi)部的上祈，中間的狀態(tài)： delete-only 和 write-only培遵。
Definition 1：delete-only：一個delete-only 表、列登刺、索引 不存在可以被用戶讀取的對應的k-v對籽腕。并且，如果 E 是一個表或者列纸俭，它僅僅可以被刪除操作修改皇耗。如果E是一個索引， 它僅僅可以被delete和update操作修改揍很，并且郎楼，update操作只能刪除k-v對（當更新索引時）万伤，但不能創(chuàng)建新的k-v對。
Definition 2：write-only狀態(tài)是為列和索引定義的呜袁，write-only：一個write-only的列或索引可以允許insert敌买、delete和update操作修改k-v對，但是任何上述的k-v對都不能對用戶的讀可見阶界。因此虹钮，write-only狀態(tài)允許數(shù)據(jù)被寫入，但不允許讀缺烊凇（就索引而言芙粱，F(xiàn)1服務不使用write-only的索引去加速尋找。）
Definition 3：write-only狀態(tài)也定義了約束氧映，write-only 約束：write-only 約束對于新的 insert春畔、delete和update操作生效，但是它不保證對于所有已存在的數(shù)據(jù)也保持岛都。
-
Definition 4：一個數(shù)據(jù)庫d在schema S下是遵守一致性的拐迁，當且僅當：
- 不存在沒有表和行的列數(shù)據(jù)存在
- 所有的數(shù)據(jù)行都必須存在必須存在的列數(shù)據(jù)
- 不存在表結構中沒有索引的索引數(shù)據(jù)項
- 所有對外可見的索引必須有所有數(shù)據(jù)的完整的索引項
- 所有的索引項目必須指向合法的行數(shù)據(jù)
- 所有對外公開的約束必須是被遵守的
- 不存在未知的數(shù)據(jù)
-
Definition 5：一次schema變更，從S1 到 S2 是一致性保持的疗绣，當且僅當對于任何數(shù)據(jù)庫d线召，要一致性遵守包括S1和S2
- 任何在S1下的操作，要維護遵守數(shù)據(jù)庫d在S2下的一致性多矮。
- 任何在S2下的操作缓淹，要維護遵守數(shù)據(jù)庫d在S1下的一致性。
數(shù)據(jù)庫的一致性
F1服務將強制新的操作滿足約束塔逃，但讀操作可能看到違背約束讯壶。
確保所有的F1服務對于數(shù)據(jù)庫都有一個一致性視圖是至關重要的。
- 不允許有孤兒數(shù)據(jù)湾盗。
- 不允許有違反完整性約束的數(shù)據(jù)伏蚊。
添加或者刪除schema element
可選結構化項
- 添加：absent -> delete only -> public
- 刪除：public -> delete only -> database reorganization -> absent
按照上述的schema狀態(tài)流程做schema變更，所有操作都會避免產(chǎn)生孤兒數(shù)據(jù)格粪。并且由于添加的schema結構是可選的躏吊，所以也不存在完整性異常。
刪除時候使用 database reorganization 來對列數(shù)據(jù)進行回收帐萎，清除那些刪除掉的列對應的kv對比伏。
必需的結構化項
- 添加：absent -> delete only -> write only -> database reorganization -> public
- 刪除：public -> write only -> delete only -> database reorganization -> absent
對于約束
- 添加：absent -> write only -> public
- 刪除：public -> write only -> absent
實現(xiàn)
- GC：對于刪除列或者索引等，可以使用異步的GC機制來優(yōu)化 database reorganization 階段疆导。通過異步刪除赁项，加快DDL的進度。
- Write fencing：寫柵欄，Schema需要有Lease機制悠菜，不允許那些超過Lease的Schema的事務進行提交舰攒，以避免數(shù)據(jù)完整性被違反、或者有孤兒數(shù)據(jù)悔醋。每個Schema都存在一個版本號與之對應摩窃，當事務將要提交的時候，通過與內(nèi)存中的Schema 倉庫的接口進行校驗篙顺，如果事務開始時使用的schema版本已經(jīng)過時了偶芍，則該事務不能提交充择。必須重試德玫。
F1使用了單獨的Schema變更進程。通過版本控制倉庫來保存schema變更記錄椎麦，schema變更進程按照版本控制的更改記錄進行schema變更宰僧，使其按順序生效。
不變式：
如果schema S 在時間點t0 寫入了观挎，并且沒有其它 schema 在 t0 -> t1 之間寫入 (t1 > t0 + lease_period )琴儿，因此，在 t1 時刻嘁捷，每個F1服務要么使用 S造成，要么不允許事務提交。
續(xù)Lease根據(jù)經(jīng)驗雄嚣，一般在Lease過半的時候進行續(xù)Lease晒屎，續(xù)Lease的方式，通過周期性地重新讀取schema從一個眾所周知的位置在k-v store中缓升。如果F1服務沒辦法續(xù)lease鼓鲁，則自行terminate。一般情況下港谊，會再次拉起來骇吭，拉起來的時候會獲取最新的schema。
對于執(zhí)行Schema變更的進程歧寺，每個狀態(tài)必須等待Lease時間之后燥狰，才能進行下一步狀態(tài)，盡可能保證所有F1都使用到了最新的Schema斜筐。
續(xù)Lease可以優(yōu)先檢查Schema 的commit ts是否有變更碾局，沒有變更則不重新Load schema。有變更則才重新Load奴艾。
Data reorganization净当，數(shù)據(jù)重組
- 數(shù)據(jù)重組必須支持暫停/恢復，并且過程是需要冪等的。
- 在重組期間像啼，所有的數(shù)據(jù)都是必須可以訪問的俘闯。因此，重組過程忽冻，必須能夠容忍并發(fā)的訪問修改的數(shù)據(jù)真朗。
- 減少不必要的數(shù)據(jù)寫入。當用戶的事務已經(jīng)寫入了需要重組的kv對時僧诚，重組執(zhí)行時就不需要寫入遮婶。
F1使用了MapReduce的框架的思路，MapReduce控制器將待重組的數(shù)據(jù)進行分組湖笨，將分組信息給到map 任務旗扑，map任務掃描分組內(nèi)所有的行，使用一個快照時間戳（這個時間戳應該是重組執(zhí)行的時候獲取的）慈省。更新每一行遵從新的schema臀防。取決于對應的schema變更操作，可能添加key或者移除边败。
每個map任務讀取每一行并確定它是否已經(jīng)被用戶事務更新過了袱衷。如果用戶事務更新過了，則map任務不需要更進一步修改行笑窜。遵循了Thomas寫規(guī)則致燥。
The End;
