# The Time Machine in Columnar NoSQL Databases: The Case of Apache HBase
## 3 Architectures and Approaches
### Proposals
#### 3.2.3 Data Structure  
Before we discuss potential solutions to the DR problem, we introduce the data structures on which these solutions rely. In particular, we propose _shadow tables_. A shadow table is essentially a table in the HBase. A data table created by a user in the HBase is basically associated with a shadow table unless the data table will not be recovered in the future. Here, we differentiate a data table from its shadow table where the former is used to serve normal requests from clients while the latter tracks the update operations to the data table. Shadow tables are solely adopted for recovery.  
Table 1 shows the data structure of a shadow table. We assume that the data table \(T\) to be recovered contains a single column. Consider any key-value pair, \(kv\), of a data table \(T\) and its shadow table \(D_{T}\). Each key-value pair \(kv\) in \(T\) has a corresponding row (denoted by \(D_{kv}\)) in \(D_{T}\), and each row in \(D_{T}\) consists of a row key and a value. The row key comprises six fields as follows:  
* _Prefix_: As \(D_{T}\) can be quite large (in terms of the number of its maintained key-value pairs), the prefix field is used to partition and distribute \(D_{T}\) into the region servers in the destination HBase cluster. If the number of region servers in the destination cluster is \(k\), then the prefix is generated uniformly at random over \([0,k-1]\).
* _Batch Time Sequence_: In the HBase, clients may put their key-value pairs into \(T\) in batches to amortize the RPC overhead per inserted key-value pair. In \(T\), each \(kv\) of the key-value pairs in a batch is labeled with a unique timestamp, namely, the _batch time sequence_, when it is mirrored to a shadow table (i.e., \(D_{kv}\) in \(D_{T}\)). The time sequence basically refers to the local clock of the region server that hosts \(kv\), thereby enabling the proposed approaches to recover data within a designated time period, as will be discussed later.
* _ID of a Key-Value Pair in a Batch_: To differentiate distinct key-value pairs in a batch for \(T\), we assign each key-value pair in the batch an additional unique ID in \(D_{T}\). This step ensures that when a user performs two updates to the same (row) key at different times, if the two updates are allocated in the same batch, then they are labeled with different IDs in the batch. Consequently, our recovery solution can differentiate the two updates in case we want to recover any of them. On the other hand, in the HBase, if two updates go to the same key, the latter update will mask the former when they are issued by an identical client in the same batch. The ID of a key-value pair in a batch helps explicitly reveal the two updates.
* _Region ID_: The ID associated with \(D_{kv}\) in \(D_{T}\) for the corresponding \(kv\) in \(T\) indicates the region server that hosts \(kv\) for \(T\). Region IDs are critical when we aim to recover the distribution of regions in the HBase source cluster.
* _Operation Type_: The field denotes the operation for \(kv\) in \(T\). Possible operations include PUT and DELETE provided by the HBase.
* _Original Row Length_: As a value of a key-value pair, \(kv\), in \(T\) can be any byte string whose length varies. The _original row length_ field indicates the number of bytes for the string length taken by the value of the key-value pair \(kv\) in \(T\).  
The value in a row of \(D_{T}\) contains only  
* _Original Row Key Concatenated by Original Value_: The original row key represents the row key of \(kv\) in \(T\), and the original value is the value of \(kv\). In addition to the value of \(kv\), we also need to recover the row key of \(kv\) such that \(T\) with designated data objects is recovered.