[MUSIC]. 
Okay. 
So, the third influential system that 
Rick mentioned in the paper is BigTable 
from Google which is a paper from 2006. 
And so, here we're looking at primary 
index look up, secondary index look up. 
Transactions are also at this sort of 
scale of individual record. 
joint analytic is not supported by 
BigTable directly, but in the, in H base 
which is the open source implementation 
of it. 
And in, well, in, in Google's 
implementation as well, it was sort of 
designed to be compatible with MapReduce. 
And so, you can run MapReduce on, over 
here with the same data that's stored in 
BigTable. 
So, there kind of complementary, and then 
there some notion of integrity 
constraints or schema here, and we'll 
talk about how to implement it. 
There's no views that I can see and 
there's no sort of language level or 
alge, or algebra level for manipulating 
these things. 
There all sort of NoSQL style micro 
interactions with individual records and 
cells, okay? 
So, this is a paper in OSDI for 2006, and 
some overlap with the authors of the 
MapReduce paper. 
And it was sort of designed from the 
start to be complementary of MapReduce. 
So, if you can remember what was one of 
the main things that was missing from 
MapReduce s, or a few things that are 
missing. 
Well, in particular, you couldn't look 
things up by index. 
You couldn't get these little sort of low 
latency accesses. 
So, for example, you want to find all the 
records, you know, given a big data set, 
you want to find all the records in some 
other data set that correspond to. 
You want to do some sort of a join. 
The best you could do is process, you had 
to touch every single record. 
There was no way to zoom in to adjust the 
right one you wanted, okay? 
And so, BigTable provides that fast 
key-based look up, but you could still 
process the overall data as a big set of 
key value records with MapReduce. 
Fine. 
So, the data model here is a sparse, 
distributed, persistent, 
multidimensional, sorted map. 
And what they mean here is that, you can 
basically access any cell in a big table 
by giving a row ID, a column, a column 
name and a time stamp. 
the time stamp isn't really describing 
this English description here, it's for 
versioning. 
So, when you have, after you have 
updates, you'll, you'll keep track of 
past versions of the same cell, okay? 
And so, if you provide these three 
parameters, data table will return you a 
string quickly, all right? 
So each row is data's all sorted 
lexigraphically by the row key, which is 
this row ID in this, in this bit, right? 
So this is a, some sort of primary key, 
and it, you know, in sort of relational 
language or just a key in, in kind of a 
NoSQL framework. 
And then this key range, I say that that 
the integers, the contiguous subranges of 
this set of keys, will be assigned to a 
tablet, all right? 
Okay, so this is a little different way 
of dividing up the data that we've seen 
in the past, in at least one system. 
We talked about a parallel database model 
we happened to use the example from 
Teradata, and so how did they breakup 
data. 
Well, they did it by hashing, right? 
So, every individual record would be sent 
to a server according to a hash function, 
which you can generally just think of as 
sort of a round robin. 
The point is that two keys that are next 
to each other in space, so sort of time 
stamp 5 pm, and time stamp 5:01. 
There's no reason to believe that 5:00 
and 5:01 are going to be on the server in 
Teradata's model. 
Here they are. 
So, what are the pros and cons of this? 
Well, if you're going to typically access 
a whole range of keys at once, it's 
pretty nice to be able to, you know, when 
you get one. 
You get the others, too, sort of for 
free, because you're, you're pulling them 
all back. 
However If one particular key range is 
much more popular than the others, just 
by using the time example again. 
the most recent data perhaps is the most 
popular. 
And so, if all the requests are going to 
that, one key range. 
Then, you got a bunch of idle servers 
hosting all the other tablets that are 
corresponding to older times and all the 
requests are going to this one tablet. 
And so for that reason, Teradata sort of 
chooses to hash everything. 
So that on every request, all the servers 
may have to be accessed, but that's good 
for scalability. 
Okay, so pros and cons. 
Alright, so the tablet here is the unit 
of distribution and load balancing 
fluency. 
And so, they'll move tablets between 
servers as things start to get 
unbalanced, right? 
A key, if you're, if you're key range is, 
you know, January, February, March, 
April, May. 
And there's a whole lot of data coming in 
from March, they'll split that into 
multiple tablets and start, and start 
moving. 
They're moving those tablets around 
between servers in order to balance 
things. 
Okay, so within a single table, you can 
have these groups of columns called 
Column Families. 
And the column names have the family 
right in there as a qualifier. 
And this family is the basic unit of axis 
control so you can provide permissions on 
a group of columns. 
memory accounting in that they are sort 
of allocated as a, as a unit in memory, 
and then disk accounting. 
So, they moved around on disk as a unit 
as well, okay? 
And so, during this point, the typically 
all columns in the family are the same 
type, which I find a little unusual. 
Because they sort of talk about being the 
basic unit of access control and suggests 
that there's, you know, things that go 
together. 
for access control sort of social 
security number and employee ID or 
something may or may not be the same 
type. 
So, there's sort of a logical grouping 
requirement that they seem to be trying 
to meet. 
But then there at the same time, they 
have to be the same type which is very 
technical reasons, especially because 
they want to compress these things. 
So, if you have a whole bunch of integers 
it's easier to compressed, and you have a 
mix of integers and strings. 
So, I think they're trying to kill too 
many birds with one stone here, alright? 
And then, each cell a can be versioned, 
which is the third part of that of that 
key look up, row ID, column name and time 
stamp. 
And each new version increments that time 
stamp and say hey, you here, you can 
enact different kinds of policies. 
Where you only keep the latest inversions 
or you keep only the versions since a 
given, a given time stamp, right? 
So, how these tablets are managed is a 
master will assign the tablets to tablet 
servers. 
And the tablet server handles reads and 
writes from the tablets it controls, 
okay? 
And so, clients communicate directly with 
the tablet server as oppose to having to 
go through the master every time, which 
is helps through scalability, okay? 
And when, when a tablets are to get too 
big, it will split it and load balance 
it, alright? 
So, the metadata keeping track of where 
tablets are located is organize itself in 
another tablet. 
So, there is a root tablet here that 
describes each record in here describes a 
group of records. 
A group of location records in a, you 
know, bigger table, and then each one of 
these metadata tablets gives the location 
of a particular user table, okay? 
And so, this is how you sort of keep 
track hierarchically of where everything 
is at one time. 
and so chubby that they mention in the 
paper is a distributed lock service for 
controlling access to things. 
I'm not going to talk too much about it, 
okay? 
So how, how are reads and writes handled 
in this system? 
Well, there's a table in memory that 
stores a sequence of updates as they 
occur, okay? 
And, a right operation is lo, is, you 
know, adds a record into the memory, 
memory resident table, but it's also 
written to a log for fault tolerance 
purposes, okay? 
So, if this [UNKNOWN] ever goes down, it 
reads the tablet log and you can 
reconstruct what's going on. 
And then read operations are served by 
reading these SSTable files. 
You have actual data itself, but then 
also by applying the updates from the 
memtable on the fly, right? 
So it needs, it needs a stream, it says 
here's the value and then here's the 
stream of updates. 
I can do apply that value to get the true 
value, okay? 
And then, there's two, so this, so this 
is fine but, but what happens when the 
memtable gets bigger and bigger and 
bigger? 
Well, there's two kinds of events that 
occur to, you know, do the bookkeeping 
here. 
So, one is a minor compaction. 
And this is when the memtable gets big, 
it gets written out into an SS, into a 
new SS Table file and the changes are 
merged okay? 
And then a major compaction is, take all 
the SS Tables and rewrite them all into 
one big one. 
They may be split into multiple files, 
and also clean up any deletes that have 
occurred. 
So, deletes are just appended as 
instructions but aren't necessarily, 
doesn't actually remove anything, so they 
are sort of garbage collected, okay? 
So in this way, you can keep sort of the 
read throughput pretty high. 
And for, to keep this upkeep going on in 
the background, alright? 
So, those are a host of other tricks 
here, too, where they, can do various 
forms of compression, specify by 
compliance, which can be specified by the 
clients. 
There's some different ways of doing it. 
They use bloom filters to speed up 
existence test. 
So, if I give you row ID, a column ID and 
a time stamp and say find me this value, 
what these bloom filters allow you to do 
are, is to very quickly determine whether 
that does not exist in the system. 
So, these bloom filter data structures 
are pretty cool. 
And I'm going to walk through them in 
this course in a, in a couple of weeks, 
okay? 
So, they help you quickly determine 
whether that key does not exist in the 
system, it avoids disk accesses during, 
during reads. 
Alright, and then there's locality groups 
which you can define another layer of 
organization on top of families. 
And these are groups of column families 
that tend to be accessed together. 
Fine. 
And then, another trick here is, is to 
make sure that the SS Tables, these disk 
chunks are immutable. 
They never get written indirectly. 
The only time they get written is when 
these major compactions happen and the 
whole thing is sort of reorganized. 
And so, that means that the only writable 
data structure is this memtable. 
And so, the amount of concurrency control 
to keep things un, remains, remains 
pretty simple, okay?