Re: [Qemu-devel] qcow2 performance plan

[Anthony Liguori]

Hi Avi,

On 09/14/2010 08:07 AM, Avi Kivity wrote:
>  Here's a draft of a plan that should improve qcow2 performance.  It's 
> written in wiki syntax for eventual upload to wiki.qemu.org; lines 
> starting with # are numbered lists, not comments.

Thanks for putting this together.  I think it's really useful to think 
through the problem before anyone jumps in and starts coding.

> = Basics =
>
> At the minimum level, no operation should block the main thread.  This
> could be done in two ways: extending the state machine so that each
> blocking operation can be performed asynchronously 
> (<code>bdrv_aio_*</code>)
> or by threading: each new operation is handed off to a worker thread.
> Since a full state machine is prohibitively complex, this document
> will discuss threading.

There's two distinct requirements that must be satisfied by a fast block 
device.  The device must have fast implementations of aio functions and 
it must support concurrent request processing.

If an aio function blocks in the process of submitting the request, it's 
by definition slow.  But even if you may the aio functions fast, you 
still need to be able to support concurrent request processing in order 
to achieve high throughput.

I'm not going to comment in depth on your threading proposal.  When it 
comes to adding concurrency, I think any approach will require a rewrite 
of the qcow2 code and if the author of that rewrite is more comfortable 
implementing concurrency with threads than with a state machine, I'm 
happy with a threaded implementation.

I'd suggest avoiding hyperbole like "a full state machine is 
prohibitively complex".  QED is a full state machine.  qcow2 adds a 
number of additional states because of the additional metadata and sync 
operations but it's not an exponential increase in complexity.

There are alternative models of concurrency that are worth exploring.  
For instance, coroutines are extremely appealing to me for this type of 
concurrency.  Let me give an example of why.  To handle a read request, 
qed loosely looks like:

aio_read():
   read_table(l1_table, aio_read_l2_table, opaque)

aio_read_l2_table():
   read_table(l2_table, aio_read_data, opaque)

aio_read_data():
   read_data(offset, aio_read_complete, opaque)

aio_read_complete():
   complete_request()

There's no parallelism so there's no need for locking.  With coroutines, 
there is no added parallelism but you can encode a state machine table 
using control flow by yielding to the next state.  QED aio_read() ends 
up looking like:

aio_read():
   launch_coroutine(aio_read_impl)

aio_read_impl():
   read_table(l1_table)
   read_table(l2_table)
   read_data(offset)
   complete_request()

There's a subtle difference with threads though.  Instead of being 
re-entrant by default, you only are re-entrant at well defined points in 
time.

What's nice is that coroutines can be implemented using threads or 
something more sophisticated (like ucontext).  Code written via state 
machine can be converted to coroutines without really thinking.

I'd like to get QED merged first, but my plan is to attempt to introduce 
coroutines to QEMU with something like QED.  I think coroutines are a 
much better fit for concurrency in QEMU than using pre-emptive threads.

> = Speeding up allocation =
>
> When a write grows a qcow2 image, the following operations take place:
>
> # clusters are allocated, and the refcount table is updated to reflect 
> this
> # sync to ensure the allocation is committed
> # the data is written to the clusters
> # the L2 table is located; if it doesn't exist, it is allocated and 
> linked
> # the L2 table is updated
> # sync to ensure the L2->data pointer is committed
>
> We can avoid the first sync by maintaining a volatile list of allocated
> but not yet linked clusters.  This requires a tradeoff between the 
> risk of
> losing those clusters on an abort, and the performance gain.  To 
> minimize the
> risk, the list is flushed if there is no demand for it.
>
> # we maintain low and high theresholds for the volatile free list
> # if we're under the low threshold, we start a task to allocate 
> clusters up to the midpoint
> # if we're above the high threshold, we start a task to return 
> clusters down to the midpoint
> # if we ever need a cluster (extent) and find that the volatile list 
> is empty, we double the low and thresholds (up to a limit)
> # once a second, we decrease the thresholds by 25%
>
> This ensures that sustained writes will not block on allocation.
>
> Note that a lost cluster is simply leaked; no data loss is involved.  
> The free list can be rebuilt if an unclean shutdown is detected.  
> Older implementations can ignore this those leaks.  To transport an 
> image, it is recommended to run qemu-img to reclaim any clusters in 
> case it was shut down uncleanly.

I'm not sure that letting older implementations ignore leaks is a 
reasonable approach.

> == Alternative implementation ==
>
> We can avoid a volatile list by relying on guest concurrency.  We replace
> <code>bdrv_aio_write</code> by <code>bdrv_aio_submit</code>, which issues
> many operations in parallel (but completes each one separately).  This 
> mimics
> SCSI and virtio devices, which can trigger multiple ops with a single 
> call
> to the hardware.  We make a first pass over all write operations, 
> seeing how
> many clusters need to be allocated, allocate that in a single 
> operation, then
> submit all of the allocating writes.

The difficulty here is that making a first pass means you have to read 
the metadata for each operation.  Each write() may have many writes to 
difference clusters which means that you've got to potentially read a 
lot of metadata.

This means that you may have one write that you know needs a new cluster 
but you wait to do the actual write until you finish other metadata 
operations.  It's non obvious without benchmarking whether this is the 
best strategy.

Regards,

Anthony Liguori

> = Avoiding L2 syncs =
>
> Currently after updating an L2 table with a cluster pointer, we sync 
> to avoid
> loss of a cluster.  We can avoid this since the guest is required to sync
> if it wants to ensure the data is on disk.  We need only to sync if we 
> UNMAP
> the cluster, before we free it in the refcount table.
>
> = Copying L1 tables =
>
> qcow2 requires copying of L1 tables in two cases: taking a snapshot, 
> and growing the physical image size beyond a certain boundary.  Since 
> L1s are relatively small, even for very large images, and growing L1 
> is very rare, we can exclude all write operations by having a global 
> shared/exclusive lock taken for shared access by write operations, and 
> for exclusive access by grow/snapshot operations.
>
> If concurrent growing and writing is desired, it can be achieved by 
> having a thread copy L1, and requiring each L1 update to update both 
> copies (for the region already copied) or just the source (for the 
> region that was not yet copied).