Big table and H Base were one of the first
NoSQL databases designed for large scale
batch processing essentially and therefore
didn't really have strong support for
indexes.
Recently, the database called MongoDB has
become very popular, because it does, in
fact, include significant support for
indexes.
Instead of records, MongoDB uses the term
documents, which are essentially
structured documents spo they look a lot
like records, but they can be more complex
than records in the sense that one might
have multiple titles or multiple
categories, for example, in this case.
This is sort of like H Base records,
because H Base can also have multiple
values for a particular column.
Like H Base, it's a sharded database, so
that documents or records are kept in
different shards on different processors
so that a set of keys goes to one shard.
Additionally, just like H Base we have
three replicas for each shard.
Mongodb, however, doesn't rely on the
underlying distributed file system, like
HDFS.
But, keeps track of it's own replicas, in
a manner reminiscent of traditional paddle
relation databases.
The underlying file system can be any
operating system, file system, like Linux
file system or something else.
Further, the indexes that MongoDB supports
include full text indexes so that it
essentially has support for inverted
indexing as we saw in the first week of
this course.
Lastly, it also supports a form of
map-reduce within the database itself.
So, when [unknown] effectively write
map-reduce programs which process data in
MongoDB using Javascript which is the only
language it supports.
Another important feature of MongoDB which
is shared by some other no sequel
databases, is its consistency model for
writes.
We recall that in H Base, for example, a
write relies on a write to the distributed
file system.
We just essentially completes writing a
record only all three replicas write
successfully.
This essentially makes writes into both
GFS, HDFS, as well as H Base rather costly
because it relies on altering replicas
agreeing, before a write succeeds.
It's quite okay for large bulk rights, but
doesn't quite add up for smaller rights,
or random rights because the extra
overhead of making sure the replicas are
consistent is relatively high for small
operations.
So, instead MongoDB uses something called
eventual consistency, where writes or
updates are propagated to replicas
eventually, and not synchronously with the
write.
So, it's possible for a write to complete
without all it's replicas having been
updated with that write.
The first database to use eventual
consistency was Amazon Simple DB, where
the idea of vector clocks was used to
achieve eventual consistency.
Other NoSQL data bases, such as Mongol DB,
still use vector clocks.
So, this is quite an important concept and
we'll illustrate it through an example.
Each record is represented by a key which
could be, for example, the transaction ID
or something else.
And it needs to get replicated at three
different replicas.
In Amazon Simple DB, for example, these
replicas are chosen by hashing each key
and essentially distributing the hashed
values in a round roving fashion to
different physical notes.
A different replication technique is used
in MongoDB, but that's not relevant for
the vector clock discussion.
Nonetheless, let's assume that there is a
record which is mapped to three physical
nodes x, y and z.
And now, let's see what happens when we
try to write a record, which is replicated
at three locations.
Suppose we happen to write this record at
x, we associate it with that at time stamp
1,0,0.
So, this is a vector time stamp consisting
of three elements, which tells us that
this was written at time stamp one, at
physical note X, and the time stamps, the
other notes are maintained at zero.
Next, we may want to write it again, again
at physical note x, in which case, we
simply update the vector times stamp to
2,0,0 and forget about the old 1,0,0
version which was written earlier.
That's because in vector terms, 2,0,0 is
greater than 1,0,0 and that at least one
of the terms is greater than the one in
1,0,0 and the others are at least equal to
the same in this vector.
On the other hand, suppose we were to
first write it at location x and the next
write for some reason happened at location
y just because of parallelism.
The vector time stamp for this write would
then be 0,1,0 because the value it is
writing had, times, times, 0,0,0, and it's
writing it at y, so you, it is assigned a
time stamp of 0,1,0 now.
Next, this right is propagated to all the
replicas, both rights are propagated to
the other two replicas, so x gets the
value from y 0,1,0 and y gets the value
from x and zed gets the value from both x
and y.
Now, in each of these cases, neither of
the two values of a record are greater
than each other in vector term.
So, each replica has to maintain both the
values until something more interesting
happens in the future.
For example, now if we read the value zed,
where we read both these replicas 1,0,0
and 0,1,0 from the location zed And now,
we do some computation, and write a fresh
value.
Because we read both these replicas with
time stamps 1,0,0 and 0,1,0 figured out
which one to use using some application
logic and then wrote a value, the value
written has a time stamp 1,1,1 because
it's based on values that have seen 1,0,0
and 0,1,0 as time stamps.
Now, 1,1,1 is greater than both of these
so the value written overrides the
previous two and they can be discarded.
And when this value propagates to x and y,
the corresponding older values also get
discarded.
As a result, what we achieved is eventual
consistency in that at some point of time,
when you read a record you might get two
values instead of just one because you are
getting an inconsistent state and its up
to you, as the application, to resolve
that inconsistency usually using some
knowledge of what these values are all
about.
For example, suppose the write is
essentially adding another value to the
record.
In this case, the previous two values
simply need to be added together to which,
a third value might get added, and that in
consistencies while results because none
of the previous write has actually thrown
away, but they are actually summed up by
the third right.
A second example might be where the right
is a blind right, we doesn't really care
what was written in that record earlier,
In which case, it doesn't really matter
which of the previous two, one is to
choose because they are ignored in any
case and the third right simply writes and
resolves the conflict by assigning a
higher vector time stamp.
The final case is the most complicated one
where the write depends on the previous
value, such as a update.
So, suppose you're incrementing the value
of a record, perhaps, by different amounts
each time.
So, you have to choose which of the
previous two versions you want to use and
do this consistently so that the second
time this kind of a conflict occurs, the
rule applied is the same.
What is typically done in such situations
is, you use a lexicographical or
alphabetical ordering of the replicas so
that, for example, the replica x is
treated as higher than the replica y,
which is treated higher than the replica
zed.
So that, while choosing between 1,0,0 and
0,1,0, the third replica chooses to use
this value time stamp with one zero, zero
increment it with whatever it chooses to
do and then write with a time stamp one,
one, one.
Since we use a consistent ordering of the
replicas by alphabetical order of some
kind, we'll always get consistent results.
Now, it's not that obvious and the theory
of vector time stamps dates back to the
'70s in classical work by Leslie Lamport.
And the original paper is really worth
reading.
The paper itself is from 1978 and there
are some previous versions of it but the
most accessible one is this one, which
appeared in the communications of the ACM.
The theory of why a lexicographical
ordering works always is elegantly put in
this paper and interestingly, more than 30
years later, we are seeing this concept
being used for eventual consistency and
multiple NoSQL databases, Amazon simple DB
to start with, Mogul DB, Couch DB,
Cassandra and many others.