Tag Archives: NoSQL

Redis data sharding – part 1

In one of my previous posts on Redis i provided a definition of data sharding, quoting a great book “Redis in Action” authored by Dr. Josiah L Carlson:

  • “Sharding is a method by which you partition your data into different pieces. In this case, you partition your data based on IDs embedded in the keys, based on the hash of keys, or some combination of the two. Through partitioning your data, you can store and fetch the data from multiple machines, which can allow a linear scaling in performance for certain problem domains.”

 

Today i’d like to elaborate some more on data sharding based on IDs embedded in the keys.

 

Let’s start with an example of a hypothetical data stored in an Redis instance:

redis 127.0.0.1:6379>keys *
(empty list or set)
redis 127.0.0.1:6379>set emails:1 me@mariuszprzydatek.com
OK
redis 127.0.0.1:6379>get emails:1
"me@mariuszprzydatek.com"

what i did here is to use the basic String data type to store an email of a user. As you can see, i embedded user id within the key (’emails:1′). Now, if a front-end application would ask for an email address of a user with id=1, on the back-end side i would concatenate the keyword which i usually use to denote keys i store emails under (ie. ’emails’) with the id of a user (‘1’), add a colon (‘:’) in between, and this way i’ll get the resulting key (’emails:1′) i should look after while making a call to the Redis instance.

 

This solution is nice but if i’ll have 1 million of users registered in my system and use Redis as the data store for keeping mappings between identifier of a user and his email, i will end up with 1 million keys (’emails:1′, ’emails:2′, ’emails:3′, etc.). This is a volume my Redis instance will easily handle (see my previous post on Redis Performance Basics) and it will use little more than 190MB to store everything in the memory (so much due to a lot of overhead when storing small keys and values; the ratio is much better with large keys/values), but this is only one attribute we’re talking about – and what about firstName, lastName, etc.?. Obviously, if my system will have millions of registered users and i’d use Redis as my primary data store for users-related info, i would be running multiple instances of Redis already and based on the id of a user, route the queries to a specific instance, but there’s still a lot we can do to optimize costs prior to thinking about scaling.

 

Small code snippet to generate 1M of emails stored in Redis using String data structure (and Spring Data Redis mentioned in my other post).

int i = 0;
while(i<1000000) {
    redisTemplate.opsForValue().set(String.format("emails:%s", i++), "me@mariuszprzydatek.com");
}

the loop above executes in 2 mins on my Windows 8 64bit i7 laptop and the ‘redis-server’ process allocates ca 190 MB of memory.

 

Now, what will happen if we change the data structure let’s say to a Redis Hash?

Next code snippet and we’re getting just that:

int i = 0;
while(i<1000000) {
    String userId = String.valueOf(i++);
    String emailAddress = String.format("user_%s@mariuszprzydatek.com", userId);
    redisTemplate.opsForHash().put("emails", emailAddress, userId)
}

2 mins and 165 MB of memory allocated – a 15 % gain absolutely for free.

 

Let’s try with data sharding/partitioning. Another code snippet using Redis Hash data structure and there you go:

int shardSize = 1024;
int i = 0;
while(i<1000000) {
    int shardKey = i/shardSize;
    String userId = String.valueOf(i++);
    String emailAddress = String.format("user_%s@mariuszprzydatek.com", userId);
    redisTemplate.opsForHash().put(String.format("emailsbucket:%s", shardKey), emailAddress, userId);
}

2 mins later and… only 30 MB allocated – now you’re talking Mariusz!

Staggering 530 % increase in memory allocation efficiency!

 

Hope you enjoyed the first part of this brief tutorial.

 

Cheers!

 

 

Resources:

Advertisement

Spring Data Redis overview

If you are, like me, a great fan of the Spring Framework, you probably know already the Spring Data product and corresponding spring-data-redis module. If not, let me introduce this wonderful tool in this brief post.

 

Spring Data Redis offers the following features (copied from the product homepage):

  • Connection package as low-level abstraction across multiple Redis drivers/connectors (Jedis,  JRedisLettuceSRP and RJC)
  • Exception translation to Spring’s portable Data Access exception hierarchy for Redis driver exceptions
  • RedisTemplate that provides a high level abstraction for performing various redis operations, exception translation and serialization support
  • Pubsub support (such as a MessageListenerContainer for message-driven POJOs)
  • JDK, String, JSON and Spring Object/XML mapping serializers
  • JDK Collection implementations on top of Redis
  • Atomic counter support classes
  • Sorting and Pipelining functionality
  • Dedicated support for SORT, SORT/GET pattern and returned bulk values
  • Redis implementation for Spring 3.1 cache abstraction

 

