1
00:00:00,000 --> 00:00:05,037
One of the first no sequel databases was
Google's Big Table.

2
00:00:05,037 --> 00:00:09,094
And its, Hadoop equivalent, which is
called HBase.

3
00:00:09,094 --> 00:00:15,094
Big Table is, in many ways, probably the
origin of the term big data.

4
00:00:15,094 --> 00:00:21,425
This is one of the earliest, papers
describing this was almost three or four

5
00:00:21,425 --> 00:00:28,749
years ago and it is Google's
implementation on top of the distributed

6
00:00:28,749 --> 00:00:36,477
GFS file system, which led to the
development of many no sequel databases in

7
00:00:36,477 --> 00:00:41,968
the first place.
A big table, table is distributed across

8
00:00:41,968 --> 00:00:49,524
many different servers by row first.
So that table is broken up into many

9
00:00:49,524 --> 00:00:56,858
tablets, each containing multiple rows.
The tablets are called regions by the way

10
00:00:56,858 --> 00:01:04,414
in H base tablet is the GFS term.
Each tablet in turn, is broken up into

11
00:01:04,414 --> 00:01:13,240
column families, each containing a set of
columns from among those in that row.

12
00:01:13,240 --> 00:01:21,771
Each column family which contains.
A particular set of columns spanning

13
00:01:21,771 --> 00:01:28,422
multiple rows, is stored in a chunk of the
distributed file system.

14
00:01:28,422 --> 00:01:35,800
The GFS or HGFS.
Each, such chunk is served by, a tablet

15
00:01:35,800 --> 00:01:45,997
server which takes care of three separate
replicas as they are maintained in GFS as

16
00:01:45,997 --> 00:01:54,357
we have seen before, and the tablet
servers together, form the entire big

17
00:01:54,357 --> 00:01:57,754
table.
Of course in order to access any

18
00:01:57,754 --> 00:02:04,581
particular record, we need to know which
tablet server that particular record and

19
00:02:04,581 --> 00:02:11,560
column that we are looking for falls in.
And for that purpose there is a metadata

20
00:02:11,560 --> 00:02:18,978
table which keeps track of which tablet
server a particular row, lies in.

21
00:02:18,978 --> 00:02:29,155
The metadata table itself is another big
table and is therefore cons-, comprises of

22
00:02:29,155 --> 00:02:37,014
tablets or regions which are maintained
on, a separate set of tablets servers.

23
00:02:37,014 --> 00:02:43,049
One particular tablet is the root tablet.
So all our searches start from there.

24
00:02:43,049 --> 00:02:46,623
So to look for a particular row, and
column.

25
00:02:46,623 --> 00:02:53,017
One looks up the tablet, root tablet.
Which will tell us which child's tablet,

26
00:02:53,017 --> 00:02:59,043
among the metadata tablets contain the
information about that particular row

27
00:02:59,043 --> 00:03:03,024
column.
The child tablet will in turn tell us

28
00:03:03,024 --> 00:03:09,087
which tablet server to look for, and there
we can pick up that chunk where the

29
00:03:09,087 --> 00:03:14,012
required row and column family is actually
stored.

30
00:03:14,053 --> 00:03:20,498
Let's take a look at date, what data in a
big table looks like, to get a feel for

31
00:03:20,498 --> 00:03:25,023
how it works.
The row is indexed by some key, for

32
00:03:25,023 --> 00:03:30,015
example a transaction ID, when one is
storing sales transactions.

33
00:03:30,015 --> 00:03:35,007
Different column families can have
multiple columns within them.

34
00:03:35,007 --> 00:03:40,592
For example, we can have the location
column family which contains a whole bunch

35
00:03:40,592 --> 00:03:47,569
of columns with to deal with location, and
all those are stored together in single

36
00:03:47,569 --> 00:03:51,433
chunks.
The sale column family might have other

37
00:03:51,433 --> 00:03:57,632
set of columns and similarly for products
and many other column families would be

38
00:03:57,632 --> 00:04:01,074
there.
Each of them is stored separately in

39
00:04:01,074 --> 00:04:06,485
different chunks servers.
An important point about big table is

40
00:04:06,485 --> 00:04:13,716
that, the num, while the number of column
families for a big table is fixed when you

41
00:04:13,716 --> 00:04:18,006
create it.
The number of columns within the column

42
00:04:18,006 --> 00:04:23,011
family can vary.
So you could, dynamically add new columns

43
00:04:23,011 --> 00:04:29,549
to a particular big table column family.
Further, each parti, each column family

44
00:04:29,549 --> 00:04:33,294
for a particular row can have multiple
entries.

45
00:04:33,294 --> 00:04:37,012
For example, you could have the region
being the U.S.

46
00:04:37,012 --> 00:04:41,544
East Coast as well as the U.S.
Northeast, and that's perfectly fine

47
00:04:41,544 --> 00:04:47,732
unlike a relational database where a
particular row-column combination can have

48
00:04:47,732 --> 00:04:51,308
only one value.
Additionally, each of these different

49
00:04:51,308 --> 00:04:56,528
values for a particular row.
Column combination can be time stamped.

50
00:04:56,528 --> 00:05:04,408
So that for example, the, the location for
this transaction might be the US East

51
00:05:04,408 --> 00:05:10,063
Coast today, but tomorrow one is free to
change it by making it U.S.

52
00:05:10,063 --> 00:05:15,002
Northeast.
But that's not done by updating the value

53
00:05:15,002 --> 00:05:20,102
US East Coast, but by inserting a new
value with a new time stamp.

54
00:05:20,102 --> 00:05:26,455
So that one can always look up whichever
version of the region, one wants to look

55
00:05:26,455 --> 00:05:31,372
for depending on, which time stamps one
are, one is searching for.

56
00:05:31,372 --> 00:05:37,098
Someone can keep essential multiple
snapshots of one's categorization of data

57
00:05:37,098 --> 00:05:43,094
together in the same big table, which is
a, a tredmendous advantage compared to a

58
00:05:43,094 --> 00:05:49,084
traditional relational database.
Because Big Table and HBase rely on the

59
00:05:49,084 --> 00:05:55,041
underlying distributed file system GFS or
HDFS respectively.

60
00:05:55,041 --> 00:05:59,074
They also inherit some of the properties
of these systems.

61
00:05:59,074 --> 00:06:05,057
In particular, large parallel reads and
inserts are efficiently supported even

62
00:06:05,057 --> 00:06:11,010
simultaneously on the same table, unlike a
traditional relational database.

63
00:06:11,010 --> 00:06:17,008
Similarly, reading all the rows for a
small number of column families in a large

64
00:06:17,008 --> 00:06:20,060
table.
Such as for an aggrega, aggregation query,

65
00:06:20,060 --> 00:06:25,088
like summing them all up.
Is efficient in the manner similar to the

66
00:06:25,088 --> 00:06:31,362
column oriented databases.
Of course one of the down sides of the Big

67
00:06:31,362 --> 00:06:38,010
Table or H Base architecture is that,
there is really only one key, which is the

68
00:06:38,010 --> 00:06:43,970
primary key with which, data is
distributed across different processors or

69
00:06:43,970 --> 00:06:51,166
different channels.
If one wants to access data by any other

70
00:06:51,166 --> 00:06:56,547
column family.
One can't really rely on any other index

71
00:06:56,547 --> 00:07:00,036
and the only way to do that is by reading
all the data.

72
00:07:00,036 --> 00:07:06,762
So for queries, Big Table is not that
efficient, and one needs to add additional

73
00:07:06,762 --> 00:07:11,022
structure to it, so as to enable efficient
queries.

74
00:07:11,022 --> 00:07:17,073
In fact this is true for, any mechanism
that one used to store data in sharded

75
00:07:17,073 --> 00:07:21,049
form.
By sharding, one means storing different

76
00:07:21,049 --> 00:07:27,092
rows on different pieces of disk or
different servers like, like tablet

77
00:07:27,092 --> 00:07:34,045
servers and distributed file systems.
So, if you have sharded data, where data

78
00:07:34,045 --> 00:07:40,017
is distributed across machines by some
key, and you want to access it using

79
00:07:40,017 --> 00:07:43,060
another key.
You need to do something smarter.

80
00:07:43,060 --> 00:07:47,026
Which is essentially to create an index of
some kind.

81
00:07:47,026 --> 00:07:52,691
For example let's take our, Big Table of
records which indicate invoice

82
00:07:52,691 --> 00:07:57,055
transactions.
For example which are to do with billing

83
00:07:57,055 --> 00:08:02,090
of some kind, or some products.
So that your, our main table is the

84
00:08:02,090 --> 00:08:07,035
invoice table which has keys which is the
transaction.

85
00:08:07,035 --> 00:08:13,093
Which might have different values for
different time-stamps as we have discussed

86
00:08:13,093 --> 00:08:18,001
earlier.
But now if you want to search this table

87
00:08:18,001 --> 00:08:24,054
by some other column such as by product,
one would need to create index tables

88
00:08:24,054 --> 00:08:31,063
which would also be big tables but, their
keys would be things like, product CD

89
00:08:31,063 --> 00:08:38,068
Achieve, product DBME, etcetera, which
would tell us which key in the original

90
00:08:38,068 --> 00:08:44,018
table, this particular combination of
product actually lies.

91
00:08:44,018 --> 00:08:51,048
Similarly one could create index tables
for amounts, as well as for combinations

92
00:08:51,048 --> 00:08:56,462
between, say city and the status of the
index, of the, of the transaction.

93
00:08:56,462 --> 00:09:01,100
It's also useful to create this index in
sorted form.

94
00:09:01,100 --> 00:09:08,167
So that when you insert the records in a
index table they actually get inserted in

95
00:09:08,167 --> 00:09:12,455
sorted order.
As a result, making a query which asks us

96
00:09:12,455 --> 00:09:20,338
to find all transactions with amounts
between two ranges, say between 50 and 90

97
00:09:20,338 --> 00:09:27,868
becomes easier since all the values
between such a range lie in the same

98
00:09:27,868 --> 00:09:33,103
contiguous piece of the index table for
same amount.

99
00:09:33,103 --> 00:09:40,413
Once you've retrieved all these index
values, one knows which keys to access and

100
00:09:40,413 --> 00:09:48,084
one then can directly access them using
the original Big Table or H Base Table.

101
00:09:48,084 --> 00:09:56,090
One example where exactly such a structure
is likely used is Google App Engine's Data

102
00:09:56,090 --> 00:10:02,659
Store which is, probably based on big
table as most have speculated and uses

103
00:10:02,659 --> 00:10:07,062
indexes in exactly this way to query the
big table efficiantely