Lazy graph structure caching and concurrency

huangapple go评论68阅读模式
英文:

Lazy graph structure caching and concurrency

问题

我遇到一些奇怪的 NPE(NullPointerException),并且发现这是一个并发问题。我正在使用类似下面的代码:

    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.values = new Value[]{ m.get("some-other-key") };
        // Other code ...

        this.v = new SubValue(m);
      }

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

当我调用 `Manager.doIt` 时,有时会出现 NPE,因为 `Value.v` 为 `null`。据我所知,根据 happens-before 关系,可能发生的情况是,当同时调用 `Manager.get` 且还没有键的条目时,可能会得到一个尚未完全初始化的 Value 对象。

我在 `Value` 的构造函数中注册对象,因为 `Value` 对象之间的对象图可能会有循环引用,如果不这样做,我将会得到堆栈溢出异常。

现在的问题是,在 `doIt` 方法中,如何确保 `Value` 和所有相关的值都已完全初始化?我在考虑在 `Manager.get` 中执行一些形式的双重检查锁定,但我不确定如何解决得最好。类似这样的代码:

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

是否有人对如何解决这个问题有更好的想法,或者在这段代码中是否存在并发问题?
英文:

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&lt;String, Value&gt; map = new ConcurrentHashMap&lt;&gt;();

  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(&quot;some-other-key&quot;) };
    // Other code ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt(); // &lt;--- 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?

答案1

得分: 1

问题在于您在构造函数中让 this 逸出了。

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

  Value(String key, Manager m) {
    m.register(key, this); // <--- (this 没有正确构造)

    // 初始化一些值,这里可能引入循环引用
    // 这只是一些示例代码,重点是我们调用了 Manager.get
    this.vs = new Value[]{ m.get("some-other-key") };
    // 其他代码 ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt(); // <--- 这里可能会出现 NPE。v 有时为 null
  }
}

现在,如果某个线程在映射中针对一个未正确构造的对象调用 doIt,您可能会得到一个 NPE,因为该对象的 SubValue v 可能尚未初始化。

代码还存在另一个问题。Manager.get() 是一个复合操作,应该封装在一个 synchronized 块中。如果某个线程对一个键观察到了 null 值,在它进入 if 块的时候,这个观察结果可能会变得陈旧。由于映射涉及到复合操作,所有引用映射的方法都应该由相同的锁进行保护 - 基本上您需要使用相同的锁来保护 get()register() 方法。

英文:

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); &lt;--- (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(&quot;some-other-key&quot;) };
    // Other code ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt(); // &lt;--- 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.

答案2

得分: 0

解决方案如下具有可扩展性并且据我所知是安全的

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.values = 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();
  }
}
英文:

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

class Manager {
  private final ConcurrentMap&lt;String, Value&gt; map = new ConcurrentHashMap&lt;&gt;();

  public Value get(String key) {
    Value v = map.get(key);
    if (v == null) {
      Map&lt;String, Value&gt; subMap = new HashMap&lt;&gt;();
      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&lt;String, Value&gt; 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(&quot;some-other-key&quot;) ? subMap.get(&quot;some-other-key&quot;) : m.get(&quot;some-other-key&quot;) };
    // Other code ...

    this.v = new SubValue(m);
  }

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

huangapple
  • 本文由 发表于 2020年10月8日 01:02:16
  • 转载请务必保留本文链接:https://go.coder-hub.com/64248867.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定