How feasible would it be to add support for higher concurrency to
SQLite, especially via MVCC?  (If it turns out to be feasible and
desirable, I'd be willing to work on it in my free time.)

What I would really like in SQLite would be:
- Good concurrency, preferably similar or better to that of nsv/tsv
  (see below).
- MVCC (multi-version concurrency control) model preferred, as in
  PostgreSQL and Oracle.

How feasible is that?  What designs have been or should be considered
for it?  How much work does this seem to be?  Does it become any
easier if it's considered for in-memory databases only, rather than
both in-memory and on-disk?

After some searching around I found these previous proposals or
discussions of increasing concurrency in SQLite:

Many of the suggestions in Dr. Hipp's 2003-11-22 concurrency draft
sound very useful, especially blocking (rather than polling) locks.
(In fact, I was surprised to learn that SQLite does NOT block on locks
now.)  But, that draft never mentions MVCC at all.  Why not?  Since
MVCC both gives better concurrency and is friendlier to use than
pessimistic locking models, I was surprised not to at least see it
mentioned.  Is an MVCC implementation thought to be too complicated?

Doug Currie's <[EMAIL PROTECTED]> "Shadow Paging" design sounds
promising.  Unfortunately, I have not been able to download the
referenced papers at all (where can I get them?), but as far as I can
tell, it seems to be describing a system with the usual
Oracle/PostgreSQL MVCC semantics, EXCEPT of course that Currie
proposes that each Write transaction must take a lock on the database
as a whole.

But, other than the locking granularity, in what way is Currie's
Shadow Paging design the same or different from PostgreSQL's MVCC
implementation, both in terms of user-visible transaction semantics,
and the underlying implementation?

I believe PostgreSQL basically marks each row with a transaction id,
and keeps track of whether each transaction id is in progress,
committed, or aborted.  Here are a few links about that:

Since Currie's design has only one db-wide write lock, it is
semantically equivalent to PostgreSQL's "serializable" isolation
level, correct?  How could this be extended to support table locking
and PostgreSQL's default "read committed" isolation level?  Would the
smallest locking granularity possible in Currie's design be one page
of rows, however many rows that happens to be?

The one process, many threads aspect of Currie's design sounds just
fine to me.  The one write lock for the whole database, on the other
hand, could be quite limiting.  How much more difficult would it be to
add table locks to the design?  It would also be a nice bonus if the
design at least contemplates how to add row locks (or locks for pages
of rows) in the future, but my guess is that table locks would be good
enough in practice.

Currie's design also seems to defer writing any data to disk until the
transaction commits, which seems odd to me.  I did not follow many of
the details of that design so I'm probably missing something here, but
since most write transactions commit rather than abort, in any sort of
MVCC model wouldn't it be better to write data to disk earlier rather
than later?  I'm pretty sure that's what both Oracle and PostgreSQL

My particular interest in SQLite:

Now that I've asked lots of questions above, I'll describe some of the
real-world use cases that got me thinking about this, in case it helps
clarify how and why I'm interested in a high-concurrency SQLite:

A while back I wrote a high-performance multi-threaded application
that basically just accepted data requests, used various ugly low
level proprietary C APIs to fetch data from remote servers, and then
organized the data and fed it back to the client application as simple
rows of CSV-style text.

Using all those low-level C APIs meant tracking lots of somewhat
complicated housekeeping data.  If my application ever crashed all
housekeeping data instantly became worthless anyway, so I definitely
didn't want to store it persistently in Oracle or PostgreSQL; for both
simplicity and performance, I wanted it in-memory only.

So in my case, I used AOLserver's nsv's for this.  (The Tcl Thread
Extension has "tsv" which is just like "nsv", except better.)  Nsvs
are basically just associative arrays for storing key/value pairs
(like Tcl arrays or Perl hashes), but nsv operations are both atomic
and highly concurrent, as they were designed for inter-thread
communication in AOLserver.  (Mutex locking is automatic.  Nsvs are
assigned to buckets with one mutex lock per bucket, and the number of
buckets is tunable.)

Using nsvs worked for me, but being limited to only key/value pairs
was UGLY.  Much of the housekeeping data had 1-to-many or even
many-to-many mappings (e.g., each "query" might have many
"request_ids"), and being limited to key/value pairs was both painful
and the source of some bugs.  And I believe that the pain and bugs
could have been a lot worse if my program and its housekeeping data
had more complicated.

What I REALLY wanted was an in-memory relational database, but I
didn't have one.  When I need on-disk persistence I'd normally use
Oracle or PostgreSQL, but certainly it'd be convenient if I could use
the same lightweight both in-memory and on-disk.

So there's a hole in my toolkit, and I'm looking for software to fill
it.  For that, SQLite seems to have the following important

- Relational, transactional, ACID.
- Simple and very high quality code (so I am told; I have not yet read
  any sources).
- Option of running either in-memory or on-disk.
- Pretty good support for SQL features, joins, etc.  (No correlated
  subqueries, but I can live with that.)
- Thread safe. 
- Easily embeddable anywhere C is.

For my needs SQLite seems to have only one problem:  Both readers and
writers must lock the whole database.  Unfortunately, that's a big

Maybe, in that one particular application I would have been able to
get away with using a single thread for all SQLite access, and having
all other threads talk to that one db thread.  I have not measured
SQLite performance and concurrency, nor compared it to nsv/tsv, so I
don't really know, and I would certainly want to make those tests
before hacking on any SQLite code.

But it seems clear that whatever the exact numbers are, SQLite MUST
have much lower concurrency than either Tcl's simple and lightweight
nsv/tsv key value pairs or heavier weight databases like Oracle or
PostgreSQL - and that limits the number of places I'd be able to use

Solutions other than SQLite:

One possible alternative to SQLite is Erlang's Mnesia RDBMS:

It also works both in-memory and on-disk, apparently already has high
concurrency, and can be distributed.  I have not (yet) investigated
it, and I could not tell from its docs what locking model it uses, how
powerful its query language is, etc.  But most importantly, it
definitely requires a running Erlang interpreter to work at all, and
it seems very unclear whether or how well any sort of access from
non-Erlang environments would work at all.

On this list, Mark D. Anderson <[EMAIL PROTECTED]> recently
recommended looking at the "HUT HiBASE/Shades" papers:

The fact that Nokia funded and then canceled the HiBase project is
interesting, as Ericsson developed Erlang, which sounds similar in
some ways.

Unfortunately, it sounds as if the HiBASE project is dead and the code
was never finished.  It also appears to be strictly a main-memory
database, so I'm not sure how applicable any of that work would be so
a database like SQLite (or Mnesia for that matter) which may be used
either in-memory or on-disk.

Anyone here aware of any other good alternatives?

Andrew Piskorski <[EMAIL PROTECTED]>

To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]

Reply via email to