#多版本并发控制(MVCC)

问题

最近项目中遇到了一个分布式系统的并发控制问题。该问题可以抽象为：某分布式系统由一个数据中心D和若干业务处理中心L1，L2 … Ln组成；D本质上是一个key-value存储，它对外提供基于HTTP协议的CRUD操作接口。L的业务逻辑可以抽象为下面3个步骤：

read: 根据keySet {k1, … kn}从D获取keyValueSet {k1:v1, … kn:vn}
do: 根据keyValueSet进行业务处理，得到需要更新的数据集keyValueSet’ {k1′:v1′, … km’:vm’} (注：读取的keySet和更新的keySet’可能不同)
update: 把keyValueSet’更新到D （注：D保证在一次调用更新多个key的原子性）

在没有事务支持的情况下，多个L进行并发处理可能会导致数据一致性问题。比如，考虑L1和L2的如下执行顺序：

L1从D读取key:123对应的值100
L2从D读取key:123对应的100
L1将key:123更新为100 + 1
L2将key:123更新为100 + 2

如果L1和L2串行执行，key:123对应的值将为103，但上面并发执行中L1的执行效果完全被L2所覆盖，实际key:123所对应的值变成了102。

解决方案1：基于锁的事务

为了让L的处理具有可串行化特性(Serializability)，一种最直接的解决方案就是考虑为D加上基于锁的简单事务。让L在进行业务处理前先锁定D，完成以后释放锁。另外，为了防止持有锁的L由于某种原因长时间未提交事务，D还需要具有超时机制，当L尝试提交一个已超时的事务时会得到一个错误响应。

本方案的优点是实现简单，缺点是锁定了整个数据集，粒度太大；时间上包含了L的整个处理时间，跨度太长。虽然我们可以考虑把锁定粒度降低到数据项级别，按key进行锁定，但这又会带来其他的问题。由于更新的keySet’可能是事先不确定的，所以可能无法在开始事务时锁定所有的key；如果分阶段来锁定需要的key，又可能出现死锁(Deadlock)问题。另外，按key锁定在有锁争用的情况下并不能解决锁定时间太长的问题。所以，按key锁定仍然存在重要的不足之处。
解决方案2：多版本并发控制

为了实现可串行化，同时避免锁机制存在的各种问题，我们可以采用基于多版本并发控制（Multiversion concurrency control，MVCC）思想的无锁事务机制。人们一般把基于锁的并发控制机制称成为悲观机制，而把MVCC机制称为乐观机制。这是因为锁机制是一种预防性的，读会阻塞写，写也会阻塞读，当锁定粒度较大，时间较长时并发性能就不会太好；而MVCC是一种后验性的，读不阻塞写，写也不阻塞读，等到提交的时候才检验是否有冲突，由于没有锁，所以读写不会相互阻塞，从而大大提升了并发性能。我们可以借用源代码版本控制来理解MVCC，每个人都可以自由地阅读和修改本地的代码，相互之间不会阻塞，只在提交的时候版本控制器会检查冲突，并提示merge。目前，Oracle、PostgreSQL和MySQL都已支持基于MVCC的并发机制，但具体实现各有不同。

MVCC的一种简单实现是基于CAS（Compare-and-swap）思想的有条件更新（Conditional Update）。普通的update参数只包含了一个keyValueSet’，Conditional Update在此基础上加上了一组更新条件conditionSet { … data[keyx]=valuex, … }，即只有在D满足更新条件的情况下才将数据更新为keyValueSet’；否则，返回错误信息。这样，L就形成了如下图所示的Try/Conditional Update/(Try again)的处理模式：

虽然对单个L来讲不能保证每次都成功更新，但从整个系统来看，总是有任务能够顺利进行。这种方案利用Conditional Update避免了大粒度和长时间的锁定，当各个业务之间资源争用不大的情况下，并发性能很好。不过，由于Conditional Update需要更多的参数，如果condition中value的长度很长，那么每次网络传送的数据量就会比较大，从而导致性能下降。特别是当需要更新的keyValueSet’很小，而condition很大时，就显得非常不经济。

