1
23:59:59,500 --> 00:00:05,777
[MUSIC]. 

2
00:00:05,777 --> 00:00:09,596
So Rick Cattel wrote a nice paper in 2010 
about scalable sequel and no sequel data 

3
00:00:09,596 --> 00:00:13,415
stores where he had a taxonomy of these 
systems, and placed popular instances of 

4
00:00:13,415 --> 00:00:18,943
these systems into that taxonomy. 
And so, this slide corresponds to his 

5
00:00:18,943 --> 00:00:23,680
grouping, where each color is one of the 
groups that he defined. 

6
00:00:23,680 --> 00:00:26,680
So he's already lumped them into 
key-value stores, document stores and 

7
00:00:26,680 --> 00:00:29,752
extensible record stores. 
And so what he meant by that was, a 

8
00:00:29,752 --> 00:00:32,650
document is you know, an example of this 
is an XML document or the JSON object 

9
00:00:32,650 --> 00:00:35,318
that we looked at in that Twitter 
assignment, where you can now sort of 

10
00:00:35,318 --> 00:00:41,580
arbitrary, arbitrary nesting. 
And it's also extensible, you can add new 

11
00:00:41,580 --> 00:00:43,350
things to it whenever you want. 
Okay. 

12
00:00:43,350 --> 00:00:46,150
So, no top down schema being enforced. 
Okay. 

13
00:00:46,150 --> 00:00:51,654
An extensible record you can think of 
much as much like a database record, 

14
00:00:51,654 --> 00:00:57,143
except that new attributes can be added. 
Okay. 

15
00:00:57,143 --> 00:01:00,215
So, there is some sort of notion of a 
schema that's used for different various 

16
00:01:00,215 --> 00:01:03,575
purposes, in particular there's sort of 
groups of attributes that are manipulated 

17
00:01:03,575 --> 00:01:07,535
together these families. 
but you get single attributes in an 

18
00:01:07,535 --> 00:01:10,742
individual row which are not to do with a 
relational database. 

19
00:01:10,742 --> 00:01:14,219
And then finally a key value, I'm using 
the term object here, is a set of 

20
00:01:14,219 --> 00:01:17,628
key-value pairs. 
And the difference here is that there is 

21
00:01:17,628 --> 00:01:20,960
typically not a schema of any kind. 
So, you don't care what keys they are. 

22
00:01:20,960 --> 00:01:24,118
They could be any keys at all. 
And there's no exposed nesting. 

23
00:01:24,118 --> 00:01:26,998
And what I mean by that is you know, a 
value can be anything you want, so you 

24
00:01:26,998 --> 00:01:30,118
might have some kind of complex object in 
the value, but its not going to be sort 

25
00:01:30,118 --> 00:01:34,628
of visible to the system. 
Its just going to be a blob, a bla, a 

26
00:01:34,628 --> 00:01:38,600
black box object that this doesn't know 
anything about. 

27
00:01:38,600 --> 00:01:40,185
Okay. 
So sort of only one layer of nesting is, 

28
00:01:40,185 --> 00:01:43,041
is aware of the system, unlike a document 
store or a document object that might 

29
00:01:43,041 --> 00:01:46,765
have multiple layers nesting there are 
exposed to the system. 

30
00:01:46,765 --> 00:01:50,745
Okay. 
And so his characterization of no-sequel 

31
00:01:50,745 --> 00:01:54,521
features, you know, admitting that 
there's perhaps not a formal definition 

32
00:01:54,521 --> 00:01:59,602
of no, well, there certainly isn't a 
formal definition of no-sequel. 

33
00:01:59,602 --> 00:02:03,024
But the term tends to be applied in 
contexts of systems that have these 

34
00:02:03,024 --> 00:02:06,208
features. 
So the sum-ability to scale simple 

35
00:02:06,208 --> 00:02:09,410
operations through put to many, many 
servers. 

36
00:02:09,410 --> 00:02:12,920
And by simple operation we mean key 
lookups, or maybe even attribute lookups, 

37
00:02:12,920 --> 00:02:16,650
or reads and writes of just one or a few 
records, right? 

38
00:02:16,650 --> 00:02:19,863
So, these sort of needle in a haystack 
kind of operations as opposed to these 

39
00:02:19,863 --> 00:02:23,127
big analytic queries, like we've been 
talking about with MapRoduce and with 

40
00:02:23,127 --> 00:02:25,720
databases. 
Okay. 

