从String类的不可变谈到分布式一致性

本篇文章记录的是，在程序设计和服务层面，我对于「状态」的理解，状态就像「资本主义」，口里说的不想要，现实中又摆脱不掉。

有状态对象和无状态对象：String是否线程安全

通常，我们会讨论StringBuffer是线程安全的，而StringBuilder是线程不安全的。那么String本身是否是线程安全呢？
我认为String类是线程安全的，因为String是一个不可变对象（Immutable Object），不可变对象天生支持线程安全。在「Effective Java」中，对于不可变对象的解释如下：

不可变对象(Immutable Object)：对象一旦被创建后，对象所有的状态及属性在其生命周期内不会发生任何变化。

那么String是如何体现它的不可变的呢，因为String的本质是一个不可变的char数组。从定义可以看出：

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    /** The value is used for character storage. */
    private final char value[];
    ...
    }

也就是说，每次new一个String的时候，总是会在JVM的堆中开辟一块内存去存一个不可变的数组。那么对String进行写操作时，是如何处理的呢。比如在String的substring方法可以看到。

public String substring(int beginIndex) {
        if (beginIndex < 0) {
            throw new StringIndexOutOfBoundsException(beginIndex);
        }
        int subLen = value.length - beginIndex;
        if (subLen < 0) {
            throw new StringIndexOutOfBoundsException(subLen);
        }
        return (beginIndex == 0) ? this : new String(value, beginIndex, subLen);
    }

调用substring方法最后返回的是new了一个新的String实例。

public String(char value[], int offset, int count) {
        if (offset < 0) {
            throw new StringIndexOutOfBoundsException(offset);
        }
        if (count <= 0) {
            if (count < 0) {
                throw new StringIndexOutOfBoundsException(count);
            }
            if (offset <= value.length) {
                this.value = "".value;
                return;
            }
        }
        // Note: offset or count might be near -1>>>1.
        if (offset > value.length - count) {
            throw new StringIndexOutOfBoundsException(offset + count);
        }
        this.value = Arrays.copyOfRange(value, offset, offset+count);
    }

在String的构造方法可以看到，每次new一个String实例，调用的是Arrays.copyOfRange方法，这是一个native方法，作用就是拷贝内存块。
String里面的写操作最后返回的都是在内存中重新开辟了一块内存地址，而并不是在原有的地址上进行写操作。 通俗一点讲就是，把String实例比作是一块画板，写操作比作是在画板上画画，对于String而言，每次写操作都是重新换了一块画板并在新画板上画画，而上一块画板永远保持它的样子，写操作时在新画板上发生的。每一块画板永远保持的一个样子，不会改变，这就是String的不可变性。反过来说，假如我们所有的写操作都是在同一块画板上进行的，那么它就是可变的，因为在它的生命周期里面，变化随时都会发生。
当说一个东西不可变的时，也可以说它是没有状态的（Stateless）
在线程安全及不可变性中提供了一个不可变类的例子。

public class ImmutableValue{
	private int value = 0;