为了避免condition太大所带来的性能问题，可以为每条数据项增加一个int型的版本号字段，由D维护该版本号，每次数据有更新就增加版本号；L在进行Conditional Update时，通过版本号取代具体的值。

另一个问题是上面的解决方案假设了D是可以支持Conditional Update的；那么，如果D是一个不支持Conditional Update的第三方的key-value存储怎么办呢？这时，我们可以在L和D之间增加一个P作为代理，所有的CRUD操作都必须经过P，让P来进行条件检查，而实际的数据操作放在D。这种方式实现了条件检查和数据操作的分离，但同时降低了性能，需要在P中增加cache，提升性能。由于P是D的唯一客户端；所以，P的cache管理是非常简单的，不必像多客户端情形担心缓存的失效。不过，实际上，据我所知redis和Amazon SimpleDB都已经有了Conditional Update的支持。
悲观锁和MVCC对比

上面介绍了悲观锁和MVCC的基本原理，但是对于它们分别适用于什么场合，不同的场合下两种机制优劣具体表现在什么地方还不是很清楚。这里我就对一些典型的应用场景进行简单的分析。需要注意的是下面的分析不针对分布式，悲观锁和MVCC两种机制在分布式系统、单数据库系统、甚至到内存变量各个层次都存在。

场景1：对读的响应速度要求高

有一类系统更新特别频繁，并且对读的响应速度要求很高，如股票交易系统。在悲观锁机制下，写会阻塞读，那么当有写操作时，读操作的响应速度就会受到影响；而MVCC不存在读写锁，读操作是不受任何阻塞的，所以读的响应速度会更快更稳定。

场景2：读远多于写

对于许多系统来讲，读操作的比例往往远大于写操作，特别是某些海量并发读的系统。在悲观锁机制下，当有写操作占用锁，就会有大量的读操作被阻塞，影响并发性能；而MVCC可以保持比较高且稳定的读并发能力。

场景3：写操作冲突频繁

如果系统中写操作的比例很高，且冲突频繁，这时就需要仔细评估。假设两个有冲突的业务L1和L2，它们在单独执行是分别耗时t1，t2。在悲观锁机制下，它们的总时间大约等于串行执行的时间：

T = t1 + t2

而在MVCC下，假设L1在L2之前更新，L2需要retry一次，它们的总时间大约等于L2执行两次的时间（这里假设L2的两次执行耗时相等，更好的情况是，如果第1次能缓存下部分有效结果，第二次执行L2耗时是可能减小的）：

T’ = 2 * t2

这时关键是要评估retry的代价，如果retry的代价很低，比如，对某个计数器递增，又或者第二次执行可以比第一次快很多，这时采用MVCC机制就比较适合。反之，如果retry的代价很大，比如，报表统计运算需要算几小时甚至一天那就应该采用锁机制避免retry。

从上面的分析，我们可以简单的得出这样的结论：对读的响应速度和并发性要求比较高的场景适合MVCC；而retry代价越大的场景越适合悲观锁机制。
总结

本文介绍了一种基于多版本并发控制（MVCC）思想的Conditional Update解决分布式系统并发控制问题的方法。和基于悲观锁的方法相比，该方法避免了大粒度和长时间的锁定，能更好地适应对读的响应速度和并发性要求高的场景。

缓存问题

通常项目中是在保存数据时，清空缓存，从数据库获取数据时，将获取到数据同时写入到缓存中。

情况一

1、保存pojo，清除缓存；

2、通过get获取pojo对象，将pojo写入缓存；

3、处理pojo，提交到数据库；

4、提交异常，如数据库字段长度不够，导致数据无法保存，此时已经将修改后的pojo对象写入到了缓存中，但是数据库由于异常，数据没有真正写入。

5、通过get获取pojo，处理后保存到数据库，此时会将脏数据库保存到数据库中。

情况二

1、修改数据，删除缓存；

2、在事务未提交之前，另一个用户查询数据时会将旧数据写入缓存；

3、提交事务

4、获取数据时发现缓存中已存在数据，此时获取到就数据；

解决方案：

情况一、在保存时记录缓存的key，检测到异常，将缓存的key从缓存中删除。

