guide:glossary@zh-Hant

指南

術語表

讀者在 Zanzibar 論文中會遇到的每一個術語,以淺白的文字說明,並指向解說它的導覽頁面與論文章節。

事實查核日期

術語依英文字母順序排列。論文設定語言中的程式碼名稱(_this、computed_userset、tuple_to_userset)在排序時忽略底線。範例使用貫穿全站的範例:Anne、Beto 與 Chen;位於 folder:A 中的 doc:readme;group:eng。

A–C

ACL
存取控制清單(access control list):允許對某個物件執行某項操作的使用者集合。在 Zanzibar 中,ACL 並不是以一份清單儲存,而是以許多筆關係元組儲存。延伸閱讀:存取控制模型、§1、§2.1。
aclserver
Zanzibar 的主要伺服器類型。回應 Check、Read、Expand 與 Write,並將工作扇出至其叢集中的其他 aclserver。延伸閱讀:架構、§3。
至少一樣新(at-least-as-fresh)
zookie 的規則:Zanzibar 可以在任何不早於 zookie 時間戳記的快照上評估,而不只限於那個確切的時間戳記。正是這份自由,讓它能以本地副本處理大多數請求。延伸閱讀:一致性、§2.2。
有界陳舊度(bounded staleness)
快照讀取可以比「現在」舊,但不能舊於某個界限。在 Zanzibar 中,這個界限就是客戶端送出的 zookie。Spanner 直接提供這項功能:客戶端給出陳舊度的上限,由 Spanner 挑選時間戳記(Spanner 論文,§4.1)。延伸閱讀:一致性、§2.2。
快取踩踏(cache stampede)
許多同時發生、針對同一個尚未快取之結果的請求,在快取填入之前全部同時湧向儲存層。Zanzibar 以鎖定表防止此情況。論文引用 Wikipedia 條目作為此術語的出處(參考文獻 [3])。延伸閱讀:架構、§3.2.5。
變更日誌(changelog)
一個存放元組更新歷史紀錄的 Spanner 資料庫,與每一次元組寫入在同一筆交易中寫入。Watch 從它讀取。延伸閱讀:架構、§3.1.2。
Check
詢問某位使用者是否屬於使用者集合 ⟨object#relation⟩ 的 API 呼叫,例如「Chen 是 doc:readme 的檢視者嗎?」。在不早於給定 zookie 的快照上評估。延伸閱讀:關係元組、§2.4.4、§3.2.3。
computed_userset
改寫規則的一種葉節點,取用同一物件上另一個關係的使用者集合,例如「每位編輯者都是檢視者」。延伸閱讀:關係元組、§2.3.1。
一致性雜湊(consistent hashing)
一種將鍵分配給伺服器的方法,使新增或移除一台伺服器時只會移動一小部分的鍵。Zanzibar 用它將快取項目分散到叢集中的各台伺服器。由 Karger 等人(STOC 1997)為網頁快取而提出。延伸閱讀:架構、§3.2.5。
內容變更檢查(content-change check)
使用者即將儲存新內容時送出的 Check。它不攜帶 zookie,在最新快照上評估,並傳回一個 zookie,由客戶端與新的內容版本一併儲存。延伸閱讀:一致性、§2.2、§2.4.4。

D–H

反正規化(denormalization)
儲存衍生資料的預先計算副本(例如攤平的群組對群組成員資格),而不是從原始列計算。Zanzibar 在儲存層避免反正規化,只在 Leopard 中使用。延伸閱讀:Leopard、§3.2.4、§3.2.5。
排除(exclusion)
改寫規則的一種運算子:屬於某個使用者集合、但不屬於另一個使用者集合的使用者。延伸閱讀:關係元組、§2.3.1。
Expand
依循改寫規則,以樹的形式傳回 ⟨object#relation⟩ 之有效使用者集合的 API 呼叫。葉節點是使用者 ID 或使用者集合;中間節點是聯集、交集或排除。延伸閱讀:關係元組、§2.4.5。
外部一致性(external consistency)
若更新 x 發生在更新 y 之前,即使兩者是在系統之外協調的,x 所獲得的時間戳記也會小於 y。Zanzibar 從 Spanner 取得這項特性。論文引用 Gifford 1981 年的史丹佛大學博士論文作為此術語的出處(參考文獻 [18]);Spanner 的表述是:若 T1 在 T2 開始之前提交,則 T1 的提交時間戳記小於 T2 的提交時間戳記。延伸閱讀:一致性、§2.2。
扇出(fan-out)
一個請求變成許多子請求,例如 aclserver 將一次 Check 的各部分送往其叢集中的其他伺服器。延伸閱讀:架構、§3、§3.2.5。
心跳 zookie(heartbeat zookie)
每個 Watch 回應中所附的 zookie,標示串流已推進到哪裡,讓客戶端能從該處繼續。延伸閱讀:§2.4.3。
對沖(hedging)
在得知第一台伺服器回應緩慢後,將同一個請求送往第二台伺服器,採用先抵達的回覆並取消另一個。Zanzibar 對送往 Spanner 與 Leopard 的呼叫進行對沖,但不對其自身伺服器之間的呼叫進行對沖。此技術說明於 Dean 與 Barroso 的 “The Tail at Scale”(CACM,2013)。延伸閱讀:架構、§3.2.7。
熱點(hot spot)
流量遠多於其他項目、可能使存放它的伺服器過載的鍵、物件或群組,例如被許多 ACL 共用的熱門群組。延伸閱讀:架構、§3.2.5。

