# The Time Machine in Columnar NoSQL Databases: The Case of Apache HBase
## Appendix A Background of Apache HBase  
This section presents an overview of the Apache Hadoop HBase [5]. HBase is a _column-based_ NoSQL database management system. Clients in HBase can create a number of tables. Conceptually, each table contains any number of _rows_, and each row is represented by a unique _row key_ and a number of _column values_, where the value in a column of a row, namely, the _cell_, is simply a byte string. HBase allows clients to expend the number of columns on the fly even though the associated table has been formed and existing rows of data are present in the table. A table in the HBase can be horizontally partitioned into a number of _regions_, where the regions are the basic entities that accommodate consecutive rows of data. Regions are disjointed, and each row can be hosted by a single region only. The HBase is designed to be operated in a cluster computing environment that consists of a number of _region servers_. In default, if the number of regions of a table is \(c\) and the number of region servers available to the table is \(n\), then the HBase approximately allocates \(\frac{c}{n}\) regions to each region server, and each among \(c\) regions can only be assigned to one of the \(n\) region servers. When inserting a row of data (or a cell data in a row), the HBase first identifies the region server \(r\), which hosts the region responsible for the data item to be updated. Precisely, if the data contained is assigned with the row key \(k\), then the starting key (denoted by _l_) and the ending key (denoted by _u_) managed by the region responsible for the data item must be \(l\leq k\leq u\). Once the region server \(r\) is located, then the written data is sent to \(r\), which is buffered in _r_'s main memory, namely, _memstore_ in the HBase, to be flushed in batches into the disk latter. In the HBase, the data in a region is represented as _HFiles_ stored in the underlying _Hadoop Distributed File Systems_ (HDFS) [7]. The basic format of an HFile is a set of _key-value_ pairs. By a key-value pair, we mean that (1) the _key_ of a row data is the row key plus the column name and (2) the _value_ is the cell value that corresponds to that key. We note that key-value pairs are elementary elements that represent data stored in the HBase. In this paper, we explicitly differentiate the _row key_ from the key that uniquely identifies a key-value pair, where the latter contains the former. For example, consider a record representing customer information that includes the name of a customer and his/her contact address. Then, we may create an HBase table with unique IDs that differentiate among customers. These IDs form the set of row keys, and in addition to a unique ID of a row, each row contains two extra fields that consist of the name and the contact address of a customer. To access the cell of such a table, we specify the key-value pair as \((x,y)\), where \(x\) is the key such as customerID:name and \(y\) can be John, for example. Ideally, if an HBase table is partitioned into \(k\) regions, and each region is included in the HDFS as an HFile, then \(k\) HFiles are generated and maintained even with failures, and each HFile maintains consecutive keys of key-value pairs stored in the file. (The HDFS guarantees the reliability of storing an HFile with replication. Specifically, an HFile may be split into \(c\) disjoint chunks, and each chunk has three replicas by default, which are maintained at distinct locations, i.e., _datanodes_ in the HDFS.) However, in practice, a region server may introduce several HFiles for a particular region such that pipelining the data to the files can be performed rapidly. More precisely, a region server may manage several memstores for a particular region in its main memory, and it streamlines these memory blocks to the file system in a FIFO manner. Consequently, for a region, \(>\)1 HFiles may be present in the HDFS, which results in a lengthy delay in accessing key-value pairs in a region.