In the prior work, we described the “internal fragmentation” problem of collection files and secondary index files in MongoDB. That data fragmentation can be solved by using boundary-based stream mapping. However, in complex data model such as Linkbench, boundary-based stream mapping is inadequate with a new type of data fragmentation named cross-region fragmentation.
To illustrate the cross-region fragmentation, we implemented boundary-based stream mapping in MongoDB and experiment it with Linkbench. Figure 1 are written patterns of collection files and secondary index files using blktrace. In Figure 1 (b) all bottom regions of collection files are mapped with stream 1 (red color). However, inside this stream, there are overlapped writes of files with different write frequency as shown in Figure 1 (d) (three different colors). We observed the same phenomenon in the case of the top regions.
Figure 1. Cross-region fragmentation
Moreover, as showed in Figure 2, the write patterns of primary index files (sequential) are different to the one of secondary index files (random). Therefore, writes from those index types should be distinguished.
Figure 2. Write pattern of different file types
From those observations, we defined important criteria for a stream mapping approach as below:
1. Solve the internal fragmentation of collection files and index files.
2. Map writes on primary indexes to different streams from those of secondary indexes, and collections.
3. Solve the cross-region fragmentation.
4. Work independently of various data models (number of collections, primary indexes, and secondary indexes) and the limitation of the number of streams supported by SSDs.
Boundary-based stream mapping approach satisfies the first and the last requirement, however, suffers from the requirement (2) and (3). The file-based stream mapping approach maps each file types to different streams that solve only the second requirement. There is an extended solution from the file-based method that maps each physical collection file or index file to a stream. This approach solves requirement (2) and (3) but becomes impossible when the number of files is larger than the maximum number of streams that the underlying SSDs support.
To solve the cross-region fragmentation, we propose Dynamic Stream Mapping (DSM) approach that dynamically assign streams to regions based on their hotness value.
Dynamic Stream Mapping
The overall of DSM is showed in Figure 3.
Figure 3. Overall process of DSM approach
Normal thread: Before writing data to the buffer pool, we assign predicted streams to regions based on the boundary of each file. We then collect statistical information for each collection or index file. The algorithm of DSM at the normal thread is given below:
Checkpoint thread: When issuing checkpoints, the system blocks normal threads until the checkpoint process finished. At the checkpoint time, our proposed method follows the below steps:
1. Use statistical information collection in the eviction thread to compute the hotness values for regions.
2. Compute pivot points for each collection file or index files. Those pivot point later are used to classify regions based on their hotness values computed in the previous step.
3. Stream mapping for regions based on their hotness values and pivot points computed in step 1 and step 2.
4. For each region, compute the predict-stream for the next checkpoint based on the mapped stream in step 4 and predict-streams in the previous checkpoint.
The DSM algorithm at the checkpoint thread is given below:
Benefits of DSM
We setup the same experiment as the prior work to get a fair comparison. The stream mapping table is illustrated in Table 1. The benefit of DSM in terms of throughput and 99th latency is showed in Table 2.
Table 1. Stream mapping table of methods
Table 2. Summarize of performance improvement of methods
Please read the paper for the detail of hotness value computing, pivot points computing, stream mapping, and stream prediction.
Discussion and Conclusion
Our proposed method i.e., DSM solve all creteria of a stream mapping. For simple data model such as YCSB, the boundary-based approach is adaquate. For more complex data model such as Linkbench, DSM is recommendded. Experiments with multi-streamed SSD technique require the modification in both OS kernel and SSD’s firmware. One should aware that there is a limited number of streams supported by the SSD. For example, Samsung 840 Pro support by up to 8 streams (0 – 7).
The next work is observing I/O pattern in MySQL to adopt multi-streamed technique into that DBMS.