This repository has been archived by the owner on Sep 13, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
/
advancing-b-trees-w.html
260 lines (224 loc) · 15.1 KB
/
advancing-b-trees-w.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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
<!DOCTYPE html>
<html lang="zh">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Advancing B-trees w</title>
<link href="/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="华科美团点评技术俱乐部 Full Atom Feed" />
<link href="/feeds/alg.atom.xml" type="application/atom+xml" rel="alternate" title="华科美团点评技术俱乐部 Categories Atom Feed" />
<!-- Bootstrap Core CSS -->
<link href="/theme/css/bootstrap.min.css" rel="stylesheet">
<!-- Custom CSS -->
<link href="/theme/css/clean-blog.min.css" rel="stylesheet">
<!-- Code highlight color scheme -->
<link href="/theme/css/code_blocks/darkly.css" rel="stylesheet">
<!-- Custom Fonts -->
<link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.5.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">
<link href='https://fonts.googleapis.com/css?family=Lora:400,700,400italic,700italic' rel='stylesheet' type='text/css'>
<link href='https://fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800' rel='stylesheet' type='text/css'>
<!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
<!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
<script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
<![endif]-->
<meta name="description" content="（续上文） -- 什么？B树？ -- 不好意思，我不仅有B树，我还有……w emmm，虽然 B 树已经提供了相当优秀的使用体验了，但是如果要真的使用它来做文件系统，我们还需要一些小小的改动w 这篇博客将介绍一部分的这些改动，下一篇博客就要用 btrfs 作为例子来介绍 B...">
<meta name="author" content="Huatian Zhou">
<meta name="tags" content="OS">
<meta name="tags" content="linux">
<meta name="tags" content="ALG">
<meta property="og:locale" content="zh_CN.UTF-8">
<meta property="og:site_name" content="华科美团点评技术俱乐部">
<meta property="og:type" content="article">
<meta property="article:author" content="/author/huatian-zhou.html">
<meta property="og:url" content="/advancing-b-trees-w.html">
<meta property="og:title" content="Advancing B-trees w">
<meta property="article:published_time" content="2017-10-14 21:38:57+08:00">
<meta property="og:description" content="（续上文） -- 什么？B树？ -- 不好意思，我不仅有B树，我还有……w emmm，虽然 B 树已经提供了相当优秀的使用体验了，但是如果要真的使用它来做文件系统，我们还需要一些小小的改动w 这篇博客将介绍一部分的这些改动，下一篇博客就要用 btrfs 作为例子来介绍 B...">
<meta property="og:image" content="//images/bg.jpg">
</head>
<body>
<!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top">
<div class="container-fluid">
<!-- Brand and toggle get grouped for better mobile display -->
<div class="navbar-header page-scroll">
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target="#bs-example-navbar-collapse-1">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a class="navbar-brand" href="/">华科美团点评技术俱乐部</a>
</div>
<!-- Collect the nav links, forms, and other content for toggling -->
<div class="collapse navbar-collapse" id="bs-example-navbar-collapse-1">
<ul class="nav navbar-nav navbar-right">
<li><a href="/categories.html">分类</a></li>
<li><a href="/archives.html">归档</a></li>
<li><a href="/authors.html">作者</a></li>
<li><a href="/tags.html">标签</a></li>
<li><a href="/pages/about/index.html">关于</a></li>
<li><a href="/pages/friendlinks/index.html">友链</a></li>
</ul>
</div>
<!-- /.navbar-collapse -->
</div>
<!-- /.container -->
</nav>
<!-- Page Header -->
<header class="intro-header" style="background-image: url('/images/bg.jpg')">
<div class="container">
<div class="row">
<div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
<div class="post-heading">
<h1>Advancing B-trees w</h1>
<span class="meta">Posted by
<a href="/author/huatian-zhou.html">Huatian Zhou</a>
on 2017年10月14日 周六
</span>
</div>
</div>
</div>
</div>
</header>
<!-- Main Content -->
<div class="container">
<div class="row">
<div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
<!-- Post Content -->
<article>
<blockquote>
<p>（续上文）</p>
<p>-- 什么？B树？</p>
<p>-- 不好意思，我不仅有B树，我还有……w</p>
</blockquote>
<p>emmm，虽然 B 树已经提供了相当优秀的使用体验了，但是如果要真的使用它来做文件系统，我们还需要一些小小的改动w</p>
<p>这篇博客将介绍一部分的这些改动，下一篇博客就要用 <code>btrfs</code> 作为例子来介绍 B 树在文件系统里的应用了w</p>
<p>（啊……我就在用 <code>btrfs</code> w...</p>
<h2>0x00 B+ trees</h2>
<p></p>
<div class="highlight"><pre><span></span><span class="n">Author</span><span class="o">:</span> <span class="n">Grundprinzip</span>
<span class="n">From</span><span class="o">:</span> <span class="n">Wikipedia</span> <span class="n">B</span><span class="o">+</span> <span class="n">tree</span>
<span class="n">License</span><span class="o">:</span> <span class="n">Creative</span> <span class="n">Commons</span> <span class="n">Attribution</span> <span class="mf">3.0</span> <span class="n">Unported</span>
</pre></div>
<p><code>B+ tree</code> 是 B 树的一种变种，它使用一种不同的模式来存储键值对：在非叶子节点中，仅存储键，在叶子节点中，存储键和指向值的连接（参考上图）。</p>
<p>由于这种设计模式，B+ 树的根节点要么是叶子节点，要么是有两个或者以上键的非叶子节点。</p>
<p>首先定义 <code>b(branching factor)</code> 是 B+ 树的一个节点最大拥有的子节点的数量，那么：</p>
<p>非根节点的最小键数量是<code>上取整(b/2)-1</code> （最大键数量当然是……）。根节点和 B 树一样不受限制。</p>
<p>B+ 树的插入、删除、查找算法都与 B 树没有较大的区别。但是有一点需要注意的是，B+ 树为了保证能够实现常数时间复杂度的前驱后继（在文件系统实现当中，这是一个非常重要的特性），所以将叶子节点的最后一个指针指向了它的紧邻的右子节点，这让整个 B+ 树的叶子节点的值形成了有序的链表。在执行操作时，务必对这些指针进行维护。</p>
<h2>0x01 B-link Tree</h2>
<p>为了解决 B 树的并行访问问题（写时读，一个成熟的文件系统不可能在写的时候不允许读取），B-link 树被设计了出来 ( <code>Efficient Looking for Concurrent Operations on B-Trees, 1981</code> )。</p>
<p>B 树没有办法在写的时候读取的问题在于写入可能会导致树平衡，从而修改树的结构。</p>
<p>B-link 树采用了增加一个指针来解决这个问题。它在所有 B 树原来的节点上增加了一个指针，这个指针指向了它紧邻的右节点。在树结构变换时，会首先保证这个指针被更新。在这种情况下，由树结构改变导致的节点无法访问可以通过指针来访问到。</p>
<p>接下来将简要介绍 B-link 树的算法。由于增加了指针，它的一些算法和一般的 B 树略有区别w</p>
<h3>Search</h3>
<ol>
<li>按照 B 树的方式找到它应该在的叶子节点。</li>
<li>如果它在那个节点，那么就查找到了</li>
<li>如果它不在，用指针向右遍历。</li>
</ol>
<h3>Insertion</h3>
<p>注意所有修改节点和节点关系的操作都是需要加锁的。</p>
<p>关键的区别产生在将节点拆分的过程。</p>
<ol>
<li>首先创建拆分后的右子节点，将数据复制进去，并将它的后继指针指向原先的后继。</li>
<li>将原先节点的后继指向新的右子节点，然后将应该复制进去的数据删除。</li>
<li>最后将这个右子节点连接到父节点上。如果这个连接过程使得父节点需要拆分，那么递归向上。</li>
</ol>
<p>注意在拆分父节点的过程中，需要向右遍历：b-link 树的结构不适合维护指向父节点的指针，因此在更新某一子节点的过程中，父节点被并行的其它操作更新了。</p>
<h3>Deletion</h3>
<p>Emmmm... B-link 树使用了一种……比较emmm的方式解决删除的并行化w</p>
<p>那就是仅删除键，不平衡树……</p>
<h2>0x02 Shadowing & Cloning based on B+-trees</h2>
<p><code>B-trees, Shadowing, and Clones ,Ohad Rodeh, 2007</code></p>
<p>emmmm...</p>
<p>这篇论文说的是基于 B+ 树的 Shadowing 和 Cloning 实现（emmm 我不太清楚中文翻译过来是什么），但是实际上为了保证不会过分地 <code>Shadow</code> 节点，将不维护指向紧邻右节点的指针。</p>
<h3>Shadowing</h3>
<p>什么是 Shadowing 呢？</p>
<p><code>Shadowing</code> 就是在要修改某一个硬盘上的页（可能是存储树节点的、文件内容的、或者其他东西的区块）的时候，首先将它复制到另外一个地址，进行修改，再把指向原地址的指针改为指向新地址。</p>
<p>这个机制可以有效保证在突然崩溃的情况下对文件系统的操作不会损坏原有的文件系统结构。但是它在应用到带有指向紧邻右节点的指针的 B 树的时候，会导致不得不对整棵树进行 <code>Shadow</code> 。如果不维护这个指针，那么需要被 Shadow 的仅是从根节点到被修改节点的一条路径。</p>
<h4>Concurrency...?</h4>
<p>那么既然不维护指向紧邻右节点的指针，那么它要如何保证并行访问的性能呢？</p>
<p>答案是使用一种更为积极的操作策略w</p>
<p>相比传统的 B 树实现（在完成插入/删除操作后再进行节点的拆分/合并），为了达到较好的并行访问效率，这种结构将在寻找将要插入/删除的位置的过程中对遇到的达到上/下限的节点立即进行拆分/合并。</p>
<p>这样可以保证对一个写入操作，同时需要加锁的节点最多只有一个节点和它的直接子节点。</p>
<h4>Locking Scheme</h4>
<p>在整个操作过程中，加解锁是按照以下策略进行的：</p>
<ul>
<li>不允许写时读</li>
<li>不允许同时写</li>
<li>允许同时读</li>
</ul>
<p>（也就是说，读写两种锁之间互斥，写锁之间互斥，读锁之间共享。</p>
<h3>Clones</h3>
<p><code>Cloning</code> 指的是快速地对整个文件系统进行快照的能力。这个特性的实现旨在能够快速地备份文件系统在某个时刻的状态，并且在将来能够只读地回溯到这个状态，或者将整个文件系统重置到当时的状态。</p>
<p><code>Cloning</code> 的可用性取决于以下四个方面：</p>
<ul>
<li>空间效率：快照应当通过与当前文件系统尽可能地共享页面来节省空间消耗。</li>
<li>速度：创建快照应当尽可能地快。</li>
<li>快照数量：快照数量应当尽可能地多。</li>
<li>操作自身：快照应当能够快照某个快照。</li>
</ul>
<p>为了达到以上这些特性，我们采用一种基于“引用计数”的方式。</p>
<p>基本的思想是使用一个空闲空间表来存储对硬盘上每一块空间的引用次数。当被 clone 的时候，那个页面的引用次数就 +1 。 当某一块空间将被修改时，如果它的引用次数大于 1 ，那么它将被复制一份。</p>
<p>具体的算法如下：</p>
<h4>Create a Clone</h4>
<ul>
<li>复制根节点</li>
<li>将根节点的直接子节点的引用计数 +1 。</li>
</ul>
<h4>Modify Keys</h4>
<p>将要修改一个节点时：</p>
<ul>
<li>如果引用次数 > 1，那么将它复制，并且将它的子节点的引用计数 + 1。</li>
</ul>
<p>通过这样的方式，使得创建 Clone 消耗的时间非常小，而且能够最大可能地利用公共的页面。</p>
</article>
<div class="tags">
<p>tags: <a href="/tag/os.html">OS</a>, <a href="/tag/linux.html">linux</a>, <a href="/tag/alg.html">ALG</a></p>
</div>
<hr>
</div>
</div>
</div>
<hr>
<!-- Footer -->
<footer>
<div class="container">
<div class="row">
<div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
<ul class="list-inline text-center">
<li>
<a href="https://github.com/HUSTMeituanClub">
<span class="fa-stack fa-lg">
<i class="fa fa-circle fa-stack-2x"></i>
<i class="fa fa-github fa-stack-1x fa-inverse"></i>
</span>
</a>
</li>
<li>
<a href="mailto:@hustmeituan.club">
<span class="fa-stack fa-lg">
<i class="fa fa-circle fa-stack-2x"></i>
<i class="fa fa-envelope fa-stack-1x fa-inverse"></i>
</span>
</a>
</li>
</ul>
<p class="copyright text-muted">
Blog powered by <a href="http://getpelican.com">Pelican</a>,
which takes great advantage of <a href="http://python.org">Python</a>.
</p> </div>
</div>
</div>
</footer>
<!-- jQuery -->
<script src="/theme/js/jquery.min.js"></script>
<!-- Bootstrap Core JavaScript -->
<script src="/theme/js/bootstrap.min.js"></script>
<!-- Custom Theme JavaScript -->
<script src="/theme/js/clean-blog.min.js"></script>
</body>
</html>