Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finally Redis collections are iterable

antirez.com

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Finally Redis collections are iterable

#11

Post by nknighthb »

DanWaterworth wrote: post #3

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.

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

#12

Post by qwerta »

antirez wrote: post #7
qwerta wrote: post #6

Earlier quoted context omitted.

It is actually very reasonable. Other alternative is that iterator returns an error if underlying collection was modified (fail fast iterators).

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 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…

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

#13

Post by antirez »

jwr wrote: post #8

This is cool and helpful, but not a game-changer. For things like garbage-collecting I've been using probabilistic techniques (just get a random element and check it, make sure you check enough to have guarantees you need) with great success. The new scanning doesn't provide any tight guarantees (it can't, really, without sacrificing a lot of what Redis stands for), so it will be more of a convenience than a really n…

I agree that for some data type like Sets you could use SRANDMEMBER, however to sample all the elements by random sampling you need to perform a lot more work. For example for a 10000 elements collection in average you are going to need around 10 times the requests.

Re: Finally Redis collections are iterable

#14

Post by antirez »

qwerta wrote: post #12
antirez wrote: post #7

Earlier quoted context omitted.

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 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…

Is 64bit counter part of hash which points to current position in Hash Tree? I implemented something similar for HTreeMap, but in Java.

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

#15

Post by qwerta »

antirez wrote: post #14
qwerta wrote: post #12

Earlier quoted context omitted.

Is 64bit counter part of hash which points to current position in Hash Tree? I implemented something similar for HTreeMap, but in Java.

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.

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

#17

Post by discardorama »

DanWaterworth wrote: post #3

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.

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

#20

Post by awj »

antirez wrote: post #7
qwerta wrote: post #6

Earlier quoted context omitted.

It is actually very reasonable. Other alternative is that iterator returns an error if underlying collection was modified (fail fast iterators).

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 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…

> 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 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.
Post reply on HN