# The Time Machine in Columnar NoSQL Databases: The Case of Apache HBase
## 2 System Model and Research Problem
### Research Problem  
Consider any table \(T\) in HBase. \(T\) may consist of a large number of key-value pairs (denoted by \(kv\)), each associated with a timestamp (\(t\)). We define \(T\) as follows:  
**Definition 1**. : _A table \(T\) consists of key-value pairs \(T=\{kv(t):0\leq t\leq t_{c}\}\), where \(0\) is the initial clock time and \(t_{c}\) is the present system clock._  
**Definition 2**. : _Given two time instances \(t_{1}\) and \(t_{2}\) (where \(t_{1}\leq t_{2}\leq t_{c}\)), historical data (key-value pairs) with respect to \(T\) are \(T_{s}=\{kv(t):kv(t)\in T\text{ and }t_{1}\leq t\leq t_{2}\}\)._  
**Definition 3**. : _A row key is a prefix string of \(kv\)'s key that uniquely differentiates distinct key-value pairs in \(T\)._  
**Definition 4**. : _Let \(\mathcal{R}\) be a region of \(T\) if \(\mathcal{R}\subseteq T\) and \(\mathcal{R}\) contains key-value pairs with consecutive row keys in alphabetical order._  
**Definition 5**. : _Let \(R\) be the complete set of regions with respect to \(T\), and \(R=\{\mathcal{R}_{1},\mathcal{R}_{2},\cdots,\mathcal{R}_{k}\}\) such that_  
* \(\mathcal{R}_{i}\) _is a region of_ \(T\) _for any_ \(1\leq i\leq k\)_;_
* \(\mathcal{R}_{i}\bigcap\mathcal{R}_{j}=\emptyset\) _for any_ \(1\leq i\leq k\)_,_ \(1\leq j\leq k\) _and_ \(i\
eq j\)_;_
* \(R=\bigcup_{1\leq i\leq k}\mathcal{R}_{i}=T\)_._  
**Definition 6**. : _An HBase cluster that consists of \(r\) region servers, denoted by \(S=\{\mathcal{S}_{1},\mathcal{S}_{2},\cdots,\mathcal{S}_{r}\}\) is valid if any \(\mathcal{R}_{i}\subset R\) is allocated to a unique \(\mathcal{S}_{j}\) at any time instance, where \(1\leq i\leq k\) and \(1\leq j\leq r\)._  
Here, \(\mathcal{R}_{i}\) may be reallocated from one region server to another due to failure recovery or load balancing in HBase. Notably, data and key-value pairs are interchangeable in this paper. Clearly, \(T_{s}\subseteq T\) is a subset of key-value pairs in \(T\) for a time period between \(t_{1}\) and \(t_{2}\). \(T\) may be partitioned into a number of regions, where a region is a horizontal partition of a database table. The scaleout feature by horizontally partitioning is widely supported by distributed database storage engines. These regions are allocated to and served by different region servers,which results in the possibility that the set of key-value pairs in \(T_{s}\) may appear in distinct region servers. We now define the research problem, namely, the _data recovery problem_, studied in this paper. **Definition 7**: _Given \(T\), the current system clock \(t_{c}\) and any two time instances \(t_{1}\leq t_{2}\) (where \(t_{2}\leq t_{c}\)), then the table restoration process is to find a subset of \(T\), denoted by \(T_{s}\), such that_  
\[T_{s}=\{kv(t):kv(t)\in T\text{ and }t_{1}\leq t\leq t_{2}\}. \tag{1}\]  
**Definition 8**: _Given \(T_{s}\) and an HBase cluster \(S\), the table deployment process partitions key-value pairs in \(T_{s}\) into a number of regions and assigns these regions to region servers in \(S\) such that \(S\) is a valid HBase cluster._  
**Definition 9**: _Given two HBase clusters \(S_{1}\) and \(S_{2}\) (where \(S_{1}\) is a valid, source cluster and \(S_{2}\) is the destination cluster), two time instances \(t_{1}\) and \(t_{2}\) (where \(t_{1}\leq t_{2}\leq t_{c}\)) and a table \(T\) in \(S_{1}\), the data recovery (DR) problem includes_  
* _a table restoration process that finds_ \(T_{s}\subseteq T\) _in_ \(S_{1}\) _for the time period between_ \(t_{1}\) _and_ \(t_{2}\)_;_
* _a table deployment process that partitions_ \(T_{s}\) _into_ \(S_{2}\) _such that_ \(S_{2}\) _is a valid HBase cluster._  
Notably, \(S_{1}\) and \(S_{2}\) follow the system model as discussed in Section 2.1. \(S_{1}\) and \(S_{2}\) may not be identical in terms of cluster size (i.e., \(|S_{1}|\
eq|S_{2}|\)) and the specification of region servers in both clusters.