最近经常在工作中碰到需要访问分布式共享的资源。一般这种资源都是互斥访问。但免不了A最开始在修改，过了一段时间会话过期了，同一资源又被B修改，之后A回过神来又想修改该资源，一般这时候修改会失败。这时候A需要重新申请对该资源的互斥访问。假设A、B都可以执行对资源X的原子++操作，通常来说只希望A或者B其中一个对资源X进行++操作（负责资源X的原子++操作），但有可能出现以上情况，流程如下：

1. A获取资源X的互斥锁；
2. A检查资源X的值等于1，准备修改为2；
3. 但这时候A因为线程调度或者FullGC其他什么原因Hang住了，导致互斥锁会话过期，且资源X被分配给B负责；
4. 这时候B又尝试获取X的互斥锁，资源X的值等于1，并将资源X的值修改为2，释放互斥锁；
5. 这时候A回过神来，资源X又被分配给A负责
6. A准备修改资源X为2，但因为互斥锁过期了，所以需要重新获取；

但是如果A重新获取互斥锁，然后直接修改资源X为2，那么就不满足+1的操作了。其实也就是B对资源X的修改被覆盖掉了。

这时候我们有两种选择：

1. 直接让A进行的操作失败，让上游重试或者错误向上传递；
2. 让A重新进行所有的流程，获取资源X的互斥锁，得到资源X的值，然后修改资源X的值+1，释放互斥锁；

如果采用第一种方式的话，我们原子++的操作的伪码如下。

1
2
3
4

acquire remote resource X exclude lock
var x = value(X)
set X = x + 1 // if error then throw exception
release  remote resource X exclude lock

细心的小老弟可以观察到每次操作都要获取远程的互斥锁，难免操作成本有点高。可以想到的优化方式，可以像数据库连接池一样复用这个互斥锁。优化代码如下，不仅仅没有重复获取和释放互斥锁，也减少了每次去获取资源X的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

synchronized atomicIncrement() {
    if don't acquire remote resource X exclude lock {
        recover();
    }
    try {
        set X = ++x;  // if error then throw exception
    } catch(Throwable t) {
        recover();
        throw t;
    }
}

recover() {
    acquire remote resource X exclude lock
    x = value(X)
}

之前的伪码可以抽象成通用的分布式资源独占访问模型如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

synchronized operateRemoteResource() {
    if don't acquire remote resource X exclude lock {
        recover();
    }
    try {
        check local x's info and
        modify X
    } catch(Throwable t) {
        recover();
        throw t;
    }
}

synchronized recover() {
    acquire remote resource X exclude lock
    x = get X's info
}

一切看似很完美，我们还能怎么优化呢。假设check local x’s info是个耗时的操作，那将其从锁中移除，可以减少锁持有的时间。如果是直接移到锁外面，读到的local x’s info可能是stale的，因为从check local x’s info到operateRemoteResource可能因为修改异常已经重新recover过了，这时候local x’s info可能已经发生了变化，直接modify X其实是有问题的。

为了解决这个问题，我们可以通过类似MVCC的版本号，在check local x’s info 获取当前的version，然后在operateRemoteResource里面对比版本还是否一致，如果不一致，则说明已经重新recover过了，前面的检查是stale的local x’s info，这时候就需要放弃这次操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

opVersion = version
check local x's info 

synchronized operateRemoteResource(opVersion) {
    if (opVersion < version) {
        throw ex;
    }
    try {
        modify X
    } catch(Throwable t) {
        recover();
        throw t;
    }
}

synchronized recover() {
    acquire remote resource X exclude lock
    x = get X's info
    version++;
}

最初的recover操作放到流程外

如果这个分布式资源在多线程的情况下并不需要通过锁来进行互斥访问，这时候一般不会依赖X的信息，而只是访问修改X而已，那么代码又可以变成如下。

1
2
3
4
5
6
7
8
9
10
11
12

operateRemoteResource() {
    try {
        modify X
    } catch(Throwable t) {
        recover();
        throw t;
    }
}

synchronized recover() {
    acquire remote resource X exclude lock
}

但是这种又会带来另一个问题，当多线程同时出现修改X异常，则会出现多次recover的场景，这个是我们不希望看到的。我们希望的是针对通过一次recover就能恢复的异常只recover一次。代码如下

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

operateRemoteResource() {
	opVersion = version
	if (!recovering) {
        throw ex;
	}
    try {
        modify X
    } catch(Throwable t) {
        recover(opVersion);
        throw t;
    }
}

void recover(opVersion) {
    if (opVersion < version || !recovering) {
    	return;
    }
    synchronized {
        if (opVersion < version || !recovering) {
    		return;
    	}
    	recovering = false;
    }
    synchronized {
        acquire remote resource X exclude lock
        version++;
        recovering = true;
    }
}

本来是准备写读后感的，呃，介于水平和时间有限（偷懒），准备“暂时”先写一篇读书笔记来记录一下自己看《Chaos Engineering》觉得有意思和有感悟的地方吧。

在看《Chaos Engineering》这本书之前，就对Netflix的Chaos Monkey有所耳闻。如Chaos Monkey的名字一下，Chaos Monkey负责在生产环境中进行捣乱，随意的关掉应用实例，来测试系统的健壮性。其实刚看到Chaos Monkey的时候，不由的想起测试中的Monkey Test。虽然两者不是同一个东西，但是觉得两者的核心相似：随机性、探索未知。随机性好理解，因为两者都有Monkey（滑稽）。那探索未知是啥呢？测试人员虽然在使用Chaos Monkey和Monkey Test，有对自己的系统行为有一定的预期，但并不像单元测试、集成测试之类这些测试一样，确切知道会发生什么。因为Chaos Monkey和Monkey Test具有随机性，测试人员希望利用随机性来发现未知的问题。

呃，有点跑题。。。下面读书笔记zhai chao正式开始。

为什么需要Chaos Engineering？

首先来看看Chaos Engineering的定义。定义是一种浓缩和总结，全书都是围绕这个定义来展开，感觉这个定义贼准确。建议看完这本书的同学可以回过头来好好品味下这句话。

Chaos Engineering is an approach for learning about how your system behaves by appliying a discipline of empirical exploration.

就像开头提到的Chaos Monkey，Chaos Engineering隐隐给人有一种测试的感觉。但是它又和传统的测试不同。传统的测试的目的更多的是测试程序的行为是否符合预期。而Chaos Engineering是一个通过实验发现“新”问题，然后解决问题的过程。一个是测试已知，一个是发现未知。

In testing, an assertion is made: given specific conditions, a system will emit a specific output. Tests are typically binary, and determine whether a property is true or false. Strictly speaking, this does not generate new knowledge about the system, it just assigns valence to a known property of it. Experimentation generates new knowledge, and often suggests new avenues of exploration.

而且测试通常只是针对一个子系统/程序，而在分布式的大环境下，是由很多微服务组成一个整体对外提供服务。有一些设计和错误恢复在单个子系统看来很合理，但是从整个系统上来看，就有可能引发灾难，例如请求重试导致的雪崩。还是因为系统复杂度的提高，有些问题可能是由好几个子系统共同处于某种状态导致的，单靠人是想不过来的（估计也想不出来），这时候就需要Chaos Engineering来帮我们提早发现问题，解决问题了。

Chaos Engineering这么好，那是不是就可以直接走起了？（斜眼）首先得问问自己：

Is your system resilient to real-world events such as service failures and network latency spikes?

如果明明知道自己某个节点挂一下就GG斯密达，有问题不修，那上这个不是找死嘛。

Chaos Engineering的原则

好了好了，我知道Chaos Engineeing很好，那如果我想实践，那么它有哪些设计原则呢？

…说好的这周完成，偷懒，偷懒，最后一天才开始写 2018.10.21

稳定状态的假定

要知道一个系统的正确性，在某些条件下是否符合预期。首先我们得知道我们的预期是啥。怎么判断系统是否出于正常的状态（steady state）。都不知道系统什么算正常，怎么发现系统的异常呢。

观测系统状态比较常见的做法是通过指标（metrics）。指标分为系统指标和业务指标两种。

System metrics：CPU load, memory utilization, network I/O, and all kinds of timing information, such as how long it takes to service web requests, or how much time is spent in various database queries.

It’s the business metrics that allow us to answer questions like:

• Are we losing customers?
• Are the customers able to perform critical site functions like checking out or adding to their cart on an e-commerce site?
• Are the customers experiencing so much latency that they will give up and stop using the service?

两者本质上都是时序数据，只是角度的不同。

指标的该配的配好了，那么问题又来了，我怎么知道指标是否是正常的。这是个难题，因为指标不像人的体温一样是一个相对问题的值。不要慌不要忙，数据建模帮你忙，虽然指标在一直变化，但是它有迹可循。

It increases and decreases over time, but in a consistent way

Vary Real-World Events

只要时间够长，一切不可能都是可能。平时写代码也是一样，有些你觉得几乎不会发生，不会那么那么巧的事，到最后一定会发生。难道这就是墨菲定律！

Every system, from simple to complex, is subject to unpredictable events and conditions if it runs long enough.

现实生活中事件大概分如下几类：硬件故障、程序BUG、State transmission errors？、网络延迟、请求/输入大幅度波动和重试风暴、资源耗竭、Unusual or unpredictable combinations of interservice communication？、拜占庭将军问题（e.g. 一个节点自以为拥有最新的数据）、竞争和下游依赖故障。这些事件也许会同时发生，给你一记重拳。

这些事件的模拟的成本和带来的收益不尽相同，需要根据情况来权衡。

We don’t need to enumerate all of the possible events that can change the system, we just need to inject the frequent and impactful ones as well as understand the resulting failure domains.

在生产环境实验

先声明：在生产环境实验，并不是没有脑子的在生产环境搞破环。

• Make it easy to abort the experiment
• Minimize the blast radius of the experiment

关于为什么要在生产环境实验？“越危险的地方，越能知道真理”

We want to build confidence in the system in production, and to do that we need to explore the systemic effects there. Otherwise, we are just building confidence in a system other than the one we care about, which diminishes the value of the exercise.

自动化走起来

不自动化，每一次实验都需要人去跟踪、观察和分析，那和“智能”运维脚本有什么区别。无时无刻不在自动的运行实验，确保系统的每次变更都经历了这些实验的“回归”，这才能增强我们对系统的信息嘛。

If experimentation is not automated, it is obsolescent.

减小影响

在生产环境实验，惊险又刺激。为了真的实验暴露出系统故障时的影响范围。实验要遵循两个原则：实验本身控制影响范围；当出现故障时，实验能够快速停止，及时止血。

设计实验

设计实验分为8个步骤：1）建立假设/预期；2）选择实验的范围；3）识别需要监控的指标；4）告知相关的部门；5）运行实验；6）分析结果；7）扩大影响范围；8）自动化

瞎想系列第一期 增量Map

这里有个需求

将一个Map从Master同步到Slave

• 最终达到一致就行
• value变动的频率 >> key增加的频率 >> key减少的频率

简单粗暴

最直接的想法就是直接使用推模式和拉模式：

• 推模式：Master的Map发生变化，就往各个Slave推送整个Map
• 拉模式：Slave间隔向Master请求最新的Map数据

这两种方式虽然简单粗暴易于实现，但每当Map有更新时，传输的是全量的Map的数据。在Map数据量小的时候尚可接受，但当Map数据量“大”、变动频繁和Slave数目过多时，就（大概）会对Master的带宽和负载造成巨大的压力。

为了解决这个问题，首先想到的是全量同步变增量同步。既然Slave有老的Map了，那Slave只需要拿到一个不定Patch，将补丁打入老的Map，就可以生成新的Map。那么问题又转变成如何生成补丁和如何打入补丁。

伪“增量”Map

为啥叫伪“增量”Map呢？呃，因为它的核心原理是Slave的key只增加和变更，不减少，然后通过其他补偿方案来删除key。

核心设计

结构

1
2
3
4
5
6
7
8
9
10
11
12
13

{
    mapVersion: long // map的版本
    map: {
        key1: {
            keyVersion: long, // key的版本
            value: Object // key对应的value
        },
        key2: {
            keyVersion: long,
            value: Object
        }, ...
    }
}

map的版本 mapVersion

mapVersion需要满足以下规约：

• mapVersion在map发生变更时版本会增大
• mapVersion一定大于等于所有的keyVersion

map发生变更：添加新的key；key的value变化

key的版本 keyVersion

keyVersion需要满足以下规约：

• keyVersion在key对应的value发生变更时版本会增大
• keyVersion增大一定会比原来的mapVersion大
• 新增key的版本设置和key发生变更的规则一致

mapVersion和keyVersion更新流程

先更新keyVersion再更新mapVersion。

举个栗子

1
2
3
4
5
6
7
8

{
    mapVersion: 2
    map: {
        key1: { keyVersion: 1, value: Object },
        key2: { keyVersion: 2, value: Object },
        key3: { keyVersion: 1, value: Object }
    }
}

1. map的key1和key2的value都发生了变化
2. 更新key1和key2大于原来的mapVersion，设置为3
3. 更新mapVersion为最大的keyVersion，设置为3

同步策略

1. 初次拉取设置mapVersion为空，Master返回全量map，Slave用全量map覆盖本地map
2. Master map发生变更，广播带mapVersion的oneway请求到Slave
3. Slave以本地map的mapVersion请求Master
4. Master根据mapVersion生成补丁返回给Slave

Slave定时以mapVersion为空请求Master，Master返回全量map，Slave用全量map覆盖本地map

• 为了清除已删除的key
• 防止广播没有收到

如何生成补丁

Slave请求的时候会带上Slave当前的mapVersion

1
2
3
4
5
6

if slave.mapVersion == master.mapVersion
    // 说明slave和master的map是一致的，无需变更
	return noChangePatch
else 
	patch = { mapVersion: master.mapVersion, map: {所有keyVersion比slave.mapVersion的项} }
	return patch

如何打入补丁

1
2
3
4
5
6
7

if patch.mapVersion < slave.mapVersion
	return
for k, v in path.map
	// 这里的比较是为了即使是一个大补丁，也可以各取所需，例如slave本来只需要4和5之间的patch，master却返
	// 回了2和5之间的patch
	if v.keyVersion > slave.map.map[k].keyVersion
		slave.map.map[k] = v

优化

每次slave请求都要生成补丁？No！No！No！

可以对补丁进行缓存。例如缓存分别和最新mapVersion相差1、4、16的补丁，请求补丁都返回大于等于版本差距的补丁，例如master.mapVersion - slave.mapVersion == 2，则返回补丁4。若相差超过16，就返回全量map。

真增量Map

如果key删除的还算比较频繁，而且我想相对即使的知道key被删掉了。呃，那伪增量Map可能就不那么适用了。这时候就要请出人民的好伙伴好同志奥义-无敌-旋风-真增量Map。

真增量Map其实是对伪增量Map的一个改造，主要的不同点如下：

• map发生变更新增“key的删除”
• key被删除的时候在Master这不会真的删除，只是标记DELETED，且keyVersion的变更流程和key的value发生变更的流程一致
• 打补丁的时候，Slave如果看到key标记为DELETED，则把key从map中移除

加了DELETED标记就能解决key的删除，看起来这个方案很完美。

那么问题来了，Master map的key都不真正删除了，那之后Master的map不会越来越来大么？因此需要某种策略来裁剪map，移除掉已经删除的key。

裁剪map核心思想

越早标记为DELETED的key，越早删除，删除后，设置minPullMapVersion为最大已删的deleted key.keyVersion + 1。

如果slave拉取补丁的slave.mapVersion < minPullMapVersion && slave.mapVersion != master.mapVersion，则返回全量map，slave使用全量map覆盖本地map。

Java自带Collection、Guava等类库，提供了便捷的Set、Map、List等常用数据结构。在日常开发中，这些数据结构已经满足我们的需求。这些数据结构是基于泛型实现的，提供了一个“架子”，用户可以自行设定里面的具体类型。但涉及到原始类型Primitive types（long、int、double…）作为数据结构中的元素时，因为Java泛型的限制，对这些数据结构的操作会带来很多“不必要的”原始类型的装箱和拆箱。
例如：

1
2
3

Map<Long, Long> map = ...
map.put(1L);
long value = map.get(1L);

相当于：

1
2
3

Map<Long, Long> map = ...
map.put(new Long(1L));
long value = map.get(new Long(1L)).longValue();

为了这些问题，出现了很多支持原生类型的集合类库例如Trove、Eclipse Collections、koloboke、fastutil和argona。

具体的性能测试对比参见 https://github.com/austinv11/Long-Map-Benchmarks

从性能测试上来看Koloboke综合表现最好。但介于Koloboke在2016年后停滞在了1.0.0版本，用在生产环境还是有点虚的。论稳定性和功能的完整性，Eclipse Collections更胜一筹。

Koloboke

下面通过long-long map来初窥一下Koloboke。

使用

HashLongLongMap除了实现java.util.Map<Long, Long>的所有接口以外，还提供了long get(long key)和long put(long key, long value)等支持原生类型操作的接口。让我们可以以较低的改造成本将HashMap换成Koloboke的对应实现。

注意：

• 不支持null key、null value。
• 不支持多线程，但是是fail fast的。
• 不支持Cloneable、Serializable。
• 不能保证维持多于250,000,000个元素。当大小超过限制时，会抛出HashOverflowException。

选择

koloboke实现类库需要针对每种原始类型编写相应的实现，因此类库包会比较大（19MB）（但是方便呀）。koloboke除了提供实现类库以外，还提供了Compile，用户可以根据自己的需要生成所需的类。除了按需生成，Compile生成的实现在某些特殊场景上还比koloboke实现类库快5%。

实现

HashLongLongMap的实现类使用的实现方式和Java里面的HashMap不同，在解决Hash冲突时，使用的是开放地址法。如下图所示，它的key和value紧密相连。key存在偶数位，value存在相邻的奇数位。

优点：

• 当Hash冲突时，不需要拉链，减少在添加和删除元素时的拉链的Node创建和销毁。
• key和value在内存上紧密相连，（臆想）在同一缓存行，数据存取会比较快。
• 存储使用long[]数组，并提供原生类型操作接口，避免不必要的装箱拆箱。
  缺点：
• 当Hash冲突时，需要另外寻找位点，插入和查询性能会降低。（其实这对于拉链法也是一样的，Hash冲突，需要拉链，查询性能会降低）。

查找、插入和删除操作首先是找到key所在的位点index。index的计算方式是：

1

(mask(key)) & (capacityMask = (tab.length) - 2)

当index所在位置没有数据，即没有冲突时，就可以将tab[index] = key; tab[index + 1] = value;。如果冲突就设置index = (index - 2) & capacityMask。

那么问题来了怎么判断是否有冲突呢？存入的key是啥都有可能呐，又不能设置为null表示没有设置过值。为了解决这个问题，这里很鸡贼的引入了一个freeValue的概念。正如freeValue这个名字，freeValue就是不存在Map的keys里面的一个自由自在的long值。

那么问题又来了，万一我插入的key的值和freeValue相等呢？那我能怎么办，只能换一个不存在的freeValue值咯。（并且把数组里面原来的老的freeValue换成新的freeValue）。

增和查知道了，那删就是直接把key所在的index设为freeValue，标记为没有数据就行了吧（并不）。之前其他的数据因为冲突可能找了好几次才找到空位。这里直接设置为freeValue，那这个位点前面的数据可能就找不到了。所以需要根据情况进行相应的数据移动。如下图所示，KEY2因为KEY1已经占据，所以到前面找了个位置。当KEY1删掉后，KEY2也要进行相应的移动，移动到KEY1的位置。

删除移动的逻辑（简化版）

1
2
3
4
5
6
7
8
9
10

indexToRemove = indexToShift = index
while (true) {
    indexToShift -= 2
    if (indexShift对应的key == freeValue) {
        break
    } else if (indexShift对应的数据可以移动到indexToRemove所在位置){
        移动数据
        indexToRmove = indexToShift
    } 
}

Eclipse Collections

现有的原生类型类可能会出现OOM的BUG，详见 ISSUE 。预计在 10.0 milestone version修复

使用

LongLongHashMap只提供了操作原生类型的接口，没有实现java.util.Map<Long, Long>，在改造的时候可能工作量较大。

实现

Eclipse Collections的LongLongHashMap与前者的数据存储格式类似，都是KEY、VALUE紧密相邻存在一个数组中。不同的是它分别用key=0和key=1来表示空单元和被删除的单元。查找和插入的逻辑和Koloboke的HashLongLongMap类似，先找index，key冲突的话就去下一个位置找，匹配后key的index+1就是value存储的位置。

那么问题来了，那我要插入的数据的key为0或1怎么办（问题咋这么多）？LongLongHashMap使用了两个哨兵对象(sentinel object)来存储当key为0或1的值。查找、插入和删除都对这两个哨兵对象操作。

删除逻辑相对与Koloboke就简单很多，因为被删除的单元的key用1来表示，不需要在删除单元后移动其他的单元。只需要将被删除单元的key设置为1、value设置为0。

扩展阅读：

• Eclipse Collections随Java版本的演变

性能测试

测试程序

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
47
48
49
50
51
52

@State(Scope.Benchmark)
//@Fork(value = 1, jvmArgsAppend = "-Xmx 64m -Xms 64m -XX:+PrintGCDetails")
@Fork(value = 1)
@Warmup(iterations = 1)
@Measurement(iterations = 1)
public class PutDeleteTest {
    private static final int                      SIZE          = 1000;

    private MutableLongObjectMap<TestValueObject> eclipseLOMap  = null;
    private MutableLongLongMap                    eclipseLLMap  = null;
    private LongObjMap                            kolobokeLOMap = null;
    private LongLongMap                           kolobokeLLMap = null;
    private Map<Long, TestValueObject>            jLOmap        = null;
    private Map<Long, Long>                       jLLmap        = null;
    private long                                  putIndex      = 0;

    ...

    @Benchmark
    public void kolobokeLongLongMapTest() {
        if (kolobokeLLMap == null) {
            kolobokeLLMap = HashLongLongMaps.newMutableMap(2048);
            for (; putIndex < SIZE; putIndex++) {
                kolobokeLLMap.put(putIndex, putIndex);
            }
        }
        kolobokeLLMap.put(putIndex, putIndex);
        kolobokeLLMap.remove(putIndex - SIZE);
        putIndex++;
    }

    @Benchmark
    public void eclipseHashLongLongMapTest() {
        if (eclipseLLMap == null) {
            eclipseLLMap = new LongLongHashMap();
            for (; putIndex < SIZE; putIndex++) {
                eclipseLLMap.put(putIndex, putIndex);
            }
        }
        eclipseLLMap.put(putIndex, putIndex);
        eclipseLLMap.remove(putIndex - SIZE);
        putIndex++;
    }

    public static void main(String... args) throws RunnerException {
        Options opt = new OptionsBuilder().include(PutDeleteTest.class.getSimpleName()).addProfiler(GCProfiler.class)
            .jvmArgsAppend("-Xms4g", "-Xmx4g", "-XX:+PrintGCDetails").build();

        new Runner(opt).run();
    }

}

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
47
48
49

PutDeleteTest.concurrentHashLongLongMapTest                                     thrpt    5  25222540.523 ±  2219795.461   ops/s
PutDeleteTest.concurrentHashLongLongMapTest:·gc.alloc.rate                      thrpt    5      2213.704 ±      194.760  MB/sec
PutDeleteTest.concurrentHashLongLongMapTest:·gc.alloc.rate.norm                 thrpt    5        96.659 ±        0.001    B/op
PutDeleteTest.concurrentHashLongLongMapTest:·gc.churn.PS_Eden_Space             thrpt    5      2202.213 ±      361.536  MB/sec
PutDeleteTest.concurrentHashLongLongMapTest:·gc.churn.PS_Eden_Space.norm        thrpt    5        96.132 ±        9.404    B/op
PutDeleteTest.concurrentHashLongLongMapTest:·gc.churn.PS_Survivor_Space         thrpt    5         0.014 ±        0.023  MB/sec
PutDeleteTest.concurrentHashLongLongMapTest:·gc.churn.PS_Survivor_Space.norm    thrpt    5         0.001 ±        0.001    B/op
PutDeleteTest.concurrentHashLongLongMapTest:·gc.count                           thrpt    5        85.000                 counts
PutDeleteTest.concurrentHashLongLongMapTest:·gc.time                            thrpt    5        55.000                     ms
PutDeleteTest.concurrentHashLongObjectMapTest                                   thrpt    5  24952212.914 ±  1230098.599   ops/s
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.alloc.rate                    thrpt    5      2189.621 ±      107.990  MB/sec
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.alloc.rate.norm               thrpt    5        96.659 ±        0.001    B/op
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.churn.PS_Eden_Space           thrpt    5      2201.926 ±      330.942  MB/sec
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.churn.PS_Eden_Space.norm      thrpt    5        97.186 ±       11.418    B/op
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.churn.PS_Survivor_Space       thrpt    5         0.017 ±        0.022  MB/sec
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.churn.PS_Survivor_Space.norm  thrpt    5         0.001 ±        0.001    B/op
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.count                         thrpt    5        85.000                 counts
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.time                          thrpt    5        50.000                     ms
PutDeleteTest.hashLongLongMapTest                                               thrpt    5  42870761.215 ± 18706977.204   ops/s
PutDeleteTest.hashLongLongMapTest:·gc.alloc.rate                                thrpt    5      4048.116 ±     1765.868  MB/sec
PutDeleteTest.hashLongLongMapTest:·gc.alloc.rate.norm                           thrpt    5       104.000 ±        0.001    B/op
PutDeleteTest.hashLongLongMapTest:·gc.churn.PS_Eden_Space                       thrpt    5      4050.324 ±     1778.662  MB/sec
PutDeleteTest.hashLongLongMapTest:·gc.churn.PS_Eden_Space.norm                  thrpt    5       104.050 ±        5.407    B/op
PutDeleteTest.hashLongLongMapTest:·gc.churn.PS_Survivor_Space                   thrpt    5         0.027 ±        0.036  MB/sec
PutDeleteTest.hashLongLongMapTest:·gc.churn.PS_Survivor_Space.norm              thrpt    5         0.001 ±        0.001    B/op
PutDeleteTest.hashLongLongMapTest:·gc.count                                     thrpt    5       156.000                 counts
PutDeleteTest.hashLongLongMapTest:·gc.time                                      thrpt    5        87.000                     ms
PutDeleteTest.hashLongObjectMapTest                                             thrpt    5  44863139.823 ± 16865234.866   ops/s
PutDeleteTest.hashLongObjectMapTest:·gc.alloc.rate                              thrpt    5      4236.239 ±     1592.934  MB/sec
PutDeleteTest.hashLongObjectMapTest:·gc.alloc.rate.norm                         thrpt    5       104.000 ±        0.001    B/op
PutDeleteTest.hashLongObjectMapTest:·gc.churn.PS_Eden_Space                     thrpt    5      4232.196 ±     1681.207  MB/sec
PutDeleteTest.hashLongObjectMapTest:·gc.churn.PS_Eden_Space.norm                thrpt    5       103.853 ±        6.346    B/op
PutDeleteTest.hashLongObjectMapTest:·gc.churn.PS_Survivor_Space                 thrpt    5         0.027 ±        0.026  MB/sec
PutDeleteTest.hashLongObjectMapTest:·gc.churn.PS_Survivor_Space.norm            thrpt    5         0.001 ±        0.001    B/op
PutDeleteTest.hashLongObjectMapTest:·gc.count                                   thrpt    5       163.000                 counts
PutDeleteTest.hashLongObjectMapTest:·gc.time                                    thrpt    5        97.000                     ms
PutDeleteTest.kolobokeLongLongMapTest                                           thrpt    5  43996155.514 ±  7379424.883   ops/s
PutDeleteTest.kolobokeLongLongMapTest:·gc.alloc.rate                            thrpt    5        ≈ 10⁻⁴                 MB/sec
PutDeleteTest.kolobokeLongLongMapTest:·gc.alloc.rate.norm                       thrpt    5        ≈ 10⁻⁶                   B/op
PutDeleteTest.kolobokeLongLongMapTest:·gc.count                                 thrpt    5           ≈ 0                 counts
PutDeleteTest.kolobokeLongObjectMapTest                                         thrpt    5  42801168.145 ±  3999300.909   ops/s
PutDeleteTest.kolobokeLongObjectMapTest:·gc.alloc.rate                          thrpt    5       932.827 ±       87.300  MB/sec
PutDeleteTest.kolobokeLongObjectMapTest:·gc.alloc.rate.norm                     thrpt    5        24.000 ±        0.001    B/op
PutDeleteTest.kolobokeLongObjectMapTest:·gc.churn.PS_Eden_Space                 thrpt    5       932.455 ±      222.476  MB/sec
PutDeleteTest.kolobokeLongObjectMapTest:·gc.churn.PS_Eden_Space.norm            thrpt    5        24.001 ±        6.043    B/op
PutDeleteTest.kolobokeLongObjectMapTest:·gc.churn.PS_Survivor_Space             thrpt    5         0.007 ±        0.015  MB/sec
PutDeleteTest.kolobokeLongObjectMapTest:·gc.churn.PS_Survivor_Space.norm        thrpt    5        ≈ 10⁻⁴                   B/op
PutDeleteTest.kolobokeLongObjectMapTest:·gc.count                               thrpt    5        36.000                 counts
PutDeleteTest.kolobokeLongObjectMapTest:·gc.time                                thrpt    5        20.000                     ms

更为详细的测试，分析，待续。。。

开场白

• 参与人：啥都不知道 Amy Xia
• 参考书籍：数据结构（用面向对象方法与C++语言描述）
• 其他参考资料：网上“冲浪”搜寻来的博客
• 本篇目标：希望啥都不懂的 Amy Xia 根据问题自我学习自己筛选，希望以找到答案为目的的快速查阅

自问自答

链表

顺序表、单链表、循环链表和双向链表的结构、增删改查的方式和特点。

… 妹子已找到阿里的实习，勿念

前言

正所谓磨刀不误砍柴工，基础打好了，其他的进阶才不至于被一叶障目。个人觉得 Java 基础由：基础语法、常用类库、网络编程、并发编程和 JVM 5个部分组成。这么多东西初看未免觉得无从下手，摸不着方向，觉得看不完（对，Amy Xia 同学说的就是你）。与其自己去摸索，不如直接使用大神的贤者之石。呃，其实就是看书看书看书（这么多经典的书不看，放着夹叶子嘛）。

Java 语法基础准备

这部分主要是对 Java 语法基础的准备。Java 语法特性初看很简单，但是深入了解后，还是会有发现很多 tricky 的地方。相对比较难理解的部分就是重载/重写和泛型，如果不理解 Java 底层是如何处理这些东西，而是当纯靠死记硬背，可能面对某些复杂的情况，会有错误的判断。下面是 Java 基础准备所需要学习的书籍和文档：

• Think In Java
• Learning the Java Language

自问自答环节

这部分是对前期学习成果成果的一个检验，有些问题是面试的过程中碰到的，有些问题是自己看书的时候忽然产生的疑问或者之前知识点遗漏的地方。

3 。。。2。。1。Start

语法

public、protected、no modifier、private 四种 modifier的access layer有什么区别？介绍一下 Java 9 的模块化。

重载 overload 和重写 override 的区别。

List、List<?> 和 List<Object> 的异同是什么？各自的使用场景？

思考 Number num = (new LinkedList<Integer>()).get(0)在编译后的等价代码是什么？

List<? extends Foo>和 List<? super Foo>的异同是什么？各自的使用场景？

下面这段代码输出是什么？顺便思考子类对象的内存结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Foo {
	public String str = "Foo";
  	public Foo() { say(); }
	public void say() { System.out.println("Call method in Foo with str value:" + str); }
}

class Bar extends Foo{
  	public String str = "Bar";
  	public void say() { System.out.println("Call method in Bar with str value:" + str); }
}

...
// in main
Foo obj = new Bar();
System.out.println("Str value: " + obj.str);
obj.say();
...

下面这段代码是否有错？若有错，为什么？

1
2
3
4

class Main {
	int getResult() { return 0; }
	double getResult() { return 0.0; }
}

下面这段代码是否有错？若有错，为什么？顺便还可以思考编译时发生了什么？

1
2
3
4

class Main {
	int sum(List<Integer> intList) { return 0; }
	double sum(List<Double> doubleList) { return 0.0; }
}

下面这段代码是否有错？若有错，为什么？若没有错，输出是什么？顺便还可以思考编译时发生了什么？

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Foo<T extends Double> {
 	public void set(T t) { System.out.println("Set Foo"); }
}

class Bar<T extends Integer> extends Foo{
 	public void set(T t) { System.out.println("Set Bar"); }
}

...
// In main
Bar<Integer> bar = new Bar<>();
bar.set(1);
bar.set(1.0);
...

下面这段代码是否有错？若有错，为什么？顺便还可以思考编译时发生了什么？

1
2
3
4
5
6
7
8

class Foo<T> {
	public void set(T t) {}
}

class Bar extends Foo<Integer> {
 	public void set(Integer t) {}
 	public void set(Object t) {}
}

下面这段代码的输出是什么？顺便思考对象的初始化流程，以ClassLoader为起点。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

public class Main {
    public static void main(String... args) {
        new Out("Main start\n");
        new Out("Before new a B object");
        new Out();
        new B();
        new Out();
        new Out("After new a B object");
        new Out("");
        new Out();
        new Out(C.constCvar);
        new Out();
        new Out(C.staticCVar);
        new Out();
        new Out("Before new a C object");
        new Out();
        new C();
        new Out();
        new Out("After new a C object");
        new Out("");
        new Out("Main end");
    }
}

class Out {
    public Out() {
        System.out.println("-------------------------");
    }

    public Out(String message) {
        System.out.println(message);
    }
}


class A {
    public static Out o1 = new Out("A static member o1 initialize");
    public Out o2 = new Out("A member o2 initialize");

    { new Out("A non-static block execute"); }

    static { new Out("A static block execute"); }

    public A() { new Out("A constructor execute"); }
}

class B extends A {
    public static Out o3 = new Out("B static member o3 initialize");
    public Out o4 = new Out("B member o4 initialize");

    { new Out("B non-static block execute"); }

    static { new Out("B static block execute"); }

    public B() { new Out("B constructor execute"); }
}

class C {
    public static final String constCvar = "const C member";
    public static String staticCVar = "static C member";

    static { new Out("C static block execute"); }

    public C(){ new Out("C constructor execute"); }

}

Java 基础类库准备

基础类库的准备主要从两方面进行，一方面是使用相关：适用场景、使用方式。适用场景：通过接口的整体描述，了解在实现某个功能，需要使用什么样的类库。使用方式：类/接口的方法、方法的作用；另一方面是实现相关：实现的方式和实现的优缺点。对类库使用的了解，仅仅是赋予我们能写代码的能力，而对类库实现的了解，不仅能赋予我们会写代码的能力，更多的是，通过了解实现，给予我们新的思路，在类库功能不能完成需求的情况下，可以自己造轮子。

基础类库准备的方式，使用相关信息可以从 API 文档获得，实现相关信息可以从 API 文档 + 源码来了解。（注：从源码了解，并不代表要一行一行的把源码看完，可以只需要了解核心的实现，忽略某些实现细节，大概对实现有个掌控就行）

基础类库包括：数据结构、线程池

斜体代表要阅读源码，源码可以放到有空再读

数据结构

• 链表：接口 List；实现类 LinkedList、ArrayList
• Map：接口 Map；实现类 HashMap、HashTable、TreeMap、LinkedHashMap、WeakHashMap
• Set：接口 Set；实现类 HashSet、LinkedHashSet、TreeSet
• 队列：接口 Queue；实现类 ArrayBlockingQueue、ConcurrentLinkedQueue、DelayQueue, LinkedBlockingQueue、LinkedTransferQueue、PriorityBlockingQueue、PriorityQueue、SynchronousQueue
• Deque：接口 Deque；实现类 ArrayDeque、ConcurrentLinkedDeque、LinkedBlockingDeque

线程池

• ThreadPoolExecutor
• ScheduledThreadPoolExecutor
• ForkJoinPool
• Thread

BIO & NIO

• Java IO Tutorial
• Java Socket
• Java NIO Tutorial

自问自答环节

…

介绍

“分而治之“是理清思路和解决问题的一个重要的方法。大到系统架构对功能模块的拆分，小到归并排序的实现，无一不在散发着分而治之的思想。在实现分而治之的算法的时候，我们通常使用递归的方法。递归相当于把大的任务拆成多个小的任务，然后大任务等待多个小的子任务执行完成后，合并子任务的结果。一般来说，父任务依赖与子任务的执行结果，子任务与子任务之间没有依赖关系。因此子任务之间可以并发执行来提升性能。于是ForkJoinPool提供了一个并发处理“分而治之”的框架，让我们能以类似于递归的编程方式获得并发执行的能力。

使用

分而治之代码典型的形式如下：

1
2
3
4
5
6
7
8
9
10

Result solve(Problem problem) {
    if (problem is small) {
        directly solve problem
    } else {
        split problem into independent parts
        fork new subtasks to solve each part
        join all subtasks
        compose result from subresults
    }
}

计算斐波那契数：

1
2
3
4
5
6
7
8
9
10
11
12

Class Fibonacci extends RecursiveTask<Integer> {
   final int n;
   Fibonacci(int n) { this.n = n; }
   Integer compute() {
     if (n <= 1)
       return n;
     Fibonacci f1 = new Fibonacci(n - 1);
     f1.fork();
     Fibonacci f2 = new Fibonacci(n - 2);
     return f2.compute() + f1.join();
   }
}

原理

ForkJoinPool的核心在于其轻量级的调度机制，采用了Cilk的work-stealing的基本调度策略：