	public ImmutableValue(int value){
		this.value = value;
	}

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

这个不可变类有几个特点：

• 成员变量value是通过构造函数赋值的
• 没有set方法
  以上保证了实例化的对象是没有公开的方法去修改它本身的。

当多个线程同时访问同一个资源，并且其中的一个或者多个线程对这个资源进行了写操作，才会产生竞态条件多个线程同时读同一个资源不会产生竞态条件。关键点在于对资源进行写操作后会改变状态，比如自增操作，在并发环境下，很难保证线程读到的永远是最新的状态，有可能由于线程切换和缓存不一致，而共享资源也是有状态的，就会出现两个线程读到的值是一样的情况（类似画板，两个画家在画画的时候均以为当前的画板是最新的，在同一个画板上同时画了两笔，恰好两笔都画在了一个地方，但在外人看来画板上只是添加了一笔而已），这就是线程不安全。那如何解决这个问题呢，只要解决一个关键问题就可以：保证画家画画的时候永远看到的是最新的画作，有两种方案：

• 线程同步共享资源的状态：从画家入手，保证同一时刻只有一位画家在画画
• 将共享资源去状态化：画家得到的画板永远都是基于上一份画板拷贝而成的，对于所有的画家而言，他们任何时刻看到的画板都是最新的
  而我们以上讲的不可变对象，采用的就是方案2，方案2在计算机设计领域有另外一个名字：写时复制（Copy-on-write，简称COW）。

写入时复制（英语：Copy-on-write，简称COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。

String 类的设计包含了COW的思想，除此之外，在Java语言中，安全失败的本质其实也是COW思想。
要说到安全失败，我们先谈什么是快速失败，两者均是Collection集合类中的概念：

fail-fast机制：当遍历一个集合对象时，如果集合对象的结构被修改了，就会抛出ConcurrentModificationExcetion异常。

以ArrayList为例，简单说ArrayList继承自AbstractList类，AbstractList内部有一个字段modCount，代表修改的次数。ArrayList类的add、remove操作都会使得modCount自增。当使用ArrayList.iterator()返回一个迭代器对象时。迭代器对象有一个属性expectedModCount，它被赋值为该方法调用时modCount的值。这意味着，这个值是modCount在这个时间点的快照值，expectedModCount值在iterator对象内部不会再发送变化，具体可以阅读这篇文章。调用next()迭代会比照两个值是否一致，否则丢出异常。
显然，modCount就是ArrayList的状态，而expectedModCount就是ArrayList的状态快照，在并发环境上，我们希望共享资源是不变的（共享资源有状态会带来线程不安全）。为什么在并发环境下推荐使用iterator.remove()而非list.remove()的原因就是，iterator.remove()会同步更新expectedModCount的值与modCount保持一致，而list.remove()只会更新modCount的值，expectedModCount没有同步更新，所以才会丢出异常。
除此之外，你可能会想到，那我把COW思想运用在容器里面，是不是也能保证容器的并发安全。是的，fail-safe安全失败概念本质就是COW思想，具体我们不在这里展开。

我们再回来不可变对象的讨论上来，至此，可以得出一个结论：不可变对象是天生支持线程安全的。

有状态服务和无状态服务：购物车功能的实现方案

无状态服务（stateless service）对单次请求的处理，不依赖其他请求，也就是说，处理一次请求所需的全部信息，要么都包含在这个请求里，要么可以从外部获取到（比如说数据库），服务器本身不存储任何信息
有状态服务（stateful service）则相反，它会在自身保存一些数据，先后的请求是有关联的.

为了好理解，举一个购物车功能的设计例子：在电商网站购物时，用户可以把自己想买的物品放入购物车。之后在某一个时间统一下单结账。购物车是有状态的，这一秒我把一本书加入了购物车，下一秒我可能就不要了。实现这个功能最常见的两种方案就是Seesion和Cookies去存储状态，那么这两种方案有什么区别呢。
我们假设Cookes永远不过期（现实一般不会这样做），在单机架构下，两者并无明显差异。

将购物车的信息存储在服务端，那么这个服务就是有状态的，购物车信息存储在Client端，服务并不保存任何状态，称为无状态服务。

但在集群架构中，对于无状态服务，横向扩展非常方便，而有状态服务则需要考虑同步状态的问题。如上图，当stateful service2 扩展到集群中时，需要将其他两台机的session同步到stateful service2 中，不然就可能出现购物车有东西的用户请求到stateful service2后，购物车被「清空」的情况。
当然，实际情况中对有状态服务进行扩展也有其他的方式，比如在负载均衡时将用户的IP和目标服务器绑定，用户所有的请求都由一台机器处理；或者使用「共享seesion」，其本质也只是将状态剥离到了其他服务中。
所以，无状态服务对横行扩展是友好的。

CAP理论

但现实世界中，几乎所有的场景都是有状态的：

• 买火车票：一个人买到车票的时段是应该完全分开的；
• 银行存钱：存进去1块钱，账户余额就必须加1；
• 秒杀场景：商品数量卖光了，不能出现超卖情况；

假如以上场景只是在一台单机上运行，状态维持在一个地方。而如果是分布式集群架构，状态的一致性则必须保证。
在理论计算机科学中，CAP理论指出，对于一个分布式系统来说，不能同时满足三个性质：

• 一致性（Consistency） （等同于所有节点访问同一份最新的数据副本）
• 可用性（Availability）（每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据）
• 分区容错性（Partition tolerance）（以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择[3]。）

比如有一个服务在全球有5个节点，正常情况下，节点互相通信保持状态一致。

突然有一天由于不可抗拒力，中美之间的网络不可互相通信了。

这是，对于整个系统来说，就是发生了分区，为了保证系统可以继续提供服务，有两个选择：

• 保证一致性：比如停掉China的两个节点，牺牲了中国地区用户的可用性；
• 保证可用性：继续提供服务，但这时两个分区的数据会出现不一致的情况；

CAP理论指出的观点是：对于一个分布式系统，如果一致性如果达到100%，那么可用性只能接近100%，反之亦然。

引用

• 深入理解Java中的不可变对象
• 线程安全及不可变性
• 写入时复制
• 快速失败与安全失败
• 精通有状态vs无状态(Stateful vs Stateless)—Immutable模式之姐妹篇
• 理解有状态服务和无状态服务
• 一致性状态机
• 状态机复制
• Raft 一致性算法论文译文