Wetts's blog

转自：http://coolshell.cn/articles/9606.html

问题的症状

从前我们的Java代码因为一些原因使用了HashMap这个东西，但是当时的程序是单线程的，一切都没有问题。后来，我们的程序性能有问题，所以需要变成多线程的，于是，变成多线程后到了线上，发现程序经常占了100%的CPU，查看堆栈，你会发现程序都Hang在了HashMap.get()这个方法上了，重启程序后问题消失。但是过段时间又会来。而且，这个问题在测试环境里可能很难重现。

我们简单的看一下我们自己的代码，我们就知道HashMap被多个线程操作。而Java的文档说HashMap是非线程安全的，应该用ConcurrentHashMap。

但是在这里我们可以来研究一下原因。

Hash表数据结构

我需要简单地说一下HashMap这个经典的数据结构。

HashMap通常会用一个指针数组（假设为table[]）来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出这个数组的下标i，然后就把这个<key, value>插到table[i]中，如果有两个不同的key被算在了同一个i，那么就叫冲突，又叫碰撞，这样会在table[i]上形成一个链表。

我们知道，如果table[]的尺寸很小，比如只有2个，如果要放进10个keys的话，那么碰撞非常频繁，于是一个O(1)的查找算法，就变成了链表遍历，性能变成了O(n)，这是Hash表的缺陷（可参看《Hash Collision DoS 问题》）。

所以，Hash表的尺寸和容量非常的重要。一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的无素都需要被重算一遍。这叫rehash，这个成本相当的大。

相信大家对这个基础知识已经很熟悉了。

HashMap的rehash源代码

下面，我们来看一下Java的HashMap的源代码。

Put一个Key,Value对到Hash表中：

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

public V put(K key, V value)
{
  ......
  //算Hash值
  int hash = hash(key.hashCode());
  int i = indexFor(hash, table.length);
  //如果该key已被插入，则替换掉旧的value （链接操作）
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      V oldValue = e.value;
      e.value = value;
      e.recordAccess(this);
      return oldValue;
    }
  }
  modCount++;
  //该key不存在，需要增加一个结点
  addEntry(hash, key, value, i);
  return null;
}

检查容量是否超标

1
2
3
4
5
6
7
8

void addEntry(int hash, K key, V value, int bucketIndex)
{
  Entry<K,V> e = table[bucketIndex];
  table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
  if (size++ >= threshold)
    resize(2 * table.length);
}

新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。

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

void resize(int newCapacity)
{
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  ......
  //创建一个新的Hash Table
  Entry[] newTable = new Entry[newCapacity];
  //将Old Hash Table上的数据迁移到New Hash Table上
  transfer(newTable);
  table = newTable;
  threshold = (int)(newCapacity * loadFactor);
}

迁移的源代码，注意高亮处：

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

void transfer(Entry[] newTable)
{
  Entry[] src = table;
  int newCapacity = newTable.length;
  //下面这段代码的意思是：
  //  从OldTable里摘一个元素出来，然后放到NewTable中
  for (int j = 0; j < src.length; j++) {
    Entry<K,V> e = src[j];
    if (e != null) {
      src[j] = null;
      do {
          Entry<K,V> next = e.next;
          int i = indexFor(e.hash, newCapacity);
          e.next = newTable[i];
          newTable[i] = e;
          e = next;
      } while (e != null);
    }
  }
}

好了，这个代码算是比较正常的。而且没有什么问题。

正常的ReHash的过程

画了个图做了个演示。

• 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
• 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。
• 接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程

并发下的Rehash

1）假设我们有两个线程。我用红色和浅蓝色标注了一下。

我们再回头看一下我们的 transfer代码中的这个细节：

1
2
3
4
5
6
7

do {
    Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

而我们的线程二执行完成了。于是我们有下面的这个样子。

注意，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

2）线程一被调度回来执行。

先是执行 newTalbe[i] = e;

然后是e = next，导致了e指向了key(7)，

而下一次循环的next = e.next导致了next指向了key(3)

3）一切安好。

线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。

4）环形链接出现。

e.next = newTable[i] 导致 key(3).next 指向了 key(7)

注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

于是，当我们的线程一调用到，HashTable.get(11)时，悲剧就出现了——Infinite Loop。

其它

有人把这个问题报给了Sun，不过Sun不认为这个是一个问题。因为HashMap本来就不支持并发。要并发就用ConcurrentHashmap

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6423457

我在这里把这个事情记录下来，只是为了让大家了解并体会一下并发环境下的危险。

参考：http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html

转自：http://ifeve.com/java-copy-on-write/

Copy-On-Write简称COW，是一种用于程序设计中的优化策略。其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改，这是一种延时懒惰策略。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用，可以在非常多的并发场景中使用到。

什么是CopyOnWrite容器

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

CopyOnWriteArrayList的实现原理

在使用CopyOnWriteArrayList之前，我们先阅读其源码了解下它是如何实现的。以下代码是向ArrayList里添加元素，可以发现在添加的时候是需要加锁的，否则多线程写的时候会Copy出N个副本出来。

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

public boolean add(T e) {
  final ReentrantLock lock = this.lock;
  lock.lock();
  try {
    Object[] elements = getArray();
    int len = elements.length;
    // 复制出新数组
    Object[] newElements = Arrays.copyOf(elements, len + 1);
    // 把新元素添加到新数组里
    newElements[len] = e;
    // 把原数组引用指向新数组
    setArray(newElements);
    return true;
  } finally {
    lock.unlock();
  }
}

final void setArray(Object[] a) {
  array = a;
}

读的时候不需要加锁，如果读的时候有多个线程正在向ArrayList添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的ArrayList。

1
2
3

public E get(int index) {
  return get(getArray(), index);
}

JDK中并没有提供CopyOnWriteMap，我们可以参考CopyOnWriteArrayList来实现一个，基本代码如下：

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

import java.util.Collection;
import java.util.Map;
import java.util.Set;

public class CopyOnWriteMap<K, V> implements Map<K, V>, Cloneable {
  private volatile Map<K, V> internalMap;

  public CopyOnWriteMap() {
    internalMap = new HashMap<K, V>();
  }

  public V put(K key, V value) {
    synchronized (this) {
      Map<K, V> newMap = new HashMap<K, V>(internalMap);
      V val = newMap.put(key, value);
      internalMap = newMap;
      return val;
    }
  }

  public V get(Object key) {
    return internalMap.get(key);
  }

  public void putAll(Map<? extends K, ? extends V> newData) {
    synchronized (this) {
      Map<K, V> newMap = new HashMap<K, V>(internalMap);
      newMap.putAll(newData);
      internalMap = newMap;
    }
  }
}

实现很简单，只要了解了CopyOnWrite机制，我们可以实现各种CopyOnWrite容器，并且在不同的应用场景中使用。

CopyOnWrite的应用场景

CopyOnWrite并发容器用于读多写少的并发场景。比如白名单，黑名单，商品类目的访问和更新场景，假如我们有一个搜索网站，用户在这个网站的搜索框中，输入关键字搜索内容，但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中，黑名单每天晚上更新一次。当用户搜索时，会检查当前关键字在不在黑名单当中，如果在，则提示不能搜索。实现代码如下：

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

package com.ifeve.book;

import java.util.Map;
import com.ifeve.book.forkjoin.CopyOnWriteMap;

/**
 * 黑名单服务
 *
 * @author fangtengfei
 *
 */
public class BlackListServiceImpl {
  private static CopyOnWriteMap<String, Boolean> blackListMap = new CopyOnWriteMap<String, Boolean>(1000);

  public static boolean isBlackList(String id) {
    return blackListMap.get(id) == null ? false : true;
  }

  public static void addBlackList(String id) {
    blackListMap.put(id, Boolean.TRUE);
  }

  /**
   * 批量添加黑名单
   *
   * @param ids
   */
  public static void addBlackList(Map<String,Boolean> ids) {
    blackListMap.putAll(ids);
  }
}

代码很简单，但是使用CopyOnWriteMap需要注意两件事情：

1. 减少扩容开销。根据实际需要，初始化CopyOnWriteMap的大小，避免写时CopyOnWriteMap扩容的开销。
2. 使用批量添加。因为每次添加，容器每次都会进行复制，所以减少添加次数，可以减少容器的复制次数。如使用上面代码里的addBlackList方法。

CopyOnWrite的缺点

CopyOnWrite容器有很多优点，但是同时也存在两个问题，即内存占用问题和数据一致性问题。所以在开发的时候需要注意一下。

内存占用问题。

因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比如说200M左右，那么再写入100M数据进去，内存就会占用300M，那么这个时候很有可能造成频繁的Yong GC和Full GC。之前我们系统中使用了一个服务由于每晚使用CopyOnWrite机制更新大对象，造成了每晚15秒的Full GC，应用响应时间也随之变长。

针对内存占用问题。

可以通过压缩容器中的元素的方法来减少大对象的内存消耗，比如，如果元素全是10进制的数字，可以考虑把它压缩成36进制或64进制。或者不使用CopyOnWrite容器，而使用其他的并发容器，如ConcurrentHashMap。

数据一致性问题。

CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

关于C++的STL中，曾经也有过Copy-On-Write的玩法，参见陈皓的《C++ STL String类中的Copy-On-Write》，后来，因为有很多线程安全上的事，就被去掉了。

转自：http://blog.csdn.net/shan9liang/article/details/8995023

RPC（Remote Procedure Call Protocol）

RPC 使用 C/S 方式，采用 http 协议，发送请求到服务器，等待服务器返回结果。这个请求包括一个参数集和一个文本集，通常形成“classname.methodname”形式。优点是跨语言跨平台，C 端、S 端有更大的独立性，缺点是不支持对象，无法在编译器检查错误，只能在运行期检查。

Web Service

Web Service 提供的服务是基于 web 容器的，底层使用 http 协议，类似一个远程的服务提供者，比如天气预报服务，对各地客户端提供天气预报，是一种请求应答的机制，是跨系统跨平台的。就是通过一个 servlet，提供服务出去。

首先客户端从服务器得到 WebService 的 WSDL，同时在客户端声称一个代理类（Proxy Class）这个代理类负责与 WebService 服务器进行 Request 和Response 当一个数据（XML 格式的）被封装成 SOAP 格式的数据流发送到服务器端的时候，就会生成一个进程对象并且把接收到这个 Request 的 SOAP 包进行解析，然后对事物进行处理，处理结束以后再对这个计算结果进行 SOAP 包装，然后把这个包作为一个 Response 发送给客户端的代理类（Proxy Class），同样地，这个代理类也对这个 SOAP 包进行解析处理，继而进行后续操作。这就是 WebService 的一个运行过程。

Web Service 大体上分为 5 个层次:

1. Http 传输信道
2. XML 的数据格式
3. SOAP 封装格式
4. WSDL 的描述方式
5. UDDI UDDI 是一种目录服务，企业可以使用它对 Webservices 进行注册和搜索

RMI （Remote Method Invocation）

RMI 采用stubs 和 skeletons 来进行远程对象（remote object）的通讯。stub 充当远程对象的客户端代理，有着和远程对象相同的远程接口，远程对象的调用实际是通过调用该对象的客户端代理对象 stub 来完成的，通过该机制 RMI 就好比它是本地工作，采用 tcp/ip 协议，客户端直接调用服务端上的一些方法。优点是强类型，编译期可检查错误，缺点是只能基于 Java 语言，客户机与服务器紧耦合。

JMS（Java Messaging Service）

JMS 是 Java 的消息服务，JMS 的客户端之间可以通过JMS服务进行异步的消息传输。JMS 支持两种消息模型：Point-to-Point（P2P）和 Publish/Subscribe（Pub/Sub），即点对点和发布订阅模型。

几者的区别与联系

1、RPC 与 RMI

（1）RPC 跨语言，而 RMI只支持Java。

（2）RMI 调用远程对象方法，允许方法返回 Java 对象以及基本数据类型，而RPC 不支持对象的概念，传送到 RPC 服务的消息由外部数据表示（External Data Representation, XDR）语言表示，这种语言抽象了字节序类和数据类型结构之间的差异。只有由 XDR 定义的数据类型才能被传递， 可以说 RMI 是面向对象方式的 Java RPC 。

（3）在方法调用上，RMI 中，远程接口使每个远程方法都具有方法签名。如果一个方法在服务器上执行，但是没有相匹配的签名被添加到这个远程接口上，那么这个新方法就不能被RMI客户方所调用。

在 RPC 中，当一个请求到达 RPC 服务器时，这个请求就包含了一个参数集和一个文本值，通常形成“classname.methodname”的形式。这就向 RPC 服务器表明，被请求的方法在为 “classname”的类中，名叫“methodname”。然后 RPC 服务器就去搜索与之相匹配的类和方法，并把它作为那种方法参数类型的输入。这里的参数类型是与 RPC 请求中的类型是匹配的。一旦匹配成功，这个方法就被调用了，其结果被编码后返回客户方。

2、JMS 和 RMI

采用 JMS 服务，对象是在物理上被异步从网络的某个 JVM 上直接移动到另一个 JVM 上（是消息通知机制）

而 RMI 对象是绑定在本地 JVM 中，只有函数参数和返回值是通过网络传送的（是请求应答机制）。

RMI 一般都是同步的，也就是说，当 client 调用 Server 的一个方法的时候，需要等到对方的返回，才能继续执行 client 端，这个过程调用本地方法感觉上是一样的，这也是 RMI 的一个特点。

JMS 一般只是一个点发出一个 Message 到 Message Server，发出之后一般不会关心谁用了这个 message。
所以，一般 RMI 的应用是紧耦合，JMS 的应用相对来说是松散耦合应用。

3、Webservice 与 RMI

RMI 是在 tcp 协议上传递可序列化的 java 对象，只能用在 java 虚拟机上，绑定语言，客户端和服务端都必须是 java

webservice 没有这个限制，webservice 是在 http 协议上传递 xml 文本文件，与语言和平台无关。

4、Webservice 与 JMS

Webservice 专注于远程服务调用，jms 专注于信息交换。

大多数情况下 Webservice 是两系统间的直接交互（Consumer <–> Producer），而大多数情况下 jms 是三方系统交互（Consumer <- Broker -> Producer）。当然，JMS 也可以实现 request-response 模式的通信，只要 Consumer 或 Producer 其中一方兼任 broker 即可。

JMS 可以做到异步调用完全隔离了客户端和服务提供者，能够抵御流量洪峰；WebService 服务通常为同步调用，需要有复杂的对象转换，相比 SOAP，现在 JSON，rest 都是很好的 http 架构方案；（举一个例子，电子商务的分布式系统中，有支付系统和业务系统，支付系统负责用户付款，在用户在银行付款后需要通知各个业务系统，那么这个时候，既可以用同步也可以用异步，使用异步的好处就能抵御网站暂时的流量高峰，或者能应对慢消费者。）

JMS 是 java 平台上的消息规范。一般 jms 消息不是一个 xml，而是一个 java 对象，很明显，jms 没考虑异构系统，说白了，JMS 就没考虑非 java 的东西。但是好在现在大多数的 jms provider（就是 JMS 的各种实现产品）都解决了异构问题。相比 WebService 的跨平台各有千秋吧。

转自：http://www.tuicool.com/articles/umEBVfI

起因

在 hexo 中使用本地图片是件非常让人纠结的事情，在 markdown 里的图片地址似乎永远无法和最后生成的网页保持一致。

这些问题使得我一度不愿意使用本地图片而选择用图床，但被移动运营商无耻的横条广告逼得打算上 https，图床只支持 http 就成了问题。

hexo 下插入图片现在大概有几个方案

放在根目录

早期大部分的方案是把图片放在 source/img 下，然后在 markdown 里写 ![img](/source/img/img.png) 。显然这样在本地的编辑器里完全不能正确识别图片的位置。

asset-image

在 hexo 2.x 时出现的插件，后来被吸纳进 hexo 3 core ，用法的介绍见 资源文件夹 | Hexo 。比较尴尬的是，这种方法直接放弃了 markdown 原来的语法，使用类似 的语法，。markdown 本来有插入图片的语法不好好支持，专门用一个新的语法来插入本地图片，让我这种强迫症不太能接受。

解决方案

CodeFalling/hexo-asset-image

使用

首先确认 _config.yml 中有 post_asset_folder:true。

在 hexo 目录，执行

npm install https://github.com/CodeFalling/hexo-asset-image --save

假设在

1
2
3
4
5

MacGesture2-Publish
├── apppicker.jpg
├── logo.jpg
└── rules.jpg
MacGesture2-Publish.md

这样的目录结构（目录名和文章名一致），只要使用 ![logo](MacGesture2-Publish/logo.jpg) 就可以插入图片。

生成的结构为

1
2
3
4
5

public/2015/10/18/MacGesture2-Publish
├── apppicker.jpg
├── index.html
├── logo.jpg
└── rules.jpg

同时，生成的 html 是

<img src="/2015/10/18/MacGesture2-Publish/logo.jpg" alt="logo">

而不是愚蠢的

<img src="MacGesture2-Publish/logo.jpg" alt="logo">

在扫描完包初始化数据之后，我们可以通过getBean获取类的实例

通过getBean获取类的实例

1

Annotation annotation = ac.getBean("annotation", Annotation.class);

Spring启动时，读取bean，将每个bean转化为BeanDefinition对象。BeanDefinition保存了一个bean的所有基本信息。

以下是一个BeanDefinition的主要属性：

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

public abstract class AbstractBeanDefinition extends BeanMetadataAttributeAccessor implements BeanDefinition, Cloneable {
    private volatile Object beanClass; // 保存bean的class属性
    private String scope = SCOPE_DEFAULT; // bean是否单例
    private boolean abstractFlag = false; // 保存该bean是否抽象
    private boolean lazyInit = false; // 保存是否延迟初始化
    private int autowireMode = AUTOWIRE_NO; // 保存是否自动装配
    private int dependencyCheck = DEPENDENCY_CHECK_NONE; // 保存是否坚持依赖
    private String[] dependsOn; // 保存该bean依赖于哪些bean
    private boolean autowireCandidate;
    private boolean primary;
    private final Map<String, AutowireCandidateQualifier> qualifiers;
    private boolean nonPublicAccessAllowed;
    private boolean lenientConstructorResolution;
    private ConstructorArgumentValues constructorArgumentValues; // 保存通过构造函数注入的依赖
    private MutablePropertyValues propertyValues; // 保存通过setter方法注入的依赖
    private MethodOverrides methodOverrides;
    private String factoryBeanName;
    private String factoryMethodName;
    private String initMethodName; // 对应init-method属性
    private String destroyMethodName; // 对应destory-method属性
    private boolean enforceInitMethod;
    private boolean enforceDestroyMethod;
    private boolean synthetic;
    private int role;
    private String description;
    private Resource resource;

    ...
}

一般我们可以通过以下方式读取Spring的配置：

1

ApplicationContext ac = new ClassPathXmlApplicationContext("test/applicationContext.xml");

IOC的基本流程：

1. 启动项目后，根据配置文件中配置的扫描路径，扫描带有注解的类，将类的基本信息（构造方法、属性、方法）封装到一个类中，存储到一个map里；
2. 需要获取一个bean的时候，首先去查询该类是否已经实例化，如果没有则去检测是否定义；

组成 Spring 框架的每个模块集合或者模块都可以单独存在，也可以一个或多个模块联合实现。每个模块的组成和功能如下：

1. 核心容器：由spring-beans、spring-core、spring-context和spring-expression（Spring Expression Language, SpEL） 4个模块组成。

• spring-beans和spring-core模块是Spring框架的核心模块，包含了控制反转（Inversion of Control, IoC）和依赖注入（Dependency Injection, DI）。BeanFactory 接口是Spring框架中的核心接口，它是工厂模式的具体实现。BeanFactory 使用控制反转对应用程序的配置和依赖性规范与实际的应用程序代码进行了分离。但 BeanFactory 容器实例化后并不会自动实例化 Bean，只有当 Bean 被使用时 BeanFactory 容器才会对该 Bean 进行实例化与依赖关系的装配。