Understanding the HBase data model

In 2006, the Google Labs team published a paper entitled BigTable: A Distributed Storage System for Structured Data. It describes a distributed index designed to manage very large datasets (``petabytes of data") in a cluster of data servers. BigTable supports key search, range search and high-throughput file scans, and also provides a flexible storage for structured data. HBase is an open-source clone of BigTable, and closely mimics its design. At Internet Memory, we use HBase as a large-scale repository for our collections, holding terabytes of web documents in a distributed cluster. HBase is often assimilated to a large, distributed relational database. It actually presents many aspects common to "NoSQL" systems: distribution, fault tolerance, flexible modeling, absence of some features deemed essential in centralized DBMS (e.g., concurrency), etc. This article presents the data model of HBase, and explains how it stands between relational DBs and the "No Schema" approach. It will be completed by an introduction to both the Java and REST APIs, and a final article on system aspects.

The map structure: representing data with key/value pairs

We start with an idea familiar to Lisp programmers of association lists, which are nothing more than key-value pairs. They constitute a simple and convenient way of representing the properties of an object. We use as a running example the description of a Web document. For instance, using the JSON notation:

{  
   'url': 'http://internetmemory.org', type: 'text/html', content: 'my document content' 
}

One obtains what is commonly called an associative array, a dictionary, or a map. Given a context (the object/document), the structure associates values to keys. We can represent such data as a graph, as shown by the figure below. The key information is captured by edges,whereas data values reside at leaves. There exists many possible representations for a map. We showed a JSON example above, but XML is of course an appropriate choice. At first glance, a map can also be represented by a table. The above example is equivalently viewed as

url	type	content
http://internetmemory.org	text/html	my document content

However, this often introduces some confusion. It is worth understanding several important differences that make a map much more flexible than the strict (relational) table structure. In particular,

• there is no schema that constrains the list of keys (unlike relational table where the schema is fixed and uniform for all rows),
• the value may itself be some complex structure.

HBase, following BigTable, builds on this flexibility. First, we can add new key-value pair to describe an object, if needed.This does not require any pre-declaration at the 'schema' level, and the new key remains local. Other objects stored in the same HBase instance remain unaffected by the change. Second, a value can be another map, yielding a multi-map structure which is exemplified below.

An HBase "table" is a multi-map structure

Instead of keeping one value for each property of an object, HBases allows the storage of several versions. Each version is identified by a timestamp. How can we represent such a multi-versions, key-value structure? HBase simply replaces atomic values by a map where the key is the timestamp. The extended representation for our example is shown below. It helps to figure out the power and flexibility of the data representation. Now, our document is built from two nested maps,

• a first one, called "column" in HBase terminology (an unfortunate choice, since this is hardly related to the column relational concept),
• a second "timestamp" (each map is named after its key).

Our document is globally viewed as a column map. If we choose a column key, say, type, we obtain a value which is itself a second map featuring as many keys as there are timestamps for this specific column. In our example, there is only one timestamp for url (well, we can assume that the URL of the document does not change much). Looking at, respectively, type and content, we find the former has two versions and the latter three. Moreover, they only have one timestamp (t₁) in common. Actually, the "timestamp" maps are completely independent from one another. Note that we can add as many timestamps (hence, as many keys in one of the second-level maps) as we wish. And, in fact, this is true for the first-level map as well: we can add as many columns as we wish, at the document level, without having to impose such a change to all other documents in a same HBase instance. In essence, each object is just a self-described piece of information (think again to the flexible representation of semi-structured data formats like XML or JSON). In this respect, HBase is in the wake of other 'NoSQL' systems, and its data model shares many aspects that characterize this trend: no schema and self-description of objects. We are not completely done with the multi-map levels of HBase. Columns are grouped in column families, and a family is actually a key in a new map level, referring to a group of columns. In the Figure below, we define two families: meta, grouping url and type, and data representing the content of a document. Important: Unlike the column and timestamp maps, the keys if a family map is fixed. We cannot add new families to a table once it is created. The family level constitutes therefore the equivalent of a relational schema, although, as we saw, the content of a family value may be a quite complex structure.

The full picture: rows and tables

So, now, we know how to represent our objects with the HBase data model. It remains to describe how we can put many objects (potentially, millions or even billions of object) in HBase. This is where HBase borrows some terminology to relational databases: objects are called "rows", and rows are stored in a "table". Although one could find some superficial similarities, this comparison is a likely source of confusion. Let us try to list the differences:

1. a "table" is actually a map where each row is a value, and the key is chosen by the table designer.
2. we already explained that the structure of a "row" has little to do with the flat representation of relational row.
3. regarding data manipulation, the nature of a "table" implies that two basic operations are available: put(key, row) and get(key): row. Nothing comparable to SQL here!

Finally, it is worth noting that the "table" map is a sorted map: rows are grouped on the key value, and two rows close from one another (with respect to the keys order) are stored is the same physical area. This make possible (and efficient) range queries of keys. We further explore this feature is the article devoted to the system aspects of HBase. The following Figures summarize our structure for an hypothetical webdoc HBase table storing a large collection of web documents. Each document is indexed by its url (which is therefore the key of the highest level map). A row is itself a local map featuring a fixed number of keys defined by the family names (f₁, f₂, etc.), associated to values which are themselves maps indexed by columns. Finally, column values are versioned, and represented by a timestamp-index map. Columns and timestamps do no obey to a global schema: they are defined on a row basis. The columns may vary arbitrarily from one row to another, and so do the timestamps for columns. The multi-map structure of a HBase table can thus be summarized as key -> family -> column -> timestamp -> value It should be clear that the intuitive meaning of common concepts such as "table", "row", and "column" must be revisited when dealing with HBase data. In particular, considering HBase as a kind of large relational database is clearly a misleading option. HBase is essentially a key-value store with efficient indexing on key access, a semi-structured data model for value representation, and range-search capabilities supported by key ordering.

References

• Understanding HBase and BigTable
• The HBase Wiki page