ConcurrentHashMap

1. 为什么 key 和 value 不允许为 null

HashMap 中允许 key、value 为 null,key 为 null 时哈希值为 0 。

ConcurrentHashMap 中都不能为 null 是因为作者 Doug Lea 认为:在并发编程中,null 值容易引来歧义,当调用 get(key) 返回 null 时,无法确定是 key 对应的 value 就是 null ,还是说这个 key 不存在。
非并发编程中可以通过调用 containsKey 方法来判断,但并发编程中无法保证这两个方法之间没有其他线程来修改 key 值。

2. 并行度 concurrencyLevel

ConcurrentHashMap 构造函数里有个参数 concurrencyLevel 提供了建议支持的并行度。

在 JDK 1.7 的实现里,分段锁段数组的大小由 concurrencyLevel 决定,为大于 concurrencyLevel 的最小的 2 次幂值,但不能超过 2^16,初始化后不能修改。

在 JDK 1.8 里,concurrencyLevel 会影响 Node 数组的初始容量,由于并发粒度是数组的元素,从而影响并发度。

concurrencyLevel 并不是指定了精确的并发度。

继续阅读

双重检查加锁 与 volatile

一个问题:双重检查加锁为什么用了 volatile 就可以正确工作?

反过来问:不用 volatile 修饰 resource 属性有什么问题?

双重检查加锁的简单示例:

public class DoubleCheckedLocking {
    private static Resource resource;

    public static Resource getInstance() {
        if (resource == null) {     // LL01
            synchronized (DoubleCheckedLocking.class) {
                if (resource == null) {
                    resource = new Resource();
                }
            }
        }
        return resource;
    }
}

继续阅读

FutureTask (JDK1.8)

本文基于 JDK 1.8.0_101 对应的源码。

FutureTask 表示一个可取消的异步计算的任务,其构造器接收一个 Runnable/Callable 表示异步计算的任务。虽然说 FutureTask 支持取消,但任务一旦开始执行,执行过程就可能不受取消操作的影响。

当任务没有执行结束时,所有获取结果的操作都会阻塞等待。

以栈的方式维护等待获取结果的线程,因为不用考虑公平性的问题,用栈更简单。

FutureTask 在 JDK 1.7 的时候是基于 AQS 实现的,可以看这里

总体上:

  • volatile int state 控制执行状态,
  • volatile Thread runner 防止重复执行,
  • volatile WaitNode waiters 以栈形式维护等待线程。

继续阅读

再读 AQS

基于 JDK 1.8.0_101 。

AQS 的核心:两种模式、一个状态、一个同步等待队列、条件对象。

  • 两种模式:是指支持独占模式或共享模式,两者不能并存,要么独占、要么共享。
  • 一个状态:状态是 AQS 的灵魂,根据所处的模式来定义其值的含义。
  • 一个同步等待队列:是线程为进入指定的模式、但还不能进入时,需要在同步等待队列上进行等待。该队列是双向链表,以方便支持取消操作。
  • 条件对象:只能在独占模式下使用,线程可以在条件对象上进行等待、由其他线程在满足条件时唤醒。
    > 每个条件对象其实是一个单向链表实现的条件等待队列,在给定条件对象上等待的线程会进入条件等待队列,等待其他线程来唤醒。
    > 进入等待之前,线程会先进入条件等待队列、保存自己持有时的状态值,然后释放独占模式,进入挂起线程、等待唤醒,唤醒后重新尝试进入独占模式,进入后再继续执行。

继续阅读

Disruptor 为什么那么快?

一个简短的笔记。

Disruptor 快的核心秘诀是:基于数组、空间局部性良好、消除伪共享、无锁、支持批量消费。

1. 基于数组的内存局部性

Disruptor 底层是一个固定大小的环形数组,初始化的时候会顺序创建与数组长度一样数量的对象,以便让这些对象在内存上尽量挨着的。

顺序创建与随机创建在内存上的差别可以对比下面两张图(来自极客时间专栏《Java并发编程实战》):

往队列里写入事件时,需要把事件的属性拷贝到这些预创建好的对象里,以保持内存的局部性。

这里的一个隐性要求是:事件的属性应该尽量是基本类型,如果是对象类型,存的是引用,访问引用指向的值时可能就是随机的内存访问。

继续阅读

一个与 Ehcache 相关的死锁案例

最近朋友分享一个与 Ehcache 相关的死锁案例,记录下。

0. 一个思考题

缓存击穿是指高并发的请求访问同一个 key,当这个 key 失效后,所有的请求都会传递到数据库,数据库因而崩溃。

为了防止数据库崩溃,我们需要在应用层面拦截这些请求,比如控制一个应用加载一个 key 时只有一个请求到数据库。

如果用加锁的方法,每个 key 一个锁,那么 100 万个 key 就会有 100 万个锁实例在 JVM 里。如果 key 过期了,锁实例可能还得过期,特麻烦。

如果所有的 key 共享同一个锁,那么这个锁就会成为瓶颈。

该如何控制是好?

1. 背景说明

一个面向海量用户的 api 服务,需要提供用户信息查询的功能。

缓存有两层,第一层是 JVM 内基于 Ehcache 的,第二层是 memcached ,查找缓存时首先从本机 Ehcache 查询,找不到再去 memcached 查找,还找不到则从 Loader 接口加载数据并存入相应的缓存。

用户信息由 会员信息、个人信息、家庭信息 等组成,这些信息位于不同的模块,存储在不同的表或库里。

在 Ehcache 里,用户信息有一层缓存,会员信息、个人信息、家庭信息 也有对应的缓存。

以 ID 为 “007” 的用户举例,用户信息缓存对应的 key 为 “User:007″,会员信息对应的缓存 key 为 “member:007″,个人信息对应的缓存 key 为 “personal:007″,家庭信息对应的缓存 key 为 “family:007″。
其中用户信息对应的缓存的过期时间是比较短的。

当用户信息在缓存里都查找不到时,它的 Loader 实现会调用 MemerbService 加载会员信息、调用 PersonalService 加载个人信息,FamilyService 加载家庭信息,然后合并成用户信息保存在缓存里。MemerbService/PersonalService/FamilyService加载信息时也是先从缓存查找,两级缓存都查找不到时也调用对应的 Loader 从表里加载数据。

使用的 Ehcache 的版本是 ehcache-core-2.6.9 。

继续阅读

HikariCP 连接池–高性能数据结构

HikariCP,日语的含义是“光”,号称目前最快的数据库连接池。

它的高性能来自两个方面:

  1. 利用 Javassist 在字节码层面优化代理对象的创建,提升代理对象的调用性能。
  2. 在数据结构上采用定制的 FastListConcurrentBag 来提升性能。

本文主要关注这两种数据结构的实现。

1. FastList

我们用 JDBC 编程的时候,首先是获取 Connection、创建 Statement、执行查询得到 ResultSet,执行完成后依次关闭:ResultSetStatementConnection,特别是一个逻辑里创建了多个 PreparedStatement 时,一般用完就关闭。

为了防止用户忘了关闭 StatementResultSet,连接池需要跟踪创建的 StatementResultSet,在连接返回到连接池时关闭这两类资源。

public abstract class ProxyConnection implements Connection
{
    // 跟踪本连接创建的语句
    private final FastList<Statement> openStatements;

   private synchronized <T extends Statement> T trackStatement(final T statement) {
      openStatements.add(statement);
      return statement;
   }

   // Statement 关闭时回调此方法
   final synchronized void untrackStatement(final Statement statement) {
      openStatements.remove(statement);
   }

   // 创建语句时加入跟踪列表
   public Statement createStatement() throws SQLException {
      return ProxyFactory.getProxyStatement(this, trackStatement(delegate.createStatement()));
   }

    // Connection.close 方法回调此方法关闭打开的语句
    private synchronized void closeStatements() {
      final int size = openStatements.size();
      if (size > 0) {
         for (int i = 0; i < size && delegate != ClosedConnection.CLOSED_CONNECTION; i++) {
            // 利用 try-with-resources 机制进行关闭
            try (Statement ignored = openStatements.get(i)) {
               // automatic resource cleanup
            } catch (SQLException e) {
               LOGGER.warn("{} - Connection {} marked as broken because of an exception closing open statements during Connection.close()",
                           poolEntry.getPoolName(), delegate);
               leakTask.cancel();
               poolEntry.evict("(exception closing Statements during Connection.close())");
               // 包装的代理对象不再持有底层的连接
               delegate = ClosedConnection.CLOSED_CONNECTION;
            }
         }

         openStatements.clear();
      }
}

关闭的顺序跟创建的顺序是相反的,要关闭并移除的对象一般在列表的末尾。而 ArrayList 的移除对象是从列表头部开始的,在这种场景下不高效。FastList 的实现是逆序查找要删除对象;对于根据下标进行的操作,移除了对下标合法性的检查,由连接池来保证。

继续阅读

JUC 并发 Queue 设计与介绍

Queue 体系

Queue 是一种先进先出的队列。

ArrayBlockingQueue 和 LinkedBlockingQueue 是带阻塞特性,基于锁来实现。ArrayBlockingQueue 采用同一把锁来控制出、入队列操作;LinkedBlockingQueue 用两把锁来分别控制出、入队列操作,提高了并发性能。

ConcurrentLinkedQueue 非阻塞,采用无锁算法、利用 CAS 操作来实现。

0.1 BlockingQueue

当生产者向队列添加元素但队列已满时,生产者会被阻塞;当消费者从队列移除元素、但队列为空时,消费者会被阻塞。

其实现类必须是线程安全,入队列 happen-before 出队列。

0.2 TransferQueue

继承自 BlockingQueue,更进一步:生产者会一直阻塞直到添加到队列的元素被某一个消费者所消费(不仅仅是添加到队列)。

特别适用于这种应用间传递消息的场景:生产者有时需要等待消费者接收消息,有时只需把消息放进队列、不需要等待消费者接收。

// 传递元素给消费者,如果需要则等待。确保一次传递完成。
void transfer(E e);

// 非阻塞
boolean tryTransfer(E e);

// 基于等待时间的。
boolean tryTransfer(E e, long timeout, TimeUnit unit);

// 返回是否有在等待接收元素的消费者
// (BlockingQueue.take()或带等待时间的 poll 方法调用)
boolean hasWaitingConsumer();

// 返回大概的在等待接收元素的消费者
//(BlockingQueue.take()或带等待时间的 poll 方法调用)
int getWaitingConsumerCount();

0.3 Deque

允许在两端进行插入、删除元素的线性集合。

实现类:

  • ArrayDeque:基于数组加头尾两个指针来实现、非线程安全的。
  • LinkedList:基于双向链表实现、非线程安全的。
  • ConcurrentLinkedDeque:基于双向链表、CAS 元语实现、无界的。

0.4 BlockingDeque

当 Deque 里没有元素时阻塞消费者,当没有空闲空间时阻塞生产者。

目前只有一个实现类 LinkedBlockingDeque,使用双向链表来存储元素,支持容量限制,用一把锁来保证线程安全性。因为允许在两端进行操作,双向链表更合适。

继续阅读

JUC 延迟队列 DelayQueue

DelayQueue 一个无界阻塞队列,只有在延迟期满时才能从中提取元素。基于 PriorityQueue 实现的延迟队列,用 ReentrantLock 提供线程安全性。

其元素必须实现 Delayed 接口。

该类可用来实现定时调度的功能,当前时间与任务的下次执行时间的距离作为延迟时间。

实现上采用 Leader_Follower 模式 的变体进行优化:leader 进行限时等待,其他线程作为 follower 无限等待。leader 在等待的过程中可能插入一个更快到期的元素,那么旧 leader 就会被作废,如果又有一个线程来获取,那么它会作为新的 leader 根据新的队列头元素进行限时等待。

继续阅读

ThreadLocal/InheritableThreadLocal 设计与源码分析

ThreadLocal 提供了线程本地的变量,每个线程只能通过 get/set 方法访问自己的变量。此类的实例通常声明为类的 private static 属性、用来把状态(比如事务ID)关联到线程上。

InheritableThreadLocal 扩展了 ThreadLocal,为子线程提供从父线程那里继承的值:在创建子线程时,子线程会接收所有可继承的线程局部变量的初始值,以获得父线程所具有的值。

1. 实现思路

如果自行实现一个 ThreadLocal,直接思路可能是:ThreadLocal 内维护一个 Map,以 线程对象为 key,value 为变量。

这个思路的问题有:
1. 当线程终止、JVM 进行垃圾回收时,这个 Map 还持有对线程的引用而没法回收线程的资源;如果 JVM 要能回收,那么必须知道有多少 ThreadLocal 实例持有对线程的引用,这会给 JVM 带来负担。
2. 为了实现 InheritableThreadLocal 时,在创建时还必须找出所有的 InheritableThreadLocal,判断父线程是否有设置变量,有的则进行拷贝变量。

从上述问题来看,实现线程本地变量至少应该考虑:
1. 线程本地变量不应该直接持有对 Thread 对象的引用,避免给 JVM 回收 Thread 带来额外的开销;
2. 为实现 InheritableThreadLocal,一个线程在哪些 InheritableThreadLocal 里设置了变量应该有个集中式的存储,这样才方便把父线程的可继承本地变量拷贝到子线程的。
3. 可能有多个线程同时对 ThreadLocal 进行设置变量,那么对 Map 的访问应当是线程安全的。

再来看下线程本地变量涉及哪些参与者:ThreadLocal 、Thread、变量值。

一个 ThreadLocal 可以持有多个 Thread 的变量,一个 Thread 也可以在多个 ThreadLocal 上设置变量。因此一个 (ThreadLocal, Thread) 的组合才能唯一确定一个线程本地变量值。

Map 只能放在 (ThreadLocal, Thread) 中的一个,前面也说了放在 ThreadLocal 上是不合适的。再来看看放在 Thread 上如何。

每个 Thread 的 Map 属性的 key 是 ThreadLocal 对象,value 是变量值,看来也能实现线程本地变量。

这样反转之后,ThreadLocal 不会持有线程的引用,线程回收不存在问题,线程的 Map 也可以在线程回收时进行回收,Map 里面保存的变量值也可以进行回收。

可继承的线程本地变量可以用另一个 Map 来维护,起到了集中存储的作用。

每个线程都只访问自己的 Map,自然没有并发的竞争。

完美!JDK 从 1.3 开始就是按这个思路去实现的。

继续阅读