Redis, NoSQL with extensive features - Part I
Redis (Remote Dictionary Server) is an open source, networked, in-memory, persistent, journaled, key-value data store. It is similar to memcached, but goes beyond storing simple string values by allowing for lists, sets and sorted sets. It can be used as a cache in front of a traditional database. As the in-memory datasets are not volatile but persisted on disk allows it to be used on its own (A case study using Redis alone for a web application is available at http://code.google.com/p/redis/wiki/TwitterAlikeExample).
Advanced Key-value Store
Redis is an advanced key-value store, where the keys must be simple strings. The power is in the values, which can be of the following types:
- Strings – Most basis type and the single elements in other data types are strings. Redis strings are binary safe, in the sense, it can contain any kind of data (JPEG image, serialize Ruby object etc.). Strings can be of maximum 1 GB in length and when treated as integer value is limited to signed 64 bit value.
- Lists – Lists are list of Redis Strings, sorted by insertion order. We can add new elements to the head of the list (using LPUSH command) or to the tail of the list (using RPUSH command).
- Sets – Sets are unordered collection of non-repeating Redis Strings. Sets (as expected) does not allow repeated members and adding same element multiple times results in the set having a single copy of the element (and doesn’t require a check for exists). Sets support a wide range of operations – Union, Intersection and difference.
- Sorted sets (zsets) – Collection of non-repeating elements ordered using an associated score (every member hash a score that is used to take the member in the right order). It is possible to get or remove a range of elements by score. It is also possible to use the SORT command to get the elements in a different order.
- Hashes – Unordered map of Redis strings between fields and values. Hashes provide a simple way for a key holding an object composed of different fields. For instance web applications users can be represented by a Redis Hash containing fields such username, encrypted password, last logic etc.
The maximum number of elements – applicable for lists, sets and hashes – is 232-1 (more than 4 billion).
Memory Efficient Implementation
Redis performance is its major strength as it uses memory and a few of the implementation details that make it efficient are listed below:
- Strings are implemented using a dynamic strings library called sds.c that caches the current length of the string (obtaining the length of a Redis string is an O(1) operation).
- Redis strings are stored as Redis Objects that enabling a single Redis String to be shared in different places of the dataset. If you use the same strings many time, Redis will try to use the same string object instead of allocating one every time.
- Redis encodes strings that actually save numbers so as to use less memory.
- Redis Lists are implemented as doubly linked lists making it possible to reach the needed element starting from the nearest extreme.
- The user of linked lists also guarantees that re regardless of the length of the list pushing and popping are O(1) operations.
- Redis Lists cache length information so that getting a length of a list is a O(1) Operation.
- Redis Sets are implemented using hash tables, so adding, removing and testing for members is O(1) in the average. The hash table will automatically resize when new elements are added or removed into a Set.
- Redis Sorted Sets are implemented using a dual-ported data structure containing a skip list and an hash table. When an element is added a map between the element and the score is added to the hash table (so that given the element we get the score in O(1)), and a map between the score and the element is added in the skip list so that elements are taken in order.
- Redis uses a different specialized representation for small hashes with limited number of fields using very little memory compared to storing every field as a top level Redis key.
For Sets and sorted sort, the hash table resizing is a blocking operation performed synchronously so working with huge sorted sets (consisting of many millions of elements) care should be taken when mass-inserting a very big amount of elements in a Set while other clients are querying Redis at high speed.
Redis as a Cache
Redis can work as a cache (similar to memcached) by using the EXPIRE and EXPIREAT commands. These set a key to expire after a certain number of seconds or at a specific time specified as a unix timestamp. The TTL command can be used to find out if a key is due to expire in a certain number of seconds.
Usually Redis places both keys and the associated values in Memory. But this may not be the best option, when the values are pretty large and available memory is limited. Redis Virtual memory, feature in ver 2.0, addresses this issue by swapping the values out to disk when they are rarely used.
Virtual Memory feature is useful when the data access is very biased and involves a small percentage of keys (say the active users in a web site). If you have a dataset of 100,000 keys in memory, with only 10% of keys are often used, Redis with Virtual Memory enabled will try to transfer the values associated to the rarely used keys on disk. When the values in disk are requested, the values get loaded from the swap file to the main memory.
Using client support for consistent hashing is recommended when Redis is used as cache.
Redis as a Data Store
Redis loads and mantains the whole dataset into memory, but the dataset is persistent, since it is also saved on disk, so that when the server is restarted data can be loaded back in memory.
In snapshotting mode, Redis periodically writes to disk asynchronously. Redis can be configured to save the dataset when a certain number of changes (say 1000 changes) is reached or after a given number of seconds (say 60 seconds) if there is at least a single change. Snapshotting is not very durable, as in case of failures, the latest data written will be lost. This could be applicable for most applications and where it is not, the alternative is provided.
Append only file is the alternative durability option provided by Redis. Every time Redis receives a command that changes a dataset (say a SET or LPUSH command) it appends the command in the append only file. When the server is restarted after failure, these commands are replayed in order to rebuild the database in memory.
If the changes are quite frequent, the append log file can become very big. The server provides an interesting feature (using command BGREWRITEAOF) by which it can safely rebuild in the background in a non-blocking fashion when the Append only file is too long. This command is able to use the dataset in memory in order to rewrite the shortest sequence of commands to rebuild the exact dataset that is currently in memory.
The user can configure the durability of the Append only file as follows:
- Always – Fsync() every time a new command is appended to the append log file. Obviously it is very safe but also very slow.
- Never – Do not Fsync(), just let the Operating system handle the sync with disk. This is much faster but not safe and gives no control
- Fsync() once every “n” seconds – The suggested and default policy is every second. This is quite fast and sage. In case of disaster, you can lose 1 second of data.
When using Redis as data store, application level sharding can be done – different users or different kind of objects can be placed in different Redis instances.