System Design goal: efficient property reads from multiple sources
Tags: systemdesign, java, threadsafe, datastructures
Published: 2021-09-09 09:04:48

---
title: System Design goal: efficient property reads from multiple sources
published: true
date: 2021-09-06 00:00:00 UTC
tags: SystemDesign,Java,ThreadSafe,DataStructures
cover_image: https://unsplash.com/photos/SpCrTUG2nu8/download?force=true&w=2400
canonical_url: https://MihaiBojin.com/application-settings/system-design/read-key-from-multiple-sources
---

🔔 This article was originally posted on my site, [MihaiBojin.com](https://MihaiBojin.com/application-settings/system-design/read-key-from-multiple-sources?utm_source=DevTo&utm_medium=organic&utm_campaign=top-promo "MihaiBojin.com").  Since it contains a few diagrams, it cannot be correctly displayed on DevTo.  I highly recommend reading it on [my site!](https://MihaiBojin.com/application-settings/system-design/read-key-from-multiple-sources?utm_source=DevTo&utm_medium=organic&utm_campaign=top-promo) 🔔

* * *

## [<svg aria-hidden="true" focusable="false" height="16" version="1.1" viewbox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg>](#a-problem-of-ownership)A problem of ownership

I set out to build the [props](https://github.com/props-sh/props) library to standardize retrieving `(key,value)` pairs from multiple _sources_ while also allowing a simple mechanism to establish _key_ precedence when more than one source is aware of the same key.

Let's consider the following scenario, where multiple _source_s define _property X_:

| Source (Layer) | Value |
| --- | --- |
| Prop X is defined by source 1 | 1 |
| Prop X is defined by source 3 | 2 |
| Prop X is defined by source 4 | 3 |
| **Effective value** | **3** |

Sources can be property files, system properties, or they can be coming from a key-value store or database.

Since each _(key,value)_ pair can change independently on each source, we need to establish a key's precedence, basically answering the **"Who provides the value for this key?"** question.

We do so by introducing the concept of **layers.**

Each added layer can retrieve data from a source. As we add more layers, each takes precedence over the previous layer, for any keys it defines.

We call this concept **ownership.**

* * *

## [<svg aria-hidden="true" focusable="false" height="16" version="1.1" viewbox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg>](#sources-vs-layers)Sources vs. layers

Let's think for a moment about sources and layers.

A naïve approach would be to model a 1:1 relationship between Sources and Layers, basically creating a single entity to represent both, then passing a list of these entities to a _registry_.

We see that both sources point to the _same file on disk_. However, we have two objects that independently read the same data and create a potential for contention and consistency problems (e.g., SourceLayer 1 reads data, the file is updated on disk, SourceLayer2 reads different data).

Consistency is not always possible and cannot always be a property of a system, but in this case, we can ensure that a _source_ has the same view of its data in a running JVM process.

Rather than have _source_s and _layer_s be the same (1:1), let's instead have a single _source_ representing a dataset and multiple _layers_ (1:N) which receive updates when the dataset changes. An added benefit of this design is that our system only needs to do **one read operation per dataset** instead of _one per layer_. Since I/O is generally more "expensive" than in-memory operations, **this is a win!**

Here are the components of our system:

- `Source`: loads the data from its origin (e.g., filesystem), reloads it using user-defined logic (e.g., an interval), and notifies registered layers of any reload events
- `Layer`: holds copies of the data for each registry
- `Registry`: queries data from each of its layers

## [<svg aria-hidden="true" focusable="false" height="16" version="1.1" viewbox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg>](#retrieving-the-effective-value)Retrieving the effective value

But what if a layer adds a new key or removes an existing one!?

Between two reads of _X_, the owner could change from Layer 3 to Layer 2.

A simple algorithm to solve this problem is always to query all layers, e.g.:

- ask Layer 1-3: Do you define _X_?
- Layers 2 and 3 respond _yes_
- Layer 3 has precedence and _owns_ the key
- X is unset from Layer 3
- we repeat the first three steps and establish Layer 2 as the _owner of X_

This choice is not ideal. First, we'd have to repeat this **on every read** , which would result in `O(K)` time-complexity (where K is the number of layers in the registry) for every single read property. This doesn't sound performant!

A side objective here is to deal with a high frequency of ownership changes; for example, a source dataset may repeatedly set and unset one or more keys in a short interval.

## [<svg aria-hidden="true" focusable="false" height="16" version="1.1" viewbox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg>](#type-casting-values)Type casting values

Before we talk about ownership, let's quickly segue into data types. The values will always be serialized as strings as we're reading them from property files, system properties, and the environment. (The library will support loading values from other data stores, e.g., databases, but the problem of casting strings from property files remains)

Here's an example of a standard Java property file:

```
string.prop=some value
int.prop=42
float.prop=1.23
```

Even though we have integer and float values, the relevant Java APIs will still return a `Map<String,String>`, leaving the job of casting these values to the appropriate types to the developer.

In practice, while developers "come and go" in projects, this results in many ways to, not-so-optimally, load strings and repeatedly convert them to the desired type.

When I set out to build the `props` library, I wanted to give developers "one" way of loading the values corresponding to each key without worrying about types, simple validations, or caching. My goal is to implement a no-hassle, efficient library for dealing with application properties!

## [<svg aria-hidden="true" focusable="false" height="16" version="1.1" viewbox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg>](#how-do-we-establish-key-ownership)How do we establish key ownership?

Ok, back to ownership!

The registry needs to keep track of a large enough number of keys (let's say in the 10,000s range), and retrieve values from the appropriate layer.

Developers will be able to rely on a **registry** to retrieve values cast to their desired type.

Let's examine the internals of a `get(key, type)` call.

A client queries the registry (1), which in turn checks all its layers (2), awaiting responses (3), then determining the _owner_ and returning the _effective value_ to the client (4).

In practical applications, we can assume a _registry_ will have a few layers (`K`).

If our application handles `N` properties (keys), then reading all the properties at least once would be an `O(N*K)` operation. Given that ultimately a key is _owned_ by a single layer, the best we can hope for is `O(N)` for N keys, or `O(1)`, constant time, per key.

This time-complexity is not only more efficient but also totally achievable!

* * *

Internally, the _registry_ needs to keep track of which layers own each key.

Since layers can be updated concurrently, we need a thread-safe data structure.

Since we need to _"map"_ (pun intended) keys to layers, we need to use a `Map` (duh!)

The Java SDK provides a very efficient, thread-safe map: [ConcurrentHashMap](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/ConcurrentHashMap.html).

Let's see how this could look in code:

```java
public class Registry {
    ConcurrentHashMap<String, Layer> owners;

    // retrieves the value for the specified key
    public <T> T get(String key, Class<T> clz) {
        // finds the owner
        Layer owner = owners.get(key);
        // retrieves the value
        String effectiveValue = owner.get(key);
        // casts it
        return clz.cast(effectiveValue);
    }
}

public interface Layer{
    // retrieves the value for the specified key, from this layer alone
    String get(String key);
}
```

The last piece of the puzzle is updating ownership. Below, we examine the _new key_ case.

```java
public class Source{
    List<Layer> layers;

    // reloads data periodically, at the specified interval
    void reload(Duration interval) {
        // the trigger will be periodically scheduled at an interval
        var trigger = () -> {
            // data is reloaded from source
            Map<String, String> data = ...;

            // and then sent to all registered layers for this source
            for (Layer layer : layers) {
                layer.onReload(data);
            }

            // we may also want a sync stage here
            // to make the new dataset available to all sources at the same time
            // but it's beyond the scope, for the moment
        }
    }
}

public class Layer{
    // processes the reloaded data
    public void onReload(Map<String, String> data) {
        // for each key in the dataset
        for (var entry : data.entrySet()) {
            // updates the value
            updateValue(entry.getKey(), entry.getValue());
            // and notifies the registry that a new owner might be available
            registry().bindKey(entry.getKey(), this);
        }
    }

    // decides the priority of this layer, in the current registry
    int priority();

    // reference to the registry that owns this layer
    abstract Registry registry();
    
    // stores the (key,value) pair
    abstract void updateValue(String key, String value);
}

public class Registry {
    ConcurrentHashMap<String, Layer> owners;

    // registers ownership of a layer over a key
    void bindKey(String key, Layer layer) {
        // finds the current owner
        Layer owner = owners.get(key);
        
        // determines if ownership change is required
        if (owner.priority() < layer.priority()) {
            // change the current owner
            owners.put(key, layer);

            // from this point, all "get"s of "key" will be routed to "layer"
        }
    }
}
```

The scenario above details how the system will handle new keys appearing in a layer.

A full implementation also needs to consider _deleted keys_ and _updated keys_. For those cases, we'd want to avoid calling `registry().bindKey(...)` since it would result in a no-op anyway.

* * *

Overall, I am willing to bet that ownership changes will be less frequent than value changes in real-world scenarios. So, the upfront cost of _adding_ and _deleting_ keys, represented by registering and unregistering keys from a layer, will be worth it to achieve constant time (`O(1)`) reads per key.

## [<svg aria-hidden="true" focusable="false" height="16" version="1.1" viewbox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg>](#conclusion)Conclusion

At this point, **I am genuinely excited to implement this code!**

I'm sure I will learn more as I go along and may change my mind on some of these choices, but this is the plan for now!

Until next time...

* * *

If you liked this article and want to read more like it, [please subscribe to my newsletter](https://motivated-founder-807.ck.page/db1cf284bf "newsletter link"); I send one out every few weeks!