请珍惜你身边的最佳损友 (转载)# Joke - 肚皮舞运动
b*d
1 楼
最近有道多线程的题答得不好，大家看看有没有什么好的思路，或者有链接可以share
一下看看？：
（lockless concurrency）
一个分布式hash table（MemCache的意思），多个worker，每个上边有一段hash key
range，另外加一个load balancer 和 persistence用的mysql DB。
其中两台机器对某个cache有读写操作，找出可能产生不一致的一个执行序列，比如：
DB中的资源是一个表C，thread A和B 都在添加entries到表C中去。
cache的key，value是这样的：
每个thread向表中添加entry后，要update对应的cache kv：
{
...
addEntrySQL(c);
kv = readCountSQL(c);
updateMemCache(kv);
...
}
找到一个使结果不consistent的执行序列，如：
kv:.
A_addEntrySQL(C),
A_readCountSQL(c), // in A, kv is.
B_addEntrySQL(c),
B_readCountSQL(c) // in B, kv is.
B_updateMemCache(kv), // kv set to
A_updateMemCache(kv), // kv set to
所以B对MemCache的update被lost掉了。
找出这样的一个operation序列。
如何fix这种情况？use lock to protect cache，make readCountSQL(c)和
updateMemCache(kv) 成为一个atomic的操作：
{
...
addEntrySQL(c);
lockManager.lock(c);
kv = readCount(c);
updateMemCache(kv);
lockManager.unlock(c);
...
}
到此还属于我比较熟悉的内容。
问题是这种lock比较heavy，因为这个是global lock manager，每次lock/unlock都是
个rpc call。如何improve？
我说一个方案是把所有对key=c的kv的操作重新route到对应的machine上去，然后只用
申请一个local的lock，没有global lock server。但这有点违反load balancer（LB）
的意思，或者加大了LB的复杂度。但对方貌似也认可了。
better improvement? 我不是很能follow。只想了个对memcache的value部分加上个
version number，或者说把每次addEntrySQL(c)之后的timestamp存下来，把memcache
改成>的样子。每次对cache update的时候，先无lock的
get出对应的pair，如果当前的version > cache中的version，ignore current update
；反之，加lock update， as：
{
...
addEntrySQL(c);
version_new = System.curMills();
kv_old = readMemCache(c);
if (kv_old.value.second > version_new) {
return; // cache is already newer than current thread.
} else {
lockManager.lock(c);
kv_new = readCount(c);
updateMemCache(kv_new, version_new);
lockManager.unlock(c);
...
}
}
这样能够省一点lock/unlock的操作。
但还是不够，对方问能否干脆去掉lock？我完全没有思路了，胡乱说了一些busy
looping之类就没了。
回家后，我想，是不是把cache结构变成>？ 这样，不
管来的什么kv值，都往里头添加，反正version不同，value最终的位置也不同，没有真
正的concurrency。get()的时候，把整个hashmap都return，caller自己去找最大
version的value值当做valid的值。
但这是不是太麻烦了。。？？？但实在是对去掉lock没有idea。。
一下看看？：
（lockless concurrency）
一个分布式hash table（MemCache的意思），多个worker，每个上边有一段hash key
range，另外加一个load balancer 和 persistence用的mysql DB。
其中两台机器对某个cache有读写操作，找出可能产生不一致的一个执行序列，比如：
DB中的资源是一个表C，thread A和B 都在添加entries到表C中去。
cache的key，value是这样的：
每个thread向表中添加entry后，要update对应的cache kv：
{
...
addEntrySQL(c);
kv = readCountSQL(c);
updateMemCache(kv);
...
}
找到一个使结果不consistent的执行序列，如：
kv:
A_addEntrySQL(C),
A_readCountSQL(c), // in A, kv is
B_addEntrySQL(c),
B_readCountSQL(c) // in B, kv is
B_updateMemCache(kv), // kv set to
A_updateMemCache(kv), // kv set to
所以B对MemCache的update被lost掉了。
找出这样的一个operation序列。
如何fix这种情况？use lock to protect cache，make readCountSQL(c)和
updateMemCache(kv) 成为一个atomic的操作：
{
...
addEntrySQL(c);
lockManager.lock(c);
kv = readCount(c);
updateMemCache(kv);
lockManager.unlock(c);
...
}
到此还属于我比较熟悉的内容。
问题是这种lock比较heavy，因为这个是global lock manager，每次lock/unlock都是
个rpc call。如何improve？
我说一个方案是把所有对key=c的kv的操作重新route到对应的machine上去，然后只用
申请一个local的lock，没有global lock server。但这有点违反load balancer（LB）
的意思，或者加大了LB的复杂度。但对方貌似也认可了。
better improvement? 我不是很能follow。只想了个对memcache的value部分加上个
version number，或者说把每次addEntrySQL(c)之后的timestamp存下来，把memcache
改成
get出对应的pair，如果当前的version > cache中的version，ignore current update
；反之，加lock update， as：
{
...
addEntrySQL(c);
version_new = System.curMills();
kv_old = readMemCache(c);
if (kv_old.value.second > version_new) {
return; // cache is already newer than current thread.
} else {
lockManager.lock(c);
kv_new = readCount(c);
updateMemCache(kv_new, version_new);
lockManager.unlock(c);
...
}
}
这样能够省一点lock/unlock的操作。
但还是不够，对方问能否干脆去掉lock？我完全没有思路了，胡乱说了一些busy
looping之类就没了。
回家后，我想，是不是把cache结构变成
管来的什么kv值，都往里头添加，反正version不同，value最终的位置也不同，没有真
正的concurrency。get()的时候，把整个hashmap都return，caller自己去找最大
version的value值当做valid的值。
但这是不是太麻烦了。。？？？但实在是对去掉lock没有idea。。
