深入并发包 ConcurrentHashMap

原文出处: pettyandydog
前言
以前写过介绍HashMap的文章,文中提到过HashMap在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。

我们来了解另一个键值存储集合HashTable,它是线程安全的,它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table,这就意味着所有的线程都在竞争一把锁,在多线程的环境下,它是安全的,但是无疑是效率低下的。

其实HashTable有很多的优化空间,锁住整个table这么粗暴的方法可以变相的柔和点,比如在多线程的环境下,对不同的数据集进行操作时其实根本就不需要去竞争一个锁,因为他们不同hash值,不会因为rehash造成线程不安全,所以互不影响,这就是锁分离技术,将锁的粒度降低,利用多个锁来控制多个小的table,这就是这篇文章的主角ConcurrentHashMap JDK1.7版本的核心思想。

ConcurrentHashMap
JDK1.7的实现
在JDK1.7版本中,ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成,如下图所示:

Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁,也就是上面的提到的锁分离技术,而每一个Segment元素存储的是HashEntry数组+链表,这个和HashMap的数据存储结构一样

初始化
ConcurrentHashMap的初始化是会通过位与运算来初始化Segment的大小,用ssize来表示,如下所示

int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}

如上所示,因为ssize用位于运算来计算(ssize <<=1),所以Segment的大小取值都是以2的N次方,无关concurrencyLevel的取值,当然concurrencyLevel最大只能用16位的二进制来表示,即65536,换句话说,Segment的大小最多65536个,没有指定concurrencyLevel元素初始化,Segment的大小ssize默认为16

每一个Segment元素下的HashEntry的初始化也是按照位于运算来计算,用cap来表示,如下所示

int cap = 1;
while (cap < c)
cap <<= 1;
如上所示,HashEntry大小的计算也是2的N次方(cap <<=1), cap的初始值为1,所以HashEntry最小的容量为2

put操作
对于ConcurrentHashMap的数据插入,这里要进行两次Hash去定位数据的存储位置

