319
needs to store data that is unique to one thread of execution. In the persistent case,
we often need to associate data with a transaction rather than a thread.
In libpmemobj, we need a way to create an association between an in-flight
transaction and its persistent logs. It also requires a way to reconnect to those logs after
an unplanned interruption. The solution is to use a data structure called a “lane,” which
is simply a persistent byte buffer that is also transaction local.
Lanes are limited in quantity, have a fixed size, and are located at the beginning
of the pool. Each time a transaction starts, it chooses one of the lanes to operate from.
Because there is a limited number of lanes, there is also a limited number of transactions
that can run in parallel. For this reason, the size of the lane is relatively small, but the
number of lanes is big enough as to be larger than a number of application threads
that could feasibly run in parallel on current platforms and platforms coming in the
foreseeable future.
The challenge of the lane mechanism is the selection algorithm, that is, which lane
to choose for a specific transaction. It is a scheduler that assigns resources (lanes) to
perform work (transactions).
The naive algorithm, which was implemented in the earliest versions of libpmemobj,
simply picked the first available lane from the pool. This approach has a few problems.
First, the implementation of what effectively amounts to a single LIFO (last in, first
out) data structure of lanes requires a lot of synchronization on the front of the stack,
regardless of whether it is implemented as a linked list or an array, and thus reducing
performance. The second problem is false sharing of lane data. False sharing occurs
when two or more threads operate on data that is being modified, causing CPU cache
thrashing. And that is exactly what happens if multiple threads are continually fighting
over the same number of lanes to start new transactions. The third problem is spreading
the traffic across interleaved DIMMs. Interleaving is a technique that allows sequential
traffic to take advantage of throughput of all of the DIMMs in the interleave set by
spreading the physical memory across all available DIMMs. This is similar to striping
(RAID0) across multiple disk drives. Depending on the size of the interleaved block, and
the platform configuration, using naive lane allocation might continuously use the same
physical DIMMs, lowering the overall performance.
To alleviate these problems, the lane scheduling algorithm in libpmemobj is more
complex. Instead of using a LIFO data structure, it uses an array of 8-byte spinlocks, one
for each lane. Each thread is initially assigned a primary lane number, which is assigned
in such a way as to minimize false sharing of both lane data and the spinlock array.
Chapter 16 pMDK Internals: IMportant algorIthMs anD Data struCtures
needs to store data that is unique to one thread of execution. In the persistent case,
we often need to associate data with a transaction rather than a thread.
In libpmemobj, we need a way to create an association between an in-flight
transaction and its persistent logs. It also requires a way to reconnect to those logs after
an unplanned interruption. The solution is to use a data structure called a “lane,” which
is simply a persistent byte buffer that is also transaction local.
Lanes are limited in quantity, have a fixed size, and are located at the beginning
of the pool. Each time a transaction starts, it chooses one of the lanes to operate from.
Because there is a limited number of lanes, there is also a limited number of transactions
that can run in parallel. For this reason, the size of the lane is relatively small, but the
number of lanes is big enough as to be larger than a number of application threads
that could feasibly run in parallel on current platforms and platforms coming in the
foreseeable future.
The challenge of the lane mechanism is the selection algorithm, that is, which lane
to choose for a specific transaction. It is a scheduler that assigns resources (lanes) to
perform work (transactions).
The naive algorithm, which was implemented in the earliest versions of libpmemobj,
simply picked the first available lane from the pool. This approach has a few problems.
First, the implementation of what effectively amounts to a single LIFO (last in, first
out) data structure of lanes requires a lot of synchronization on the front of the stack,
regardless of whether it is implemented as a linked list or an array, and thus reducing
performance. The second problem is false sharing of lane data. False sharing occurs
when two or more threads operate on data that is being modified, causing CPU cache
thrashing. And that is exactly what happens if multiple threads are continually fighting
over the same number of lanes to start new transactions. The third problem is spreading
the traffic across interleaved DIMMs. Interleaving is a technique that allows sequential
traffic to take advantage of throughput of all of the DIMMs in the interleave set by
spreading the physical memory across all available DIMMs. This is similar to striping
(RAID0) across multiple disk drives. Depending on the size of the interleaved block, and
the platform configuration, using naive lane allocation might continuously use the same
physical DIMMs, lowering the overall performance.
To alleviate these problems, the lane scheduling algorithm in libpmemobj is more
complex. Instead of using a LIFO data structure, it uses an array of 8-byte spinlocks, one
for each lane. Each thread is initially assigned a primary lane number, which is assigned
in such a way as to minimize false sharing of both lane data and the spinlock array.
Chapter 16 pMDK Internals: IMportant algorIthMs anD Data struCtures