# Balloon: An Elastic Data Management Strategy for Interlaced Magnetic Recording
## 4 Balloon Design
### On-Demand Data Shuffling  
After switching to the top allocation phase, some free top tracks are used as temporary buffers for bottom tracks with write interference, which accelerates the exhaustion of the free top tracks. When the free top track is used up, the track merge/swap operation is enabled to reclaim the free top track. In the Balloon, the track relocator determines its target storage locations based on the hotness of the tracks. In essence, the track relocator tries to place cold and hot data in the bottom and top tracks, respectively, to achieve the desirable data layout. To reduce the frequency of track rewrites, the track relocator preferentially searches for cold tracks as candidates. Typically, the selected candidate is either a data track or a buffer track. For the former, the track relocator uses a swap operation to relocate it to any free track in the bottom region. As for the latter, the track relocator merges it directly into the data track to which it is associated with. The assumption here is that an updated track is more likely to be updated again than an un-updated track, so the data track is given a higher merge/swap priority. In addition, once the bottom track is associated with the buffer track, subsequent writes are directed to the buffer track, which can invalidate the original data in the data track. As shown in Figure 7, when there are no valid data in the bottom data track 2, the buffer track 5 is automatically converted to a data track, and the previous data bottom track 2 becomes free again. This implicit merge operation can migrate hot and cold data without introducing extra I/Os, significantly reducing the cost of data shuffling. It is essential to emphasize that before swapping a data track into the bottom region, the track relocator first checks for the availability of a free bottom track to accommodate its data. If no free bottom track is available, the track relocator will merge a hot data track from the bottom region into its buffer track, thereby creating a free track. For instance, the hot bottom track 22 is merged upward into buffer track 19, thus freeing up a usable bottom track 22. In contrast, if the candidate is a buffer track, the track relocator directly performs a downward merge directly without considering the availability of free tracks in the bottom region. For example, the candidate is buffer track 9, which is merged downward into its data track 14. Figure 6: A track-level multiple-Bloom-filter-based framework for track hotness scoring. However, apart from implicit merges, both up/down merges and track swaps introduce non-negligible extra I/Os, which are costly. Specifically, a data track swap requires 4-8 extra I/Os, while a buffer track merge requires at least 3 extra I/Os. If there are no cold tracks to act as candidates, there is a high probability that swapping warm/hot tracks to the bottom region will increase the frequency of track rewrites, thus deteriorating disk performance. To solve this problem, blocks of warm/hot tracks are relocated to a reserved region on the disk to avoid track rewrites. Reserved region management is described in Section 4.4. Also, in real workloads, the distribution of updated blocks within a track is not uniform; some tracks have a small update range (few updated blocks), while others have a large update range (most updated blocks). Therefore, it is beneficial to reserve the tracks with large update ranges in the top region to better exploit the spatial locality of the tracks and reduce the write latency of user requests. To evaluate the update range of a track, a metric called update block coverage is introduced. In our design, a bit array is used to capture the distribution of updated data blocks within the track, and its size is equal to the number of blocks contained in the track. In summary, when there are only warm/hot tracks in the upper region, the track with the lowest update block coverage is selected as a candidate and swapped to the reserved region.