情况二、在保存数据删除缓存时记录删除缓存的key，在事务提交后，再次从缓存中删除该key。

###避免死锁
死锁满足的条件：

1. 互斥条件：一个资源每次只能被一个线程使用。

2. 请求与保持条件：一个进程因请求资源而阻塞时，对已经获得的资源保持不放

3. 不剥夺条件：进程已经获得的资源，在未使用之前，不能强行剥夺

4. 循环等待：若干进程直接形成一种头尾相接的循环等待关系

解决死锁：
​ 只要打破死锁必要条件中的一个就可以解决死锁问题

###减小锁的持有时间

1
2
3
4
5

public synchronized void someMethod(){
    method1();
    method2();
    method3();
}

如果只有method2是需要同步的，而method1和method3不需要同步的话，直接在method2执行时进行同步，这样可明显减少锁的持有时间，提高系统的吞吐量。

1
2
3
4
5
6
7

public void someMethod() {
    method1();
    synchronized (this) {
        method2();
    }
    method3();
}

###减少锁粒度
JDK并发中的ConcurrentHashMap很好的使用拆分锁对象的方式提高ConcurrentHashMap的吞吐量，ConcurrentHashMap将整个HashMap分成若干个段(Segment),
每一个段都是一个子HashMap，如果需要在ConcurrentHashMap中增加一个新的表列，并不是整个ConcurrentHashMap加锁，而是根据hashcode得到该表的项应该放
到哪个段中，然后对这个段加锁，并完成put()操作,只要加入的表项不存在同一个段中，则线程之间可以实现真正的并行。

然而减少锁粒度会引入一个新的问题，如果要获取全局锁的时候，消耗的资源会比较多。如ConcurrentHashMap中put()方法很好的分离了锁，但是在获取全局信息
如获取size()的时候，它将返回所有段的数量之和，而获取的时候需要获取所有段的锁，事实上，size()方法先使用无锁的方式求和，如果失败后才会尝试使用加锁
的方式获取。但在高并发的场景中，size()方法的性能仍然差于SynchronizedHashMap,因此，只有在类似于size()获取全局信息调用不频繁的时候，这种减小锁
粒度的方法才能真正的提高系统吞吐量。

1. redis有各种复杂的数据结构list, has, set。也就是说，对于一个(key, value)，value的类型可以是list, hash, set。在实际应用场景中，很容易出现多个客户端对同一个key的这个复杂的value数据结构进行并发操作，如果是多线程，势必要引入锁，而锁却是性能杀手。相比较而言，memcached只有简单的get/set/add操作，没有复杂数据结构，在互斥这个问题上，没有redis那么严重。
2. 对于纯内存操作来说，cpu并不是瓶颈，瓶颈在网络IO上。所以即使单线程，也很快。另外，如果要利用多核的优势，可以在一个机器上开多个redis实例。

##一致性hash算法

• 首先开辟一块非常大的空间(如图中:0~2³²),然后将所有的数据使用hash函数(如MD5、Ketama等)映射到这个空间内,形成一个Hash环. 当有数据需要存储时,先得到一个hash值对应到hash环上的具体位置(如k1),然后沿顺时针方向找到一台机器(如B),将k1存储到B这个节点中:
  

• 如果B节点宕机,则B上的所有负载就会落到C节点上：
  

• 这样,只会影响C节点，对其他的节点如A、D的数据都不会造成影响. 然而,这样又会带来一定的风险,由于B节点的负载全部由C节点承担,C节点的负载会变得很高,因此C节点又会很容易宕机,依次下去会造成整个集群的不稳定.
  理想的情况下是当B节点宕机时,将原先B节点上的负载平均的分担到其他的各个节点上. 为此,又引入了“虚拟节点”的概念: 想象在这个环上有很多“虚拟节点”,数据的存储是沿着环的顺时针方向找一个虚拟节点,每个虚拟节点都会关联到一个真实节点,但一个真实节点会对应多个虚拟节点,且不同真实节点的多个虚拟节点是交差分布的:
  
  图中A1、A2、B1、B2、C1、C2、D1、D2 都是“虚拟节点”,机器A负责存储A1、A2的数据, 机器B负责存储B1、B2的数据… 只要虚拟节点数量足够多且分布均匀,当其中一台机器宕机之后,原先机器上的负载就会平均分配到其他所有机器上(如图中节点B宕机,其负载会分担到节点A和节点D上).