41
00:02:25,720 --> 00:02:30,140
And, sequel criteria is the ability to 
replicate and partition data over many 

42
00:02:30,140 --> 00:02:33,788
servers here. 
So you know, break a single large data 

43
00:02:33,788 --> 00:02:37,363
set into multiple pieces, [UNKNOWN] 
automatically, which you automate just 

44
00:02:37,363 --> 00:02:40,364
yourself. 
And here you might see the terms sharding 

45
00:02:40,364 --> 00:02:43,427
and horizontal partitioning. 
the difference between the two, if there 

46
00:02:43,427 --> 00:02:46,930
is any, is not particularly important, so 
you can think of them as synonyms. 

47
00:02:46,930 --> 00:02:50,030
Whenever you see sharding, think 
horizontal partitioning of a of, of a 

48
00:02:50,030 --> 00:02:52,598
database table. 
You'll see the term horizontal 

49
00:02:52,598 --> 00:02:55,479
partitioning used more in the database 
community and sharding used more in the, 

50
00:02:55,479 --> 00:02:57,391
the SQL community. 
Okay. 

51
00:02:57,391 --> 00:03:00,478
And then simple APIs are no query 
language this corresponds to the first 

52
00:03:00,478 --> 00:03:03,768
bullet, these are the simple operation, 
operations. 

53
00:03:03,768 --> 00:03:06,904
And then critically a weaker concurrency 
model then, what I'm saying is ACID 

54
00:03:06,904 --> 00:03:10,089
transactions now, and I might, we'll go, 
we'll talk a bit about ACID in the next 

55
00:03:10,089 --> 00:03:14,280
slide, but I'm not going to go into a lot 
of detail here. 

56
00:03:14,280 --> 00:03:18,115
There's, you know, 40 years of research 
on the, this topic, too much to cover in 

57
00:03:18,115 --> 00:03:22,068
this course, especially when we're mostly 
focused on you know, reading data and 

58
00:03:22,068 --> 00:03:26,694
analyzing data as opposed to a 
concurrency draw. 

59
00:03:26,694 --> 00:03:30,116
But we will spend some time on some 
techniques of converge control in a 

60
00:03:30,116 --> 00:03:33,330
minute okay. 
and then some of efficient use of 

61
00:03:33,330 --> 00:03:36,894
distributing, he tells us efficient use 
of a distributed in X is and RAM for data 

62
00:03:36,894 --> 00:03:40,426
storage. 
So, this is kind of minimizing latency, 

63
00:03:40,426 --> 00:03:43,600
is their emphasis, as opposed to just 
throughput. 

64
00:03:43,600 --> 00:03:45,953
All right. 
And then typically, they have this 

65
00:03:45,953 --> 00:03:49,487
ability to add new attributes to data 
records in various ways, as we talked 

66
00:03:49,487 --> 00:03:54,191
about on the previous slide, right. 
So the, the, the lack of a sche, no 

67
00:03:54,191 --> 00:03:57,290
schema, is what you can I can think of 
here. 

68
00:03:57,290 --> 00:04:04,630
Alright. 
So, this is no schema, no transactions. 

69
00:04:04,630 --> 00:04:12,187
And so, we'll go into more detail there. 
No query language, we can go no SQL. 

70
00:04:12,187 --> 00:04:19,388
Right. 
And high scale. 

71
00:04:19,388 --> 00:04:24,304
Okay. 
So, ACID, and he, he talks about this 

72
00:04:24,304 --> 00:04:30,424
term BASE that never quite caught on. 
I, I wouldn't typically use that, this 

73
00:04:30,424 --> 00:04:33,380
term, and I'm not sure I recommend you do 
either. 

74
00:04:33,380 --> 00:04:39,210
Certainly, ACID is much more permanent in 
the vernacular than, than this BASE is. 

75
00:04:39,210 --> 00:04:42,863
it's, it's, okay. 
So ACID is an acronym standing for these 

76
00:04:42,863 --> 00:04:47,280
four concepts: atomicity, consistency, 
isolation and durability. 

77
00:04:47,280 --> 00:04:52,131
And just briefly, this is you know, the 
context here is when we're modifying 

78
00:04:52,131 --> 00:04:56,882
records in, let's say a database. 
And we can be modifying lots of different 

79
00:04:56,882 --> 00:04:59,330
records across different tables, anything 
we want. 

