小谈 .NET 和 Java 的并发容器 API 设计

今天看博客园，看到一篇文章。它的主要内容是：

• 为什么 ConcurrentHashMap<K, V> 不支持 null 值？因为这样就无法区分给定的键不存在还是对应值就是 null。
• 为什么 ConcurrentHashMap<K, V> 不支持 null 键？可能只是 Lea 自己的喜好——因为从逻辑上来说，允许也没有什么问题（虽然有潜在的语义错误）。

文章内容不赘述了。

我看完之后想到的是，.NET 的并发容器（ConcurrentDictionary<TKey, TValue> 等等）的 API 设计和它的普通容器有着巨大的不同。把它们和这个 ConcurrentHashMap<K, V> 的坑联系在一起，可能会发现什么。

以前我笑话过 .NET 的容器 API 设计。我们知道，.NET 的 Stack<T> 和 Queue<T> 是基于数组的。这给予了它们一定的随机访问能力（不过没什么卵用，想想它们是做什么的），保持内存连续性（提高缓存命中率），但是坏处就是不适合频繁的扩容和收缩。（在提高数组的利用率上，Stack<T> 比较好办，Queue<T> 用的是循环缓冲区。）我想实现基于 LinkedListNode<T> 的版本，却发现 .NET 并没有提供 IStack<T> 和 IQueue<T>。简单搜索就可以找到 StackOverflow 上的问题。其中有那么一句话：

As it pointed Queue and ConcurrentQueue don’t have that much similar to make them implement single interface.

我就顺着看了一下 ConcurrentQueue<T> 的 API，接着就被震撼到了。其他的容器也是类似的。这是什么玩意儿！相比之下，人家 Java，ConcurrentHashMap<K, V> implements Map<K, V>，多么优雅。也就是说，理论上，我可以将某个类型为 Map<K, V> 的成员字段啊参数啊变量啊，从原来赋值为 HashMap<K, V> 的实例改为 ConcurrentHashMap<K, V> 的实例，然后瞬间就不担心这里的多线程问题了（假设其余部分正确实现）。这不是很爽吗？而如果我使用了 Dictionary<TKey, TValue>，由于其和 ConcurrentDictionary<TKey, TValue> 没有共同的基类或者适合的接口，所以我无法只使用一个变量就兼容二者。太麻烦了，就为了这个区别，也得开始使用策略模式吗……

今天突然理解了。ConcurrentHashMap<K, V> 中的 null 是一个坑，而且“这种限制”这样的无聊问题会成为 Java 开发者懂不懂并发的其中一个筛子，很大程度上就是因为它实现了 Map<K, V>，而后者在设计之初就计划使用 null 作为键不存在的表示，从而没有其余携带信息的手段。这是不是设计失误我不敢下结论（不知道 Bloch 当初是怎么想的），但是一定是有问题的。

我们先来看看 ConcurrentHashMap<K, V> 的存取 API。由于实现了 Map<K, V>，所以签名是一样的：

interface Map<K, V> /* ... */ {
    // ...
    public V get(Object key);
    public V put(K key, V value);
    // ...
}

class ConcurrentHashMap<K, V> /* ... */
    implements Map<K, V> /* ... */ {
    // ...
    public V get(Object key);
    public V put(K key, V value);
    public V putIfAbsent(K key, V value);
    // ...
}

“无法使用 null 值”可以从“需要实现 Map<K, V>”这个前提推断出来：

1. 必须实现 Map<K, V>，因此存取必须使用 get(K) 和 put(K, V)。
2. 在 Map<K, V> 的大多数实现中，get(K) 对于不存在的键会返回 null 而不是抛出异常。
3. 怎么判断返回 null 是代表键不存在，还是代表设置的值就是 null 呢？那就得在获取值之前先使用 contains(K) 检查了。
4. 假设允许 null 值。一样会遇到2所示的问题。那么此时怎么判断是哪一种情况呢？还是先用 contains(K) 吗？这可是可能处于并发状态下的啊，两次操作之间或许这个容器状态就改变了，引发别的问题。因此，不可以使用预先判断。
5. 现在唯一能表示键不存在的只有返回值了。在这里做文章，规定一个特殊值 null（有经验都知道使用特殊值一般不是个好主意），用它来表示键不存在。
6. 由于 null 返回值在这个操作的上下文中有了“键不存在”的特殊意义，为了不引发冲突，容器内的所有值都不允许为 null。

可以注意到，状态附加、原子性保证，使得应用前提发生了变化。因此，ConcurrentHashMap<K, V> 不适合实现 Map<K, V>。

再来看看 .NET 这边。

interface IDictionary<TKey, TValue> /* ... */ {
    // ...
    void Add(TKey key, TValue value);
    bool TryGetValue(TKey key, out TValue value);
    // ...
}

class ConcurrentDictionary<TKey, TValue>
    : IDictionary<TKey, TValue> /* ... */ {
    // ...
    public bool TryGetValue(TKey key, out TValue value);
    public TValue GetOrAdd(TKey key, TValue value);
    public bool TryAdd(TKey key, TValue value);
    public bool TryUpdate(TKey key, TValue newValue, TValue comparisonValue);
    // ...
}