详细：

白话解析一致性hash算法http://www.zsythink.net/archives/1182

独立的组件

表单验证

用 Redis 模拟 session

Redis 是一个强大而简单的键值型数据库，之前在公司网站改版的过程中大量使用 Redis 来处理一些特殊的需求，我希望能将自己对 Redis 的使用经验都分享出来，而这里算是第一篇吧。
背景

i++为什么是非线程安全的？

先来解释下什么叫“线程安全” :

即一段代码可以被多个线程调用，调用过程中对象的状态不出现冲突，或者对象按照正确的顺序进行了操作。

i++ 线程安全是指我们读取一个值希望的是每一次读取到的值都是上一次+1 。

i++是分为三个步骤，获取i的值；temp = i+1操作；temp写入i; 如果存在两个线程，都执行i++. 正常情况应该是线程A 先执行，得到1； 线程B再执行，得到2.

但是又常常出现：

线程A : 获取i的值;得到0；temp = i+1操作；得到i= 1;
线程B : 获取i的值;得到0；temp = i+1操作；得到i= 1;
线程A : i = temp 赋值 i =1 被写入；
线程B ：i = temp 赋值 i =1 被写入；

或者更形象的举例：线程A，B对i不停的进行操作，A执行i++, B执行打印。程序的逻辑是每次加1后就打，这样应该输出的结果是顺序的不断加1。由于i++不是原子操作，在执行的过程中发生了线程的切换，i+1没有被回写之前就被2访问了，这时打印的还是原来的数字，并不是预期的+1。

线程的这种交叉操作会导致线程不安全。在Java中可以有很多方法来保证线程安全，即原子化 —— 同步，使用原子类，实现并发锁，使用volatile关键字，使用不变类和线程安全类。

何为 Atomic？

Atomic 一词跟原子有点关系，后者曾被人认为是最小物质的单位。计算机中的 Atomic 是指不能分割成若干部分的意思。如果一段代码被认为是 Atomic， 原子操作是指一个不受其他操作影响的操作任务单元，原子操作不能中断。原子操作是在多线程环境下避免数据不一致必须的手段。通常来说，原子指令由硬件提供，供软件来实现原子方法（某个线程进入该方法后，就不会被中断，直到其执行完成）

如何实现原子操作

为了解决这个问题，必须保证增加操作是原子的，在 JDK1.5 之前我们可以使用同步技术（synchonized关键字， 锁）来做到这一点。到 JDK1.5，java.util.concurrent.atomic 包提供了 int 和 long 类型的装类，它们可以自动的保证对于他们的操作是原子的并且不需要使用同步。

同步技术/锁 ：synchronized 关键字修饰，给方法自动获取和释放锁

public class Example {
    private int value = 0;    

    public synchronized int getNextValue(){
        return value++;
    }
}

或者

public class Example {
    private int value = 0;

    public int getNextValue() {
        synchronized (this) {
            return value++;
        }
    }
}

或者想对其他对象加锁，而非当前对象

public class Example {
    private int value = 0;

    private final Object lock = new Object();

    public int getNextValue() {
        synchronized (lock) {
            return value++;
        }
    }
}

Volatile

关键词：可见性

当对非volatile变量进行读写的时候，每个线程先从内存拷贝变量到CPU缓存中。如果计算机有多个CPU，每个线程可能在不同的CPU上被处理，这意味着每个线程可以考虑到不同的CPU cache中。
而声明变量是volatile的，JVM保证了每次读变量都从内存中读，跳过CPU cache这一步。
编译器可以改变指令执行的顺序以使吞吐量最大化，这种顺序上的便会导致内存的值不同步。

volatile关键字为实例域的同步访问提供了一种免锁机制。如果声明一个域为volatile. 一些情况就可以确保多线程访问到的变量是最新的。（并发要求）

