## 3 Constructing a Lightweight Key-Value Store Based on the Windows Native Features
### A Hash-Based Multi-Level Registry Index  
In this section, we present how to construct the index structure for WR-Store. For this, we need to determine the names of keys and subkeys in the registry path. One simple way is using the key in the key-value store as it is in the Windows registry. For example, in Figure 2, \"2149\" becomes the key in the registry, and thus, the registry path for the key \"2149\" becomes \"Computer\HKCU\k\kvs\2149\". In this case, WR-Store has one-level index structure. However, to make a scalable index, the multi-level structure is required.  
To make the multi-level structure, we can use substrings of the key in the key-value store as keys and subkeys in the Windows registry. For example, when we have a key \"2149\", we partition it into two substrings \"21\" and \"49\". Then, \"21\" becomes the key in the first-level registry structure, and \"49\" becomes the key in the second-level registry structure. As a result, a path for the registry key becomes \"Computer\HKCU\k\kvs\21\49\". However, in this case, according to the distribution of the keys, the stored key-value data could be skewed. That is, all the key-value pairs whose keys are starting with \"2149\" such as \"214910\", \"214911\", \"214912\", and \"214913\" will be stored under the same registry key \"Computer\HKCU\k\kvs\21\49\".  
Now, we present a method to distribute key-value data uniformly over the registry keys in the multi-level structure. For this, we use a hash function to determine a registry path from a specified key in the key-value store. The hash function has a property that distributes data uniformly regardless of the distribution of the original keys. In addition, the hash collision is not the problem in WR-Store because the Windows registry allows to store multiple values in the same registry key. Here, we can identify the values in a registry key using the name attribute. In this paper, we use MD5 for a hash function and represent the hash result in hexadecimal. To make the multi-level structure, we partition the hash result into multiple substrings and use each substring as a registry key for each level of the multi-level structure.  
Figure 3 shows a registry path for a hash-based multi-level registry index in WR-Store. A registry path for indexing consists of \(WR_{D}\) hash values where each hash value \(i\) (\(1\leq i\leq WR_{D}\)) has a length \(WR_{L}\) and is used for an \(i\)-th level index in the Windows registry. We can define \(WR_{D}\) as the depth of the registry and \(WR_{L}\) as the length of each subkey in the registry path. Therefore, the total length of a registry path for indexing is \(WR_{L}\times WR_{D}\).  
Table 3 shows the example of the registry path in WR-Store. We have a key \"2149\" and \(MD5(\text{``2149\"})=\text{``fe40a2892 ab382 cd\"}\). Let us suppose that \(WR_{D}\) is 2, \(WR_{L}\) is 2, and the database name is \"kvs\". The first two bytes of the hash result \"fe\" becomes the registry key for the first level and the next two bytes of the hash result \"40\" becomes the registry key for the second level.  
Figure 3: A registry path for a hash-based multi-level index structure in WR-Store.  
As a result, a final path for the registry key becomes \"Computer\(\backslash\)HKCU\(\backslash\)kvs\(\backslash\)fe\(\backslash\)40\". If \(WR_{D}\) and \(WR_{L}\) become different, the corresponding registry paths are also changed as presented in Table 3. Consequently, it will generate completely different index structures. Here, we note that the hash results of the keys \"214910\" and \"214911\" are totally different even if the original keys are similar. Therefore, the key-value data can be distributed uniformly on the Windows registry.  
The structure of WR-Store can impact the performance of WR-Store. That is, we can control \(WR_{D}\) and \(WR_{L}\) to find the best setting for WR-Store. In Section 4, we will perform the empirical analysis to check the performance variations as those factors are varied, and then, find the best parameter setting for WR-store.