Building a distributed eventually consistent key-value store with DNS and Elixir

"Hello. I'm Dr. Sheldon Cooper, and welcome to Sheldon Cooper presents: Fun with Flags."

While vexillology may attract some people, here at DNSimple we deal a lot with, as you might guess, DNS. That's why I wanted to share a little thought experiment I did recently:

Fun with DNS: DNS as a distributed, eventually consistent, key-value store

DNS has certain strengths: availability, partition tolerance, and performance, that we strive for almost all systems we build nowadays. Two of these might sound familiar if you know about the CAP theorem already. The theorem essentially states that you can only always have two of the following three attributes for any persistent datastore:

• Consistency (Every read receives the most recent write or an error)
• Availability (Every request receives a (non-error) response – without guarantee that it contains the most recent write)
• Partition tolerance (The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes)

Let's prove that you can use DNS as a distributed, eventually consistent, key-value store. As I'm a big fan of Elixir, let's spike this idea using our new API v2 and the official Elixir API client.

Security concerns

DNS is an open system. No information within the Domain Name Service is confidential; you can query any record from any DNS server resolver and get an answer.

When we want to build a datastore facilitating DNS, we need to make sure to not disclose the data in our database, or to only disclose information that is considered public.

The idea - meet DNStore

How would a DNS based key-value store look like?

My first idea was to store everything in a big JSON blob in a TXT record. But the length of TXT records is limited, and this approach would lead to prolonged update times.

The next approach would be to have one TXT record per key. But I do not want to expose all my keys to the public. To achieve this and a consistent key lookup, hashing the keys and using them as the host for the record will do the job.

Encrypting data in Elixir

As stated above we do not want to disclose any information about the values we store in the system. But hashing would not work here because we need the values in the system as well. Encrypting the data instead would give us exactly that, for one the public would not be able to decrypt the values and to access them in DNStore you would only need the shared secret.

For Elixir I found Cipher, a handy library wrapping Erlang's :crypto module. After you configure it in your config.exs:

config :cipher, keyphrase: "testiekeyphraseforcipher",
                ivphrase: "testieivphraseforcipher",
                magic_token: "magictoken"

Using it is as easy as:

"secret"
|> Cipher.encrypt  # "KSHHdx0uyveYGY5PHqLAKw%3D%3D"
|> Cipher.decrypt  # "secret"

Part 1: Write to DNStore

The next part to make DNStore happen is to write into a zone at DNSimple. We use the DNSimple Elixir API client to do this.

def set(key, value) do
  # Setup the client and read configuration
  client = %Dnsimple.Client{access_token: Application.get_env(:dnstore, :token)}
  account = Application.get_env(:dnstore, :account_id)

  Dnsimple.Zones.create_zone_record(client, account, "dnstore.cloud", %{
    name: keyify(key),
    type: "TXT",
    content: Cipher.encrypt(value),
    ttl: 60
  })
end

The private helper function keyify essentially hashes the key, makes it a readable string, and cuts of the first nine characters. This is done because there is a certain limit in domain name length.

defp keyify(key) do
  :crypto.hash(:sha256, key)
  |> Base.encode16
  |> String.downcase
  |> String.slice(0..8)
end

Let's run this first part and see what it looks like:

$ iex -S mix
iex(1)> Dnstore.set("avocado", "Frozen paella rocks!")

15:09:34.008 [debug] [dnsimple] POST https://api.dnsimple.com/v2/12437/zones/dnstore.cloud/records
{:ok,
 %Dnsimple.Response{data: %Dnsimple.ZoneRecord{content: "4SYp5vCEGXAJiBFaSXig0frooZiUyIsrk7DnVRCumt4%3D",
   created_at: "2017-11-15T14:09:34Z", id: 12721184, name: "f9c9baac9",
   parent_id: nil, priority: nil, regions: ["global"], system_record: false,
   ttl: 60, type: "TXT", updated_at: "2017-11-15T14:09:34Z",
   zone_id: "dnstore.cloud"},
  http_response: %HTTPoison.Response{...},
   headers: [...], status_code: 201},
  pagination: nil, rate_limit: 200, rate_limit_remaining: 100,
  rate_limit_reset: 1510757283}}

We can verify that this worked by querying Google's public DNS resolver using dig:

$ dig TXT @8.8.8.8 f9c9baac9.dnstore.cloud +short
"4SYp5vCEGXAJiBFaSXig0frooZiUyIsrk7DnVRCumt4%3D"

Part 2: Read from DNStore

Now that the value was successfully written let's add the pieces to read the value from DNStore again. We need to make sure to use the same key hashing function to generate the key we want to retrieve.

In this case, we could also use the DNSimple API to retrieve the value again, but I think that misses the point because we want to prove that we can use the public DNS system to store and retrieve values. That is why we use the Erlang built-in :inet_res module.

As you know dealing with Erlang is a bit clunky sometimes, that is why we have a bit to String <=> Charlist conversion in the code.

Last but not least we need to decrypt the value from the TXT record using the shared secret.

def get(key) do
  "#{keyify(key)}.dnstore.cloud"
  |> String.to_charlist
  |> :inet_res.lookup(:in, :txt) # => [[ 'value' ]]
  |> List.flatten # => [ 'value' ]
  |> List.first # => 'value'
  |> to_string # => "value"
  |> Cipher.decrypt
end

Let's see how this looks in action:

$ iex -S mix
iex(1)> Dnstore.get("avocado")
"Frozen paella rocks!"

Yippie! It works (like we expected)!

Wrap up and closing remarks

I claim that this experiment was a success. In case you are curious you can find the source code of DNStore on GitHub.

DISCLAIMER: DNS is not meant to be used in that way, and with how caching works, doing this may get you into situations where DNStore is inconsistent a lot of times. Also, the content length for TXT is limited and depending on your DNS provider long list of records on a single zone may cause problems.

This approach is not completely new; for example in DNS-Based Service Discovery (RFC 6763) TXT records are used for service discovery.

If you have an awesome idea what else you could do with DNS, I want to invite you to check out our API and all the different official API clients, like: Ruby, Go, Elixir, Node.js, and Java.

Built something great? We would LOVE to hear about it! Write to @dnsimple on Twitter or contact us.

Share on Twitter and Facebook

Ole Michaelis

Conference junkie, user groupie and boardgame geek also knows how to juggle. Oh, and software.