An update on efficient multi-layered key ownership

🔔 This article was originally posted on my site, MihaiBojin.com. 🔔

---

In the previous article, I introduced the concept of key ownership.

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 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

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 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 useJava Microbenchmark Harness (jmh).

Until next time, stay tuned and if you want to follow this series by email don't forget to subscribe!

---

If you liked this article and want to read more like it, please subscribe to my newsletter; I send one out every few weeks!