I–N

交集(intersection)
改寫規則的一種運算子:同時屬於數個使用者集合中每一個的使用者。延伸閱讀:關係元組、§2.3.1。
Leopard
用於深層巢狀或極寬群組的索引系統。它將群組成員資格攤平為整數集合,使成員資格檢查變成集合交集,並透過 Watch 保持最新。延伸閱讀:Leopard、§3.2.4。
鎖定表(lock table)
每台伺服器上記錄進行中之讀取與檢查的表。共用同一個快取鍵的請求中,只有一個會執行;其餘的等待其結果。延伸閱讀:架構、§3.2.5。
鎖定元組(lock tuple)
一筆一般的關係元組,客戶端在每次寫入某個物件時都會觸及它,使寫入能以「自讀取以來沒有其他人寫入」為條件。延伸閱讀:§2.4.2。
命名空間(namespace)
由客戶端定義的物件種類,例如 doc 或 folder,也就是 doc:readme 中冒號之前的部分。每個命名空間的元組存放在各自的資料庫中。延伸閱讀:關係元組、§2.1、§2.3、§3.1.1。
命名空間設定(namespace config)
單一命名空間的設定:其各個關係(每個關係可選擇性地帶有一條使用者集合改寫規則),以及分片等儲存參數。延伸閱讀:關係元組、§2.3、§3.1.3。
「new enemy」問題(new enemy problem)
由於檢查忽略了兩次 ACL 變更之間的順序,或套用了比內容更舊的 ACL,而將內容顯示給已從其 ACL 中移除的人。延伸閱讀:一致性、§2.2。

O–R

物件(object)
受保護的事物,寫作 ⟨namespace⟩:⟨object_id⟩,例如 doc:readme。延伸閱讀:關係元組、§2.1。
Paxos
一種共識協定,即使部分副本故障,也能讓一組副本對每一次寫入達成共識。論文將 Zanzibar 儲存層的五個投票副本放置在彼此相距 25 毫秒以內的位置,讓 Paxos 交易能快速提交。參見 Lamport 的 “Paxos Made Simple”(2001)。延伸閱讀:架構、§3.1.4。
指標追蹤(pointer chasing)
以一次一步地追蹤使用者集合來回答 Check:從 readme 的檢視者到 group:eng#member,再到該群組的成員,依此類推。群組很深或很寬時會很慢。延伸閱讀:關係元組、Leopard、§3.2.3、§3.2.4。
Read
傳回符合一個或多個元組集合之儲存元組的 API 呼叫。它不套用改寫規則。延伸閱讀:關係元組、§2.4.1。
Recent 請求(Recent request)
參見 Safe/Recent 請求。延伸閱讀:一致性、§4.1。
關係(relation)
物件與使用者之間、或兩個物件之間(例如 parent 將文件連結到其資料夾)的具名關係,例如 owner、viewer、member 或 parent。定義於命名空間設定中。延伸閱讀:關係元組、§2.1、§2.3。
關係元組(relation tuple)
一則儲存的事實,⟨object⟩#⟨relation⟩@⟨user⟩,例如 doc:readme#owner@user:anne。這是 Zanzibar 儲存的唯一一種權限資料。延伸閱讀:關係元組、§2.1。
副本(replica)
資料在某一地點的一份副本。Zanzibar 的資料被複製到數十個地點,讓大多數讀取都能就近處理。延伸閱讀:架構、§3.1.4。

S

Safe/Recent 請求(Safe / Recent requests)
論文依 zookie 的新舊程度對請求所做的區分。Safe 請求攜帶超過 10 秒的 zookie,通常可在區域內處理;Recent 請求攜帶較新的 zookie,經常需要一次跨區域往返。延伸閱讀:一致性、§4.1。
分片(shard)
資料庫或索引中被分開儲存與服務的一部分。元組的分片 ID 通常來自其物件 ID;對於非常大的群組,則來自物件 ID 與使用者。延伸閱讀:架構、§3.1.1、§3.2.4。
快照讀取(snapshot read)
一種讀取,所看到的資料庫恰好是某一時間戳記當下的狀態:包含該時間點及之前的所有寫入,不含之後的任何寫入。Zanzibar 在單一快照上評估每一次 Check。Spanner 將其定義為 “a read in the past that executes without locking”(在過去某一時間點執行、不需鎖定的讀取)(Spanner 論文,§4.1)。延伸閱讀:一致性、§2.2。
Spanner
Google 的全球分散式資料庫。Zanzibar 將元組、命名空間設定與變更日誌存放在其中,並依賴其時間戳記來達成一致性。說明於 Corbett 等人,OSDI 2012。延伸閱讀:一致性、架構、§2.2、§3。

