Non-volatile memory (NVM) represents a new class in the traditional storage hierarchy. The technologies in this class share characteristics of both primary and secondary storage; they provide latency that approaches that of DRAM, albeit moderately higher1, yet significantly lower than that of secondary storage devices, are addressable from cache lines, and, most importantly, ofer persistence. NVM is often referred to as a disruptive memory technology because it has invalidated the traditional programming paradigms used in applications such as database management systems (DBMS) and file systems (FS). Substantial research have focused on integrating NVM into diverse DBMS and FS, specifically through optimizing data structures such as B-trees and LSM-trees. Despite these advancements, considerable opportunities remain to further exploit NVM to boost application performance, particularly by exploring variations of these data structures. In this work, we present a proposal to optimize the B -tree for use with NVM. The proposed modifications aim to capitalize on the unique characteristics of NVM, enhancing the tree's eficiency in both read and write operations. Additionally, the suggested changes are designed to reduce computational overhead, particularly by minimizing the need for tree rebalancing operations. The development of the tree is in progress, and it is assumed that completion will take some time; therefore, this paper is presented as preliminary work.
move the data across the storage devices depending on
their usage and access patterns. For example, bcache and
One of the key challenges that applications used for data dm-cache in the Linux kernel use solid-state drives as a
management and analysis face is keeping the data as cache for hard disk drives.
close as possible to the CPU. This issue is exacerbated Non-volatile memory, or persistent memory, is a
comby the unbounded growth of data. The volume of data paratively new storage class in the storage hierarchy that
doubles approximately every two years [
The extensibility of DRAM has resolved this issue to higher capacity than DRAM. Furthermore, they are
capasome extent, resulting in a new type of database sys- ble of storing data persistently. NVM has not only added
tem called the main memory database system [
The remainder of this paper is structured as follows. any level [
A B-tree is a balanced m-ary search tree. It can also ’1’. However, most configurations use =1/2, and with
be considered as a generalization of a balanced search this value, B -trees provide asymptotically better insert
tree. It contains two types of nodes, internal and leaf performance with the same asymptotic point query
pernodes, with all the leaf nodes at the same level as the formance as B-trees [
Currently, Intel® is the only producer of commercially uses three techniques to boost performance by moving
available persistent memory modules [
As already discussed, NVM is byte-addressable, and its
capabilities cannot be leveraged using the traditional
programming model. Therefore, numerous research studies
have been conducted on optimizing diferent data
structures to leverage NVM. CDDS B-Tree [
Furthermore, in [
The core functionalities of the B -tree include managing the index structure in the root and internal nodes, as well as maintaining the bufers to mitigate the cost of the writes and updates. The suggested design primarily targets enhancing these functionalities by incorporating NVM and adding other enhancements to address the goals mentioned in the previous section. A conceptual diagram of a well-grown tree spread across diferent storage media is presented in Figure 1.
NVM, SSD, and HDD. The internal nodes are persisted
on NVM and SSD, and the leaf nodes are stored on SSD
and HDD3. The nodes are depicted using various
objects and colors to highlight diferences in their layouts
and structures. Nodes with a red border (in NVM and
SSD) represent hot nodes whose working copies exist in
DRAM (highlighted with a red box). When nodes are
moved from NVM to DRAM, they are transformed into
typical internal nodes with bufers. This process is
discussed in Section 5.1. Next, nodes filled with white color
and a gray border (in NVM) are also frequently accessed
nodes, but they do not meet the criteria, for example [
layout (data structure) varying across diferent devices.
4The rule outlined in [
In the suggested design, the internal nodes are
preferably5 stored on NVM. As previously discussed, the
internal nodes of a B -tree typically contain keys, pivots,
and messages. In contrast, the proposed design stipulates
that internal nodes in NVM contain only keys and pivots,
while messages are maintained in a shared centralized
bufer in NVM, as discussed in Section 5.2. The internal
nodes on NVM are directly accessed for lookups and the
centralized bufer for messages. This segregation ofers
the following benefits:
• Contrary to [
Lastly, the design assumes the frequently accessed nodes (or hot nodes) would be in the main memory. However, as the internal nodes on NVM follow a diferent 5A cold or rarely accessed node can be moved to slow storage. structure and its data is stored across diferent data struc- and must be accessed individually for each key—unlike tures, therefore, copying an internal node between NVM typical settings where messages benefit from spatial localand DRAM requires transforming the nodes into the re- ity. Nevertheless, these settings can support write-heavy spective layouts. For example, moving a node from NVM workloads, and the tree can be gradually adapted for readto DRAM would require copying the keys and values heavy workloads by storing linked messages in a separate from the node, and the respective messages from the node (e.g., bufer node) to achieve spatial locality. shared bufer.
NVM. A small centralized bufer in DRAM is maintained
In [
In the proposed design, these costs are reduced by 5.4. In-place Writes
using a centralized bufer, which is an NVM-optimized
hash table [
Consequently, messages are added to both the bufer and the auxiliary hash table without incurring additional I/O or computational costs. Furthermore, during a flush operation among the nodes in NVM, only the pointers in the auxiliary hash table need updating, significantly reducing I/O and computational expenses. The centralized bufer ofers the following benefits:
ularly related to leveraging NVM; it could be applied to nodes stored on NVM and other block devices.
As already mentioned in [
The proposed change enables direct in-place updates in the bufer segment of a B -tree node on block storage by writing update messages sequentially to available ofsets until the bufer, which is half of the standard 4 MB node size, is full. This method avoids the need to transfer the entire node into DRAM for read-modify-write cycles since updates are performed in granular block sizes of 4 KB. The updates in the bufer area are not normalized, meaning there could be multiple update messages for a single key. Normalization of messages occurs in DRAM when reading the bufer’s contents, streamlining the pro• Updates to the nodes on NVM do not require mov- cess and reducing I/O and computational costs associing the entire node to DRAM; instead, they can ated with data serialization and deserialization. When be made directly onto the shared bufer. This re- the bufer reaches capacity, the node is fetched into main duces I/O and computations such as serialization memory for updates and written back to storage. A conand deserialization. ceptual diagram is shown in Figure 2. • This would help reduce the fragmentation men
tioned in the previous section. Keys/Pivots Buffer (Messages) • The flush operation within the nodes on NVM Time t only requires updating the pointers in the aux- Time t+1 iliary hash table, which again saves on I/O and Time t+2 computation. Time t+3
optimized by saving I/O and computation costs, thus allowing more time for batch updates to nodes on slow storage. However, this might negatively afect range queries since messages are scattered across the bufer Batch 1
Batch 2
Batch 3
Free Buffer
timestamps. At time ’t’, the bufer contains keys and pivots, and its bufer part does not contain any messages or updates. At time ’t+1’, a batch of messages in cyan is moved from the parent node and written to the bufer. Next, at time ’t+2’, a batch of messages in brown is again lfushed down from the parent node and written to the next available location in the bufer. Finally, at time ’t+3’, the batch of messages in blue is moved to the node.
On the other hand, in the typical design, each node undergoes three read-modify-write cycles for updates, which can lead to increased computation costs and fragmentation, given that the node is retrieved from persistent media or storage for each update.
model, the B -tree grows in DRAM using memoryresident data structures and is persisted using storageresident data structures.
The suggested design begins with the same workflow. However, the flow changes when the nodes are flushed to the persistent media. In this design, the internal nodes are by default flushed onto NVM where keys and pivots are stored in an optimized node layout, and the messages are moved to the centralized bufer as discussed in Section 5.2. Later, when the tree needs to access the nodes on NVM, their data is directly accessed from the respective data structures, and only the nodes on other block storages are copied into DRAM. That said, frequently accessed nodes on NVM can be moved to DRAM to minimize latency.
of the node are pushed into the centralized bufer in NVM. This change in workflow allows the algorithm more time and space to perform batch updates to subsequent nodes and eventually to the leaf nodes. Furthermore, if the descent of the messages only involves the internal nodes on NVM, it involves merely updating the pointers in the auxiliary hash table in NVM.
This section discusses a scenario involving a highly random workload. Consider a dense tree distributed across various storage devices, with internal nodes on NVM and leaf nodes on SSD and HDD. Here, small updates accumulate in a central bufer in NVM. Furthermore, most leaf nodes receive a single or few updates from their preceding internal node in NVM, necessitating occasional lfushing of updates to the leaf nodes. The primary challenge with this flushing process is the significant write amplification it causes. For instance, flushing 1000 small updates from NVM to 1000 leaf nodes on SSD or HDD would result in 1000 writes of 4 MB each (the default node size). Additionally, this process also requires reading leaf nodes into DRAM first, which incurs additional cost.
There are two potential solutions to mitigate this issue. First, a small bufer could be integrated into each leaf node (as discussed in Section 5.4), allowing small updates to be directly written to this bufer area without needing to read the entire node into DRAM, deserialize, serialize, and then write it back to storage. This approach would still involve 1000 writes but would reduce the data size of each write, saving on read and computation costs. Second, instead of flushing small updates directly to leaf nodes, messages related to the internal node in NVM could be serialized and stored as a typical node (e.g., bufer node). This strategy would result in a single write. However, when accessing the internal node later, its corresponding bufer node would need to be retrieved from storage.
This use case discusses a scenario where the hot nodes 7. Preliminary Experiments are in DRAM, the internal nodes are on NVM, and the leaf nodes, or the least accessed nodes, are on slow storage. In this section, we present a small (single-threaded) exper
The scan operations on the nodes in DRAM follow iment6, in favor of the proposed design, particularly the the typical workoflw. However, the flow changes when granular reads on NVM. The experiments are performed accessing nodes on NVM. First, they can be queried with- in a sandbox where NVM is accessed using diferent apout being fetched into DRAM. Second, the centralized proaches and access patterns. In it, multiple Objects bufer can be queried simultaneously. Only the nodes on are used to imitate the internal node structure (partially) slow storage need to be moved into DRAM. where all the Objects contain 1024 Strings. However,
Moreover, the update operation on nodes on NVM the sizes of the Strings vary in each Object, from 4 KB
does not require moving the nodes into DRAM. Contrary to 2 bytes, which is done to cover primitive data types
to [
The experiments are conducted on a dual-socket server DRAM (Sequential) DRAM (Random) featuring Intel® Xeon® Gold 5220R CPUs. Each CPU Direct (Sequential) Direct (Random) has 24 physical cores, with each socket being equipped IInn--ddiirreecctt III((SSeeqquueennttiaial)l) IInn--ddiirreecctt III((RRaannddoomm)) with 4 PMem7 and 6 DRAM DIMMs. The experiments Bytes Read (Direct) Bytes Read (In-direct) are run on NUMA node ’0’ to minimize memory access (o5v.4e.r0h-e1a26d-sg, eannedricth).eTmheacPhMinemermunosduUlebuisnatcuce2s0s.e0d4.i3nLaTppS 600 4096 direct mode using fsdax8.
The results are illustrated in Figure 3. The experiment )s 400 ibnavcoklivnesdiwferreitnitnsge1tt0in24gso, bejiethctesr troanNdVomMlyanodr sreeqaudeinngtiathlleym, i(eTmm200 64 for instance. This process is repeated for each Object type, as indicated on the horizontal axis, using their respective String sizes. The right vertical axis shows the 0 data moved to DRAM from NVM, and the left one shows 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 the time taken in milliseconds. Block Size (bytes)
The direct approach reads (pmem_memcpy) the strings
in the objects one by one from NVM. Conversely, the
indirect-II approach first copies ( pmem_memcpy) the entire Figure 3: Accessing NVM in diferent settings and access
object into DRAM, then reads (memcpy) the strings in the patterns, and imitating the node reading behavior in [
The case that took the least time, unsurprisingly, in- Intel’s discontinuation of its Optane Persistent Memory
volves copying data within DRAM. The next expected modules.
pattern is the in-direct-I case, which consumes the same The insights from this study will deepen our
underamount of time throughout the experiments as it copies standing of storage solutions that balance the speed of
the same volume of data each time from NVM. The in- DRAM with the capacity of NVMe SSDs. Particularly
direct-II case takes longer as it involves copying the data relevant is Compute Express Link (CXL), a leading
into DRAM, then copying the strings one by one to a dif- terconnect technology that enables rapid data transfers
ferent location in DRAM. The case that is of our interest and manages large, variable-speed memory pools. CXL’s
is the direct case. It performs read operations in small coherent memory protocol, which maintains data
conblocks (the size of the String in the respective Object sistency across local memory caches, positions it as a
type), yet it takes less time than the in-direct cases, ex- transformative technology for future enterprise data
storcept for 4096. However, the cost to serialize/deserialize age [
B -tree is presented. While various B-tree variants have been developed to utilize the characteristics of NVM, none have specifically optimized a B -tree for this pur
interleaved settings, and the block size is 4 KB. 8https://docs.pmem.io/ndctl-user-guide/managing-namespaces
be found at: https://github.com/sajadKarim/haldendb/