용어는 영어 표기의 알파벳 순서로 배열했다. 논문의 설정 언어에 나오는 코드 이름(_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 et al. (STOC 1997)이 도입했다. 더 보기: 아키텍처, §3.2.5.
- content-change 검사(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년 Stanford 학위 논문을 인용하며(참고 문헌 [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 and 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)
- 클라이언트가 객체에 쓸 때마다 touch하는 일반 관계 튜플로, 읽기 이후 아무도 쓰지 않았다는 조건을 쓰기에 붙일 수 있게 한다. 더 보기: §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)
- 보호 대상.
doc:readme처럼 ⟨namespace⟩:⟨object_id⟩로 쓴다. 더 보기: 관계 튜플, §2.1. - Paxos
- 일부 복제본이 장애를 일으켜도 복제본 그룹이 각 쓰기에 합의할 수 있게 하는 합의 프로토콜. 논문은 Paxos 트랜잭션이 빠르게 커밋되도록 Zanzibar 저장소의 투표 복제본 다섯 개를 서로 25 ms 이내에 둔다. 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.
- 따로 저장되고 제공되는 데이터베이스나 인덱스의 조각. 튜플의 샤드 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 et al., OSDI 2012에 기술되어 있다. 더 보기: 일관성, 아키텍처, §2.2, §3.
T
- 꼬리 지연 시간(tail latency)
- 99번째나 99.9번째 백분위수처럼 가장 느린 요청들의 지연 시간. 검색 결과 한 페이지에 수십에서 수백 건의 검사가 필요할 수 있으므로 중요하다. Dean and 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
- 타임스탬프를 인코딩한 불투명한 토큰. 클라이언트는 content-change 검사에서 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 (paper reference [18]; no online copy checked)
- “Cache stampede”, Wikipedia, en.wikipedia.org (the source the paper cites)
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang