資訊專欄INFORMATION COLUMN
摘要：減少鎖的持有時(shí)間降低發(fā)生競爭可能性的一種有效方式就是盡可能縮短鎖的持有時(shí)間。代替獨(dú)占鎖第三種降低競爭鎖的影響的技術(shù)就是放棄使用獨(dú)占鎖，從而有助于使用一種友好并發(fā)的方式來管理共享狀態(tài)。
序
本文介紹一下提升并發(fā)可伸縮性的一些方式：減少鎖的持有時(shí)間，降低鎖的粒度，鎖分段、避免熱點(diǎn)域以及采用非獨(dú)占的鎖或非阻塞鎖來代替獨(dú)占鎖。
減少鎖的持有時(shí)間降低發(fā)生競爭可能性的一種有效方式就是盡可能縮短鎖的持有時(shí)間。例如，可以將一些與鎖無關(guān)的代碼移出同步代碼塊，尤其是那些開銷較大的操作，以及可能被阻塞的操作，例如I/O操作。
優(yōu)化前
@ThreadSafe
public class AttributeStore {
@GuardedBy("this") private final Map
attributes = new HashMap();
public synchronized boolean userLocationMatches(String name,
String regexp) {
String key = "users." + name + ".location";
String location = attributes.get(key);
if (location == null)
return false;
else
return Pattern.matches(regexp, location);
}
}
優(yōu)化后
@ThreadSafe
public class BetterAttributeStore {
@GuardedBy("this") private final Map
attributes = new HashMap();
public boolean userLocationMatches(String name, String regexp) {
String key = "users." + name + ".location";
String location;
synchronized (this) {
location = attributes.get(key);
}
if (location == null)
return false;
else
return Pattern.matches(regexp, location);
}
}
降低鎖的粒度
另一種減小鎖的持有時(shí)間的方式是降低線程請(qǐng)求鎖的頻率（從而減小發(fā)生競爭的可能性）。這可以通過鎖分解和鎖分段等技術(shù)來實(shí)現(xiàn)，在這些技術(shù)中將采用多個(gè)相互獨(dú)立的鎖來保護(hù)獨(dú)立的狀態(tài)變量，從而改變這些變量在之前由單個(gè)鎖來保護(hù)的情況。這些技術(shù)能減小鎖操作的粒度，并能實(shí)現(xiàn)更高的可伸縮性，然而，使用的鎖越多，那么發(fā)生死鎖的風(fēng)險(xiǎn)也就越高。
優(yōu)化前
@ThreadSafe
public class ServerStatusBeforeSplit {
@GuardedBy("this") public final Set users;
@GuardedBy("this") public final Set queries;
public ServerStatusBeforeSplit() {
users = new HashSet();
queries = new HashSet();
}
public synchronized void addUser(String u) {
users.add(u);
}
public synchronized void addQuery(String q) {
queries.add(q);
}
public synchronized void removeUser(String u) {
users.remove(u);
}
public synchronized void removeQuery(String q) {
queries.remove(q);
}
}
優(yōu)化后
@ThreadSafe
public class ServerStatusAfterSplit {
@GuardedBy("users") public final Set users;
@GuardedBy("queries") public final Set queries;
public ServerStatusAfterSplit() {
users = new HashSet();
queries = new HashSet();
}
public void addUser(String u) {
synchronized (users) {
users.add(u);
}
}
public void addQuery(String q) {
synchronized (queries) {
queries.add(q);
}
}
public void removeUser(String u) {
synchronized (users) {
users.remove(u);
}
}
public void removeQuery(String q) {
synchronized (users) {
queries.remove(q);
}
}
}
鎖分段
在某些情況下，可以將鎖分解技術(shù)進(jìn)一步擴(kuò)展為對(duì)一組獨(dú)立對(duì)象上的鎖進(jìn)行分解，這種情況被稱為鎖分段。例如，在ConcurrentHashMap的實(shí)現(xiàn)中使用了一個(gè)包含16個(gè)鎖的數(shù)組，每個(gè)鎖保護(hù)所有散列桶的1/16，其中第N個(gè)散列桶由第（Nmod 16）個(gè)鎖來保護(hù)。假設(shè)散列函數(shù)具有合理的分布性，并且關(guān)鍵字能夠?qū)崿F(xiàn)均勻分布，那么這大約能把對(duì)于鎖的請(qǐng)求減少到原來的1/16。正是這項(xiàng)技術(shù)使得ConcurrentHashMap能夠支持多達(dá)16個(gè)并發(fā)的寫入器。（要使得擁有大量處理器的系統(tǒng)在高訪問量的情況下實(shí)現(xiàn)更高的并發(fā)性，還可以進(jìn)一步增加鎖的數(shù)量，但僅當(dāng)你能證明并發(fā)寫入線程的競爭足夠激烈并需要突破這個(gè)限制時(shí)，才能將鎖分段的數(shù)量超過默認(rèn)的16個(gè)。）
鎖分段的一個(gè)劣勢在于：與采用單個(gè)鎖來實(shí)現(xiàn)獨(dú)占訪問相比，要獲取多個(gè)鎖來實(shí)現(xiàn)獨(dú)占訪問將更加困難并且開銷更高。通常，在執(zhí)行一個(gè)操作時(shí)最多只需獲取一個(gè)鎖，但在某些情況下需要加鎖整個(gè)容器，例如當(dāng)ConcurrentHashMap需要擴(kuò)展映射范圍，以及重新計(jì)算鍵值的散列值要分布到更大的桶集合中時(shí)，就需要獲取分段所集合中所有的鎖。
@ThreadSafe
public class StripedMap {
// Synchronization policy: buckets[n] guarded by locks[n%N_LOCKS]
private static final int N_LOCKS = 16;
private final Node[] buckets;
private final Object[] locks;
private static class Node {
Node next;
Object key;
Object value;
}
public StripedMap(int numBuckets) {
buckets = new Node[numBuckets];
locks = new Object[N_LOCKS];
for (int i = 0; i < N_LOCKS; i++)
locks[i] = new Object();
}
private final int hash(Object key) {
return Math.abs(key.hashCode() % buckets.length);
}
public Object get(Object key) {
int hash = hash(key);
synchronized (locks[hash % N_LOCKS]) {
for (Node m = buckets[hash]; m != null; m = m.next)
if (m.key.equals(key))
return m.value;
}
return null;
}
public void clear() {
for (int i = 0; i < buckets.length; i++) {
synchronized (locks[i % N_LOCKS]) {
buckets[i] = null;
}
}
}
}
避免熱點(diǎn)域
如果一個(gè)鎖保護(hù)兩個(gè)獨(dú)立變量X和Y，并且線程A想要訪問X，而線程B想要訪問Y（這類似于在ServerStatus中，一個(gè)線程調(diào)用addUser，而另一個(gè)線程調(diào)用addQuery），那么這兩個(gè)線程不會(huì)在任何數(shù)據(jù)上發(fā)生競爭，即使它們會(huì)在同一個(gè)鎖上發(fā)生競爭。當(dāng)每個(gè)操作都請(qǐng)求多個(gè)變量時(shí)，鎖的粒度將很難降低。這是在性能與可伸縮性之間相互制衡的另一個(gè)方面，一些常見的優(yōu)化措施，例如將一些反復(fù)計(jì)算的結(jié)果緩存起來，都會(huì)引入一些“熱點(diǎn)域（HotField）”，而這些熱點(diǎn)域往往會(huì)限制可伸縮性。當(dāng)實(shí)現(xiàn)HashMap時(shí)，你需要考慮如何在size方法中計(jì)算Map中的元素?cái)?shù)量。最簡單的方法就是，在每次調(diào)用時(shí)都統(tǒng)計(jì)一次元素的數(shù)量。一種常見的優(yōu)化措施是，在插入和移除元素時(shí)更新一個(gè)計(jì)數(shù)器，雖然這在put和remove等方法中略微增加了一些開銷，以確保計(jì)數(shù)器是最新的值，但這將把size方法的開銷從O（n）降低到O（l）。
在單線程或者采用完全同步的實(shí)現(xiàn)中，使用一個(gè)獨(dú)立的計(jì)數(shù)能很好地提高類似size和isEmpty這些方法的執(zhí)行速度，但卻導(dǎo)致更難以提升實(shí)現(xiàn)的可伸縮性，因?yàn)槊總€(gè)修改map的操作都需要更新這個(gè)共享的計(jì)數(shù)器。即使使用鎖分段技術(shù)來實(shí)現(xiàn)散列鏈，那么在對(duì)計(jì)數(shù)器的訪問進(jìn)行同步時(shí)，也會(huì)重新導(dǎo)致在使用獨(dú)占鎖時(shí)存在的可伸縮性問題。一個(gè)看似性能優(yōu)化的措施—緩存size操作的結(jié)果，已經(jīng)變成了一個(gè)可伸縮性問題。在這種情況下，計(jì)數(shù)器也被稱為熱點(diǎn)域，因?yàn)槊總€(gè)導(dǎo)致元素?cái)?shù)量發(fā)生變化的操作都需要訪問它。為了避免這個(gè)問題，ConcurrentHashMap中的size將對(duì)每個(gè)分段進(jìn)行枚舉并將每個(gè)分段中的元素?cái)?shù)量相加，而不是維護(hù)一個(gè)全局計(jì)數(shù)。為了避免枚舉每個(gè)元素，ConcurrentHashMap為每個(gè)分段都維護(hù)了一個(gè)獨(dú)立的計(jì)數(shù)，并通過每個(gè)分段的鎖來維護(hù)這個(gè)值。
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
代替獨(dú)占鎖
第三種降低競爭鎖的影響的技術(shù)就是放棄使用獨(dú)占鎖，從而有助于使用一種友好并發(fā)的方式來管理共享狀態(tài)。例如，使用并發(fā)容器、讀-寫鎖、不可變對(duì)象以及原子變量。ReadWriteLock能提供比獨(dú)占鎖更高的并發(fā)性。而對(duì)于只讀的數(shù)據(jù)結(jié)構(gòu)，其中包含的不變性可以完全不需要加鎖操作。
