序

本文介紹一下提升并發(fā)可伸縮性的一些方式：減少鎖的持有時(shí)間，降低鎖的粒度卖局，鎖分段斧蜕、避免熱點(diǎn)域以及采用非獨(dú)占的鎖或非阻塞鎖來代替獨(dú)占鎖。

減少鎖的持有時(shí)間

降低發(fā)生競(jìng)爭(zhēng)可能性的一種有效方式就是盡可能縮短鎖的持有時(shí)間砚偶。例如批销，可以將一些與鎖無關(guān)的代碼移出同步代碼塊，尤其是那些開銷較大的操作染坯，以及可能被阻塞的操作均芽，例如I/O操作。

• 優(yōu)化前

@ThreadSafe
public class AttributeStore {
    @GuardedBy("this") private final Map<String, String>
            attributes = new HashMap<String, String>();

    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<String, String>
            attributes = new HashMap<String, String>();

    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ā)生競(jìng)爭(zhēng)的可能性）单鹿。這可以通過鎖分解和鎖分段等技術(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<String> users;
    @GuardedBy("this") public final Set<String> queries;

    public ServerStatusBeforeSplit() {
        users = new HashSet<String>();
        queries = new HashSet<String>();
    }

    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<String> users;
    @GuardedBy("queries") public final Set<String> queries;

    public ServerStatusAfterSplit() {
        users = new HashSet<String>();
        queries = new HashSet<String>();
    }

    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ā)寫入線程的競(jìng)爭(zhēng)足夠激烈并需要突破這個(gè)限制時(shí)拜秧，才能將鎖分段的數(shù)量超過默認(rèn)的16個(gè)痹屹。）

鎖分段的一個(gè)劣勢(shì)在于：與采用單個(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ā)生競(jìng)爭(zhēng)当纱，即使它們會(huì)在同一個(gè)鎖上發(fā)生競(jìng)爭(zhēng)呛每。當(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ù)量叁幢。最簡(jiǎn)單的方法就是滤灯，在每次調(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ú)占鎖

第三種降低競(jìng)爭(zhēng)鎖的影響的技術(shù)就是放棄使用獨(dú)占鎖葵硕，從而有助于使用一種友好并發(fā)的方式來管理共享狀態(tài)眉抬。例如，使用并發(fā)容器懈凹、讀-寫鎖蜀变、不可變對(duì)象以及原子變量。ReadWriteLock能提供比獨(dú)占鎖更高的并發(fā)性介评。而對(duì)于只讀的數(shù)據(jù)結(jié)構(gòu)库北，其中包含的不變性可以完全不需要加鎖操作爬舰。

public class ReadWriteMap <K,V> {
    private final Map<K, V> map;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock r = lock.readLock();
    private final Lock w = lock.writeLock();

    public ReadWriteMap(Map<K, V> map) {
        this.map = map;
    }

    public V put(K key, V value) {
        w.lock();
        try {
            return map.put(key, value);
        } finally {
            w.unlock();
        }
    }

    public V remove(Object key) {
        w.lock();
        try {
            return map.remove(key);
        } finally {
            w.unlock();
        }
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        w.lock();
        try {
            map.putAll(m);
        } finally {
            w.unlock();
        }
    }

    public void clear() {
        w.lock();
        try {
            map.clear();
        } finally {
            w.unlock();
        }
    }

    public V get(Object key) {
        r.lock();
        try {
            return map.get(key);
        } finally {
            r.unlock();
        }
    }

    public int size() {
        r.lock();
        try {
            return map.size();
        } finally {
            r.unlock();
        }
    }

    public boolean isEmpty() {
        r.lock();
        try {
            return map.isEmpty();
        } finally {
            r.unlock();
        }
    }

    public boolean containsKey(Object key) {
        r.lock();
        try {
            return map.containsKey(key);
        } finally {
            r.unlock();
        }
    }

    public boolean containsValue(Object value) {
        r.lock();
        try {
            return map.containsValue(value);
        } finally {
            r.unlock();
        }
    }
}

doc

• Java并發(fā)編程實(shí)戰(zhàn)