Re: Parallel serialization and writes ? (Was: ACIDity of Prevayler 2.6)

Rather than responding in detail, I'd just like to quickly explain a couple
of points that I've so far just been hinting at.

First, remember that whether you're writing 1 byte or 1000 bytes, the
latency is really the same. Disks typically write in blocks of, say, 8K.
The latency of serializing a transaction to an in-memory buffer is really
pretty trivial compared to the latency of actually writing that buffer or
even a tiny marker to disk. That's where the inherent latency of
transactions vs. queries comes from. Prevayler already maximizes the
throughput of transactions by batching lots of transactions together in a
single disk write, but the latency (50-100ms) is unavoidable.

Second, let's make sure we're on the same page about why queries would also
have to be slow if transactions were written to disk _after_ execution.
Between the time a transaction executes and the time it (or its commit
marker) is written to disk, any changes it caused must be considered
uncommitted. We don't ever want uncommitted changes to be seen by the user.
It's actually fine for queries to execute against uncommitted data
(isolation is guaranteed by Prevayler's simple locking model) as long as
the results aren't actually returned until all the transactions preceding
that query are committed. Each batch of transactions actually being written
to disk effectively "releases" the results of those transactions _and_ any
queries that were interleaved with them.

Let's say our disk write latency is 100ms (pretty close to the truth), and
let's say the actual execution of a query or transaction is instantaneous
(also pretty close to the truth). As Prevayler currently works, queries
don't wait for disk writes and therefore execute and return
near-instantaneously. Each transaction arrives somewhere in the middle of a
prior batch being written to disk, so it has to wait for, on average, 50ms
for that batch to finish writing and an additional 100ms to be written
itself, for an average latency of 150ms. If transactions were to be written
to disk after execution, their latency would stay the same but queries
would also have to wait an average of 150ms before returning their results.

That's actually pretty significant. Adding 150ms latency to every query
means adding _at least_ 150ms latency to every page-load in a webapp, for
example. A typical target for reasonable responsiveness is less than 200ms
_total_ from the user clicking to the user seeing the result rendered in
the browser. Of course, most apps come nowhere near achieving that level of
responsiveness; if you already have 5s page-load times then your users
might not notice an extra 150ms. But if you're down around 200ms, an extra
150ms would make the difference between "Wow, this app is fast," and "Ugh,
this app is slow."


On Sat, Nov 17, 2012 at 12:56 PM, Arnaud Masson <[email protected]> wrote:

> It's a bit like my last email, because there are 2 phases:
>
> write "unfinished" tx in journal --> mark tx as completed
> vs
> prepare capsule --> write capsule
>
> Tx execution on in-memory model is during or after the 1st phase.
>
> The key point is that the first phase doesn't have to block incoming
> queries, while second phase must block them because the in-memory model
> has already been changed, so the tx must be made "durable" before its
> effects are visible by new queries.
>
> So it adds latency for (some) queries, the latency of the 2nd phase.
> That's why as much work as possible should be done in the 1st phase,
> while the 2nd phase should be as short as possible (e.g. write just one
> byte in the journal on disk).
>
> (With 2 "twin" in-memory models, I think it's possible to have both
> journal correctness and no IO latency on queries, but you need more RAM...)
>
>
> On 17/11/2012 16:27, Paul Bennett wrote:
> > I've been pouring through the code (version 2.3), both to understand in
> > more details, and see if it is possible to serialize and write
> > transactions completely in parallel with execution. I *think* I
> > understand what is happening, and want to offer a possible explanation
> > and implementation
> >
> > It seems to me that as a general principle, if you can order writes to
> > the journal in the same order as transaction execution, there is no
> > reason why you cannot do the two in parallel. It would mean that the
> > system state could get ahead of the log by
> > multiple transaction executions, but as long as this is bounded, it
> > doesn't violate the persistence invariants (I'm trying to stay away from
> > the term 'ACID' :-) - the system would still restore properly up to the
> > point of last write. The only transactions lost would be the ones
> > waiting to be written, which would by definition be bounded - probably
> > by a system parameter or some kind of heuristic
> >
> > So how would you do that? As I understand it now, Prevayler orders
> > journal serialization and write first, using the Guide's Turn,then use
> > that ordering to drive transaction execution (and interleaving queries
> > with that). So how would it be if that were reversed? Transaction would
> > arrive and be dispatched to a parallel journal-writing thread, and then
> > go on to execute, ordered as is done now. The writing thread would
> > prepare the transaction for writing (create the Capsule), then wait for
> > a signal from the transaction execution before actually writing it
> > (actually, that would be the publish operation, so that other publishers
> > (e.g ClientPublish) would get the same ordering).
> >
> > All that is required to do this is a reference in
> > the transaction execution that references the to-be-created Capsule.
> > When transactions executes, their references are queued in the same
> > order, so that the writing thread can examine that queue each time it is
> > done with preparation - it then decides if it has the Capsule referred
> > to by the head of the queue ready for writing. If it does, it removes
> > the reference and writes the Capsule, if not it goes back to preparing
> > more capsules. You might even prepare each Capsule on it's own thread,
> > and match Capsule creation and queue head each time one finishes. You
> > would not have more threads than there are CPU cores, with an amount
> > left over for user threads.
> >
> > It seems that this would remove the journal write and serialization
> > latency from transactions in the same way as is now done for queries,
> > while still maintaining the correct ordering and persistence guarantees.
> >
> > What did I miss ?
> >
> > -pb
> >
> >
> > On Nov 17, 2012, at 2:44 AM, Justin T. Sampson wrote:
> >
> >> Arnaud -- You've got things a bit backwards. Yes, larger latencies are
> >> acceptable for transactions than for queries, but that's exactly how
> >> Prevayler behaves: Queries execute and return immediately whereas
> >> transactions have to wait for writing to disk before executing and
> >> returning. If transactions were written to disk after executing, then
> >> both queries and transactions would execute immediately but both would
> >> wait for writing to disk before returning. Throughput would be
> >> similar, but query latency would be worse than it is now.
> >>
> >> Transactions are already serialized concurrently (in memory) without
> >> holding any locks, so don't worry about that. And the journal is
> >> written as a continuous stream, not individual files, so
> >> moving/renaming is not an option (and would be significantly slower).
> >>
> >>
> >> On Fri, Nov 16, 2012 at 2:06 AM, Arnaud Masson <[email protected]
> >> <mailto:[email protected]>> wrote:
> >>
> >>     Many systems have much more queries than transactions,
> >>     so transaction latency wouldn't be so critical.
> >>
> >>     Moreover a transaction could be physically pre-serialized (or maybe
> in
> >>     parallel thread) on the disk, in some temporary location, before the
> >>     lock scope.
> >>     After tx successful execution, just a quick "file move/rename"
> >>     operation
> >>     would be required to commit it to the journal, not a full
> >>     serialization.
> >>
>

------------------------------------------------------------------------------
Monitor your physical, virtual and cloud infrastructure from a single
web console. Get in-depth insight into apps, servers, databases, vmware,
SAP, cloud infrastructure, etc. Download 30-day Free Trial.
Pricing starts from $795 for 25 servers or applications!
http://p.sf.net/sfu/zoho_dev2dev_nov

_______________________________________________
To unsubscribe go to the end of this page: http://lists.sourceforge.net/lists/listinfo/prevayler-discussion
_______________________________________________
"Databases in Memoriam" -- http://www.prevayler.org