public class SharedObject{
    public volatile int counter = 0;
    }
}

一个线程对对象进行了操作，对象发生了变化，这种变化应该对其他线程是可见的。但是默认对这点没有任何保障。所以我们使用了Synchonized. 另一种方法是使用volatile关键字确保多线程对对象读写的可见性（但是只是在某些情况可以保证同步，比如一个线程读，然后写在了volatile变量上，其他线程只是进行读操作； 如果多个线程都进行读写，那么就一定要在用synchronized）。volatile只确保了可见性，并不能确保原子性。

当我们使用 volatile 关键字去修饰变量的时候，所以线程都会直接读取该变量并且不缓存它。这就确保了线程读取到的变量是同内存中是一致的

原子操作类

几乎 java.util.concurrent 包中的所有类都使用原子变量，而不使用同步。原因是 同步（lock）机制并不是一个轻量级的操作，它存在一些缺点。缺点如下

JUC这包里面提供了一组原子类。其基本的特性就是在多线程环境下，当有多个线程同时执行这些类的实例包含的方法时，具有排他性，即当某个线程进入方法，执行其中的指令时，不会被其他线程打断，而别的线程就像自旋锁一样，一直等到该方法执行完成，才由 JVM 从等待队列中选择一个另一个线程进入，这只是一种逻辑上的理解。实际上是借助硬件的相关指令来实现的，不会阻塞线程 (或者说只是在硬件级别上阻塞了)。

根据修改的数据类型，可以将 JUC 包中的原子操作类可以分为 4 类。

基本类型: AtomicInteger, AtomicLong, AtomicBoolean ;
数组类型: AtomicIntegerArray, AtomicLongArray, AtomicReferenceArray ;
引用类型: AtomicReference, AtomicStampedRerence, AtomicMarkableReference ;
对象的属性修改类型: AtomicIntegerFieldUpdater, AtomicLongFieldUpdater, AtomicReferenceFieldUpdater 。

这些类都是基于CAS实现的。处理器提供了CAS操作来实现非加锁的原子操作。

引用《Java Concurrency in Practice》里的一段描述：

在这里，CAS 指的是现代 CPU 广泛支持的一种对内存中的共享数据进行操作的一种特殊指令。这个指令会对内存中的共享数据做原子的读写操作。简单介绍一下这个指令的操作过程：首先，CPU 会将内存中将要被更改的数据与期望的值做比较。然后，当这两个值相等时，CPU 才会将内存中的数值替换为新的值。否则便不做操作。最后，CPU 会将旧的数值返回。这一系列的操作是原子的。它们虽然看似复杂，但却是 Java 5 并发机制优于原有锁机制的根本。简单来说，CAS 的含义是 “我认为原有的值应该是什么，如果是，则将原有的值更新为新值，否则不做修改，并告诉我原来的值是多少”。 CSA的优点：Compare and Set 是一个非阻塞的算法，这是它的优势。因为使用的是 CPU 支持的指令，提供了比原有的并发机制更好的性能和伸缩性。可以认为一般情况下性能更好，并且也更容易使用

使用原子类实现i++方法

public class AtomicCounter {
    private final AtomicInteger value = new AtomicInteger(0);

    public int getValue(){
        return value.get();
    }

    public int getNextValue(){
        return value.incrementAndGet();
    }

    public int getPreviousValue(){
        return value.decrementAndGet();
    }
}

一个线程安全的栈

public class Stack {
    private final AtomicReference<Element> head = new AtomicReference<Element>(null);

    public void push(String value){
        Element newElement = new Element(value);

        while(true){
            Element oldHead = head.get();
            newElement.next = oldHead;

            //Trying to set the new element as the head
            if(head.compareAndSet(oldHead, newElement)){
                return;
            }
        }
    }

    public String pop(){
        while(true){
            Element oldHead = head.get();

            //The stack is empty
            if(oldHead == null){
                return null;
            }

            Element newHead = oldHead.next;

            //Trying to set the new element as the head
            if(head.compareAndSet(oldHead, newHead)){
                return oldHead.value;
            }
        }
    }