• 每个工作线程维持一个任务队列
• 任务队列以双端队列的形式维护，不仅支持先进后出的push和pop操作，还支持先进先出的take操作
• 由父任务fork出来的子任务被push到运行该父任务的工作线程对应的任务队列中
• 工作线程以先进后出的方式处理pop自己任务队列中的任务（优先处理最年轻的任务）
• 当任务队列中没有任务时，工作线程尝试随机从其他任务队列中窃取任务
• 当工作线程没有任务可以执行，且窃取不到任务时，它会“退出”（yiled、sleep、优先级调整），经过一段时间后再次尝试。除非其他所有的线程也都没有任务可以执行，这种情况下它们会一直阻塞直到有新的任务从上层添加进来

一个简单的实现：

参考资料：

• A Java Fork/Join Framework

背景

无论是整个系统，还是系统的各个模块，都有自己的负载承受能力。最直观的从系统层面来说，我们往往会提到这个系统能够承载的 TPS 是多少，这个 TPS 也一般作为系统提供服务能力的体现。若 TPS 超过了系统能够承载的上限，系统就可能出现 SLA 不满足客户需求，甚至于即使之后 TPS 下降到低于 TPS上限，系统仍不能恢复正常的情况。因此对系统服务访问的限流是至关重要的，通过控制访问系统的 TPS，从而达到保护系统的目的。本文将会介绍一些常见的限流算法。

算法介绍

滑动窗口算法

我们最初可能是从 TCP 网络协议接触到滑动窗口（Sliding Window）。在 TCP 网络协议中，滑动窗口里面的槽位放置的可以发送但还没有发送成功的 segment。下面要介绍的滑动窗口限流算法，虽然形式上看起来和 TCP 中的滑动窗口略有相似，实际本质上有很大的不同。

以图为例，滑动窗口限流算法的槽位（Sliding Cell）对应的是时间段和该时间段的请求次数，例如图中第一个槽位代表的就是时间段 0.0s~0.1s 和这个时间段内的请求次数。假设当前时间是 1.0s，想得知最近一秒钟的 tps，就可以通过将 0.0s~1.0s之间的所有槽位的计数器相加来计算。当时间过去 0.1s ，滑动窗口整体向后移动一个槽位，0.1~1.1s之间的槽位计数器总和即最近一秒钟 tps。以此类推。

不难看出滑动窗口的精度与在滑动窗口中分割的槽位的个数有很大的关系，槽位个数越多，滑动窗口限流越精确，移动更加平滑，当槽位个数退化为一个的时候，滑动窗口限流退化成计数器法限流。

漏斗桶算法

漏斗桶算法有两种理解方式，一种是作为度量器（meter），一种是作为队列（queue）。两种理解方式的基础都是漏桶，所以下面先介绍漏桶的原理，再介绍两种理解方式的差别。

如下图所示，每次请求都会将水滴带入到水中。当水桶仍然能够装下水滴时，允许执行后续的业务逻辑；当水桶已满，后续的水滴就会溢出来，拒绝执行后续的业务逻辑。与此同时，水桶下面有个孔洞，以恒定的速率不断往下滴水，给水桶腾挪出容量。（有点像小学的水池同时蓄水和防水的题目 2333）

度量器 Meter

漏斗桶算法从度量器来理解，和前面介绍的滑动窗口算法类似、是后面要介绍的令牌桶算法的镜像算法（一个是判断桶还有没有容量、一个是判断桶里面有没有令牌，一个是恒定速率漏水、一个是恒定速率增加令牌）。从程序执行的角度来看，当成功往桶里加水（允许执行），就代表后续的业务逻辑可以立即执行了（同步），起到了限流的作用。

队列 Queue

漏斗桶算法从队列来理解，限流的原理是和度量器类似的，不同的地方在于，后续业务逻辑的执行。当成功往桶里加水，后续的业务逻辑（task）被放到队列中，以先进先出、恒定的速率异步的执行。因此相比度量器的方式，队列的方式除了能够限流以外，还多了整流的功能。请求的速率是不均匀的，不可预测的，通过这种的方式，可以将请求整流成可预测、恒定的速率来执行。

令牌桶算法

令牌桶算法和漏桶的度量器实现比较类似。请求需要从桶中获取令牌，有令牌才能执行后续的业务逻辑。令牌以恒定的速率往桶里填充，当桶满时，令牌溢出。

其他相关实现

Guava RateLimiter

PREFACE

第一部分讲述了Java Concurrency的基础知识，第二部分来简单的介绍一下Java的java.util.concurrent类库。这篇写着写着还是觉得官方文档比较清楚详细23333，建议还是把整个concurrent package的官方文档读了。

LIBRARY

ConcurrentHashMap

ConcurrentHashMap提供和HashMap相同的功能，正如名字所表现的一样，ConcurrentHashMap同时还提供了同步机制。ConcurrentHashMap和对整个方法使用synchronized来达到同步的效果不同，它采用了更加细粒度的锁，以提高并发和可扩展性。

查询retrieve操作（包括get）通常不会被阻塞，因此在A线程对Map进行更新update操作（包括put、remove）的时候，线程B可以完成查询操作。查询操作得到的结果是最近在查询操作之前完成的更新操作所改变的状态，也就是说所有更新操作满足happens-before查询操作。但对于聚合aggregate操作（putAll、clear），并发的查询操作可能会得到一些“中间状态”，比如查到部分加入或者删除的entries。

在通过iterator对ConcurrentHashMap的entries进行遍历的同时，我们还可以对ConcurrentHashMap进行更新操作，而不会抛出ConcurrentModificationException的异常（注意，在设计中iterators一次只被一个线程所使用？？不知道指的是一个iterator只被一个线程所使用（个人倾向）？还是在同一时间只能有一个iterator被使用）

See also:

• ConcurrentHashMap
• ConcurrentSkipListMap

CopyOnWriteArrayList

CopyOnWriteArrayList是synchronized list的替代版本，它在某些常见的情形（iteration的频率远远大于更新的频率）下提供了更好的并发行，且省去了在iteration时候对锁的需要，和ConcurrentHashMap类似，在iterator的过程中，CopyOnWriteArrayList的修改并不会引起ConcurrentModificationException。

CopyOnWriteArrayList的每次更新操作都会创建一个新的副本。Iterators保留的数组引用是iteration开始时CopyOnWriteArrayList底层数组的快照，因为该数组永远都不会改变，所以我们也无需额外的同步。

Queue

BlockingQueue提供put/take和offer/poll。如果Queue是满的，put操作会阻塞直到有空间；如果Queue是空的take操作会阻塞直到Queue之中有元素。而offer(E e)会在Queue为满时，直觉返回false，也可以offer(E e, long timeout, TimeUnit unit)等待一段时间，同理pool。Queue通常会用在生产者消费者模式上，一边生产put，一边消费take，Queue简直天生为此。

See also:

• LinkedBlockingQueue
• ArrayBlockingQueue
• DelayQueue
• PriorityBlockingQueue

Latch

Latch中文名字门闩，常常被用在线程C等待其他线程A、B条件后再继续执行的情形。CountDownLatch。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// in somewhere
CountDownLatch latch = new CountDownLatch(2);

// thread A
// ... do something
latch.countDown();

// thread B
// ... do something
latch.countDown();

// thread C
// ... do something
latch.await(); // waiting util latch count down to zero
// ... do something

还有另外一种类似的情形，不过不是Latch，一组线程都互相等待直到大家都达到某个边界情况。当A、B都执行到barrier.await()时，线程A、B才会向下继续执行。还可以通过添加Runnable的形式CyclicBarrier(int parties, Runnable barrierAction)，增加后置的处理工作，当线程A、B都执行到await时，barrierAction会被执行。CyclicBarrier

1
2
3
4
5
6
7
8
9
10
11

// in somewhere
CyclicBarrier barrier = new CyclicBarrier(2);

// thread A
// ... do something
latch.await();

// thread B
// ... do something
latch.await();
Semaphore

信号量Semaphore这个词让我回想起了那一天曾经被操作系统的过桥问题支配深深的恐惧。Semaphore适合控制资源的线程访问数量的场景，通过acquire来获得权限，release来释放权限。如下面程序所示，当线程A、B分别acquire，且还未release之前，线程C会被阻塞在acquire上，直到A或B调用release。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// in somewhere
Semaphore available = new Semaphore(2);

// thread A
available.acquire();
// ...do something
available.release();

// thread B
available.acquire();
// ...do something
available.release();

// thread C
available.acquire();
// ...do something
available.release();

Remaining…

还是把官方文档全都看一遍吧，写起来太无聊！！！

HOW TO WRITE A CONCURRENT PROGRAM

Explicitly Creating Threads for Tasks

最简单的方式就是显式的创建Thread并且调用start()开始任务并发的执行。

通常通过显式的创建Thread执行并发任务有两种方式。

继承Thread

继承Thread，将所需执行的任务重写入run()方法中。使用start()方法来启动线程。

注意是调用start()来启动线程，而不是run()。调用run()只会像正常的方法调用一样，顺序执行run()中的代码，执行完毕后继续执行调用run()之后的代码。

1
2
3
4
5
6
7
8
9
10
11

public class MyTask extends Thread{
    public void run() {
        // your task ...
    }
}

public class Main {
    public static void main(String ... args) {
        new MyTask().start();
    }
}

实现Runnable

实现Runnable接口，将所需执行的任务写入run()方法中。再用实现Runnable接口的对象作为参数传入Thread的构造函数来实例化Thread对象。最后调用Thread的start()来启动线程。

1
2
3
4
5
6
7
8
9
10
11

class MyTask implements Runnable {
    public void run() {
        // you task ...
    }
}

public class Main {
    public static void main(String ... args) {
        new Thread(new MyTask()).start();
    }
}

两种方式都最终需要显示的创建Thread来执行任务。这些Threads执行完毕以后就会被销毁。然而Thread的创建和销毁都需要较多的时间，这就给程序带来了延迟和资源负担。如果执行的任务都是轻量级的，且很频繁，正如很多服务器程序一样，为每个请求都创建一个新的Thread会消耗系统大量的计算资源。

The Executor Framework

前面两种方式线程执行完任务就被销毁了，不免会有点浪费。为了减少线程的创建和销毁，让线程活得重于泰山，线程池应运而生。线程池有两个重要的组成部分：Queue（任务寄存处），Worker（处理任务的工人）。最简单的线程池实现如下。提交任务#submit就是把任务放入任务寄存处中。处理任务的工人不断的从任务寄存处中取出任务#take，然后执行任务#run。呃，这样最简单的线程池就实现了。

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

class NaiveThreadPool {
    private BlockingQueue<Runnable> tasks   = new LinkedBlockingQueue<>();
    private Thread[]                workers = new Worker[4];

    public NaiveThreadPool() {
        for (Thread worker : workers) {
            worker.start();
        }
    }

    public void submit(Runnable task) {
        tasks.add(task);
    }

    class Worker extends Thread {
        public void run() {
            for (;;) {
                try {
                    Runnable task = tasks.take();
                    task.run();
                } catch (InterruptedException e) {
                    return;
                } catch (Exception ex) {
                    // 任务执行异常
                }
            }
        }
    }

其余的什么corePoolSize、maximumPoolSize、不同种类的Queue、线程过期策略、任务拒绝策略，建议自行看文档，已经很详细了。

Code

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

public class Main {
    public static void main(String... args) {
        new Out("Main start\n");
        new Out("Before new a B object");
        new Out();
        new B();
        new Out();
        new Out("After new a B object");
        new Out("");
        new Out();
        new Out(C.constCvar);
        new Out();
        new Out(C.staticCVar);
        new Out();
        new Out("Before new a C object");
        new Out();
        new C();
        new Out();
        new Out("After new a C object");
        new Out("");
        new Out("Main end");
    }
}

class Out {
    public Out() {
        System.out.println("-------------------------");
    }

    public Out(String message) {
        System.out.println(message);
    }
}


class A {
    public static Out o1 = new Out("A static member o1 initialize");
    public Out o2 = new Out("A member o2 initialize");

    { new Out("A non-static block execute"); }

    static { new Out("A static block execute"); }

    public A() { new Out("A constructor execute"); }
}

class B extends A {
    public static Out o3 = new Out("B static member o3 initialize");
    public Out o4 = new Out("B member o4 initialize");

    { new Out("B non-static block execute"); }

    static { new Out("B static block execute"); }

    public B() { new Out("B constructor execute"); }
}

class C {
    public static final String constCvar = "const C member";
    public static String staticCVar = "static C member";

    static { new Out("C static block execute"); }

    public C(){ new Out("C constructor execute"); }

}

Output

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

Main start

Before new a B object
-------------------------
A static member o1 initialize
A static block execute
B static member o3 initialize
B static block execute
A member o2 initialize
A non-static block execute
A constructor execute
B member o4 initialize
B non-static block execute
B constructor execute
-------------------------
After new a B object

-------------------------
const C member
-------------------------
C static block execute
static C member
-------------------------
Before new a C object
-------------------------
C constructor execute
-------------------------
After new a C object

Main end