Menu
I have a question - lookup of a key value pair in an index - let's say on cassandra or postgres - is typically at around O(logn)
source: https://github.com/tinkerpop/blueprints/wiki/Graph-Indices.
In the redis documentation it states that runtime complexity is O(1).
Source: http://redis.io/commands/get http://redis.io/commands/hget
And getting the value of multiple keys is only linear O(m) where m is the number of keys retrieved http://redis.io/commands/hmget
How is it possible?
705
According to this run of memtier_benchmark , our Redis server can execute about 90 thousand operations per second in a 1:10 SET / GET ratio. It's important to note that each benchmark tool has its own algorithm for performance testing and data presentation.
redis is an in-memory, key/value store. Think of it as a dictionary with any number of keys, each of which has a value that can be set or retrieved. However, Redis goes beyond a simple key/value store as it is actually a data structures server, supporting different kinds of values.
A Redis hash is a collection of key value pairs. Redis Hashes are maps between string fields and string values. Hence, they are used to represent objects.
Redis can handle up to 2^32 keys, and was tested in practice to handle at least 250 million keys per instance. Every hash, list, set, and sorted set, can hold 2^32 elements. In other words your limit is likely the available memory in your system.
Redis is an in-memory store. It can therefore use data structures which are adapted to memory storage (allowing for fast random access).
To implement dictionaries (used for the main dictionary, but also for hash and set objects, and in conjunction with a skip list for zset objects), Redis use separate chaining hash tables, whose access complexity is O(1+n/k) where n is the number of items and k the number of buckets.
Redis makes sure the number of buckets grows with the number of items so that in practice n/k is kept low. This rehashing activity is done incrementally in background. When the number of items is significant, the complexity is close to O(1) (amortized).
Other stores (Cassandra for instance) are designed to store data on disk while minimizing the number of random I/Os for performance reasons. A hash table is not a good data structure for this, because it does not enforce the locality of the data (it does not benefit from buffer caching very well). So disk based stores usually use B-tree variants (most RDBMS) or log-structured merge (LSM) trees variants (Cassandra), which have O(log n) complexity.
So yes, Redis offers O(1) for many operations, but there is a constraint: all data should fit in memory. There is no magic here.
200
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