80
00:04:59,330 --> 00:05:02,360
And the point is they're all lumped into 
one transaction. 

81
00:05:02,360 --> 00:05:05,816
And so, each one of these refers to you 
know, that's the context for each one of 

82
00:05:05,816 --> 00:05:09,040
these concepts. 
So, atomicity means that the entire 

83
00:05:09,040 --> 00:05:11,880
transaction either needs to succeed or 
needs to fail. 

84
00:05:11,880 --> 00:05:15,040
Right, you gotta learn to have partial 
transaction succeed. 

85
00:05:15,040 --> 00:05:20,650
Consistency is the slipperiest one in my 
mind and this quote down here maybe 

86
00:05:20,650 --> 00:05:24,424
captures that. 
And so, there's sort of any data written 

87
00:05:24,424 --> 00:05:27,158
into the database must be valid according 
to all defined rules. 

88
00:05:27,158 --> 00:05:29,350
And the question is well, where do these 
defined rules come from. 

89
00:05:29,350 --> 00:05:32,240
Sometimes they're actually integrity 
constraints in the database. 

90
00:05:32,240 --> 00:05:35,828
other times they're just sort of business 
logic rules, perhaps enforced by the 

91
00:05:35,828 --> 00:05:39,113
application or just assumed by the 
application. 

92
00:05:39,113 --> 00:05:42,941
So, it's a little bit difficult to say, 
prove a system is, achieves application 

93
00:05:42,941 --> 00:05:47,748
level consistency but that's the goal. 
The point is, you, if, if there's only 

94
00:05:47,748 --> 00:05:50,820
certain allowed states the database to 
have, you can't, you shouldn't have a 

95
00:05:50,820 --> 00:05:55,290
system that allows transactions to put 
you into an invalid state, okay? 

96
00:05:55,290 --> 00:05:57,465
Usually, you'd only go from working state 
to working state. 

97
00:05:57,465 --> 00:06:02,009
Isolation means that while the 
transaction is occurring, other readers 

98
00:06:02,009 --> 00:06:06,720
and writers can't sniff partially 
completed values. 

99
00:06:06,720 --> 00:06:10,077
Okay. 
No, partially, you, you can't sniff 

100
00:06:10,077 --> 00:06:16,380
values of data items before the 
transaction is complete. 

101
00:06:16,380 --> 00:06:19,090
They only get final stage. 
And this one is the one most often 

102
00:06:19,090 --> 00:06:22,879
relaxed in various ways. 
In part because it's very expensive and 

103
00:06:22,879 --> 00:06:25,860
also because it's not usually all that 
critical. 

104
00:06:25,860 --> 00:06:28,506
And then durability just means that if 
you report back that the transaction 

105
00:06:28,506 --> 00:06:31,057
succeeded, it needs to have actually 
succeeded. 

106
00:06:31,057 --> 00:06:33,829
Meaning that it needs to be written out 
to some kind of non-volatile storage, so 

107
00:06:33,829 --> 00:06:36,265
that if the power goes out and the 
machine crashes, you don't say, hey, 

108
00:06:36,265 --> 00:06:40,606
whoops that transaction that I accepted 
yesterday or committed yesterday. 

109
00:06:40,606 --> 00:06:42,930
Well, you need to do that again because 
it didn't take. 

110
00:06:42,930 --> 00:06:44,670
Alright, so that's not allowed. 
So fine. 

111
00:06:44,670 --> 00:06:47,678
So these, these all make some sense with 
you know, a little bit of, a little bit 

112
00:06:47,678 --> 00:06:51,606
of notion of consistency as I mentioned. 
And the pun here is that they're trying 

113
00:06:51,606 --> 00:06:54,076
to sort of force an acronym on BASE, and 
this isn't Rick Cottell, this came out, 

114
00:06:54,076 --> 00:06:57,938
else from elsewhere. 
but the idea is well, it's basically 

115
00:06:57,938 --> 00:07:01,239
available. 
There's some notion of soft state and it 

116
00:07:01,239 --> 00:07:05,760
eventually consistent. 
We talked about eventual consistency eh, 

117
00:07:05,760 --> 00:07:10,219
eh, at least an overview in the previous 
segment. 

118
00:07:10,219 --> 00:07:14,040
Fine, that's all I'm going to say about, 
that. 

119
00:07:14,040 --> 00:07:16,768
So, something else I like about this 
paper is, he sort of says look, you know, 

120
00:07:16,768 --> 00:07:19,790
the, the major impact systems here are 
these three. 

121
00:07:19,790 --> 00:07:28,530
This Memcached or Memcache D, Dynamo from 
Amazon and BigTable from Google. 

122
00:07:28,530 --> 00:07:31,153
And the reason he says these are the 
major impacts is, you can kind of trace 

123
00:07:31,153 --> 00:07:33,948
the lineage and show that other systems 
are basically taking ideas from one of 

124
00:07:33,948 --> 00:07:38,970
these three early systems. 
So memcache is very, very simple. 

125
00:07:38,970 --> 00:07:42,333
And we'll talk a little bit about one 
particular technique that it made 

126
00:07:42,333 --> 00:07:46,655
popular, in a minute. 
but it's essentially just, hey, look, 

127
00:07:46,655 --> 00:07:52,476
let's just load everything into memory, 
scale it out across many, many machine. 

128
00:07:52,476 --> 00:07:55,531
Right, and they'll be able to serve read 
requests without having to go sort of, 

129
00:07:55,531 --> 00:07:58,491
query the data base. 
We'll just be able to do it directly from 

130
00:07:58,491 --> 00:08:00,950
memory. 
And what's also made this very, very 

131
00:08:00,950 --> 00:08:04,918
popular is you can kind of install it on 
top of your either scale, scale-out or 

132
00:08:04,918 --> 00:08:09,989
non scale-out database. 
And it just sort of just works, right. 

133
00:08:09,989 --> 00:08:13,544
It just makes things faster for, for read 
heavy workloads. 

134
00:08:13,544 --> 00:08:18,570
And that was kind of a nice thing. 
So that's an older system, sort of around 

135
00:08:18,570 --> 00:08:22,466
the scale of 2003, but it's still very 
widely used. 

136
00:08:22,466 --> 00:08:26,331
And very, very popular, and there has 
been all sorts of extensions to it. 

137
00:08:26,331 --> 00:08:29,560
And so, we'll talk about the probably the 
most basic version. 

138
00:08:29,560 --> 00:08:33,720
Amazon's dynamo paper which has been 
somewhat more recently released as a 

139
00:08:33,720 --> 00:08:38,712
cloud service called dynamo DB. 
what they did was, they didn't invent the 

140
00:08:38,712 --> 00:08:42,540
concept of eventual consistency, but they 
did sort of show that if you relax the 

141
00:08:42,540 --> 00:08:47,610
consistency notion, that will allow you 
to scale way, way out. 

142
00:08:47,610 --> 00:08:49,764
Okay. 
And so data fetched can not be allowed, 

143
00:08:49,764 --> 00:08:52,866
can not guaranteed to be up to date, but 
updates are guaranteed to be eventually 

144
00:08:52,866 --> 00:08:57,042
propagated, everywhere they need to be. 
And we gave an example of why this was a 

145
00:08:57,042 --> 00:09:00,437
good idea in the last segment. 
And then Google's BigTable that we'll 

146
00:09:00,437 --> 00:09:05,173
spend some time on you know, demonstrated 
that record oriented storages could scale 

147
00:09:05,173 --> 00:09:09,205
to 1000's and 1000's of machines, and 
that was something that data bases had 

148
00:09:09,205 --> 00:09:12,830
not shown. 
Okay. 

149
00:09:12,830 --> 00:09:18,722
So, let's talk about each one of these 
systems in turn. 

150
00:09:18,722 --> 00:09:23,211
So memcached, as he says, main-memory 
caching service, no persistence, the 

151
00:09:23,211 --> 00:09:27,900
basic version is no replication. 
Meaning there's not two copies, there's 

152
00:09:27,900 --> 00:09:31,703
only one copy of every cached value. 
So, if something goes down, if that goes 

153
00:09:31,703 --> 00:09:35,374
down then it's gone. 
That's okay, because it's sort of a 

154
00:09:35,374 --> 00:09:39,720
cache, it's not assumed to be the golden 
copy of anything. 

155
00:09:39,720 --> 00:09:43,122
That being said, there's been many 
extensions that provide various, these 

156
00:09:43,122 --> 00:09:46,360
various features including membrain and 
membase. 

157
00:09:46,360 --> 00:09:50,323
So it's a very mature system and still in 
wide use. 

158
00:09:50,323 --> 00:09:55,237
And an important concept that they 
adopted, in this context was consistent 

159
00:09:55,237 --> 00:10:01,511
hashing, so I want to explain a little 
bit what consistent hashing is. 

160
00:10:01,511 --> 00:10:04,369
so that's one takeaway from, from this 
lecture, okay. 

161
00:10:04,369 --> 00:10:07,114
So first for those of you without 
actually having too much of a background 

162
00:10:07,114 --> 00:10:09,938
in programming. 
What is hashing, so what is regular 

163
00:10:09,938 --> 00:10:12,250
hashing? 
Well, the problem we're looking at there 

164
00:10:12,250 --> 00:10:15,085
in this co, hashing's a very, very 
general kind of, it's very fundamental to 

165
00:10:15,085 --> 00:10:18,048
all programming. 
But in the context of what we're doing 

166
00:10:18,048 --> 00:10:21,145
here, we're trying to assign data keys to 
a bunch of different servers. 

167
00:10:21,145 --> 00:10:25,277
Okay. 
And the simplest way you might do this is 

168
00:10:25,277 --> 00:10:27,330
sort of a round robin thing. 
Right? 

169
00:10:27,330 --> 00:10:29,772
The first key goes to the first server, 
the second key goes to the second server, 

170
00:10:29,772 --> 00:10:32,220
and you keep going untill you run out of 
servers. 

171
00:10:32,220 --> 00:10:35,575
And you start back over by the first one. 
And that's implemented by this module. 

172
00:10:35,575 --> 00:10:41,370
Okay. 
So, each of these data keys is placed 

173
00:10:41,370 --> 00:10:47,458
somewhere on this, on one of these 
servers at various points. 

174
00:10:47,458 --> 00:10:52,500
Fine, that's how hashing works. 
What's, what's wrong with that? 

175
00:10:52,500 --> 00:10:56,054
Well, what happens if I want to add more 
servers to the mix, right. 

176
00:10:56,054 --> 00:11:00,370
I want to scale out to, I want to double 
the number of servers. 

177
00:11:00,370 --> 00:11:06,310
Well, every existing data key now needs 
to be reeval, it's place, it's location 

178
00:11:06,310 --> 00:11:13,596
needs to be reevaluated by computing k 
mod 2 N instead of k mod N. 

179
00:11:13,596 --> 00:11:23,900
Which means every single data item is 
going to be remapped at once. 

180
00:11:23,900 --> 00:11:26,060
So every time you want to add a server, 
you end up having to move all the data 

181
00:11:26,060 --> 00:11:28,895
that's already in the system and you're 
dead in the water. 

182
00:11:28,895 --> 00:11:30,596
Okay. 
So what you want is some notion of 

183
00:11:30,596 --> 00:11:34,200
consistent hashing, where consistent 
means when I play something somewhere and 

184
00:11:34,200 --> 00:11:37,539
I add more servers, it's typically 
going to stay right where right where it 

185
00:11:37,539 --> 00:11:41,309
is. 
And so there's a pretty good trick that's 

186
00:11:41,309 --> 00:11:44,052
pretty simple to understand for doing 
this. 

187
00:11:44,052 --> 00:11:47,035
Okay. 
So here's how it works. 

188
00:11:47,035 --> 00:11:53,041
First key idea is you're going to map the 
server IDs into the same space as the key 

189
00:11:53,041 --> 00:11:57,304
values themselves. 
Okay. 

190
00:11:57,304 --> 00:12:03,499
So we apply a fa, a function that I'm 
going to leave sort of unspecified and 

191
00:12:03,499 --> 00:12:10,324
map server 1 to some point on this circle 
and server 2 some point on this circle, 

192
00:12:10,324 --> 00:12:18,670
and server 3 some place on this on this 
circle. 

193
00:12:18,670 --> 00:12:24,545
And now, what that does is, divide this 
space up into three sections. 

194
00:12:24,545 --> 00:12:27,412
Okay. 
And now, each key that comes around, I 

195
00:12:27,412 --> 00:12:32,722
also map it into this circle. 
So, this gets key one and this gets key 

196
00:12:32,722 --> 00:12:40,345
two, key three, key four, key five, key 
six, key seven and so on. 

197
00:12:40,345 --> 00:12:44,808
Okay. 
And now this entire region one, server 1, 

198
00:12:44,808 --> 00:12:55,044
server 2, server 3, this entire region is 
responsible for all of these data keys. 

199
00:12:55,044 --> 00:13:01,708
Sorry, this server is responsible for all 
these data keys. 

200
00:13:01,708 --> 00:13:05,841
And then this server is responsible for 
all the data keys in this region. 

201
00:13:05,841 --> 00:13:06,844
And this server is responsible for all 
the data keys in this region. 

202
00:13:06,844 --> 00:13:08,640
Okay. 
And so what's nice about this is, now 

203
00:13:08,640 --> 00:13:11,655
when I add a new server, server ID equals 
4. 

204
00:13:11,655 --> 00:13:15,170
Well, let's say it comes around and it 
gets stuck right here. 

205
00:13:25,500 --> 00:13:27,770
Well, that's a bad spot for, for my 
example actually. 

206
00:13:27,770 --> 00:13:35,410
Let's say it comes around right here. 
Well, you just apply the same rule. 

207
00:13:35,410 --> 00:13:41,428
It should be a po, it should be 
responsible for every key in this region, 

208
00:13:41,428 --> 00:13:50,668
which means that these two guys need to 
be moved from server 3 to server 4. 

209
00:13:50,668 --> 00:13:57,049
Right? 
But you only have to move that one 

210
00:13:57,049 --> 00:14:02,552
section of data. 
And so, it splits at most sort of k over 

211
00:14:02,552 --> 00:14:06,563
N data items. 
Alright. 

212
00:14:06,563 --> 00:14:11,225
So this is a nice trick and there's all 
kinds of extension for supporting 

213
00:14:11,225 --> 00:14:16,109
replicas we need to put data in obviously 
more than one place, well, just sort of 

214
00:14:16,109 --> 00:14:22,675
hashed in two different places. 
So if you want to hash the same data 

215
00:14:22,675 --> 00:14:27,566
under two different places compute, h of, 
lets say d as the data key, and then also 

216
00:14:27,566 --> 00:14:34,075
put it to, you know, put it all three 
places, and you're done. 

217
00:14:34,075 --> 00:14:39,399
Okay. 
So how do we serve request in this set 

218
00:14:39,399 --> 00:14:43,436
up? 
Well, imagine the key space is divided 

219
00:14:43,436 --> 00:14:48,060
across various servers in the same way we 
describe, and the request comes into the 

220
00:14:48,060 --> 00:14:52,344
leader that may be elected among the 
servers or may be just assigned top down 

221
00:14:52,344 --> 00:15:00,728
by the, by the system. 
Or could even be assigned randomly. 

222
00:15:00,728 --> 00:15:04,563
And the naive way of, of doing this is 
well, this, this, this server would check 

223
00:15:04,563 --> 00:15:08,044
to see whether it has the key being 
requested, and if it doesn't it would 

224
00:15:08,044 --> 00:15:12,500
just forward the request on to the next 
guy. 

225
00:15:12,500 --> 00:15:14,379
Okay. 
But this is no good because there could 

226
00:15:14,379 --> 00:15:18,411
be many, many servers and this would 
encourage server latency every time you 

227
00:15:18,411 --> 00:15:23,915
would want to do a read. 
So, a better way of doing this is for 

228
00:15:23,915 --> 00:15:31,500
each server to memorize the locations of 
other servers in the ring. 

229
00:15:31,500 --> 00:15:34,040
And which servers it memorizes is like 
this. 

230
00:15:34,040 --> 00:15:45,014
So it knows where itself is, it knows, A 
plus 2, A plus 4, A plus 8, A plus 16 and 

231
00:15:45,014 --> 00:15:53,200
so on. 
And what it does is, how it knows the key 

232
00:15:53,200 --> 00:15:57,115
range being managed by each one of these 
servers. 

233
00:15:57,115 --> 00:16:02,255
Okay. 
And so what it can do, is forward the 

234
00:16:02,255 --> 00:16:10,646
request to the server that is closest to 
the key range it is looking for, okay. 

235
00:16:10,646 --> 00:16:16,086
And so this takes a logarithmic number of 
hops away, you can imagine there are lots 

236
00:16:16,086 --> 00:16:24,256
of servers here. 
And keeping all this information straight 

237
00:16:24,256 --> 00:16:26,970
when new servers come in is still, each 
server only has to keep track of a 

238
00:16:26,970 --> 00:16:33,025
algorithm of servers as well. 
So everything sort of ends up being 

239
00:16:33,025 --> 00:16:37,643
algorithm to maintain this. 
Okay.