ConcurrentHashMap 与 CAS

骑猪看日落 2022-03-26 11:43 146阅读 0赞

在做接口限流时涉及到了一个有意思问题，牵扯出了关于concurrentHashMap的一些用法，以及CAS的一些概念。限流算法很多，我主要就以最简单的计数器法来做引。先抽象化一下需求：统计每个接口访问的次数。一个接口对应一个url，也就是一个字符串，每调用一次对其进行加一处理。可能出现的问题主要有三个：

1.  多线程访问，需要选择合适的并发容器
2.  分布式下多个实例统计接口流量需要共享内存
3.  流量统计应该尽可能不损耗服务器性能

但这次的博客并不是想描述怎么去实现接口限流，而是主要想描述一下遇到的问题，所以，第二点暂时不考虑，即不使用Redis。

说到并发的字符串统计，立即让人联想到的数据结构便是ConcurrentHashpMap<String,Long> urlCounter; 
如果你刚刚接触并发可能会写出如代码清单1的代码

代码清单1：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 </td> 
 <td> <code>public</code> <code>class</code> <code>CounterDemo1 { </code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code> <code>final</code> <code>Map&lt;String, Long&gt; urlCounter = </code><code>new</code> <code>ConcurrentHashMap&lt;&gt;();</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//接口调用次数+1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>long</code> <code>increase(String url) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Long oldValue = urlCounter.get(url);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Long newValue = (oldValue == </code><code>null</code><code>) ? 1L : oldValue + </code><code>1</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>urlCounter.put(url, newValue);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>newValue;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//获取调用次数</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>Long getCount(String url){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>urlCounter.get(url);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ExecutorService executor = Executors.newFixedThreadPool(</code><code>10</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>final</code> <code>CounterDemo1 counterDemo = </code><code>new</code> <code>CounterDemo1();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>callTime = </code><code>100000</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>final</code> <code>String url = </code><code>"http://localhost:8080/hello"</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>CountDownLatch countDownLatch = </code><code>new</code> <code>CountDownLatch(callTime);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//模拟并发情况下的接口调用统计</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;callTime;i++){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>executor.execute(</code><code>new</code> <code>Runnable() { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>@Override</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>void</code> <code>run() { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>counterDemo.increase(url);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>countDownLatch.countDown();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>});</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>try</code> <code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>countDownLatch.await();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code><code>catch</code> <code>(InterruptedException e) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>e.printStackTrace();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>executor.shutdown();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//等待所有线程统计完成后输出调用次数</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"调用次数："</code><code>+counterDemo.getCount(url));</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>}</code> &nbsp; <code>console output：</code> <code>调用次数：</code><code>96526</code> </td> 
 </tr> 
 </tbody> 
</table>

都说concurrentHashMap是个线程安全的并发容器，所以没有显示加同步，实际效果呢并不如所愿。

问题就出在increase方法，concurrentHashMap能保证的是每一个操作（put，get,delete…）本身是线程安全的，但是我们的increase方法，对concurrentHashMap的操作是一个组合，先get再put，所以多个线程的操作出现了覆盖。如果对整个increase方法加锁，那么又违背了我们使用并发容器的初衷，因为锁的开销很大。我们有没有方法改善统计方法呢？  
代码清单2罗列了concurrentHashMap父接口concurrentMap的一个非常有用但是又常常被忽略的方法。

代码清单2：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 </td> 
 <td> <code>/**</code> <code>&nbsp;</code><code>* Replaces the entry for a key only if currently mapped to a given value.</code> <code>&nbsp;</code><code>* This is equivalent to</code> <code>&nbsp;</code><code>*&nbsp; &lt;pre&gt; {@code</code> <code>&nbsp;</code><code>* if (map.containsKey(key) &amp;&amp; Objects.equals(map.get(key), oldValue)) { </code> <code>&nbsp;</code><code>*&nbsp;&nbsp; map.put(key, newValue);</code> <code>&nbsp;</code><code>*&nbsp;&nbsp; return true;</code> <code>&nbsp;</code><code>* } else</code> <code>&nbsp;</code><code>*&nbsp;&nbsp; return false;</code> <code>&nbsp;</code><code>* }&lt;/pre&gt;</code> <code>&nbsp;</code><code>*</code> <code>&nbsp;</code><code>* except that the action is performed atomically.</code> <code>&nbsp;</code><code>*/</code> <code>boolean</code> <code>replace(K key, V oldValue, V newValue);</code> </td> 
 </tr> 
 </tbody> 
</table>

这其实就是一个最典型的CAS操作，except that the action is performed atomically.这句话真是帮了大忙，我们可以保证比较和设置是一个原子操作，当A线程尝试在increase时，旧值被修改的话就回导致replace失效，而我们只需要用一个循环，不断获取最新值，直到成功replace一次，即可完成统计。

改进后的increase方法如下

代码清单3：

再次调用后获得了正确的结果，上述方案看上去比较繁琐，因为第一次调用时需要进行一次初始化，所以多了一个判断，也用到了另一个CAS操作putIfAbsent，他的源代码描述如下：

代码清单4：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 </td> 
 <td> <code>/**</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* If the specified key is not already associated</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* with a value, associate it with the given value.</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* This is equivalent to</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp; &lt;pre&gt; {@code</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* if (!map.containsKey(key))</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp; return map.put(key, value);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* else</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp; return map.get(key);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* }&lt;/pre&gt;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* except that the action is performed atomically.</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @implNote This implementation intentionally re-abstracts the</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* inappropriate default provided in {@code Map}.</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @param key key with which the specified value is to be associated</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @param value value to be associated with the specified key</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @return the previous value associated with the specified key, or</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {@code null} if there was no mapping for the key.</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (A {@code null} return can also indicate that the map</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; previously associated {@code null} with the key,</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if the implementation supports null values.)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @throws UnsupportedOperationException if the {@code put} operation</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; is not supported by this map</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @throws ClassCastException if the class of the specified key or value</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; prevents it from being stored in this map</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @throws NullPointerException if the specified key or value is null,</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; and this map does not permit null keys or values</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @throws IllegalArgumentException if some property of the specified key</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; or value prevents it from being stored in this map</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*/</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>V putIfAbsent(K key, V value);</code> </td> 
 </tr> 
 </tbody> 
</table>

简单翻译如下：“如果（调用该方法时）key-value 已经存在，则返回那个 value 值。如果调用时 map 里没有找到 key 的 mapping，返回一个 null 值”。值得注意点的一点就是concurrentHashMap的value是不能存在null值的。实际上呢，上述的方案也可以把Long替换成AtomicLong，可以简化实现， ConcurrentHashMap

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 </td> 
 <td> <code>private</code> <code>AtomicLongMap&lt;String&gt; urlCounter3 = AtomicLongMap.create();</code> &nbsp; <code>public</code> <code>long</code> <code>increase3(String url) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>long</code> <code>newValue = urlCounter3.incrementAndGet(url);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>newValue;</code> <code>}</code> &nbsp; &nbsp; <code>public</code> <code>Long getCount3(String url) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>urlCounter3.get(url);</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

看一下他的源码就会发现，其实和代码清单3思路差不多，只不过功能更完善了一点。

和CAS很像的操作，我之前的博客中提到过数据库的乐观锁，用version字段来进行并发控制，其实也是一种compare and swap的思想。

杂谈：网上很多对ConcurrentHashMap的介绍，众所周知，这是一个用分段锁实现的一个线程安全的map容器，但是真正对他的使用场景有介绍的少之又少。面试中能知道这个容器的人也确实不少，问出去，也就回答一个分段锁就没有下文了，但我觉得吧，有时候一知半解反而会比不知道更可怕。

**如有披露或问题欢迎留言或者入群探讨**

![20180614130621747][]

[20180614130621747]: /images/20220326/ee1a44ccbb2c49f681d4fe5f868a798a.png