    private static final class Element {
        private final String value;
        private Element next;

        private Element(String value) {
            this.value = value;
        }
    }
}

总结

synchronized 实现的同步能确保线程安全，实现可见性和原子性；但是代价大，效率低，更慢；
volatile 能够实现多线程操作产生变化的可见性，但是不能实现原子性。
atomic 类 是一种更轻量级的方法实现可见性和原子性

数据库三范式

范式

关系模型R(U,F),U为属性，F为属性U上的一组数据依赖。
关系数据库的关系是要满足一定要求的，满足不同程度要求的为不同范式。

• 第一范式 (1NF)
  定义：如果关系模式 R 的每个关系 r 的属性都是不可分的数据项，那么就称 R 是第一范式的模式。
  简单的说，每一个属性都是原子项，不可分割。

  1NF 是关系模式应具备的最起码的条件，如果数据库设计不能满足第一范式，就不称为关系型数据库。关系数据库设计研究的关系规范化是在 1NF 之上进行的。例如 (学生信息表)：

以上的表就不符合，第一范式：联系方式字段可以再分，所以变更为正确的是：

第二范式（2NF）
定义：如果关系模式 R 是 1NF，且每个非主属性完全函数依赖于候选键，那么就称 R 是第二范式。
简单的说，第二范式要满足以下的条件：首先要满足第一范式，其次每个非主属性要完全函数依赖与候选键，或者是主键。也就是说，每个非主属性是由整个主键函数决定的，而不能由主键的一部分来决定。
例如 (学生选课表):

这里通过（学生，课程）可以确定教师、教师职称，教材，教室和上课时间，所以可以把（学生，课程）作为主键。但是，教材并不完全依赖于（学生，课程），只拿出课程就可以确定教材，因为一个课程，一定指定了某个教材。这就叫不完全依赖，或者部分依赖。出现这种情况，就不满足第二范式。
修改后，
选课表：

课程表：

所以，第二范式可以说是消除部分依赖。第二范式可以减少插入异常，删除异常和修改异常。
第三范式（3NF）
定义：如果关系模式 R 是 2NF，且关系模式 R（U，F）中的所有非主属性对任何候选关键字都不存在传递依赖，则称关系 R 是属于第三范式。
简单的说，第三范式要满足以下的条件：首先要满足第二范式，其次非主属性之间不存在函数依赖。由于满足了第二范式，表示每个非主属性都函数依赖于主键。如果非主属性之间存在了函数依赖，就会存在传递依赖，这样就不满足第三范式。
上例中修改后的选课表中，一个教师能确定一个教师职称。这样，教师依赖于（学生，课程），而教师职称又依赖于教师，这叫传递依赖。第三范式就是要消除传递依赖。
修改后，
选课表：

教师表：

这样，新教师的职称在没被选课的时候也有地方存了，没人选这个教师的课的时候教师的职称也不至于被删除，修改教师职称时只修改教师表就可以了。
简单的说，
第一范式就是原子性，字段不可再分割；
第二范式就是完全依赖，没有部分依赖；
第三范式就是没有传递依赖。

SpringMVC 工作原理

Spring MVC原理图

Spring MVC工作原理
工作过程

1. Spring MVC是通过将需要Spring MVC处理的请求映射到一个名叫DispatcherServlet的servlet上实现的。

2. 客户端请求首先会交给DispatcherServlet，DispatcherServlet会通过HandlerMapping去查找当前请求的URL对应的那个Handler（通常是Controller中对应的一个方法）。

3. DispatcherServlet会将请求交给第2步找到的那个Handler方法执行
4. 执行的过程可能会调用若干的Service来完成业务的处理
5. 最后在这个Handler中将处理的结果封装成未ModelAndView对象返回给DispatcherServlet。ModelAndView是模型和视图的封装对象。
6. DispatcherServlet根据ModelAndView中的View，去ViewResolver（视图解析器）中找到对应的视图。
7. DispatcherServlet将ModelAndView中的Model交给第6步中找到的那个View（JSP,JSTL…）进行视图的渲染。
8. 渲染后，将视图转为HTTP响应流返回给客户端。