（或许你要问，其余对 IDictionary<TKey, TValue> 的方法实现，比如 Add(TKey, TValue) 呢？答案是它们都成了显式接口实现。）

可见，虽然同样是实现了字典接口，但是由于 .NET 这边并未采用特殊值，所以 TryGetValue(TKey, out TValue) 有很高的并发接口适应性。开发者不需要关心特殊值的问题，而是可以和普通的 Dictionary<TKey, TValue> 一样，使用 null 作为项的值，不需要抓破脑袋。

.NET 这样设计的一部分原因也可能是不得已而为之。因为在 CTS 中是有严格的值类型和引用类型的区分的。ConcurrentDictionary<T> 并没有泛型类型约束，因此可以用于这两种类型。如果想像 Java 那样找 null 这样的特殊值，是找不到的——值类型没有“空”（null）的概念，但是不排除有“空”（empty）的值，包括默认的全零值。因此，为了携带状态，就得多加参数。

这个设计带来的一个（可能是）意想不到的好处是，它将“检测并获取”作为一个原子操作（API 层面，当然不是指令层面），而且没有副作用。这样开发者过渡到并发反而容易了。

我们再来看看在队列上的区别。

interface Queue<E> /* ... */ {
    // ...
    // 失败抛出异常
    public boolean add(E e);
    public E remove();
    public E element();
    // 失败返回特殊值
    public boolean offer(E e);
    public E poll();
    public E peek();
    // ...
}

// 和 Queue<E> 一样，不赘述
class ConcurrentLinkedQueue<E> /* ... */
    implements Queue<E> /* ... */ {
    // ...
}

class Queue<T> /* ... */ {
    // ...
    public void Enqueue(T item);
    public T Dequeue();
    public T Peek();
    // ...
}

class ConcurrentQueue<T> /* ... */ {
    // ...
    public void Enqueue(T item);
    public bool TryDequeue(out T result);
    public bool TryPeek(out T result);
    // ...
}

在这个设计上，Java 提供了两套令人迷惑的 API。它们提供相同的功能，但是在失败时的行为完全不同。一套是快速失败（fail-fast），抛出异常，另一套是安全失败（fail-safe），返回特殊值 null。（说实话，如果不是这次我看了文档，否则我也不会知道两套的区别。）很明显，抛出异常适用于简单开发，而在复杂的并发系统中返回“失败”这个状态更好。但是由于使用的特殊值也是个合法值（null），因此 Queue<E> 一般是不允许其中的项是 null 的。（但是也有例外：LinkedList<E> 是允许 null 项的，因为用内部的 Node<E> 包装了。新的坑。）且不论两套 API 是否让人头大，针对 null 的行为已经让人头大。不过，和 Map<K, V 到 HashMap<K, V>/ConcurrentHashMap<K, V> 的暗坑，Queue<E> 到 LinkedList<E>/ConcurrentLinkedQueue<E> 反而没什么坑。

当然，你也可以说 null 本身就是个 billion dollar mistake。在这种意义上，null 本来就不该出现。可惜广泛应用的语言大多都没有禁止 null……

.NET 这边的设计就有意思了。对于普通场景的 Queue<T>，失败都是抛出异常的。而 ConcurrentQueue<T> 入队失败抛出异常，后两者失败时是返回 false 的（从命名就可以看出来）。而且 ConcurrentQueue<T> 和 Queue<T> 没有关系（见上文），因此不提供相同的 API。失败行为和 API 对于是否支持并发时线程安全（和性能！）完全不同——这虽然“适应”了不同场景，让开发者只需要“自然地”使用，但这差异同样增加了认知的负担。

---

另外还有一个有意思的讨论。我们知道有 ConcurrentHashMap<K, V>，但是线程安全的随机访问列表实现只有 Vector<E>（或者使用 Collections.synchronizedList() 包装），而且原理还是全部加锁的。为什么没有 ConcurrentArrayList？（原文链接已经失效，所以只好引用译文。）

回答是：

很难去开发一个通用并且没有并发瓶颈的线程安全的 List。

像 ConcurrentHashMap 这样的类的真正价值并不是它们保证了线程安全，而在于它们在保证线程安全的同时不存在并发瓶颈。……

比如，调用 contains() 或者 indexOf() 的时候，最坏的情况下需要搜索整个列表，所以必须锁定整个列表。这个时候如果要修改列表（增删改）那必然会引发瓶颈。

相比之下，ConcurrentHashMap<K, V> 在修改/搜索的最坏情况下最多只需要锁住其一部分（如果你疯狂构造哈希冲突；另参考 Java 7 到 Java 8 的实现变更）。ConcurrentLinkedQueue<E>/ConcurrentLinkedDeque<E> 则更简单，无法搜索，修改也只有一个/两个方向。因此它们的使用不会构成瓶颈。

---

我本来还想吐槽一下 wildcard capture 的，因为我记得以前在哪里看到过，它的不恰当应用会得出合乎语法却毫无意义的结果。我写这篇文章的时候找了很久，可是就是找不到了。不过反而有了其他的发现，比如这个和这个。