Lazy graph structure caching and concurrency

Question

I am seeing some strange NPEs and have found out that this is a concurrency issue. I'm using code similar to the following:

class Manager {
  private final ConcurrentMap<String, Value> map = new ConcurrentHashMap<>();

  public Value get(String key) {
    Value v = map.get(key);
    if (v == null) {
      new Value(key, this);
      v = map.get(key);
    }
    return v;
  }

  public void doIt(String key) {
    get(key).doIt();
  }

  void register(String key, Value v) {
    map.put(key, v);
  }
}

class Value {
  private final Value[] values;
  private final SubValue v;

  Value(String key, Manager m) {
    m.register(key, this);

    // Initialize some values, this is where a cycle can be introduced
    // This is just some sample code, the gist is, we call Manager.get
    this.vs = new Value[]{ m.get("some-other-key") };
    // Other code ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt(); // <--- NPE here. v is null sometimes
  }
}

When I call Manager.doIt, I sometimes get an NPE because Value.v is null. As far as I understand the happens-before relationships, it might be possible, that when Manager.get is called concurrently and when there is no entry yet for a key, that I can get back a not yet fully initialized Value.

I'm registering objects in the constructor of Value because the object graph between Value objects can have cycles and without this, I would get a stackoverflow exception.

The question now is, how do I ensure in doIt that the Value and all connected values are fully initialized? I'm thinking about doing some kind of double checked locking in Manager.get but I'm not sure how to solve this best. Something like this:

  public Value get(String key) {
    Value v = map.get(key);
    if (v == null) {
      synchronized(map) {
        v = map.get(key);
        if (v == null) {
          v = new Value(key, this);
        }
      }
    }
    return v;
  }

Has anyone a better idea about how to solve this or sees a concurrency issue with that code?

Answer 1

The solution I went with is the following which is scalable and as far as I can tell, safe:

class Manager {
  private final ConcurrentMap<String, Value> map = new ConcurrentHashMap<>();

  public Value get(String key) {
    Value v = map.get(key);
    if (v == null) {
      Map<String, Value> subMap = new HashMap<>();
      new Value(key, subMap);
      map.putAll(subMap);
      v = map.get(key);
    }
    return v;
  }

  public void doIt(String key) {
    get(key).doIt();
  }
}

class Value {
  private final Value[] values;
  private final SubValue v;

  Value(String key, Map<String, Value> subMap) {
    subMap.put(key, this);

    // Initialize some values, this is where a cycle can be introduced
    // This is just some sample code, the gist is, we call Manager.get
    this.vs = new Value[]{ subMap.containsKey("some-other-key") ? subMap.get("some-other-key") : m.get("some-other-key") };
    // Other code ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt();
  }
}

Answer 2

The problem here is that you're making this escape in the constructor.

class Value {
  private final Value[] values;
  private final SubValue v;

  Value(String key, Manager m) {
    m.register(key, this); <--- (this is not properly constructed)

    // Initialize some values, this is where a cycle can be introduced
    // This is just some sample code, the gist is, we call Manager.get
    this.vs = new Value[]{ m.get("some-other-key") };
    // Other code ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt(); // <--- NPE here. v is null sometimes
  }
}

Now if some thread calls doIt on a key that has an improperly constructed object against it in the map, you might get an NPE as the Subvalue v for that object might not have been initialised.

The code has another issue. Manager.get() is a compound action, and should be encapsulated in a synchronised block. If one thread observes a null value for a key, by the time it enters the if block, that observation might become stale. Since the map is involved in the compound action, all methods that reference the map should be guarded by the same lock - basically you need to guard get() and register() with the same lock.