Google Datastore intro

I have been getting updated on the Google Datastore for several months now. It seems the major promotions for it started back in 2008, or at least that is when the most videos on Google IO started to appear. It got some hype until 2012, and then no more promotions from Google - they focus now on mobile, web and material designs. Anyway, I've watched multiple time the following videos - and recommend them if you want to know more about scallable, sorted, distributed, persisted nosql solution

"Datastore under the covers", 2008 talk.

The slides are a mess, but Ryann Barret makes a good introduction

to how the entities and inded are layed out, and how transactions work.

"Scalable, Complex Apps on App Engine" 2009 talk

Brett Slatkin presents solutions for complex datastructures

having in mind the limitations of the Datastore

Under the covers

Under many architecutral layers under the Datastore is a BigTable - which is very very large, ordered key-value store. How can you get that simple concept and with some fancy distirbuted locking, distributed file service, very preceise times and Paxos to arrive at Datastore. It is not that hard to understand and follow how the pieces work together, with the right team - it migth be not that hard even to implement it.. But anyway.. back to the key-value store of the BigTable - the keys and values are arbitrary strings.

The key-values are sorted by its keys - so you oculd have verfy fast retrieval by key. The operations allowed are:

insert a new key-value pair. BigTable inserts it into the appropriate sorted place. If there are too many key-value pairs in one server (in Google terminology tablet server) - they got split and a new server is allocated.
delete a key/value pair by its key
get the value by its key
prefix scan: i.e. get all key/value pairs that have a specific prefix for the key. Here is where the magic of select with equality filters, and with special indexes on inequality filters with ziz-zagging (but more on this in the future).

Google allows only prefix scans - because in this way all the keys will be dense - i.e. they would be contiguous one after another. In this way the disk seeks are minimized. And searching in a sorted set is with logarithmic complexity, and sacraficing a bit of space for bloom filters some small performance gains could be achieved.

You should realize that all data from all Google App Engine, Compute Engine, or Kubernetes that choose Datastore is stored in one BigTable. Really the Big in the name is meant to be that way. Since the data is sorted by its key - Google employs a specific scheme for the keys so the data for an app stays close together densely packed. Lets look into how the key is subdivided.

Keys

The BigTable keys have the following layout (some are implicit and some are optional and some are required) wich buble as different concepts in the Datastore:

the project ID - all keys will have this prefix authomatically inserted. There is no way for the user to change this part. This ensures that all the data for you app is densely packed in the BigTable in contiguous tablet server - i.e. in a continuous, non interupted region. There are thousands and thousands of applications that use the Datastore, and in this way their data is namespaced on project level. And because of this, even though all the data for all the apps is in one big BigTable - there is no way for an app to access the data for another app.
optional namespace - user defined namespace to futher subdivide the data. I.e. usefull for stuff like development/staging/production separation. The default namespce is the empty string. If you use a namespace then the data is not visible in the Google Console.
entity group - the support for transactions is implemented in kind of wierd way with the concept of entity group - which is set of key-value pairs that have a common prefix. Transactions work mainly within the boundaries of entity groups.
the key kind - wich is the analogue of table name in the SQL world
the key identifier - which is the analogue of the row id in the SQL world. The key identifier could be string or numeric and could be autogenerated.

How would the BigTable keys for a Books :

ID	Title	Author	Year published
1	Summer in Greece	Paparakis	2015
2	Felicity and fear	Tani Han	1905

table look like? Lets assume that:

the project ID is: marvelous-times-234
there is no user defined namespace,i.e. empty string
the Books entities are not part of entity group

the key for those 2 entities (i.e. rows in SQL world) would be:

marvelous-times-234||Books|1
marvelous-times-234||Books|2

here the separator "|" character represents the point where Google uses some kind of separator mechanism to be able to bread down the long key string when needed. And this example is for illustration purposes only.

The BigTable value is just a binary blob with some appropriate encoding and compressing. BigTable does not offer searches on the value part. Datastore offers search on the BigTable value part by using index tables.

If we want to insert a Book in "development" namespace, within the entity group "Person"|87321, then the full key as stored in the BigTable would look like:

marvelous-times-234|development|Person|87321|Books|3

Fascinating how a simple key value store can be made in such a way as to support Petabytes and Petabytes of data, and effectively search in them with complexity equal to the size of the result set. I.e. it does not matter if you have gazilion entities in your Datastore - if you query is so crafted as to match only 100 entities - the speed of your query would be just that - the cost of accessing those 100 entities. And since they are sorted sequentially by the key - they are contiguous on the HDD, and could be read in a few disc reads. Which delivers the best possible performance on the spinning disk technology which was mainstream in 2008 - since the reading head does not do seeks. This was one of the main design goals for Bigtable - to optimize the sequential read from cheap spinning disks.

And here is how you could insert a Book entity with the gcloud-node client library for the Datastore:

dataset.save(
 {
  key : dataset.key(["Book", 1]);,
  data : {
   Title : "Summer in Greece",
   Author : "Paparakis",
   Year : 2015
  }
 },
 function(err) {
  // handle the error or the success...
 }
);

Entities

As a no-sql database there is no strict requirments for the records that you put in - it just gets serialized downo to a binary bytestream, appropriately encoded, compressed and indexed. Google uses the term entity for the record that you want to store, index and retrieve. The entity is the value part in the BigTable world, and is binary blob. But in the Datastore, the entity is further subdivided into a list of key-values.

For example in javascript a Book entity coud be represented as object (a very suitable value/key structure):

{
    Title : "Alone in the wild",
    Author : "Lesner Wigner",
    Year : 1934
}

It is confusing.. the BigTable itself is just a big, sparse, sorted, persistent, redundant key-value store. The BigTable key is subdivided into multiple concepts in the Datastore world. I.e. the project, the namespace if present, the entity group if present, the key kind and key identifier are all packed into the BigTable key.

The BigTable value part is subdivided into a list of key-values in the Datastore world. BigTable offersr only prefix searches on its keys. The Datastore overcomes this limitation by indexing the "columns", i.e. the key-values of the BigTable value into indexing BigTables..

You have to watch the IO talks and read the papers if you want to go into more detail. And sure if you want to architect a system - and to navigate around the limitations - you have to dig into the details.

But you could just use one of the client libraries that abstract further away the complexities and build many usefull apps, with them. Lately I've been experimenting with node-gcloud with god results.

Read further for articles with the datastore label to learn more.

Search This Blog

on various topics