As of the time of writing this post, the latest product release is labeled ‘1.0.6.RELEASE’, and available as a Maven dependency:

<dependency>
    <groupId>org.springframework.data</groupId>
    <artifactId>spring-data-redis</artifactId>
    <version>1.0.6.RELEASE</version>
</dependency>

 

Using Spring Data Redis in your project is as easy as defining the above dependency in your master pom.xml file, and configuring the RedisTemplate bean in either xml context file (example below) or using Java configuration:

    <context:property-placeholder location="classpath:redis.properties"/>

    <bean id="connectionFactory"
          class="org.springframework.data.redis.connection.jedis.JedisConnectionFactory"
          p:hostName="${redis.host}"
          p:port="${redis.port}"
          p:password="${redis.pass}"
          p:usePool="${redis.pool}" />

    <bean id="stringRedisSerializer" class="org.springframework.data.redis.serializer.StringRedisSerializer" />

    <bean id="redisTemplate" class="org.springframework.data.redis.core.RedisTemplate"
          p:connectionFactory-ref="connectionFactory"
          p:defaultSerializer-ref="stringRedisSerializer" />

 

and the corresponding redis.config file:

# Redis settings
redis.host=localhost
redis.port=6379
redis.pass=
redis.pool=true

 

…in code you’re using the RedisTemplate like this:

@Autowired
private RedisTemplate redisTemplate;

    public void saveEmail(String email, long userId) {
        redisTemplate.opsForHash().put("emails", String.valueOf(userId), email);
    }

 

I did also i quick overview of the extend to which Redis native API commands, related to performing operations on 5 basic Redis data types, have been implemented in the product. Below you’ll find a short visual summary:

 

  • Strings

Spring Data Redis String

 

 

  • Lists

Spring Data Redis List

 

 

  • Sets

Spring Data Redis Set

 

 

  • Hashes

Spring Data Redis Hash

 

 

  • ZSets

Spring Data Redis ZSet

 

 

Cheers!

 

 

 

Resources:

Redis performance basics

I wish i knew the below when starting my adventure with Redis…

 

General notes:

  • advantage of a in-memory database like Redis is that the memory representation of complex data structure is much simpler to manipulate compared to the same data structure on disk.
  • At the same time Redis’ on-disk data format does not need to be suitable for random access and therefore is compact and always generated in an append-only fashion
  • 1 Million keys with the key being the natural numbers from 0 to 999999 and the string “Hello World” as value use 100MB on a 32bit computer. The same data stored linearly in an unique string takes something like 16MB and this is because with small keys and values in Redis there is a lot of overhead. With large keys/values the ratio is much better.
  • 64 bit systems will use considerably more memory than 32 bit systems to store the same keys, especially if the keys and values are small, this is because pointers takes 8 bytes in 64 bit systems. But of course the advantage is that 64 bit systems can address/have a lot more of memory, so in order to run large Redis servers a 64 bit system is more or less required
  • because Redis stores everything in memory you cannot obviously have a dataset larger than the memory of your server. But Redis users like Craigslist and Groupon are distributing their data among multiple Redis nodes, using client-side hashing which can be an effective solution.
  • client libraries such Redis-rb (the Ruby client) and Predis (one of the most used PHP clients) are able to handle multiple Redis servers automatically using consistent hashing.
  • if you don’t want to use consistent hashing or data distribution across different nodes, you can consider using Redis as a secondary data store (metadata, small but often written info and all the other things that get accessed very frequently: user auth tokens, Redis Lists with chronologically ordered IDs of the last N-comments, N-posts, etc.).
  • Write scripts that will monitor your Redis servers (checking for critical conditions) using the INFO command that reports the memory utilization
  • Redis on-disk-snapshots are atomic – Redis background saving process is always fork(2)ed when the server is outside of the execution of a command, so every command reported to be atomic in RAM is also atomic from the point of view of the disk snapshot.
  • Although Redis is single threaded it’s very unlikely that CPU becomes a bottleneck, this is because Redis usually either memory or network bound. For example using pipelining Redis running on an average Linux system can deliver even 500k requests per second, so if an application mainly uses O(N) or O(log(N)) commands it is hardly going to use too much CPU. However, you can maximize CPU usage by starting multiple instances of Redis in the same box and treat them as different servers.
  • maximum number of keys a single Redis instance can hold is in theory up to 232. Redis was tested in practice to handle at least 250 million of keys per instance.
  • Every list, set, and sorted set, can hold in theory 232 – 1 (4294967295, more than 4 billion) elements as well.

 

