分布式缓存系统 Memcached CAS协议

Memcached在1.2.4版本后新增了CAS(Check and Set)协议，主要用于并发控制：memcached中同一个item同时被多个线程（多个客户端）更改的并发问题。CAS协议最本质的东西——版本号，即将每个item都关联一个全局唯一的编号，从而利用该唯一的编号来判断item数据在某个线程操作期间有无被其他的线程所更改（每次更改版本号都会改变，因此可作为判断的标识）。

如果不采用CAS，则有如下的情景：
第一步，A取出数据对象X； 
第二步，B取出数据对象X； 
第三步，B修改数据对象X，并将其放入缓存； 
第四步，A修改数据对象X，并将其放入缓存。 
我们可以发现，第四步中会产生数据写入冲突。

如果采用CAS协议，则是如下的情景。 
第一步，A取出数据对象X，并获取到CAS-ID1； 
第二步，B取出数据对象X，并获取到CAS-ID2； 
第三步，B修改数据对象X，在写入缓存前，检查CAS-ID与缓存空间中该数据的CAS-ID是否一致。结果是“一致”，就将修改后的带有CAS-ID2的X写入到缓存。 
第四步，A修改数据对象Y，在写入缓存前，检查CAS-ID与缓存空间中该数据的CAS-ID是否一致。结果是“不一致”，则拒绝写入，返回存储失败。

可以通过重试，或者其他业务逻辑解决第四步设置失败的问题。

具体的，在Memcached中，每个key关联都一个64-bit长度的long型惟一数值，表示该key对应value的版本号。这个数值由Memcached server产生，从1开始，且同一Memcached server中不会重复。在两种情况下这个版本数值会加1：新增一个key-value对 和 对某已有key对应的value值更新成功。删除item，而版本值不会减小。

可由如下例子看出：

MemcachedClient client = new MemcachedClient();  
  client.set("fKey", "fValue");  
  //第一次set, 在Memcached server中会维护fKey对应的value的版本号，假设是548;  
  
  client.set("fKey", "sValue");  
  //再次set，则这个fKey对应的value的版本号变为549;  
  
  CASValue casValue = client.gets("fKey");  
  //这样就可以得到对应key的cas版本号和实际value(各个Memcached client都有类似的对象表示，名字可能不一样，但效果类同)，如 casValue.getValue = "sValue"，casValue.getCas=549; 

注：get命令返回给定key的value值。 而gets则会返回给定key的value和cas版本号值。如下图：

其中，先set 一次name,再gets name的返回值为：“VALUE  name 0 3 2", 然后再进行一次set name，  这时gets name的返回值为”VALUE  name 0 3 3“,最后一个字段由2变为了3，即版本号因为set更改了value值而被增加了一，而get name的返回值为”VALUE name 0 3“,与gets的返回值相比，少最后的版本号的字段。

CAS协议在并发控制中的具体应用：

一个memcached server在有多个额客户端时，分析下多个client并发set同一个key的场景。如clientA想把当前key的value set为"x"，且操作成功；clientB却把当前key的value值由"x"覆盖set为"y"，这时clientA再根据key去取value时得到"y"而不是期望的"x"，它使用这个值，但不知道这个值已经被其它线程修改过，就可能会出现问题。

而CAS协议正是用于解决这种并发修改问题。有线程试图修改当前key-value对的value时，先由gets方法得到item的版本号，操作完成提交数据时，则先比较获取的版本号与当前item key中的版本号是否一致，如果是相同的，则提交数据，完整set等更改操作。反之，如果不一致，则说明在该线程对item操作过程中，这个key-value对被其它线程更改过（当然也就更改了版本号），于是放弃此次修改(乐观锁概念)。

Memcached默认是打开cas属性的，每次执行更改操作后，存储数据时，都会生成其cas值并和item一起尝试这存储（是否存储成功，需要有版本号cas值是否一致来决定）如果操作成功则更改原版本号为该cas值，否则放弃本次操作。在进行gets操作会返回系统生成的cas值。

看下在存储item时的操作函数stor_item的相关代码：

 //为新的item生成cas值  
uint64_t get_cas_id(void)  
{  
    static uint64_t cas_id = 0;  
    return ++cas_id;  
}  
//执行cas存储时执行的判断逻辑，  
else if (ITEM_get_cas(it) == ITEM_get_cas(old_it))//版本号cas值一致  
{  
    pthread_mutex_lock(&c->thread->stats.mutex);  
    c->thread->stats.slab_stats[old_it->slabs_clsid].cas_hits++;  
    pthread_mutex_unlock(&c->thread->stats.mutex);  
  
    item_replace(old_it, it, hv);//执行存储逻辑  
    stored = STORED;  
}  
else //版本号cas值不一致，不进行实际的存储  
{  
    pthread_mutex_lock(&c->thread->stats.mutex);  
    c->thread->stats.slab_stats[old_it->slabs_clsid].cas_badval++; //更新统计信息  
    pthread_mutex_unlock(&c->thread->stats.mutex);  
  
    if (settings.verbose > 1)  
    {  
        //打印错误日志  
        fprintf(stderr, "CAS:  failure: expected %llu, got %llu\n",  
                (unsigned long long) ITEM_get_cas(old_it),  
                (unsigned long long) ITEM_get_cas(it));  
    }  
    stored = EXISTS;  
}

当因为cas值冲突，而不能完成对item的更改操作时，可以通过比如重试等方式，待没有其他线程同时来更改该item时，则能顺利完成更改操作。

原文：http://www.cnblogs.com/duanxz/p/5138103.html