HashMap

本文源码基于 JDK 1.8.0_101 。

在 JDK 1.8 之前,HashMap 采用 槽数组 + 单链表 来实现;

在 JDK 1.8 开始采用 槽数组 + 单链表 + 红黑树 来实现。

1. 为什么引入红黑树?

解决哈希冲突时、链表过长导致访问效率低下的问题。

为什么是红黑树不是其他树:
二叉排序树在极端情况下会退化成线性结构。
平衡二叉树(AVL树)是严格平衡树,在增加或删除节点时,旋转次数比红黑树要多。红黑树的统计性能高于 AVL 树。

红黑树特性,RBT树上的每个节点,都要遵循下面的规则:
① 每个节点都是红色或者黑色;
② 根节点必须始终是黑色;
③ 没有两个相邻的红色节点;
④ 对每个结点,从该结点到其子孙节点的所有路径上包含相同数目的黑结点。

继续阅读

HashTable 有什么奇怪的知识?

本文涉及的源码基于 JDK 1.8.0_101 。

1. HashTable

  1. 采用数组 + 链表(表头插入)方式解决哈希冲突。
  2. 所有的 public 方法都用 synchronized 修饰以保证线程安全。
  3. 在构造时就初始化槽数组(默认大小为 11)。
  4. 键、值 都不能为 null
  5. 指定 key 的目标槽的定位逻辑:(key.hashCode() & 0x7FFFFFFF) % table.length,掩码+求模。
  6. 槽数组的最大尺寸为 MAX_ARRAY_SIZE: Integer.MAX_VALUE - 8(减 8 是因为一些 JVM 会在数组里保留一些 header words)。
  7. 扩容逻辑为 两倍 + 1。
  8. 阈值为: (int)(capacity * loadFactor),但不能超过 MAX_ARRAY_SIZE + 1

继续阅读

双重检查加锁 与 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并发编程实战》):

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

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

继续阅读

RateLimiter 浅析

本文基于 Guava-18.0.jar 。

0. 概述

RateLimiter 是令牌桶思想的一个实现,可实现流量整形、资源访问速率控制。

与信号量对比:

  • 一旦从 RateLimiter 获得许可,不需要释放。信号量分配后必须释放。
  • RateLimiter 控制的是速率,以配置的速率分发许可,速率不变时单位时间内分发的许可量是恒定的。信号量控制的是并发访问的数量,单位时间内分配的次数跟使用许可的时长有关,每次申请使用的时间越短,则单位时间内能分配的次数就越多。

RateLimiter 请求许可的数量不会对请求本身产生抑制影响,但会对下一个请求产生抑制。例如一个请求很大数量许可的请求到达空闲 RateLimiter 时,它将马上获得许可,但下一个请求会被抑制,从而为前面昂贵的请求付出代价。

RateLimiter 申请许可时,可能会阻塞、也可能不会,是否阻塞取决于上一次分配许可的时间和当前请求的许可数量。

RateLimiter 可以配置一个 warnup 热身周期,在这个周期内每秒发出的许可数量稳步增长直至达到稳定的速率。简单说是慢启动吧。

1. 使用示例:

// 每秒2个的速率提交任务
final RateLimiter rateLimiter = RateLimiter.create(2.0);
void submitTasks(List tasks, Executor executor) {
    for (Runnable task : tasks) {
        rateLimiter.acquire(); // may wait
        executor.execute(task);
    }
}

继续阅读

一个与 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 。

继续阅读

LMAX 架构–笔记

原文 The LMAX Architecture

原文介绍了 LMAX 支持高性能、低延迟的架构,还介绍了 Disruptor 这个框架的设计缘由。

LMAX 用 3Ghz 的 CPU 单线程处理达到 600w TPS,意味着要在 500 个时钟周期内处理完一个事务。(dual-socket quad-core,32GB RAM)

LMAX 整体架构:

Business Logic Processor,BLP

只是简单的 Java 代码,不依赖于任何框架。单线程执行,全内存操作, 顺序地获取输入的消息。

要操作的数据全在内存里。好处有两点:快 和 简化了编程(没有对象/关系映射)。

用 Event Sourcing 事件溯源机制来保证 BLP 的状态是可以重建的,输入事件由 input disruptor 来进行持久化。事件溯源机制可以采用快照的方式来缩短重建需要的时间。

LMAX 采用多个 BLP 同时处理同样的事件(两个在同一个数据中心,第三个在灾备中心),但只有一个 BLP 的输出是有效的。当存活的 processor 失败时,系统切换到另一个。

事件溯源的另一个好处是诊断方便,可以把事件拷贝到开发环境进行重放。

继续阅读

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 的实现是逆序查找要删除对象;对于根据下标进行的操作,移除了对下标合法性的检查,由连接池来保证。

继续阅读