Keys:

  • are binary safe (ie. you can use any binary sequence as a key, including empty string)
  • too long keys (eg. 1kB) are a bad idea, both memory-wise as well as because the lookup of the key in the dataset may require several costly key-comparisons
  • the shorter the key the less memory it’ll consume, however it’s negligible compared to to the space used by the key object itself and the value object. Therefore go with human readable keys (eg. password:789 instead of p:789)
  • stick with a naming convention, eg. object-type:id:field or comment:1234:reply.to, etc.

 

Data structures:

  • Strings:
    • values can’t be bigger than 512 MB.
    • Keys can be anything including binary mp3
    • the INCR command parses the string as an integer, increments by one, and creates a new string
    • other related commands (INCRBY, DECR, DECRBY) all use internally INCR
    • INCR is atomic – multiple clients issuing INCR against the same key will never incur into a race condition
  • Hashes:
    • maps between string fields and string values (therefore a perfect data type to represent objects)
    • Hashes are encoded using a memory efficient data structure when they have a small number of entries, and the biggest entry does not exceed a given threshold. These thresholds can be configured in /redis.conf file with following directives:
      • hash-max-ziplist-entries (default value 512)
      • hash-max-ziplist-value (default value 64)
  • Lists:
    • are implemented via Linked Lists (not via Arrays)
    • in case of a list containing millions of elements, adding a new element in the head or in the tail of the list is still performed in constant time O(1)
    • main feature of lists from the point of time complexity is the support for constant time insertion and deletion of (even many millions) elements near the head and tail. Accessing elements is very fast near the extremes of the list but is slow if you try accessing the middle of a very big list, as it is an O(N) operation.
    • Accessing an element by index is not so fast in lists implemented by linked lists (Arrays are better in this case)
    • with LRANGE you can easily paginate results (constant length in constant time)
    • putting objects inside lists isn’t a good idea as you often need to access those objects and given that Redis is using Linked Lists as the underlying impl, it’s not efficient.
    • Lists are sortable
    • Similarly to hashes, small lists are also encoded in a special way in order to save a lot of space. The special representation is only used when you are under the following limits:
      • list-max-ziplist-entries 512
      • list-max-ziplist-value 64
  • Sets:
    • unordered collection of binary-safe strings
    • adding the same element multiple times will result in a set having a single copy of this element
    • are very good for expressing relations between objects (eg. to implement “tags”)
    • Sets are sortable
    • Sets have a special encoding in /redis.config in just one case: when a set is composed of just strings that happens to be integers in radix 10 in the range of 64 bit signed integers. The following configuration setting sets the limit in the size of the set in order to use this special memory saving encoding.
      • set-max-intset-entries 512
  • ZSets
    • sorted Sets are similar to Sets, collections of binary-safe strings, but this time with an associated score throughout the use of which you’re getting “sorting capabilities”
    • you can think of ZSet as of a equivalent of an Index in the SQL world
    • they are implemented via a dual-ported data structure containing both a skip list and a hash table, so every time you add an element Redis performs an O(log(N)) operation
    • ZSets have a “default” ordering but you are still free to call the SORT command against sorted sets to get a different ordering (but in this case the server will waste CPU). Solution for having multiple orders is to add every element in multiple sorted sets simultaneously.
    • calling again ZADD against an element already included in the sorted set will update its score (and position) in O(log(N)), so sorted sets are suitable even when there are tons of updates
    • Similarly to hashes and lists, sorted sets are also specially encoded in order to save a lot of space. This encoding is only used when the length and elements of a sorted set are below the following limits:
      • zset-max-ziplist-entries 128
      • zset-max-ziplist-value 64

 

 

Resources: