Re: [IndexedDB] Cursors and modifications

On Wed, Jul 14, 2010 at 6:20 PM, Pablo Castro
<Pablo.Castro@microsoft.com> wrote:
> Making sure I get the essence of this thread: we're saying that cursors see live changes as they happen on objects that are "after" the object you're currently standing on;

Yes.

> and of course, any other activity within a transaction sees all the changes that happened before that activity took place. Is that accurate?

Yes. All other activity sees all changes as soon as they have happened.

> If it's accurate, as a side note, for the async API it seems that this makes it more interesting to enforce callback order, so we can more easily explain what we mean by "before".

Indeed.

/ Jonas

> From: jorlow@google.com [mailto:jorlow@google.com] On Behalf Of Jeremy Orlow
> Sent: Wednesday, July 14, 2010 9:27 AM
>
> On Wed, Jul 14, 2010 at 5:17 PM, Jonas Sicking <jonas@sicking.cc> wrote:
> On Wed, Jul 14, 2010 at 5:12 AM, Jeremy Orlow <jorlow@chromium.org> wrote:
>> On Thu, Jul 8, 2010 at 8:42 PM, Jonas Sicking <jonas@sicking.cc> wrote:
>>>
>>> On Mon, Jul 5, 2010 at 9:45 AM, Andrei Popescu <andreip@google.com> wrote:
>>> > On Sat, Jul 3, 2010 at 2:09 AM, Jonas Sicking <jonas@sicking.cc> wrote:
>>> >> On Fri, Jul 2, 2010 at 5:44 PM, Andrei Popescu <andreip@google.com>
>>> >> wrote:
>>> >>> On Sat, Jul 3, 2010 at 1:14 AM, Jonas Sicking <jonas@sicking.cc>
>>> >>> wrote:
>>> >>>> On Fri, Jul 2, 2010 at 4:40 PM, Pablo Castro
>>> >>>> <Pablo.Castro@microsoft.com> wrote:
>>> >>>>>
>>> >>>>> From: public-webapps-request@w3.org
>>> >>>>> [mailto:public-webapps-request@w3.org] On Behalf Of Jonas Sicking
>>> >>>>> Sent: Friday, July 02, 2010 4:00 PM
>>> >>>>>
>>> >>>>>>> We ran into an complicated issue while implementing IndexedDB. In
>>> >>>>>>> short, what should happen if an object store is modified while a cursor is
>>> >>>>>>> iterating it? >> Note that the modification can be done within the same
>>> >>>>>>> transaction, so the read/write locks preventing several transactions from
>>> >>>>>>> accessing the same table isn't helping here.
>>> >>>>>>>
>>> >>>>>>> Detailed problem description (this assumes the API proposed by
>>> >>>>>>> mozilla):
>>> >>>>>>>
>>> >>>>>>> Consider a objectStore "words" containing the following objects:
>>> >>>>>>> { name: "alpha" }
>>> >>>>>>> { name: "bravo" }
>>> >>>>>>> { name: "charlie" }
>>> >>>>>>> { name: "delta" }
>>> >>>>>>>
>>> >>>>>>> and the following program (db is a previously opened IDBDatabase):
>>> >>>>>>>
>>> >>>>>>> var trans = db.transaction(["words"], READ_WRITE); var cursor; var
>>> >>>>>>> result = []; trans.objectStore("words").openCursor().onsuccess = function(e)
>>> >>>>>>> {
>>> >>>>>>>   cursor = e.result;
>>> >>>>>>>   result.push(cursor.value);
>>> >>>>>>>   cursor.continue();
>>> >>>>>>> }
>>> >>>>>>> trans.objectStore("words").get("delta").onsuccess = function(e) {
>>> >>>>>>>   trans.objectStore("words").put({ name: "delta", myModifiedValue:
>>> >>>>>>> 17 }); }
>>> >>>>>>>
>>> >>>>>>> When the cursor reads the "delta" entry, will it see the
>>> >>>>>>> 'myModifiedValue' property? Since we so far has defined that the callback
>>> >>>>>>> order is defined to be >> the request order, that means that put request
>>> >>>>>>> will be finished before the "delta" entry is iterated by the cursor.
>>> >>>>>>>
>>> >>>>>>> The problem is even more serious with cursors that iterate
>>> >>>>>>> indexes.
>>> >>>>>>> Here a modification can even affect the position of the currently
>>> >>>>>>> iterated object in the index, and the modification can (if i'm reading the
>>> >>>>>>> spec correctly) >> come from the cursor itself.
>>> >>>>>>>
>>> >>>>>>> Consider the following objectStore "people" with keyPath "name"
>>> >>>>>>> containing the following objects:
>>> >>>>>>>
>>> >>>>>>> { name: "Adam", count: 30 }
>>> >>>>>>> { name: "Bertil", count: 31 }
>>> >>>>>>> { name: "Cesar", count: 32 }
>>> >>>>>>> { name: "David", count: 33 }
>>> >>>>>>> { name: "Erik", count: 35 }
>>> >>>>>>>
>>> >>>>>>> and an index "countIndex" with keyPath "count". What would the
>>> >>>>>>> following code do?
>>> >>>>>>>
>>> >>>>>>> results = [];
>>> >>>>>>> db.objectStore("people",
>>> >>>>>>> READ_WRITE).index("countIndex").openObjectCursor().onsuccess =
>>> >>>>>>> function (e) {
>>> >>>>>>>   cursor = e.result;
>>> >>>>>>>   if (!cursor) {
>>> >>>>>>>     alert(results);
>>> >>>>>>>     return;
>>> >>>>>>>   }
>>> >>>>>>>   if (cursor.value.name == "Bertil") {
>>> >>>>>>>     cursor.update({name: "Bertil", count: 34 });
>>> >>>>>>>   }
>>> >>>>>>>   results.push(cursor.value.name);
>>> >>>>>>>   cursor.continue();
>>> >>>>>>> };
>>> >>>>>>>
>>> >>>>>>> What does this alert? Would it alert "Adam,Bertil,Erik" as the
>>> >>>>>>> cursor would stay on the "Bertil" object as it is moved in the index? Or
>>> >>>>>>> would it alert "Adam,Bertil,Cesar,David,Bertil,Erik" as we would iterate
>>> >>>>>>> "Bertil" again at its new position in the index?
>>> >>>>>
>>> >>>>> My first reaction is that both from the expected behavior of
>>> >>>>> perspective (transaction is the scope of isolation) and from the
>>> >>>>> implementation perspective it would be better to see live changes if they
>>> >>>>> happened in the same transaction as the cursor (over a store or index). So
>>> >>>>> in your example you would iterate one of the rows twice. Maintaining order
>>> >>>>> and membership stable would mean creating another scope of isolation within
>>> >>>>> the transaction, which to me would be unusual and it would be probably quite
>>> >>>>> painful to implement without spilling a copy of the records to disk (at
>>> >>>>> least a copy of the keys/order if you don't care about protecting from
>>> >>>>> changes that don't affect membership/order; some databases call these keyset
>>> >>>>> cursors).
>>> >>>>>
>>> >>>>>>>
>>> >>>>>>> We could say that cursors always iterate snapshots, however this
>>> >>>>>>> introduces MVCC. Though it seems to me that SNAPSHOT_READ already does that.
>>> >>>>>
>>> >>>>> Actually, even with MVCC you'd see your own changes, because they
>>> >>>>> happen in the same transaction so the buffer pool will use the same version
>>> >>>>> of the page. While it may be possible to reuse the MVCC infrastructure, it
>>> >>>>> would still require the introduction of a second scope for stability.
>>> >>>>
>>> >>>> It's quite implementable using append-only b-trees. Though it might
>>> >>>> be
>>> >>>> much to ask that implementations are forced to use that.
>>> >>>>
>>> >>>> An alternative to what I suggested earlier is that all read
>>> >>>> operations
>>> >>>> use "read committed". I.e. they always see the data as it looked at
>>> >>>> the beginning of the transaction. Would this be more compatible with
>>> >>>> existing MVCC implementations?
>>> >>>>
>>> >>>
>>> >>> Hmm, so if you modified the object store and then, later in the same
>>> >>> transaction, used a cursor to iterate the object store, the cursor
>>> >>> would not see the earlier modifications? That's not very intiutive to
>>> >>> me...or did I misunderstand?
>>> >>
>>> >> If we go with "read committed" then yes, your understanding is correct.
>>> >>
>>> >> Out of curiosity, how are you feeling about the "cursors iterate data
>>> >> as it looked when cursor was opened" solution?
>>> >>
>>> >
>>> > I feel that that's the easiest solution to specify although it may
>>> > also be unintuitive if one calls 'put / update' and then expects to
>>> > see the updated value once the cursor gets to the relevant object. My
>>> > other concern was the one brought by Pablo, i.e. is it even more
>>> > complex to implement another scope of isolation for the duration of
>>> > the cursor?
>>> >
>>> >>>> I'd imagine this should be as easy to implement as SNAPSHOT_READ.
>>> >>>>
>>> >>>>>>> We could also say that cursors iterate live data though that can
>>> >>>>>>> be pretty confusing and forces the implementation to deal with entries being
>>> >>>>>>> added and >> removed during iteration, and it'd be tricky to define all edge
>>> >>>>>>> cases.
>>> >>>>>
>>> >>>>> Would this be any different from the implementation perspective than
>>> >>>>> dealing with changes that happen through other transactions once they are
>>> >>>>> committed? Typically at least in non-MVCC systems committed changes that are
>>> >>>>> "further ahead" in a cursor scan end up showing up even when the cursor was
>>> >>>>> opened before the other transaction committed.
>>> >>>>
>>> >>>> IndexedDB doesn't allow write transactions to a given store to start
>>> >>>> while there are read transactions using that store, so that doesn't
>>> >>>> seem to be a problem. Unless I'm misunderstanding something?
>>> >>>>
>>> >>>
>>> >>> That was my understanding too: while a cursor was open, you can't
>>> >>> allow a write transaction to start.
>>> >>
>>> >> Exactly. Though "while a read transaction was open, you can't allow a
>>> >> write transaction to start" is even more correct.
>>> >>
>>> >>>>>>> It's certainly debatable how much of a problem any of these
>>> >>>>>>> edgecases are for users. Note that all of this is only an issue if you
>>> >>>>>>> modify and read from the >> same records *in the same transaction*. I can't
>>> >>>>>>> think of a case where it isn't trivial to avoid these problems by separating
>>> >>>>>>> things into separate transactions.
>>> >>>>>>> However it'd be nice to avoid creating foot-guns for people to
>>> >>>>>>> play with (think of the children!).
>>> >>>>>>>
>>> >>>>>>> However we still need to define *something*. I would suggest that
>>> >>>>>>> we define that cursors iterate snapshots. It seems the cleanest for users
>>> >>>>>>> and easiest >> to define. And once implementations add MVCC support it
>>> >>>>>>> should be easy to implement. I think we've come up with a decent plan for
>>> >>>>>>> how to do implement it in sqlite even without proper MVCC, so it should be
>>> >>>>>>> doable even then.
>>> >>>>>
>>> >>>>> Besides the expectations aspects, I worry that doing this means that
>>> >>>>> opening a cursor means incurring in substantial cost for all cases (e.g.
>>> >>>>> creating a keyset or something like that).
>>> >>>>
>>> >>>> I agree we definitely don't want that. We are working on an
>>> >>>> implementation which is backed by a SQL database and completely
>>> >>>> incapable of MVCC, so it seems doable. However I don't yet know how
>>> >>>> much of a complexity and performance penalty that carries.
>>> >>>>
>>> >>>
>>> >>> On the other hand, as you said earlier, maybe allowing the live
>>> >>> changes to be visible in the cursor is not such a big problem as apps
>>> >>> can work around these edge cases?
>>> >>
>>> >> I suspect so. Though given that behavior can be very unintuitive, we
>>> >> would have to define things to a very high level of detail to ensure
>>> >> that the same unintuitive behavior is happening in all
>>> >> implementations. Additionally, I suspect implementation can get quite
>>> >> complex in order to deal with all edge cases, for example dealing with
>>> >> data that was read ahead optimistically.
>>> >>
>>> >> We strategy for defining this is to define all mutating operations in
>>> >> terms of which ones are insertions vs. updates vs. removals. Both in
>>> >> the objectStore and in indexes. For example, does a IDBObjectStore.put
>>> >> call that modifies an existing entry cause corresponding entries in
>>> >> indexes to be updated or removed and reinserted? Both in the situation
>>> >> when the put call causes index values to be changed and not changed.
>>> >>
>>> >> Then define how active cursors move around when an entry that they are
>>> >> currently on is removed, or when entries before and after the current
>>> >> entry are inserted. For all types of cursors; forwards, backwards and
>>> >> no_duplicate. Also need to define this in situations when the cursor
>>> >> is currently firmly in one position, or when a .continue() call has
>>> >> been made, but the callback not yet has fired. Likewise when the
>>> >> cursor has not yet fired its first callback and entries are inserted
>>> >> in the beginning, and when a cursor has notified about the last entry,
>>> >> and entries are added after the end.
>>> >>
>>> >> It's certainly possible, but no small feat.
>>> >>
>>> >
>>> > Ok, let me try to come up with some wording for this in the spec. I
>>> > think we should go for this solution for now and see what the
>>> > implementation feedback is.
>>>
>>> Actually, I had a somewhat different idea for how this should be
>>> specified, which I think both would be easier to specify, as well as
>>> implement.
>>>
>>> When iterating using a cursor, always remember the key-value of the
>>> last returned entry. Whenever .continue() is called, it goes to find
>>> the next entry with a key-value bigger than the one last returned.
>>> This way the cursor isn't affected if the current entry is removed,
>>> we'll still remember and use the key-value that that entry had.
>>>
>>> This is simple when iterating objectStores since keys are always
>>> unique. However it's only marginally trickier when iterating indexes
>>> which can contain duplicate key-values. As I suggested in bug 10058, I
>>> think we should defined that duplicate index entries are ordered by
>>> their key-value in the objectStore. So all a index-cursors needs to do
>>> is to remember both the index key-value and the objectStore key-value
>>> of the last returned entry. When .continue() is called it returns the
>>> next entry with the same index key-value and larger objectStore
>>> key-value if one exists, or the next entry with a larger index
>>> key-value otherwise.
>>>
>>> Simpler put: For objectStore cursors, the key remembered is the
>>> objectStores key-value. For index cursors, the key remembered is the
>>> <index-key-value, objectStore-key-value> tuple.
>>>
>>> Let me know what you think.
>>
>> This sounds good.  The only problem is how to specify a sort order for
>> values.  Sorting on the value itself means that structured clones themselves
>> need a sort order.  This would include things like files, regexs, images,
>> etc.  So maybe we want to make the sort order be based on insertion order?
>>  Does anyone have any better ideas?
> Note that I'm always talking about sorting on key-values. I.e. the
> value of the keys. So we'll only ever need to define sorting of the
> types that we accept as keys. So currently none of the types you are
> mentioning above.
>
> Good point.  Got mixed up.  That definitely makes things easier!
>
> J
>

Received on Thursday, 15 July 2010 01:45:46 UTC