search

Level / memdown

In-memory abstract-leveldown store for Node.js and browsers.
MIT License
287 stars 37 forks source link

puts/deletes during iteration messes with stream reads #9

Closed mhart closed 10 years ago

mhart commented 10 years ago

Because stream reads can happen asynchronously, modifications to _keys in between _next calls can result in items being emitted twice (or skipped entirely).

Eg: stream is iterating, _pos is 1 so _next returns the value from that index, but then a key is inserted at index 0 due to a _put, so now, even though _pos has been incremented to 2, _next will return the same value as last time because it's been shifted up the array.

The are two solutions that I can think for this off the top of my head:

  1. Take a snapshot/clone of _keys in the MemIterator constructor
  2. Increment/decrement _pos whenever an entry is added/removed (iterators could listen for these events)

I'd be leaning towards 1 as it's simpler, but it could take up a chunk of memory.

mhart commented 10 years ago

I'd be interested to know how LevelDB handles isolation with range queries...?

rvagg commented 10 years ago

LevelDB does an implicit snapshot when you request an iterator so you get a consistent view of the data no matter how long it takes to consume the readStream.

So yes, memdown doesn't behave like leveldb in this respect and it could lead to some awkward situations. Your suggested fix #1 would be fine in the case of a small amount of data but I'd hate to think of the GC churn happening with large data sets and frequent queries.

I'm happy for you to experiment here if this functionality is important to your use-case.

mhart commented 10 years ago

Yeah, agree with the GC churn... Thankfully in my main use case I have both a start and end - so should be able to get the iterator to only take a small slice. However, the general case is worse than that.

I'll have a play and let you know what I come up with.

mhart commented 10 years ago

Oops

mhart commented 10 years ago

OK, done in #10 - let me know what you think (the tests I added there fail currently)

mhart commented 10 years ago

Ah - I meant - the tests I added there fail currently on master - they succeed on the branch :-)

mhart commented 10 years ago

As in - they are actually testing the scenario I'm talking about, that's all.

calvinmetcalf commented 10 years ago

We can close this right since it got merged?