3 ms·

Such systems exist (Redis is a great example of the "just keep it in RAM" idea) but I think what Ousterhout et al are getting at is that we are just starting to

by evgen 17y ago

Such systems exist (Redis is a great example of the "just keep it in RAM" idea) but I think what Ousterhout et al are getting at is that we are just starting to think about the consequences of moving to RAM-based dbs and have not really worked out the kinks. Right now RAM-based systems that I am aware of do not do very much meta-analysis on the access patterns or the data itself to try to migrate or cluster blobs for maximum performance. We have started to get better at doing this for data on disk (e.g. column-based stores, using large disk chunks to cut down on seeks, etc) but have just started thinking about how things will change when primary data is all in RAM. We have a lot of experience with dealing with efficient use of disk resources but the world of RAM-resident data is still pretty new and we are learning how many of our assumptions about how things should work based on the world of disk-based storage will carry over to the new paradigm.

antirez 17y ago
I'm starting to do things like this in Redis. For instance consider Redis Lists: POP and PUSH are O(1), also to get the first or last 10 items in constant time is possible with LRANGE, but what if the user is often accessing a "far" range in a very long list? A similar problem happens to ZRANGE and Sorted Sets. Ok this problems allows to apply some access-pattern based optimization solution. For instance the linked list will have an associated N-elements circular buffer with pointers to far elements, so you can jump to the N-th node if it's on the (small) circular buffer and the clients continue to ask for an "LRANGE mylist 1000000 1000010". This is probably just the start but in general a small cache of "nodes" to recently very used places of data structures is a promising strategy in order to turn otherwise O(N) access patterns in constant time when they are very frequent.

by evgen 17y ago

antirez 17y ago

I'm starting to do things like this in Redis. For instance consider Redis Lists: POP and PUSH are O(1), also to get the first or last 10 items in constant time is possible with LRANGE, but what if the user is often accessing a "far" range in a very long list? A similar problem happens to ZRANGE and Sorted Sets. Ok this problems allows to apply some access-pattern based optimization solution. For instance the linked list will have an associated N-elements circular buffer with pointers to far elements, so you can jump to the N-th node if it's on the (small) circular buffer and the clients continue to ask for an "LRANGE mylist 1000000 1000010". This is probably just the start but in general a small cache of "nodes" to recently very used places of data structures is a promising strategy in order to turn otherwise O(N) access patterns in constant time when they are very frequent.