ロックストライピングの概要

投稿日: 2022-10-29 2022-10-29
タグ: Java Concurrency

1. 序章

このチュートリアルでは、優れたパフォーマンスを維持しながらデータ構造への同時アクセスを処理するためのパターンである、ロックストライピングとも呼ばれるきめ細かい同期を実現する方法を学習します。

2. 問題

HashMap は、同期されていない性質があるため、スレッドセーフなデータ構造ではありません。つまり、マルチスレッド環境からのコマンドにより、データの不整合が発生する可能性があります。

この問題を解決するには、 Collections＃synchronizedMap メソッドを使用して元のマップを変換するか、HashTableデータ構造を使用します。どちらもMapインターフェースのスレッドセーフな実装を返しますが、パフォーマンスが犠牲になります。

単一のロックオブジェクトを使用してデータ構造に対する排他的なアクセスを定義するアプローチは、粗粒度同期と呼ばれます。

大まかな同期の実装では、オブジェクトへのすべてのアクセスは、一度に1つのスレッドで行う必要があります。最終的にはシーケンシャルアクセスになります。

私たちの目標は、スレッドセーフを確保しながら、同時スレッドがデータ構造で動作できるようにすることです。

3. ロックストライピング

目標を達成するために、ロックストライピングパターンを使用します。ロックストライピングは、複数のバケットまたはストライプでロックが発生する手法です。つまり、バケットにアクセスすると、そのバケットのみがロックされ、データ構造全体はロックされません。

これを行うには、いくつかの方法があります。

まず、タスクごとにロックを使用して、タスク間の同時実行性を最大化できます。ただし、これによりメモリフットプリントが高くなります。
または、タスクごとに1つのロックを使用することもできます。これにより、使用するメモリが少なくなりますが、同時実行のパフォーマンスが低下します。

このパフォーマンスとメモリのトレードオフを管理するために、GuavaにはStripedというクラスが付属しています。にあるロジックに似ています ConcurrentHashMap 、しかし縞模様クラスは、セマフォまたは再入可能ロックを使用して個別のタスクの同期を減らすことにより、さらに進んでいます。

4. 簡単な例

このパターンの利点を理解するのに役立つ簡単な例を見てみましょう。

HashMapとを比較します。 ConcurrentHashMapとシングルロックvs。 4つの実験をもたらす縞模様のロック。

実験ごとに、基になるMapで読み取りと書き込みを同時に実行します。異なるのは、各バケットへのアクセス方法です。

そのために、2つのクラスを作成します– シングルロックと StripedLock。これらは抽象クラスの具体的な実装です ConcurrentAccessExperiment それが仕事をします。

4.1. 依存関係

GuavaのStripedクラスを使用するので、guava依存関係を追加します。

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

4.2. メインプロセス

ConcurrentAccessExperiment クラスは、前述の動作を実装します。

public abstract class ConcurrentAccessExperiment {

    public final Map<String,String> doWork(Map<String,String> map, int threads, int slots) {
        CompletableFuture<?>[] requests = new CompletableFuture<?>[threads * slots];

        for (int i = 0; i < threads; i++) {
            requests[slots * i + 0] = CompletableFuture.supplyAsync(putSupplier(map, i));
            requests[slots * i + 1] = CompletableFuture.supplyAsync(getSupplier(map, i));
            requests[slots * i + 2] = CompletableFuture.supplyAsync(getSupplier(map, i));
            requests[slots * i + 3] = CompletableFuture.supplyAsync(getSupplier(map, i));
        }
        CompletableFuture.allOf(requests).join();

        return map;
    }

    protected abstract Supplier<?> putSupplier(Map<String,String> map, int key);
    protected abstract Supplier<?> getSupplier(Map<String,String> map, int key);
}

テストはCPUにバインドされているため、バケットの数を使用可能なプロセッサの数倍に制限していることに注意してください。

4.3. ReentrantLockによる同時アクセス

次に、非同期タスクのメソッドを実装します。

SingleLock クラスは、 ReentrantLock を使用して、データ構造全体に対して単一のロックを定義します。

public class SingleLock extends ConcurrentAccessExperiment {
    ReentrantLock lock;

    public SingleLock() {
        lock = new ReentrantLock();
    }

    protected Supplier<?> putSupplier(Map<String,String> map, int key) {
        return (()-> {
            lock.lock();
            try {
                return map.put("key" + key, "value" + key);
            } finally {
                lock.unlock();
            }
        });
    }

    protected Supplier<?> getSupplier(Map<String,String> map, int key) {
        return (()-> {
            lock.lock();
            try {
                return map.get("key" + key);
            } finally {
                lock.unlock();
            }
        });
    }
}

4.4. Stripedによる同時アクセス

次に、 StripedLock クラスは、バケットごとにストライプロックを定義します。

public class StripedLock extends ConcurrentAccessExperiment {
    Striped lock;

    public StripedLock(int buckets) {
        lock = Striped.lock(buckets);
    }

    protected Supplier<?> putSupplier(Map<String,String> map, int key) {
        return (()-> {
            int bucket = key % stripedLock.size();
            Lock lock = stripedLock.get(bucket);
            lock.lock();
            try {
                return map.put("key" + key, "value" + key);
            } finally {
                lock.unlock();
            }
        });
    }

    protected Supplier<?> getSupplier(Map<String,String> map, int key) {
        return (()-> {
            int bucket = key % stripedLock.size();
            Lock lock = stripedLock.get(bucket);
            lock.lock(); 
            try {
                return map.get("key" + key);
            } finally {
                lock.unlock();
            }
        });
    }
}

では、どちらの戦略がより効果的ですか？

5. 結果

JMH （Javaマイクロベンチマークハーネス）を使用して調べてみましょう。ベンチマークは、チュートリアルの最後にあるソースコードのリンクから見つけることができます。

ベンチマークを実行すると、次のようなものが表示されます（スループットが高いほど優れていることに注意してください）。

Benchmark                                                Mode  Cnt  Score   Error   Units
ConcurrentAccessBenchmark.singleLockConcurrentHashMap   thrpt   10  0,059 ± 0,006  ops/ms
ConcurrentAccessBenchmark.singleLockHashMap             thrpt   10  0,061 ± 0,005  ops/ms
ConcurrentAccessBenchmark.stripedLockConcurrentHashMap  thrpt   10  0,065 ± 0,009  ops/ms
ConcurrentAccessBenchmark.stripedLockHashMap            thrpt   10  0,068 ± 0,008  ops/ms

6. 結論

このチュートリアルでは、Mapのような構造でロックストライピングを使用してパフォーマンスを向上させるさまざまな方法を検討しました。結果をいくつかの実装と比較するためのベンチマークを作成しました。

ベンチマークの結果から、さまざまな同時戦略がプロセス全体にどのように大きな影響を与える可能性があるかを理解できます。ストライプロックパターンは、HashMapとConcurrentHashMapの両方で〜10 % e xtraを獲得するため、かなりの改善が見られます。

いつものように、このチュートリアルのソースコードはGitHubから入手できます。

getdocs

13036