Reducing Space Usage in Redis for UUIDs

One of the primary concerns when setting up a data store is figuring out how much space it will need to cover your use case, relatedly how it will perform on datasets of the sizes you expect, and when you will need consider engaging advanced features like sharding to handle your load. With this in mind, I was thinking about how to spec a system the other day for storing large amounts of data in Redis, keyed for the most part by UUID. Most of the values associated with these keys were either UUIDs as well, or relatively tiny data types like booleans and integers. Given these aspects of the intended system, and combined with the standard practice of storing data in Redis as UTF-8 strings, it was immediately apparent to me that there were some easy gains to be had.

How to turn 36 bytes into 16

The data type of Redis keys is binary-safe string, so the majority of libraries simply execute toString() or whatever your language equivalent is on your key and call it a day. It occurred to me that the majority of the space this data store occupied would be taken up by these string-encoded UUIDs, which has this canonical form:

de305d54-75b4-431b-adb2-eb6b9e546014

As a UTF-8 string, this form will take up one byte per character or 36 bytes, 32 for informational characters and 4 for dashes. What a waste! A UUID is simply a 16 octet (16 byte) integer. The maximum value of this number is 2^128:

340282366920938463463374607431768211456

As a UTF-8 string, this would be 39 bytes. Not only is that worse than 36 bytes, it's pretty close to the average case integer representation (2^128/2). But! Who says we have to represent this as a human-readable string of bytes? If we represent the UUID as a byte array, it is of course only 16 bytes:

��£¬¾ý�ȹɀɱ��ʜͶϋ͍

Boom. We just reduced our data store size on the order of 50%. It's not going to be as good as 16/36 = 55% reduction because there's overhead for every KV pair and there's potentially some other data stored (boolean, int, etc.), but that's still a huge win. Now my single instance of Redis can last me twice as long (assuming a linear growth curve) before I need to worry about sharding, etc. Normally I wouldn't recommend relying on anything less than an order magnitude gain for an architectural decision, but this is really just a thought experiment :)

Are you crazy?

Obviously this does have some drawbacks. If I'm debugging some production issue and the logs say there's a problem with ID xxx-xx-xx, I can't just fire up redis-cli and get the value of $keyPrefix-xxx-xx-xx. I'm going to have to use some custom tooling to convert my logged ID to a byte array, add my prefix and run the command I want against that. This is a non-trivial cost, but for a use-case in which the primary data stored is UUIDs we're talking about a ~55% reduction in space (16/36 bytes). If I can support a userbase & dataset that is more than twice as large on the same hardware I consider that a win, especially since the primary limiting factor in most projects is IO bottlenecking. That said, I probably wouldn't do this in the real world because the value of being able to debug quickly and get other developers up-to-speed quickly usually exceeds the value of performance gains less than 10x.

Let's go further

Alright so we've already established that I'm crazy. How far can we take it? There's one other obvious target for reducing wasted space in Redis KV pairs - the key prefix. Normally we namespace keys to keep them from colliding, so we might have some keys that look like (assuming non-binary UUIDs):

     standardUser-de305d54-75b4-431b-adb2-eb6b9e546014
groupNotification-de305d54-75b4-431b-adb2-eb6b9e546015
   messageContent-de305d54-75b4-431b-adb2-eb6b9e546016

For these keys we're using about 16 bytes each for the function of namespacing. With 16 bytes we could represent 2^128 namespaces! (Conveniently the same size as a UUID :) How many namespaces do we really need for keys? 256? 65536? Let's go with that. 2 bytes as a byte array gives us our 65k prefixes. We store these in an enum somewhere in the common lib for our project and bingo, we have a way to reference our keys 77.5% more space efficiently:

�¬-de305d54-75b4-431b-adb2-eb6b9e546015
ɱ�-de305d54-75b4-431b-adb2-eb6b9e546015
�Ͷ-de305d54-75b4-431b-adb2-eb6b9e546015

When we combine the two approaches together, we turn an average key length of 16 + 1 + 36 = 53 bytes into 2 + 1 + 16 = 19 bytes, for an average savings of 64%. Awesome:

�¬-��£¬¾ý�ȹɀɱ��ʜͶϋ͍
ɱ�-��£¬¾ý�ȹɀɱ��ʜͶϋ͍
�Ͷ-��£¬¾ý�ȹɀɱ��ʜͶϋ͍

Yea, this is crazy

If you go take a gander at the Redis intro to data types, it mentions the following about best practices for keys:

"Very short keys are often not a good idea. There is little point in writing "u1000flw" as a key if you can instead write "user:1000:followers". The latter is more readable and the added space is minor compared to the space used by the key object itself and the value object. While short keys will obviously consume a bit less memory, your job is to find the right balance."