T

尾端延遲(tail latency)
最慢那部分請求的延遲,例如第 99 或第 99.9 百分位。它之所以重要,是因為一頁搜尋結果可能需要數十到數百次檢查。參見 Dean 與 Barroso 的 “The Tail at Scale”(CACM,2013)。延伸閱讀:架構、§1、§3.2.7、§4.2、§4.5。
_this
改寫規則的一種葉節點,傳回儲存的元組中針對此物件與關係的使用者,包括這些元組所指向的使用者集合。關係沒有規則時的預設行為。延伸閱讀:關係元組、§2.3.1。
時間戳記量化(timestamp quantization)
將評估時間戳記向上取整到較粗的間隔(例如 1 秒或 10 秒),讓許多請求共用同一個時間戳記,進而共用快取項目。這不會削弱一致性:zookie 只設定下限,而在未來時間戳記上進行的 Spanner 快照讀取,會等到 TrueTime 越過該時間戳記為止(§3.2.5)。延伸閱讀:架構、一致性、§2.2、§3.2.5。
TrueTime
Spanner 的時鐘機制,為每一次寫入賦予一個反映因果順序、微秒解析度的時間戳記。正是它讓 Zanzibar 的時間戳記具有意義。TT.now() 傳回一個保證包含真實時間的區間;參見 Spanner 論文(OSDI 2012)§3。延伸閱讀:一致性、§2.2、§3.2.5。
元組集合(tupleset)
儲存元組的選取器:單一元組鍵,或某個物件 ID 或使用者集合的所有元組,並可選擇性地限定為單一關係。由 Read 與 tuple_to_userset 使用。延伸閱讀:關係元組、§2.4.1。
tuple_to_userset
改寫規則的一種葉節點,讀取物件的部分元組,並從每一筆計算出一個使用者集合,例如「查找 readme 的上層資料夾並取其檢視者」。延伸閱讀:關係元組、§2.3.1。

U–W

聯集(union)
改寫規則的一種運算子:屬於數個使用者集合中任一個的使用者。論文圖 1 中 viewer 的三個分支都以聯集結合。延伸閱讀:關係元組、§2.3.1。
使用者(user)
元組的第三個部分:單一使用者 ID 或一個使用者集合。延伸閱讀:關係元組、§2.1。
使用者集合(userset)
一個 ⟨object⟩#⟨relation⟩ 配對,代表對該物件具有該關係的所有使用者,例如 group:eng#member。它讓一筆元組能將存取權授予一個群組,也讓群組能包含群組。延伸閱讀:關係元組、§2.1。
使用者集合改寫規則(userset rewrite rule)
關係設定的一部分:一個從物件 ID 對應到使用者集合運算式樹的函式,由 _this、computed_userset 與 tuple_to_userset 以聯集、交集與排除組合而成。延伸閱讀:關係元組、§2.3.1。
使用者集合樹(userset tree)
Expand 的結果:葉節點是使用者 ID 或使用者集合,中間節點是集合運算子。延伸閱讀:關係元組、§2.4.5。
Watch
從某個 zookie 開始,依時間戳記順序串流傳送一個或多個命名空間之元組變更的 API 呼叫。用來讓次要索引(例如 Leopard)保持最新。延伸閱讀:架構、§2.4.3。
watchserver
透過持續追蹤變更日誌尾端來回應 Watch 的伺服器類型。延伸閱讀:架構、§3。
Write
新增或移除元組的 API 呼叫。會改寫某個物件所有元組的客戶端,先進行一次讀取,再進行一次以鎖定元組未變更為條件的寫入。延伸閱讀:架構(一次寫入會觸及哪些東西)、§2.4.2。

Z

zookie
編碼了一個時間戳記的不透明權杖。客戶端從內容變更檢查取得 zookie(Read 與 Write 的回應也會攜帶 zookie),將它與內容一併儲存,並在之後的檢查中送出,使這些檢查在至少一樣新的快照上評估。延伸閱讀:一致性、§2.2、§2.4。

資料來源

  • J. C. Corbett et al., “Spanner: Google’s Globally-Distributed Database”, OSDI ’12, PDF
  • D. Karger et al., “Consistent Hashing and Random Trees”, STOC ’97, PDF
  • J. Dean and L. A. Barroso, “The Tail at Scale”, CACM 56(2), 2013, research.google
  • L. Lamport, “Paxos Made Simple”, ACM SIGACT News 32(4), 2001, PDF
  • D. K. Gifford, “Information Storage in a Decentralized Computer System”, PhD thesis, Stanford University, 1981(論文參考文獻 [18];未查核線上版本)
  • “Cache stampede”, Wikipedia, en.wikipedia.org(論文所引用的出處)
  • Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang