文档章节

Java 并发实践 — ConcurrentHashMap 与 CAS

大数据之路
 大数据之路
发布于 2012/10/07 19:32
字数 1707
阅读 402
收藏 2
点赞 0
评论 0

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

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

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

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

代码清单1:

public class CounterDemo1 {
 
    private final Map<String, Long> urlCounter = new ConcurrentHashMap<>();
 
    //接口调用次数+1
    public long increase(String url) {
        Long oldValue = urlCounter.get(url);
        Long newValue = (oldValue == null) ? 1L : oldValue + 1;
        urlCounter.put(url, newValue);
        return newValue;
    }
 
    //获取调用次数
    public Long getCount(String url){
        return urlCounter.get(url);
    }
 
    public static void main(String[] args) {
        ExecutorService executor = Executors.newFixedThreadPool(10);
        final CounterDemo1 counterDemo = new CounterDemo1();
        int callTime = 100000;
        final String url = "http://localhost:8080/hello";
        CountDownLatch countDownLatch = new CountDownLatch(callTime);
        //模拟并发情况下的接口调用统计
        for(int i=0;i<callTime;i++){
            executor.execute(new Runnable() {
                @Override
                public void run() {
                    counterDemo.increase(url);
                    countDownLatch.countDown();
                }
            });
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        executor.shutdown();
        //等待所有线程统计完成后输出调用次数
        System.out.println("调用次数:"+counterDemo.getCount(url));
    }
}
 
console output:
调用次数:96526

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

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

代码清单2:

/**
 * Replaces the entry for a key only if currently mapped to a given value.
 * This is equivalent to
 *  <pre> {@code
 * if (map.containsKey(key) && Objects.equals(map.get(key), oldValue)) {
 *   map.put(key, newValue);
 *   return true;
 * } else
 *   return false;
 * }</pre>
 *
 * except that the action is performed atomically.
 */
boolean replace(K key, V oldValue, V newValue);

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

改进后的increase方法如下

代码清单3:

public long increase2(String url) {
        Long oldValue, newValue;
        while (true) {
            oldValue = urlCounter.get(url);
            if (oldValue == null) {
                newValue = 1l;
                //初始化成功,退出循环
                if (urlCounter.putIfAbsent(url, 1l) == null)
                    break;
                //如果初始化失败,说明其他线程已经初始化过了
            } else {
                newValue = oldValue + 1;
                //+1成功,退出循环
                if (urlCounter.replace(url, oldValue, newValue))
                    break;
                //如果+1失败,说明其他线程已经修改过了旧值
            }
        }
        return newValue;
    }
 
console output:
调用次数:100000

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

代码清单4:

/**
     * If the specified key is not already associated
     * with a value, associate it with the given value.
     * This is equivalent to
     *  <pre> {@code
     * if (!map.containsKey(key))
     *   return map.put(key, value);
     * else
     *   return map.get(key);
     * }</pre>
     *
     * except that the action is performed atomically.
     *
     * @implNote This implementation intentionally re-abstracts the
     * inappropriate default provided in {@code Map}.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with the specified key, or
     *         {@code null} if there was no mapping for the key.
     *         (A {@code null} return can also indicate that the map
     *         previously associated {@code null} with the key,
     *         if the implementation supports null values.)
     * @throws UnsupportedOperationException if the {@code put} operation
     *         is not supported by this map
     * @throws ClassCastException if the class of the specified key or value
     *         prevents it from being stored in this map
     * @throws NullPointerException if the specified key or value is null,
     *         and this map does not permit null keys or values
     * @throws IllegalArgumentException if some property of the specified key
     *         or value prevents it from being stored in this map
     */
     V putIfAbsent(K key, V value);

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

private AtomicLongMap<String> urlCounter3 = AtomicLongMap.create();
 
public long increase3(String url) {
    long newValue = urlCounter3.incrementAndGet(url);
    return newValue;
}
 
 
public Long getCount3(String url) {
    return urlCounter3.get(url);
}

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

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

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

Refer:

[1] 非阻塞同步算法与CAS(Compare and Swap)无锁算法

http://www.cnblogs.com/Mainz/p/3546347.html

     小白科普:悲观锁和乐观锁

     http://bit.ly/2isI7Jx

     并发一枝花之 ConcurrentLinkedQueue

     http://bit.ly/2hEmxlR

[2] ConcurrentHashMap使用示例

https://my.oschina.net/mononite/blog/144329

[3] 深度剖析ConcurrentHashMap源码

http://blog.csdn.net/xiaoxian8023/article/details/49249091

[4] CAS下ABA问题及优化方案 | 架构师之路

     http://bit.ly/2w1Vfve

     库存扣多了,到底怎么整 | 架构师之路

     http://chuansong.me/n/1921434646119

     库存扣减还有这么多方案? | 架构师之路

     http://chuansong.me/n/1921434546720

[5] Java并发编程——锁与可重入锁

     http://www.jianshu.com/p/007bd7029faf

     java的可重入锁用在哪些场合?

     https://www.zhihu.com/question/23284564

     java自旋锁

     http://www.jianshu.com/p/dfbe0ebfec95

     java锁的种类以及辨析(一):自旋锁

     http://ifeve.com/java_lock_see1/

[6] Disruptor简介

     http://blog.csdn.net/winwill2012/article/details/71718809

     高性能队列——Disruptor

     https://zhuanlan.zhihu.com/p/23863915

     并发框架DISRUPTOR译文

