-
Notifications
You must be signed in to change notification settings - Fork 0
/
spanner.html
134 lines (112 loc) · 6.82 KB
/
spanner.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
<title>Spanner 概要（K-V 部分） — Feng's blog 1.0 documentation</title>
<link rel="stylesheet" type="text/css" href="_static/pygments.css" />
<link rel="stylesheet" type="text/css" href="_static/alabaster.css" />
<script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script>
<script src="_static/jquery.js"></script>
<script src="_static/underscore.js"></script>
<script src="_static/doctools.js"></script>
<script src="_static/custom.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="Percolator 的事务模型" href="percolator.html" />
<link rel="prev" title="The Hungry Beast And The Ugly Baby" href="the-hungry-beast-and-ugly-baby.html" />
<link rel="stylesheet" href="_static/custom.css" type="text/css" />
<meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
</head><body>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<section id="spanner-gai-yao-k-v-bu-fen">
<h1>Spanner 概要（K-V 部分）<a class="headerlink" href="#spanner-gai-yao-k-v-bu-fen" title="Permalink to this headline">¶</a></h1>
<ul class="simple">
<li><p><a class="reference external" href="http://research.google.com/archive/spanner.html">http://research.google.com/archive/spanner.html</a></p></li>
<li><p><a class="reference external" href="https://research.google.com/pubs/pub46103.html">https://research.google.com/pubs/pub46103.html</a></p></li>
</ul>
<section id="paxos-group">
<h2>Paxos Group<a class="headerlink" href="#paxos-group" title="Permalink to this headline">¶</a></h2>
<p>Spanner 底层是一个类似于 Bigtable 的 K-V 存储，存储如下形式的数据：</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>(key:string, timestamp:int64) → string
</pre></div>
</div>
<p>按 key 分片（sharding），每个分片归属于一个 paxos group（replicated state machine）， paxos group 维护一个 replicated write-ahead log，使用 paxos 共识算法保证其在每一个副本（replica）上的一致性。每个副本再根据 write-ahead log 更新各自的数据，从而保证每个副本数据的一致。</p>
<img alt="_images/spanner-paxos-group.png" src="_images/spanner-paxos-group.png" />
<p>分片可以从一个 paxos group 移到另外 group，也可以分裂到新的 group 中（一般是因为负载）。</p>
<p>副本的数据存在一个叫做 Colossus 的分布式追加（append-only）文件系统上，原始使用的文件格式是 SSTable，后期（2017-）改为了 Ressi 格式（build from ground up）。</p>
<p>Spanner 提供了一个叫做 coprocessor framework 的 RPC 框架来隐藏查找数据的复杂性，读写请求指定 key 或者一个 key range 而不是某一个服务器。coprocessor framework 隐藏底层复杂的 paxos group 查找，满足条件的副本确定等事宜。</p>
</section>
<section id="data-model">
<h2>Data Model<a class="headerlink" href="#data-model" title="Permalink to this headline">¶</a></h2>
<p>Spanner 中每张表都必须包含一个和多个主键（primary key），每张表在底层的 K-V 存储中就是 <em>主键列</em> 到 <em>非主键列</em> 的映射。</p>
<p>表之间可以存在父子（parent-child）关系。存在父子关系的表会按其主键或者主键前缀交叉存取在同一分片中。例如：</p>
<img alt="_images/spanner-interleave.png" src="_images/spanner-interleave.png" />
<p>用户可以使用 <em>INTERLEAVE IN</em> 关键字来将相关联的表的数据存储在一起。</p>
</section>
<section id="concurrency-control">
<h2>Concurrency Control<a class="headerlink" href="#concurrency-control" title="Permalink to this headline">¶</a></h2>
<p>对于只写（blind-write）、读写（read-modify-write） 事务，<a class="reference external" href="https://en.wikipedia.org/wiki/Two-phase_locking">2 阶段锁（2PL）</a> 可以确保同一个 paxos group 中并行事务的可串行化（serializability），2 阶段提交（2PC）可以确保整个数据库上的可串行化。</p>
<p>每个事务提交都会被赋予一个时间戳，通过时间戳，用户可以读取这个时间点上数据库的快照数据（也就是应用所有提交时间 <= T 的事务后都到的数据）。可以参照： <a class="reference internal" href="percolator.html"><span class="doc">Percolator 的事务模型</span></a> 。</p>
</section>
</section>
</div>
</div>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">Spanner 概要（K-V 部分）</a><ul>
<li><a class="reference internal" href="#paxos-group">Paxos Group</a></li>
<li><a class="reference internal" href="#data-model">Data Model</a></li>
<li><a class="reference internal" href="#concurrency-control">Concurrency Control</a></li>
</ul>
</li>
</ul>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="_sources/spanner.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="https://cn.bing.com/search" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
<input type="submit" value="Go" />
</form>
</div>
</div>
<script>
$('#searchbox').show(0);
document.getElementsByClassName('search')[0].addEventListener('submit', function(event) {
event.preventDefault();
var form = event.target;
var input = form.querySelector('input[name="q"]');
var value = input.value;
var q = 'ensearch=1&q=site%3Achanfung032.github.io++' + value;
var url = form.action + '?' + q;
window.location.href = url;
});
</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="footer">
©2017, chanfung032.
|
Powered by <a href="http://sphinx-doc.org/">Sphinx 4.1.2</a>
& <a href="https://github.com/bitprophet/alabaster">Alabaster 0.7.12</a>
|
<a href="_sources/spanner.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>