b*******d
发帖数: 750 | 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。。 |
g*****g
发帖数: 34805 | 2 一种可能的做法，就是把+1,-1的操作加到cache里(commit log)，然后由读进程或者后
台进程做contraction。 |
r****s
发帖数: 1025 | 3 Java的atomic里面没有比较大小的，只有CAS。所以只能用spin lock+CAS，如果
version number或者timestamp过期，就break，不然就spin下去。
在heavy contention情况下，用lock吧。 |
g*****g
发帖数: 34805 | 4 Java 的atomic里有，如AtomicInteger里的compareAndSet。
问题在于distributed cache不一定有这样的API。
【在 r****s 的大作中提到】
: Java的atomic里面没有比较大小的，只有CAS。所以只能用spin lock+CAS，如果
: version number或者timestamp过期，就break，不然就spin下去。
: 在heavy contention情况下，用lock吧。
|
r****s
发帖数: 1025 | 5 CAS是比较大小？
【在 g*****g 的大作中提到】
: Java 的atomic里有，如AtomicInteger里的compareAndSet。
: 问题在于distributed cache不一定有这样的API。
|
b*******d
发帖数: 750 | 6
compare and swap?
【在 r****s 的大作中提到】
: CAS是比较大小？
|
b***i
发帖数: 3043 | 7 每个单独计数,需要读数的时候再加?
share
【在 b*******d 的大作中提到】
: 最近有道多线程的题答得不好，大家看看有没有什么好的思路，或者有链接可以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：
: {
|
b*******d
发帖数: 750 | 8 how do you know if your current cache is stale already?
I think you might need to update your cache whenever your persistence is
refreshed with new writes.?
【在 b***i 的大作中提到】
: 每个单独计数,需要读数的时候再加?
:
: share
|
