Re: [IndexedDB] Avoiding reader/writer starvation

On Mon, Aug 16, 2010 at 3:06 AM, Jeremy Orlow <jorlow@chromium.org> wrote:
> On Fri, Aug 13, 2010 at 7:30 PM, Pablo Castro <Pablo.Castro@microsoft.com>
> wrote:
>>
>> In the context of transactions, readers using READ_ONLY and writers using
>> READ_WRITE may block each other when starting transactions, at least for
>> cases where the underlying implementation uses locking for isolation. Since
>> we allow multiple readers and they can start while other readers were
>> already running, it's possible that readers end up starving writers in a
>> concurrent setting. It seems it would be a good idea to add some minimum
>> guarantees to the spec that ensures some amount of fairness to concurrent
>> activities against a given database.
>>
>> We could either include a loose recommendation or try to mandate a strict
>> behavior. It seems the loose recommendation is more practical, the questions
>> are a) is there a risk of incompatible behavior because of
>> under-specification, and b) will we risk that some implementations will just
>> ignore this aspect if it's specified too informally.
>>
>> The loose recommendation could just be a sentence in the transactions
>> section:
>>
>> "UAs need to ensure a reasonable level of fairness across readers and
>> writers to prevent starvation."
>>
>> If we wanted to be more specific, we could go with something like this
>> (we'd probably spell it out as rules if we decide to put this strict version
>> in the spec):
>>
>> "All readers can run concurrently, but once a writer tries to start a
>> transaction we stop allowing new readers to start and queue up the writer
>> and any subsequent reader/writer. Once the existing readers are drained the
>> writer runs, and after that whatever is queued up next runs, which can be
>> another writer or all the remaining readers (depending upon what came first,
>> another writer or another reader; readers are released all simultaneously
>> since they run concurrently)."
>>
>> Given that not all implementations will have to deal with this and that
>> different implementations may want to have different strategies, it seems
>> that just having the recommendation around starvation is the best option.
>
> I agree that we should have some (non-normative?) recommendation to avoid
> starvation in the spec and that anything more formal would be too
> constraining.

Sounds good to me. Here is the strategy that we're currently using in Firefox:

1. Transactions are always executed in the order they are "started".
Unless they can execute in parallel.
2. Transactions are considered to be started when the first request is
placed against them.

So in the following code:

trans1 = db.transaction(["foo"]);
trans1.objectStore("foo").get(...).onsuccess = ...;
trans2 = db.transaction(["foo"], READ_WRITE);
trans2.objectStore("foo").put(...).onsuccess = ...;
trans3 = db.transaction(["foo"]);
trans3.objectStore("foo").get(...).onsuccess = ...;

trans3 won't start until trans2 is committed.

/ Jonas

Received on Monday, 16 August 2010 20:50:31 UTC