     http://coolshell.cn/articles/9169.html

[7] Java并发编程-原子性变量

http://www.jianshu.com/p/9e473657340a

本文转载自:http://www.importnew.com/26035.html

共有 人打赏支持
大数据之路
粉丝 1485
博文 516
码字总数 344497
作品 0
武汉
架构师
Java:ConcurrentHashMap的实现机制

探索 ConcurrentHashMap 高并发性的实现机制 Java并发编程之ConcurrentHashMap 聊聊并发(四)——深入分析ConcurrentHashMap 上面的三篇分析是针对java7的,java8中的实现方式已经变化。...

樂天
2015/06/28
0
0
【Java并发专题】27篇文章详细总结Java并发基础知识

努力的意义,就是,在以后的日子里,放眼望去全是自己喜欢的人和事! github:https://github.com/CL0610/Java-concurrency,欢迎题issue和Pull request。所有的文档都是自己亲自码的,如果觉...

你听___
05/06
0
0
Java Concurrency(二)——J.U.C atomic包源码解读

java5之后的java.util.concurrent包是世界级并发大师Doug Lea的作品,里面主要实现了 atomic包里Integer/Long对应的原子类,主要基于CAS; 一些同步子,包括Lock,CountDownLatch,Semaphore...

谦谦君子
2015/01/06
0
2
ConcurrentHashMap基于JDK1.8源码剖析

前言 声明,本文用的是jdk1.8 前面章节回顾: Collection总览 List集合就这么简单【源码剖析】 Map集合、散列表、红黑树介绍 HashMap就是这么简单【源码剖析】 LinkedHashMap就这么简单【源码...

Java3y
04/14
0
0
Java锁有哪些种类,以及区别

一、公平锁/非公平锁 公平锁是指多个线程按照申请锁的顺序来获取锁。 非公平锁是指多个线程获取锁的顺序并不是按照申请锁的顺序,有可能后申请的线程比先申请的线程优先获取锁。有可能,会造...

晨猫
03/23
0
0
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin
05/25
0
0
无锁的同步策略——CAS操作详解

1. 从乐观锁和悲观锁谈起 乐观锁和悲观锁是两种不同的解决并发问题的策略。悲观锁策略假定任何一次并发都会发生冲突,所以总是采用最严格的方式来进行并发控制。java中的独占锁(synchronized...

takumiCX
07/14
0
0
第三章 spring-bean之DefaultSingletonBeanRegistry(3)

前言 SingletonBeanRegistry是一个非常重要的接口,用于注册,获得,管理singleton对象。 SingletonBeanRegistry目前唯一的实现是DefaultSingletonBeanRegistry,DefaultSingletonBeanRegis...

鸟菜啊
前天
0
0
【转】15个顶级Java多线程面试题及回答

Java 线程面试问题   在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分。如果你想获得任何股票投资银行的前台资讯职位,那么你应该准备很多关于多线程的问题。在投资银行业务...

一只死笨死笨的猪
2014/09/30
0
0
Java多线程三(线程安全的集合及java.util.concurrent包的锁)

一、线程安全的集合 JDK1.5之前,可以使用Venctor和Hashtable,也可以由java.util.Collections来创建线程安全的集合,如:Connections.synchronizedSet(Set<T>); Connections.synchronizedLi......

dkz
2013/03/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

shell及python脚本方式登录服务器

一、问题 在工作过程中,经常会遇见需要登录服务器,并且因为安全的原因,需要使用交互的方式登录,而且shell、python在工作中也经常用到,并且可以提供交互的功能。都是利用了expect、spawn...

yangjianzhou
10分钟前
0
0
upstream sent too big header while reading...

nginx 报错:1736 upstream sent too big header while reading response header from upstream 1. 一般处理 location ~ \.php$ { #增加下面两句 fastcgi_buffer_size 128k; ......

dubox
21分钟前
0
0
Python解析配置文件模块:ConfigPhaser

import configparser as pa# [SectionA]# a = aa# b = bb# c = cc# [SectionB]# optionint = 1# optionfloat = 1.1# optionstring = string#https://www.cnblogs.com/a......

易野
28分钟前
0
0
Java基础——面向对象

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 Object的方法: clone() Object 克隆 to Strin...

凯哥学堂
29分钟前
0
0
rabbitmq学习记录(八)消息发布确认机制

RabbitMQ服务器崩了导致的消息数据丢失,已经持久化的消息数据我们可以通过消息持久化来预防。但是,如果消息从生产者发送到vhosts过程中出现了问题,持久化消息数据的方案就无效了。 Rabbit...

人觉非常君
34分钟前
0
0
毕业5年,我是怎么成为年薪30W的运维工程师

#转载# 我在大学读的是计算机专业,但大学毕业之后,进入到一家私企进行工作,工作的内容类似于网管,会经常的去修电脑,去做水晶头等内容。刚开始工作,也没想太多,最想的是丰富自己的工作...

Py爱好
41分钟前
1
0
大数据基础知识,大数据学习,涉及的知识点

一、什么是大数据 一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合,具有海量的数据规模、快速的数据流 转、多样的数据类型和价值密度低四大特征。...

董黎明
56分钟前
0
0
Linux CentOS 7上安装极点五笔

话说几天前在新买的惠普笔记本上成功地安装了Linux CentOS 7操作系统、Nvidia Quandro P600驱动程序及X Window,并在VMware下安装Red Hat教学环境,彻底跳出Windows的苦海,但仍然有一件事不...

大别阿郎
今天
17
0
2018年7月20日集群课程

一、集群介绍 集群,简单地说是指一组(若干个)相互独立的计算机,利用高速通信网络组成一个较大的计算机服务系统,每个集群节点(即集群中的每台计算机)都是运行各自服务的独立服务器。 ...

人在艹木中
今天
0
0
spark开发机中调试snappy

目的 在Idea中的点击运行,使spark可以直接读取snappy 自己编译hadoop,以支持snappy的压缩。 自己编译的目的就是要得到支持snappy文件读写的动态链接库。如果可以在网上下载,可以跳过自行编...

benny周
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部