Bah humbug. As much as I hate to admit it, this is right, the grist just isn't worth the grind. You win this time antirez!

That said - in my next post I'm still going to implement an extension to Scredis to do this anyway, just for kicks.

Extending Scredis, a Scala Redis Client, to Write Binary Keys

In my last post I discussed the possibility of reducing Redis key space usage for UUID-based keys by storing them as byte arrays, along with converting key namespacing from human readable strings to integers as well. The conclusion of that post was that is a bad idea(tm), but I'm going to do it anyway. For TL;DR, show me the code, see the pull request.

The Current Scredis interface

Creating and modifying keys with Scredis is wonderfully simple and easy. It looks like this:

package scredis.commands

import org.scalatest._
import org.scalatest.concurrent._
import scredis._
import scredis.protocol.requests.StringRequests._
import scredis.util.TestUtils._

class BlogExampleSpec extends WordSpec
  with GivenWhenThen
  with BeforeAndAfterAll
  with Matchers
  with ScalaFutures {

  private val client = Client()
  private val SomeKey = "someKey"
  private val SomeValue = "HelloWorld!虫àéç蟲"

  Set.toString when {
    "setting a key that does not exist" should {
      "succeed" in {
        client.set(SomeKey, SomeValue)
        client.get(SomeKey).futureValue should contain(SomeValue)
      }
    }
  }

}

Ok great. Let's take that a step further and figure out how to write our UUID values as byte arrays rather than UTF-8 strings. To do that we will implement a Scredis Reader and Writer for the java.util.UUID type:

package scredis.commands

import java.nio.ByteBuffer
import java.util.UUID

import org.scalatest._
import org.scalatest.concurrent._
import scredis._
import scredis.protocol.requests.StringRequests._
import scredis.serialization.{Reader, Writer}
import scredis.util.TestUtils._

class BlogExampleSpec extends WordSpec
  with GivenWhenThen
  with BeforeAndAfterAll
  with Matchers
  with ScalaFutures {

  private val client = Client()
  private val SomeKey = UUID.randomUUID()
  private val SomeValue = UUID.randomUUID()

  implicit val uuidReader = new Reader[UUID] {
    protected def readImpl(bytes: Array[Byte]): UUID =
    bytes.length == 16 match {
      case false => null
      case true =>
        var msb = 0L
        var lsb = 0L
        for (i <- 0 until 8) {
          msb = (msb << 8) | (bytes(i) & 0xff)
        }
        for (i <- 8 until 16) {
          lsb = (lsb << 8) | (bytes(i) & 0xff)
        }
        new UUID(msb, lsb)
    }
  }

  implicit val uuidWriter = new Writer[UUID] {
    protected def writeImpl(value: UUID): Array[Byte] = {
      val bb = ByteBuffer.wrap(new Array[Byte](16))
      bb.putLong(value.getMostSignificantBits)
      bb.putLong(value.getLeastSignificantBits)
      bb.array()
    }
  }

  Set.toString when {
    "setting a key that does not exist" should {
      "succeed" in {
        client.set(SomeKey.toString, SomeValue)
        client.get[UUID](SomeKey.toString).futureValue should contain(SomeValue)
      }
    }
  }

}

Pretty cool, we just got our 36 byte UUID value down to a length 16 byte array. However, our goal was to have both UUID-based keys and values. In order to do that we have to update Scredis to allow the concept of Readers and Writers for keys, the same as we do for values. That's actually a pretty big interface change so I can't paste it all here, but you can review the PR to see how it's done. As an example, here's how the interface of the set command changed:

  def set[W: Writer](
    key: String,
    value: W,
    ttlOpt: Option[FiniteDuration] = None,
    conditionOpt: Option[scredis.Condition] = None
  ): Future[Boolean]

becomes:

  def set[K: Writer, W: Writer](
    key: K,
    value: W,
    ttlOpt: Option[FiniteDuration] = None,
    conditionOpt: Option[scredis.Condition] = None
  ): Future[Boolean]

Now that we have our handy new key writer interface, we can come back to our test spec and make our UUID-key the way we want to:

  Set.toString when {
    "setting a key that does not exist" should {
      "succeed" in {
        client.set(SomeKey, SomeValue)
        client.get[UUID, UUID](SomeKey).futureValue should contain(SomeValue)
      }
    }
  }

Sweet. Now we're properly encoded on both sides of the KV pair and we've shaved off 40 bytes from our original 72 bytes worth of data. The only thing left to do would be to add a binary namespace to our key, but I'll leave that to your imagination. Please, don't do this at home kids. As discussed in the previous post, the maintainability and debugability of your data store is not worth sacrificing for a few extra bytes :)