1
static class Segment extends ReentrantLock implements Serializable {
从上Segment的继承体系可以看出,Segment实现了ReentrantLock,也就带有锁的功能,当执行put操作时,会进行第一次key的hash来定位Segment的位置,如果该Segment还没有初始化,即通过CAS操作进行赋值,然后进行第二次hash操作,找到相应的HashEntry的位置,这里会利用继承过来的锁的特性,在将数据插入指定的HashEntry位置时(链表的尾端),会通过继承ReentrantLock的tryLock()方法尝试去获取锁,如果获取成功就直接插入相应的位置,如果已经有线程获取该Segment的锁,那当前线程会以自旋的方式去继续的调用tryLock()方法去获取锁,超过指定次数就挂起,等待唤醒。

get操作
ConcurrentHashMap的get操作跟HashMap类似,只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置,然后再hash定位到指定的HashEntry,遍历该HashEntry下的链表进行对比,成功就返回,不成功就返回null。

size操作
计算ConcurrentHashMap的元素大小是一个有趣的问题,因为他是并发操作的,就是在你计算size的时候,他还在并发的插入数据,可能会导致你计算出来的size和你实际的size有相差(在你return size的时候,插入了多个数据),要解决这个问题,JDK1.7版本用两种方案。

try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j) ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment seg = segmentAt(segments, j);
if (seg != null) { sum += seg.modCount; int c = seg.count; if (c < 0 || (size += c) RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size,最多三次,比较前后两次计算的结果,结果一致就认为当前没有元素加入,计算的结果是准确的;
第二种方案是如果第一种方案不符合,他就会给每个Segment加上锁,然后计算ConcurrentHashMap的size返回。
JDK1.8的实现
JDK1.8的实现已经摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap,虽然在JDK1.8中还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本。

在深入JDK1.8的put和get实现之前要知道一些常量设计和数据结构,这些是构成ConcurrentHashMap实现结构的基础,下面看一下基本属性:

// node数组最大容量:2^30=1073741824
private static final int MAXIMUM_CAPACITY = 1 < 8 链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//树转链表阀值,小于等于6(tranfer时,lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量,<=UNTREEIFY_THRESHOLD 则untreeify(lo))
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
private static final int MIN_TRANSFER_STRIDE = 16;
private static int RESIZE_STAMP_BITS = 16;
// 2^15-1,help resize的最大线程数
private static final int MAX_RESIZERS = (1 < h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir = 0) { //表示该节点是链表结构
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
//这里涉及到相同的key进行put就会覆盖原先的value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node pred = e;
if ((e = e.next) == null) { //插入链表尾部
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {//红黑树结构
Node p;
binCount = 2;
//红黑树结构旋转插入
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) { //如果链表的长度大于8时就会进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);//统计size,并且检查是否需要扩容
return null;
}
这个put的过程很清晰,对当前的table进行无条件自循环直到put成功,可以分成以下六步流程来概述。

如果没有初始化就先调用initTable()方法来进行初始化过程
如果没有hash冲突就直接CAS插入
如果还在进行扩容操作就先进行扩容
如果存在hash冲突,就加锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入,
最后一个如果该链表的数量大于阈值8,就要先转换成黑红树的结构,break再一次进入循环
如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容
现在我们来对每一步的细节进行源码分析,在第一步中,符合条件会进行初始化操作,我们来看看initTable()方法

/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node[] initTable() {
Node[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {//空的table才能进入初始化操作
if ((sc = sizeCtl) >> 2);//记录下次扩容的大小
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
在第二步中没有hash冲突就直接调用Unsafe的方法CAS插入该元素,进入第三步如果容器正在扩容,则会调用helpTransfer()方法帮助扩容,现在我们跟进helpTransfer()方法看看

/**
*帮助从旧的table的元素复制到新的table中
*/
final Node[] helpTransfer(Node[] tab, Node f) {
Node[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode)f).nextTable) != null) { //新的table nextTba已经存在前提下才能帮助扩容
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) >> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node[] nt = (Node[])new Node[n <= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) stride ?
nextIndex – stride : 0))) {
bound = nextBound;
i = nextIndex – 1;
advance = false;
}
}
if (i = n || i + n >= nextn) {
int sc;
// 已经完成所有节点复制了
if (finishing) {
nextTable = null;
table = nextTab; // table 指向nextTable
sizeCtl = (n > 1); // sizeCtl阈值为原来的1.5倍
return; // 跳出死循环,
}
// CAS 更扩容阈值,在这里面sizectl值减一,说明新加入一个线程参与到扩容操作
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc – 1)) {
if ((sc – 2) != resizeStamp(n) <= 0 ,表示为链表节点
if (fh >= 0) {
// 构造两个链表 一个是原链表 另一个是原链表的反序排列
int runBit = fh & n;
Node lastRun = f;
for (Node p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node(ph, pk, pv, ln);
else
hn = new Node(ph, pk, pv, hn);
}
// 在nextTable i 位置处插上链表
setTabAt(nextTab, i, ln);
// 在nextTable i + n 位置处插上链表
setTabAt(nextTab, i + n, hn);
// 在table i 位置处插上ForwardingNode 表示该节点已经处理过了
setTabAt(tab, i, fwd);
// advance = true 可以执行–i动作,遍历节点
advance = true;
}
// 如果是TreeBin,则按照红黑树进行处理,处理逻辑与上面一致
else if (f instanceof TreeBin) {
TreeBin t = (TreeBin)f;
TreeNode lo = null, loTail = null;
TreeNode hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode p = new TreeNode
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 扩容后树节点个数若<=6,将树转链表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
扩容过程有点复杂,这里主要涉及到多线程并发扩容,ForwardingNode的作用就是支持扩容操作,将已处理的节点和空节点置为ForwardingNode,并发处理时多个线程经过ForwardingNode就表示已经遍历了,就往后遍历,下图是多线程合作扩容的过程:

介绍完扩容过程,我们再次回到put流程,在第四步中是向链表或者红黑树里加节点,到第五步,会调用treeifyBin()方法进行链表转红黑树的过程。

private final void treeifyBin(Node[] tab, int index) {
Node b; int n, sc;
if (tab != null) {
//如果整个table的数量小于64,就扩容至原来的一倍,不转红黑树了
//因为这个阈值扩容可以减少hash冲突,不必要去转红黑树
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n <= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode hd = null, tl = null;
for (Node e = b; e != null; e = e.next) {
//封装成TreeNode
TreeNode p =
new TreeNode(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
//通过TreeBin对象对TreeNode转换成红黑树
setTabAt(tab, index, new TreeBin(hd));
}
}
}
}
}
到第六步表示已经数据加入成功了,现在调用addCount()方法计算ConcurrentHashMap的size,在原来的基础上加一,现在来看看addCount()方法。

private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//更新baseCount,table的数量,counterCells表示元素个数的变化
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
//如果多个线程都在执行,则CAS失败,执行fullAddCount,全部加入count
if (as == null || (m = as.length – 1) = 0) {
Node[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) > RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
//当前线程发起库哦哦让操作,nextTable=null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs < 0 &&
(e = tabAt(tab, (n – 1) & h)) != null) {//读取首节点的Node元素
if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//hash值为负值表示正在扩容,这个时候查的是ForwardingNode的find方法来定位到nextTable来
//查找,查找到就返回
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode,那就往下遍历
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ConcurrentHashMap的get操作的流程很简单,也很清晰,可以分为三个步骤来描述

计算hash值,定位到该table索引位置,如果是首节点符合就返回
如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回
以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null
size操作
最后我们来看下例子中最后获取size的方式int size = map.size();,现在让我们看下size()方法

public int size() {
long n = sumCount();
return ((n (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a; //变化的数量
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
在JDK1.8版本中,对于size的计算,在扩容和addCount()方法就已经有处理了,JDK1.7是在调用size()方法才去计算,其实在并发集合中去计算size是没有多大的意义的,因为size是实时在变的,只能计算某一刻的大小,但是某一刻太快了,人的感知是一个时间段,所以并不是很精确。

总结与思考
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言,ConcurrentHashMap只是增加了同步的操作来控制并发,从JDK1.7版本的ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言,总结如下思考:

JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点)
JDK1.8版本的数据结构变得更加简单,使得操作也更加清晰流畅,因为已经使用synchronized来进行同步,所以不需要分段锁的概念,也就不需要Segment这种数据结构了,由于粒度的降低,实现的复杂度也增加了
JDK1.8使用红黑树来优化链表,基于长度很长的链表的遍历是一个很漫长的过程,而红黑树的遍历效率是很快的,代替一定阈值的链表,这样形成一个最佳拍档
JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock,我觉得有以下几点:
因为粒度降低了,在相对而言的低粒度加锁方式,synchronized并不比ReentrantLock差,在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界,更加的灵活,而在低粒度中,Condition的优势就没有了
JVM的开发团队从来都没有放弃synchronized,而且基于JVM的synchronized优化空间更大,使用内嵌的关键字比使用API更加自然
在大量的数据操作下,对于JVM的内存压力,基于API的ReentrantLock会开销更多的内存,虽然不是瓶颈,但是也是一个选择依据
参考
http://blog.csdn.net/u010412719/article/details/52145145
http://www.jianshu.com/p/e694f1e868ec
https://my.oschina.net/liuxiaomian/blog/880088
https://bentang.me/tech/2016/12/01/jdk8-concurrenthashmap-1/
http://cmsblogs.com/?p=2283

从分布式一致性谈到CAP理论、BASE理论

转自:https://www.cnblogs.com/szlbm/p/5588543.html

问题的提出

在计算机科学领域,分布式一致性是一个相当重要且被广泛探索与论证问题,首先来看三种业务场景。

1、火车站售票

假如说我们的终端用户是一位经常坐火车的旅行家,通常他是去车站的售票处购买车 票,然后拿着车票去检票口,再坐上火车,开始一段美好的旅行—-一切似乎都是那么和谐。想象一下,如果他选择的目的地是杭州,而某一趟开往杭州的火车 只剩下最后一张车票,可能在同一时刻,不同售票窗口的另一位乘客也购买了同一张车票。假如说售票系统没有进行一致性的保障,两人都购票成功了。而在检票口 检票的时候,其中一位乘客会被告知他的车票无效—-当然,现代的中国铁路售票系统已经很少出现这样的问题了。但在这个例子中我们可以看出,终端用户对 于系统的需求非常简单:

“请售票给我,如果没有余票了,请在售票的时候就告诉我票是无效的”

这就对购票系统提出了严格的一致性要求—-系统的数据(本例中指的就是那趟开往杭州的火车的余票数)无论在哪个售票窗口,每时每刻都必须是准确无误的!

2、银行转账

假如我们的终端用户是一位刚毕业的大学生,通常在拿到第一个月工资的时候,都会选 择向家里汇款。当他来到银行柜台,完成转账操作后,银行的柜台服务员会友善地提醒他:”您的转账将在N个工作日后到账!”。此时这名毕业生有一定的沮丧, 会对那名柜台服务员叮嘱:”好吧,多久没关系,钱不要少就好了!”—-这也成为了几乎所有用户对于现代银行系统最基本的需求

3、网上购物

假如说我们的终端用户是一位网购达人,当他看见一件库存量为5的心仪商品,会迅速地确认购买,写下收货地址,然后下单—-然而,在下单的那个瞬间,系统可能会告知该用户:”库存量不足!”。此时绝大部分消费者都会抱怨自己动作太慢,使得心爱的商品被其他人抢走了。

但其实有过网购系统开发经验的工程师一定明白,在商品详情页上显示的那个库存量,通常不是该商品的真实库存量,只有在真正下单购买的时候,系统才会检查该商品的真实库存量。但是,谁在意呢?

问题的解读

对于上面三个例子,相信大家一定看出来了,我们的终端用户在使用不同的计算机产品时对于数据一致性的需求是不一样的:

1、有些系统,既要快速地响应用户,同时还要保证系统的数据对于任意客户端都是真实可靠的,就像火车站售票系统

2、有些系统,需要为用户保证绝对可靠的数据安全,虽然在数据一致性上存在延时,但最终务必保证严格的一致性,就像银行的转账系统

3、有些系统,虽然向用户展示了一些可以说是”错误”的数据,但是在整个系统使用过程中,一定会在某一个流程上对系统数据进行准确无误的检查,从而避免用户发生不必要的损失,就像网购系统

分布一致性的提出

在分布式系统中要解决的一个重要问题就是数据的复制。在我们的日常开发经验中,相 信很多开发人员都遇到过这样的问题:假设客户端C1将系统中的一个值K由V1更新为V2,但客户端C2无法立即读取到K的最新值,需要在一段时间之后才能 读取到。这很正常,因为数据库复制之间存在延时。

分布式系统对于数据的复制需求一般都来自于以下两个原因:

1、为了增加系统的可用性,以防止单点故障引起的系统不可用

2、提高系统的整体性能,通过负载均衡技术,能够让分布在不同地方的数据副本都能够为用户提供服务

数据复制在可用性和性能方面给分布式系统带来的巨大好处是不言而喻的,然而数据复制所带来的一致性挑战,也是每一个系统研发人员不得不面对的。

所谓分布一致性问题,是指在分布式环境中引入数据复制机制之后,不同数据节点之间 可能出现的,并无法依靠计算机应用程序自身解决的数据不一致的情况。简单讲,数据一致性就是指在对一个副本数据进行更新的时候,必须确保也能够更新其他的 副本,否则不同副本之间的数据将不一致。

那么如何解决这个问题?一种思路是”既然是由于延时动作引起的问题,那我可以将写入的动作阻塞,直到数据复制完成后,才完成写入动作”。 没错,这似乎能解决问题,而且有一些系统的架构也确实直接使用了这个思路。但这个思路在解决一致性问题的同时,又带来了新的问题:写入的性能。如果你的应 用场景有非常多的写请求,那么使用这个思路之后,后续的写请求都将会阻塞在前一个请求的写操作上,导致系统整体性能急剧下降。

总得来说,我们无法找到一种能够满足分布式系统所有系统属性的分布式一致性解决方案。因此,如何既保证数据的一致性,同时又不影响系统运行的性能,是每一个分布式系统都需要重点考虑和权衡的。于是,一致性级别由此诞生:

1、强一致性

这种一致性级别是最符合用户直觉的,它要求系统写入什么,读出来的也会是什么,用户体验好,但实现起来往往对系统的性能影响大

2、弱一致性

这种一致性级别约束了系统在写入成功后,不承诺立即可以读到写入的值,也不久承诺多久之后数据能够达到一致,但会尽可能地保证到某个时间级别(比如秒级别)后,数据能够达到一致状态

3、最终一致性

最终一致性是弱一致性的一个特例,系统会保证在一定时间内,能够达到一个数据一致的状态。这里之所以将最终一致性单独提出来,是因为它是弱一致性中非常推崇的一种一致性模型,也是业界在大型分布式系统的数据一致性上比较推崇的模型

分布式环境的各种问题

分布式系统体系结构从其出现之初就伴随着诸多的难题和挑战:

1、通信异常

从集中式向分布式演变的过程中,必然引入网络因素,由于网络本身的不可靠性,因此 也引入了额外的问题。分布式系统需要在各个节点之间进行网络通信,因此每次网络通信都会伴随着网络不可用的风险,网络光纤、路由器或是DNS等硬件设备或 是系统不可用都会导致最终分布式系统无法顺利完成一次网络通信。另外,即使分布式系统各个节点之间的网络通信能够正常进行,其延时也会大于单机操作。通常 我们认为现代计算机体系结构中,单机内存访问的延时在纳秒数量级(通常是10ns),而正常的一次网络通信的延迟在0.1~1ms左右(相当于内存访问延 时的105倍),如此巨大的延时差别,也会影响到消息的收发过程,因此消息丢失和消息延迟变得非常普遍

2、网络分区

当网络由于发生异常情况,导致分布式系统中部分节点之间的网络延时不断增大,最终导致组成分布式系统的所有节点中,只有部分节点之间能够正常通信,而另一些节点则不能—-我们将这个现象称为网络分区。当网络分区出现时,分布式系统会出现局部小集群,在极端情况下,这些局部小集群会独立完成原本需要整个分布式系统才能完成的功能,包括对数据的事物处理,这就对分布式一致性提出了非常大的挑战

3、三态

上面两点,我们已经了解到在分布式环境下,网络可能会出现各式各样的问题,因此分布式系统的每一次请求与响应,存在特有的三态概念,即成功、失败、超时。 在传统的单机系统中,应用程序在调用一个函数之后,能够得到一个非常明确的响应:成功或失败。而在分布式系统中,由于网络是不可靠的,虽然在绝大部分情况 下,网络通信也能够接受到成功或失败的响应,当时当网络出现异常的情况下,就可能会出现超时现象,通常有以下两种情况:

(1)由于网络原因,该请求并没有被成功地发送到接收方,而是在发送过程中就发生了消息丢失现象

(2)该请求成功地被接收方接收后,进行了处理,但是在将响应反馈给发送方的过程中,发生了消息丢失现象

当出现这样的超时现象时,网络通信的发起方是无法确定当前请求是否被成功处理的

4、节点故障

节点故障则是分布式环境下另一个比较常见的问题,指的是组成分布式系统的服务器节点出现的宕机或”僵死”现象,通常根据经验来说,每个节点都有可能出现故障,并且每天都在发生

分布式事物

随着分布式计算的发展,事物在分布式计算领域也得到了广泛的应用。在单机数据库中,我们很容易能够实现一套满足ACID特性的事物处理系统,但在分布式数据库中,数据分散在各台不同的机器上,如何对这些数据进行分布式的事物处理具有非常大的挑战。

分布式事物是指事物的参与者、支持事物的服务器、资源服务器以及事物管理器分别位于分布式系统的不同节点上,通常一个分布式事物中会涉及对多个数据源或业务系统的操作。

可以设想一个最典型的分布式事物场景:一个跨银行的转账操作涉及调用两个异地的银 行服务,其中一个是本地银行提供的取款服务,另一个则是目标银行提供的存款服务,这两个服务本身是无状态并且相互独立的,共同构成了一个完整的分布式事 物。如果从本地银行取款成功,但是因为某种原因存款服务失败了,那么就必须回滚到取款之前的状态,否则用户可能会发现自己的钱不翼而飞了。

从这个例子可以看到,一个分布式事务可以看做是多个分布式的操作序列组成的,例如 上面例子的取款服务和存款服务,通常可以把这一系列分布式的操作序列称为子事物。因此,分布式事务也可以被定义为一种嵌套型的事物,同时也就具有了 ACID事物特性。但由于在分布式事务中,各个子事物的执行是分布式的,因此要实现一种能够保证ACID特性的分布式事物处理系统就显得格外复杂。

CAP理论

一个经典的分布式系统理论。CAP理论告诉我们:一个分布式系统不可能同时满足一致性(C:Consistency)、可用性(A:Availability)和分区容错性(P:Partition tolerance)这三个基本需求,最多只能同时满足其中两项。

1、一致性

在分布式环境下,一致性是指数据在多个副本之间能否保持一致的特性。在一致性的需求下,当一个系统在数据一致的状态下执行更新操作后,应该保证系统的数据仍然处于一直的状态。

对于一个将数据副本分布在不同分布式节点上的系统来说,如果对第一个节点的数据进 行了更新操作并且更新成功后,却没有使得第二个节点上的数据得到相应的更新,于是在对第二个节点的数据进行读取操作时,获取的依然是老数据(或称为脏数 据),这就是典型的分布式数据不一致的情况。在分布式系统中,如果能够做到针对一个数据项的更新操作执行成功后,所有的用户都可以读取到其最新的值,那么 这样的系统就被认为具有强一致性

2、可用性

可用性是指系统提供的服务必须一直处于可用的状态,对于用户的每一个操作请求总是能够在有限的时间内返回结果。这里的重点是”有限时间内”和”返回结果”。

“有限时间内”是指,对于用户的一个操作请求,系统必须能够在指定的时间内返回对 应的处理结果,如果超过了这个时间范围,那么系统就被认为是不可用的。另外,”有限的时间内”是指系统设计之初就设计好的运行指标,通常不同系统之间有很 大的不同,无论如何,对于用户请求,系统必须存在一个合理的响应时间,否则用户便会对系统感到失望。

“返回结果”是可用性的另一个非常重要的指标,它要求系统在完成对用户请求的处理后,返回一个正常的响应结果。正常的响应结果通常能够明确地反映出队请求的处理结果,即成功或失败,而不是一个让用户感到困惑的返回结果。

3、分区容错性

分区容错性约束了一个分布式系统具有如下特性:分布式系统在遇到任何网络分区故障的时候,仍然需要能够保证对外提供满足一致性和可用性的服务,除非是整个网络环境都发生了故障。

网络分区是指在分布式系统中,不同的节点分布在不同的子网络(机房或异地网络) 中,由于一些特殊的原因导致这些子网络出现网络不连通的状况,但各个子网络的内部网络是正常的,从而导致整个系统的网络环境被切分成了若干个孤立的区域。 需要注意的是,组成一个分布式系统的每个节点的加入与退出都可以看作是一个特殊的网络分区。

既然一个分布式系统无法同时满足一致性、可用性、分区容错性三个特点,所以我们就需要抛弃一样:

用一张表格说明一下:

选 择 说 明
CA 放弃分区容错性,加强一致性和可用性,其实就是传统的单机数据库的选择
AP 放弃一致性(这里说的一致性是强一致性),追求分区容错性和可用性,这是很多分布式系统设计时的选择,例如很多NoSQL系统就是如此
CP 放弃可用性,追求一致性和分区容错性,基本不会选择,网络问题会直接让整个系统不可用
需要明确的一点是,对于一个分布式系统而言,分区容错性是一个最基本的要求。因为 既然是一个分布式系统,那么分布式系统中的组件必然需要被部署到不同的节点,否则也就无所谓分布式系统了,因此必然出现子网络。而对于分布式系统而言,网 络问题又是一个必定会出现的异常情况,因此分区容错性也就成为了一个分布式系统必然需要面对和解决的问题。因此系统架构师往往需要把精力花在如何根据业务 特点在C(一致性)和A(可用性)之间寻求平衡。

BASE理论

BASE是Basically Available(基本可用)、Soft state(软状态)和Eventually consistent(最终一致性)三个短语的缩写。BASE理论是对CAP中一致性和可用性权衡的结果,其来源于对大规模互联网系统分布式实践的总结, 是基于CAP定理逐步演化而来的。BASE理论的核心思想是:即使无法做到强一致性,但每个应用都可以根据自身业务特点,采用适当的方式来使系统达到最终一致性。接下来看一下BASE中的三要素:

1、基本可用

基本可用是指分布式系统在出现不可预知故障的时候,允许损失部分可用性—-注意,这绝不等价于系统不可用。比如:

(1)响应时间上的损失。正常情况下,一个在线搜索引擎需要在0.5秒之内返回给用户相应的查询结果,但由于出现故障,查询结果的响应时间增加了1~2秒

(2)系统功能上的损失:正常情况下,在一个电子商务网站上进行购物的时候,消费者几乎能够顺利完成每一笔订单,但是在一些节日大促购物高峰的时候,由于消费者的购物行为激增,为了保护购物系统的稳定性,部分消费者可能会被引导到一个降级页面

2、软状态

软状态指允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时

3、最终一致性

最终一致性强调的是所有的数据副本,在经过一段时间的同步之后,最终都能够达到一个一致的状态。因此,最终一致性的本质是需要系统保证最终数据能够达到一致,而不需要实时保证系统数据的强一致性。

总的来说,BASE理论面向的是大型高可用可扩展的分布式系统,和传统的事物ACID特性是相反的,它完全不同于ACID的强一致性模型,而是通过牺牲强一致性来获得可用性,并允许数据在一段时间内是不一致的,但最终达到一致状态。但同时,在实际的分布式场景中,不同业务单元和组件对数据一致性的要求是不同的,因此在具体的分布式系统架构设计过程中,ACID特性和BASE理论往往又会结合在一起。

简析CAS机制与实现原理(转)

转自:https://blog.csdn.net/u012722531/article/details/78223113

在学习CAS的过程中,我百思不得其解的一个问题就是在多cpu并发的环境下,CAS如何保证线程的安全性呢?关于这个问题下面的两篇博客写的比较不错,基本把其中的原理解释清楚了,这里我只作一个简单的阐述。

http://m.blog.csdn.net/wbb_1216/article/details/62882921

http://m.blog.sina.com.cn/s/blog_ee34aa660102wsuv.html#page=7

一.锁机制的缺点
在jdk5以前,java基本只有靠synchronized关键字来保证同步,这会导致需要同步的对象被加上独占锁,也就是我们常说的悲观锁。悲观锁存在一些问题,典型的如:

1.在多线程竞争下,加锁和释放锁会导致比较多的上下文切换和调度延时,引起性能问题。

2.一个线程持有锁会导致其他所有需要此锁的线程挂起

与悲观锁对应的是乐观锁,乐观锁在处理某些场景的时候有更好的表现,所谓乐观锁就是认为在并发场景下大部分时候都不会产生冲突,因此每次读写数据读不加锁而是假设没有冲突去完成某项操作,如果因为冲突失败就重试,直到成功为止。乐观锁用到的机制就是CAS。

二.什么是CAS
CAS操作包含三个操作数——内存位置(V),预期原值(A)和新值(B)。如果内存位置的值与预期原值相匹配,那么处理器将会自动将该位置值更新为新值,否则,不做任何操作。无论哪种情况,它都会在CAS指令之前返回该位置的值。

通过以上定义我们知道CAS其实是有三个步骤的

1.读取内存中的值

2.将读取的值和预期的值比较

3.如果比较的结果符合预期,则写入新值

现在的CPU都支持“读-比较-修改”原子操作,也就是一个cpu在执行这个操作的时候,是绝对不会被其他线程中断的,但是多cpu环境就不一定了。可能在cpu1执行完比较操作准备修改的时候,另一块cpu2火速完成了一次“读-比较-修改”操作从而让内存中的值发生变化。而此时cpu1再写入明显就不对了。并且这个场景也并没有违背该命令的原子性。

解决这个问题的答案其实也很简单,那就是就是volatile。我之前的一篇博客讨论了volitile变量的写入机制,volatile的官方解释是可以保证可见性、顺序性、一致性。下面简单解读一下这三个特性:

可见性:volatile修饰的对象在加载时会告知JVM,对象在cpu的缓存上对多个线程是同时可见的。

顺序性:这里有JVM内存屏障的概念,可以简单理解为:可以保证线程操作对象时是顺序执行的不会进行指令重排序

一致性:可以保证多个线程读取数据时,读到的数据是最新的。

在上面的场景中,解决问题的关键就是volatile的一致性,volitile的写操作是安全的,因为他在写入的时候lock声言会锁住cpu总线导致其他CPU不能访问内存(现在多用缓存一致性协议,处理器嗅探总线上传播的数据来判断自己缓存的值是否过期),所以,写入的时候若其他cpu修改了内存值,那么写入会失败。上面的问题中,由于cpu1的CAS指令执行一半的时候cpu2火速修改了变量的值,因此这就让该变量在所有cpu上的缓存失效,cpu1在进行写入操作的时候,也会发现自己的缓存失效,那么CAS操作就会失败(在java的automicinteger中,会不停的CAS直到成功)。所以即使是在多cpu多线程环境下,CAS机制依然能够保证线程的安全。

但是CAS也并非完美的,CAS存在3个问题,ABA问题,循环时间长的话开销大(也就是说多冲突环境下乐观锁的重试消耗大),以及只能保证一个共享变量的原子操作,本文就不再详细讨论了。

HTTP1.0、HTTP1.1 和 HTTP2.0 的区别

一、HTTP的历史

早在 HTTP 建立之初,主要就是为了将超文本标记语言(HTML)文档从Web服务器传送到客户端的浏览器。也是说对于前端来说,我们所写的HTML页面将要放在我们的 web 服务器上,用户端通过浏览器访问url地址来获取网页的显示内容,但是到了 WEB2.0 以来,我们的页面变得复杂,不仅仅单纯的是一些简单的文字和图片,同时我们的 HTML 页面有了 CSS,Javascript,来丰富我们的页面展示,当 ajax 的出现,我们又多了一种向服务器端获取数据的方法,这些其实都是基于 HTTP 协议的。同样到了移动互联网时代,我们页面可以跑在手机端浏览器里面,但是和 PC 相比,手机端的网络情况更加复杂,这使得我们开始了不得不对 HTTP 进行深入理解并不断优化过程中。

二、HTTP的基本优化

影响一个 HTTP 网络请求的因素主要有两个:带宽和延迟。

带宽:如果说我们还停留在拨号上网的阶段,带宽可能会成为一个比较严重影响请求的问题,但是现在网络基础建设已经使得带宽得到极大的提升,我们不再会担心由带宽而影响网速,那么就只剩下延迟了。

延迟:

浏览器阻塞(HOL blocking):浏览器会因为一些原因阻塞请求。浏览器对于同一个域名,同时只能有 4 个连接(这个根据浏览器内核不同可能会有所差异),超过浏览器最大连接数限制,后续请求就会被阻塞。

DNS 查询(DNS Lookup):浏览器需要知道目标服务器的 IP 才能建立连接。将域名解析为 IP 的这个系统就是 DNS。这个通常可以利用DNS缓存结果来达到减少这个时间的目的。

建立连接(Initial connection):HTTP 是基于 TCP 协议的,浏览器最快也要在第三次握手时才能捎带 HTTP 请求报文,达到真正的建立连接,但是这些连接无法复用会导致每次请求都经历三次握手和慢启动。三次握手在高延迟的场景下影响较明显,慢启动则对文件类大请求影响较大。

三、HTTP1.0和HTTP1.1的一些区别

HTTP1.0最早在网页中使用是在1996年,那个时候只是使用一些较为简单的网页上和网络请求上,而HTTP1.1则在1999年才开始广泛应用于现在的各大浏览器网络请求中,同时HTTP1.1也是当前使用最为广泛的HTTP协议。 主要区别主要体现在:

缓存处理,在HTTP1.0中主要使用header里的If-Modified-Since,Expires来做为缓存判断的标准,HTTP1.1则引入了更多的缓存控制策略例如Entity tag,If-Unmodified-Since, If-Match, If-None-Match等更多可供选择的缓存头来控制缓存策略。

带宽优化及网络连接的使用,HTTP1.0中,存在一些浪费带宽的现象,例如客户端只是需要某个对象的一部分,而服务器却将整个对象送过来了,并且不支持断点续传功能,HTTP1.1则在请求头引入了range头域,它允许只请求资源的某个部分,即返回码是206(Partial Content),这样就方便了开发者自由的选择以便于充分利用带宽和连接。

错误通知的管理,在HTTP1.1中新增了24个错误状态响应码,如409(Conflict)表示请求的资源与资源的当前状态发生冲突;410(Gone)表示服务器上的某个资源被永久性的删除。

Host头处理,在HTTP1.0中认为每台服务器都绑定一个唯一的IP地址,因此,请求消息中的URL并没有传递主机名(hostname)。但随着虚拟主机技术的发展,在一台物理服务器上可以存在多个虚拟主机(Multi-homed Web Servers),并且它们共享一个IP地址。HTTP1.1的请求消息和响应消息都应支持Host头域,且请求消息中如果没有Host头域会报告一个错误(400 Bad Request)。

长连接,HTTP 1.1支持长连接(PersistentConnection)和请求的流水线(Pipelining)处理,在一个TCP连接上可以传送多个HTTP请求和响应,减少了建立和关闭连接的消耗和延迟,在HTTP1.1中默认开启Connection: keep-alive,一定程度上弥补了HTTP1.0每次请求都要创建连接的缺点。

四、HTTPS与HTTP的一些区别

HTTPS协议需要到CA申请证书,一般免费证书很少,需要交费。

HTTP协议运行在TCP之上,所有传输的内容都是明文,HTTPS运行在SSL/TLS之上,SSL/TLS运行在TCP之上,所有传输的内容都经过加密的。

HTTP和HTTPS使用的是完全不同的连接方式,用的端口也不一样,前者是80,后者是443。

HTTPS可以有效的防止运营商劫持,解决了防劫持的一个大问题。

五、SPDY:HTTP1.x的优化

2012年google如一声惊雷提出了SPDY的方案,优化了HTTP1.X的请求延迟,解决了HTTP1.X的安全性,具体如下:

降低延迟,针对HTTP高延迟的问题,SPDY优雅的采取了多路复用(multiplexing)。多路复用通过多个请求stream共享一个tcp连接的方式,解决了HOL blocking的问题,降低了延迟同时提高了带宽的利用率。

请求优先级(request prioritization)。多路复用带来一个新的问题是,在连接共享的基础之上有可能会导致关键请求被阻塞。SPDY允许给每个request设置优先级,这样重要的请求就会优先得到响应。比如浏览器加载首页,首页的html内容应该优先展示,之后才是各种静态资源文件,脚本文件等加载,这样可以保证用户能第一时间看到网页内容。

header压缩。前面提到HTTP1.x的header很多时候都是重复多余的。选择合适的压缩算法可以减小包的大小和数量。

基于HTTPS的加密协议传输,大大提高了传输数据的可靠性。

服务端推送(server push),采用了SPDY的网页,例如我的网页有一个sytle.css的请求,在客户端收到sytle.css数据的同时,服务端会将sytle.js的文件推送给客户端,当客户端再次尝试获取sytle.js时就可以直接从缓存中获取到,不用再发请求了。SPDY构成图:

SPDY位于HTTP之下,TCP和SSL之上,这样可以轻松兼容老版本的HTTP协议(将HTTP1.x的内容封装成一种新的frame格式),同时可以使用已有的SSL功能。

六、HTTP2.0性能惊人

HTTP/2: the Future of the Internet https://link.zhihu.com/?target=https://http2.akamai.com/demo 是 Akamai 公司建立的一个官方的演示,用以说明 HTTP/2 相比于之前的 HTTP/1.1 在性能上的大幅度提升。 同时请求 379 张图片,从Load time 的对比可以看出 HTTP/2 在速度上的优势。

七、HTTP2.0:SPDY的升级版

HTTP2.0可以说是SPDY的升级版(其实原本也是基于SPDY设计的),但是,HTTP2.0 跟 SPDY 仍有不同的地方,如下:

HTTP2.0和SPDY的区别:

HTTP2.0 支持明文 HTTP 传输,而 SPDY 强制使用 HTTPS

HTTP2.0 消息头的压缩算法采用 HPACK http://http2.github.io/http2-spec/compression.html,而非 SPDY 采用的 DEFLATE http://zh.wikipedia.org/wiki/DEFLATE

八、HTTP2.0和HTTP1.X相比的新特性

新的二进制格式(Binary Format),HTTP1.x的解析是基于文本。基于文本协议的格式解析存在天然缺陷,文本的表现形式有多样性,要做到健壮性考虑的场景必然很多,二进制则不同,只认0和1的组合。基于这种考虑HTTP2.0的协议解析决定采用二进制格式,实现方便且健壮。

多路复用(MultiPlexing),即连接共享,即每一个request都是是用作连接共享机制的。一个request对应一个id,这样一个连接上可以有多个request,每个连接的request可以随机的混杂在一起,接收方可以根据request的 id将request再归属到各自不同的服务端请求里面。

header压缩,如上文中所言,对前面提到过HTTP1.x的header带有大量信息,而且每次都要重复发送,HTTP2.0使用encoder来减少需要传输的header大小,通讯双方各自cache一份header fields表,既避免了重复header的传输,又减小了需要传输的大小。

服务端推送(server push),同SPDY一样,HTTP2.0也具有server push功能。

九、HTTP2.0的升级改造

前文说了HTTP2.0其实可以支持非HTTPS的,但是现在主流的浏览器像chrome,firefox表示还是只支持基于 TLS 部署的HTTP2.0协议,所以要想升级成HTTP2.0还是先升级HTTPS为好。

当你的网站已经升级HTTPS之后,那么升级HTTP2.0就简单很多,如果你使用NGINX,只要在配置文件中启动相应的协议就可以了,可以参考NGINX白皮书,NGINX配置HTTP2.0官方指南 https://www.nginx.com/blog/nginx-1-9-5/。

使用了HTTP2.0那么,原本的HTTP1.x怎么办,这个问题其实不用担心,HTTP2.0完全兼容HTTP1.x的语义,对于不支持HTTP2.0的浏览器,NGINX会自动向下兼容的。

十、附注

HTTP2.0的多路复用和HTTP1.X中的长连接复用有什么区别?

HTTP/1.* 一次请求-响应,建立一个连接,用完关闭;每一个请求都要建立一个连接;

HTTP/1.1 Pipeling解决方式为,若干个请求排队串行化单线程处理,后面的请求等待前面请求的返回才能获得执行机会,一旦有某请求超时等,后续请求只能被阻塞,毫无办法,也就是人们常说的线头阻塞;

HTTP/2多个请求可同时在一个连接上并行执行。某个请求任务耗时严重,不会影响到其它连接的正常执行;
具体如图:

服务器推送到底是什么?
服务端推送能把客户端所需要的资源伴随着index.html一起发送到客户端,省去了客户端重复请求的步骤。正因为没有发起请求,建立连接等操作,所以静态资源通过服务端推送的方式可以极大地提升速度。具体如下:

普通的客户端请求过程:

服务端推送的过程:

为什么需要头部压缩?
假定一个页面有100个资源需要加载(这个数量对于今天的Web而言还是挺保守的), 而每一次请求都有1kb的消息头(这同样也并不少见,因为Cookie和引用等东西的存在), 则至少需要多消耗100kb来获取这些消息头。HTTP2.0可以维护一个字典,差量更新HTTP头部,大大降低因头部传输产生的流量。具体参考:HTTP/2 头部压缩技术介绍

HTTP2.0多路复用有多好?
HTTP 性能优化的关键并不在于高带宽,而是低延迟。TCP 连接会随着时间进行自我「调谐」,起初会限制连接的最大速度,如果数据成功传输,会随着时间的推移提高传输的速度。这种调谐则被称为 TCP 慢启动。由于这种原因,让原本就具有突发性和短时性的 HTTP 连接变的十分低效。
HTTP/2 通过让所有数据流共用同一个连接,可以更有效地使用 TCP 连接,让高带宽也能真正的服务于 HTTP 的性能提升。

十一、参考

HTTP/2.0 相比1.0有哪些重大改进?
深入研究:HTTP2 的真正性能到底如何
HTTP/2 头部压缩技术介绍