News for hackers. Stuff that matters.
Re:Finally Redis collections are iterable by DanWaterworth on Tuesday October 29, 2013 @10:07AM (#6634159)
Elements added during the iteration may be returned, or not, at random.

I can't be the only one who thinks this is crazy behaviour.

Re:Finally Redis collections are iterable by qwerta on Tuesday October 29, 2013 @10:18AM (#6634249)
It is actually very reasonable. Other alternative is that iterator returns an error if underlying collection was modified (fail fast iterators).
Re:Finally Redis collections are iterable by antirez on Tuesday October 29, 2013 @10:21AM (#6634270)
There are alternatives but all will cost something... especially memory :-)

For example every element may have an epoch, and every time a new element is added the epoch is incremented. Then what you could do is to only remember elements with epoch <= the epoch at which you started iterating, so that all the new elements will not be returned.

We tried to do our best with the state available, that is just a 64 bit counter the server does not even need to remember, but just to return back to the caller, and get as argument in the next iterator call.

Re:Finally Redis collections are iterable by awj on Tuesday October 29, 2013 @01:01PM (#6635688)
> For example every element may have an epoch, and every time a new element is added the epoch is incremented. Then what you could do is to only remember elements with epoch <= the epoch at which you started iterating, so that all the new elements will not be returned.

Do that and you will immediately have people wanting an equally transaction-like view of the iteration set in the face of updates. I think it's best to draw the line where you have and be specific about what this is or is not intended to support.

Re:Finally Redis collections are iterable by qwerta on Tuesday October 29, 2013 @10:40AM (#6634431)
Is 64bit counter part of hash which points to current position in Hash Tree?

I implemented something similar for HTreeMap, but in Java.

Re:Finally Redis collections are iterable by antirez on Tuesday October 29, 2013 @10:46AM (#6634481)
It's actually something like a counter that counts starting from the most significant bits first, in the article there is a link to a comment that explains the implementation.
Re:Finally Redis collections are iterable by qwerta on Tuesday October 29, 2013 @11:04AM (#6634628)
So it was hard because hash table could resize between calls?

For HTreeMap I used expanding Hash Tree. There are 4 dir levels, each with 128 entries. If dir becomes full (or has too many collisions), it splits into another 128 dirs.

Iterations is done by increasing counter. If dir at level 2 is not found, it is increased by 128^2. Writing iterators took single day.

Re:Finally Redis collections are iterable by kevingadd on Tuesday October 29, 2013 @01:26PM (#6635900)
.NET's collections all fail fast for seemingly this reason - they can't really provide anything else without huge performance consequences (even the fail fast behavior comes with a cost, due to the check...)
Re:Finally Redis collections are iterable by hakt on Tuesday October 29, 2013 @02:02PM (#6636202)
I'm very happy with this compromise.

Schema migrations involving tens of millions of keys can be challenging. The KEYS command returns all matching keys, so you can roll your own iterator with KEYS AAA* then KEYS AAB* etc. But keys aren't evenly distributed so some result sets are zero and others are still too large.

I've been indexing keys with Redis lists and iterate through the index with LRANGE. That uses extra memory and causes more roundtrip calls.

I can deal with this compromise since SCAN makes Redis much more useful for my applications.

Re:Finally Redis collections are iterable by jwr on Tuesday October 29, 2013 @10:26AM (#6634310)
It's a compromise. If you need tighter specifications, you pretty much need to implement a transactional system.
Re:Finally Redis collections are iterable by discardorama on Tuesday October 29, 2013 @12:14PM (#6635245)
How is this any different from an iterator in Java? IIRC, if you have the iterator of a Collection and add elements to it during iteration, the results are undefined. You can, however, safely remove elements even while iterating.
Re:Finally Redis collections are iterable by DanWaterworth on Tuesday October 29, 2013 @04:15PM (#6637140)
I don't use Java.
Re:Finally Redis collections are iterable by thezilch on Tuesday October 29, 2013 @01:56PM (#6636145)
Redis has keyspace notifications [0], so you can make your iterator aware that it should possibly restart.

[0] http://redis.io/topics/notifications

Re:Finally Redis collections are iterable by bkirkbri on Tuesday October 29, 2013 @10:16AM (#6634239)
It's not crazy, it's realistic. Nothing is free and this sort of pragmatism lets/forces users to act like grown ups.

updated: grammar fix

Re:Finally Redis collections are iterable by nknighthb on Tuesday October 29, 2013 @10:29AM (#6634334)
I think it is the only appropriate behavior considering Redis's constraints and philosophy.

Redis is not a transactional, ACID-compliant datastore. You can, for at least some workloads, build such a datastore on top of it, but it requires care and effort. You have to assemble the given pieces correctly, and fabricate some of your own.

This SCAN mechanism seems perfectly in line with this -- if you understand its limitations, it might be a useful tool, but like every other part of Redis, you can't just use it assuming it acts like your favorite SQL RDBMS.

Re:Finally Redis collections are iterable by philsnow on Wednesday October 30, 2013 @02:40AM (#6639906)
I can't see why they don't just restart the cursor at the beginning when the collection goes up a size in the middle of an iteration.

Encode the size of the collection in the first 8 bits of the cursor value, and when the client gives you an cursor value with the first 8 bits set to a smaller size than the current size of the collection, start it over from scratch with the new size as the top 8 bits.

If the collection has shrunk, no big deal, just keep going from where the client was because of the mentioned properties of using a reversed bit set.

Re:Finally Redis collections are iterable by lmm on Tuesday October 29, 2013 @12:28PM (#6635400)
What do you think is crazy? What other behaviour do you feel would be appropriate to Redis' use cases?