An update on efficient multi-layered key ownership
Tags: algorithms, ownership, concurrency, isolationlevel
Published: 2021-09-21 14:11:13

---
title: An update on efficient multi-layered key ownership
published: true
date: 2021-09-21 00:00:00 UTC
tags: Algorithms,Ownership,Concurrency,IsolationLevel
cover_image: https://unsplash.com/photos/pY_AZJfdbHQ/download?force=true&w=1920
canonical_url: https://MihaiBojin.com/application-settings/system-design/algorithms-for-effective-key-ownership
series: Designing a library for reading application settings in Java
---

🔔 This article was originally posted on my site, [MihaiBojin.com](https://MihaiBojin.com/application-settings/system-design/algorithms-for-effective-key-ownership?utm_source=DevTo&utm_medium=organic&utm_campaign=top-promo "MihaiBojin.com"). 🔔

* * *

In the [previous article](https://mihaibojin.com/application-settings/system-design/read-key-from-multiple-sources#how-do-we-establish-key-ownership?utm_source=DevTo&utm_medium=organic&utm_campaign=rss), I introduced the concept of _key ownership_.

[Props](https://github.com/props-sh/props) is a library that allows users to load settings from multiple sources, layering them in a predetermined order.

Given two sources (i.e., layers) added to the Props registry in order, if both define a key (`X`), the second one wins (we say _owns_) the key and will provide its value, which we call an _effective value_.

My original design was to keep a map of keys to values for each _Layer_ and further have the _Registry_ keep a synchronized map of keys to layers, enabling it to determine which _Layer_ owns a _Key_ and then query it to retrieve its effective value.

As I was implementing this algorithm, I realized it was allowing a race condition that would require a severe decrease in throughput to fix.

Imagine the following scenario:

- given that both Layers 1 and 2 define values for X
- when the client requests X
- then the registry determines Layer 2 owns X
- however, before retrieving a value, Layer 2's source updates itself and unsets X
- in this scenario, the client will receive a wrong response (`X=null`) instead of the correct value from Layer 1

This situation is similar to a [dirty read](https://en.wikipedia.org/wiki/Isolation_(database_systems)#Dirty_reads) in a transactional database system.

To prevent this edge case, **we'd need a global, per-key lock** to ensure that the _Layer_ that owns _X_ cannot unset it during a `get(X)` call.

Since this would play out over multiple objects (_Registry_ and _Layer_) and data structures (`Map<Key, Layer>`, `Map<Key,Value>`), we would need another data structure to indicate that `Key` is currently being retrieved.

When any layer is updated, we'd check this map and ensure we only update `X` when it is not being read. **In high QPS applications, this would quickly become a bottleneck!**

There are ways to optimize this flow, but ultimately I realized that this design was flawed.

**What's most interesting to me is that I had this epiphany while writing this very article, showing the value of [building in public](https://twitter.com/hashtag/buildinginpublic)**

When you have to organize your thoughts well enough to write them down, **magic happens!**

* * *

This situation prompted me to rethink the implementation.

Instead of mapping _keys_ to _layers_, I could instead map _keys_ to _effective values_.

This would allow the registry to keep a single synchronized `Map<Key,EffectiveValue>`, guaranteeing atomic operations and acting similarly to the [read committed](https://en.wikipedia.org/wiki/Isolation_(database_systems)#Read_committed) isolation level in a DBMS. This _feels_ like a better implementation!

Let's examine some code:

```
// first we need an object to hold a value/layer pair
class ValueLayer {
    final String value;
    final Layer layer;

    // compares this object with deconstructed properties (value, layer) to avoid creating a new instance
    boolean equalTo(@Nullable String value, Layer layer) {
        return Objects.equals(value, this.value) && Objects.equals(layer, this.layer);
    }
}

// then we can implement reads/writes
public class Registry {
  protected final ConcurrentHashMap<String, ValueLayer> effectiveValues = new ConcurrentHashMap<>();

  // reads are straighforward, since the map is synchronized
  public ValueLayer get(String key) {
    return this.effectiveValues.get(key);
  }

  // writes are a bit more complex, since we need to determine how the value changes
  public ValueLayer put(String key, @Nullable String value, Layer layer) {
    return this.effectiveValues.compute(
        key,
        (k, current) -> {
          if (current == null) {
            // if we had no previous value for this key

            // and if the new value is null
            if (value == null) {
              // do not map the key
              return null;
            }

            // otherwise map the effective value and its owning layer
            try {
              return new ValueLayer(value, layer);
            } finally {
              // and send an update to any objects following this key
              this.sendUpdate(key, value, layer);
            }
          }

          // if nothing has changed
          if (current.equalTo(value, layer)) {
            // simply return the current value
            return current;
          }

          // if the layer's priority is lower than the current owner
          int oldPriority = current.layer.priority();
          int priority = layer.priority();
          if (priority < oldPriority) {
            // do nothing as this layer does not hold ownership over the key
            return current;
          }

          // if the value has not changed
          if (Objects.equals(current.value, value)) {
            // we need to modify the layer/value mapping
            // but not send an update to any objects following this key
            return new ValueLayer(value, layer);
          }

          ValueLayer ret;

          // but if the value has changed

          if (value == null && priority == oldPriority) {
            // it was either unset from the owning layer
            // in which case we need to find a lower priority layer that defines this key
            ret = findPrevious(key, current);

          } else if (value == null) {
            // it was unset in a higher priority layer
            // in which case, this is a no-op
            return current;

          } else {
            // or it was legitimately updated
            // and we need to modify the layer/value mapping
            ret = new ValueLayer(value, layer);
          }

          try {
            return ret;
          } finally {
            // and send an update to any objects following this key
            this.sendUpdate(key, ret != null ? ret.value : null, layer);
          }
        });
  }

  // sends updates to any objects following the key
  public abstract void sendUpdate(String key, String value, Layer layer);

  // finds the first lower priority layer that defines the key
  // or returns null if one does not exist
  private static ValueLayer findPrevious(String key, ValueLayer current);
}
```

After I fully implement this solution, I will do two things:

1. write a few unit tests to verify that the behavior of the system will not change after further refactorings.
2. write a few benchmarks and compare this new design with the previous version, for which I'll use[Java Microbenchmark Harness (jmh)](https://github.com/openjdk/jmh).

Until next time, stay tuned and if you want to follow this series by email don't forget to [subscribe](https://motivated-founder-807.ck.page/4c5fb25380)!

* * *

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!