Class Striped<L>

java.lang.Object
com.google.common.util.concurrent.Striped<L>
Direct Known Subclasses:
Striped.PowerOfTwoStriped

public abstract class Striped<L> extends Object
A striped Lock/Semaphore/ReadWriteLock. This offers the underlying lock striping similar to that of ConcurrentHashMap in a reusable form, and extends it for semaphores and read-write locks. Conceptually, lock striping is the technique of dividing a lock into many stripes, increasing the granularity of a single lock and allowing independent operations to lock different stripes and proceed concurrently, instead of creating contention for a single lock.

The guarantee provided by this class is that equal keys lead to the same lock (or semaphore), i.e. if (key1.equals(key2)) then striped.get(key1) == striped.get(key2) (assuming Object.hashCode() is correctly implemented for the keys). Note that if key1 is not equal to key2, it is not guaranteed that striped.get(key1) != striped.get(key2); the elements might nevertheless be mapped to the same lock. The lower the number of stripes, the higher the probability of this happening.

There are three flavors of this class: Striped<Lock>, Striped<Semaphore>, and Striped<ReadWriteLock>. For each type, two implementations are offered: strong and weak Striped<Lock>, strong and weak Striped<Semaphore>, and strong and weak Striped<ReadWriteLock>. Strong means that all stripes (locks/semaphores) are initialized eagerly, and are not reclaimed unless Striped itself is reclaimable. Weak means that locks/semaphores are created lazily, and they are allowed to be reclaimed if nobody is holding on to them. This is useful, for example, if one wants to create a Striped<Lock> of many locks, but worries that in most cases only a small portion of these would be in use.

Prior to this class, one might be tempted to use Map<K, Lock>, where K represents the task. This maximizes concurrency by having each unique key mapped to a unique lock, but also maximizes memory footprint. On the other extreme, one could use a single lock for all tasks, which minimizes memory footprint but also minimizes concurrency. Instead of choosing either of these extremes, Striped allows the user to trade between required concurrency and memory footprint. For example, if a set of tasks are CPU-bound, one could easily create a very compact Striped<Lock> of availableProcessors() * 4 stripes, instead of possibly thousands of locks which could be created in a Map<K, Lock> structure.

Since:
13.0
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private static class 
    Implementation of Striped where 2^k stripes are represented as an array of the same length, eagerly initialized.
    (package private) static class 
    Implementation of Striped where up to 2^k stripes can be represented, using a ConcurrentMap where the key domain is [0..2^k).
    private static class 
     
    private static class 
     
    private static class 
     
    (package private) static class 
    Implementation of Striped where up to 2^k stripes can be represented, using an AtomicReferenceArray of size 2^k.
    private static final class 
    Condition object that ensures a strong reference is retained to a specified object.
    private static final class 
    Lock object that ensures a strong reference is retained to a specified object.
    private static final class 
    ReadWriteLock implementation whose read and write locks retain a reference back to this lock.
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final int
    A bit mask were all bits are set.
    private static final int
    If there are at least this many stripes, we assume the memory usage of a ConcurrentMap will be smaller than a large array.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
     
  • Method Summary

    Modifier and Type
    Method
    Description
    bulkGet(Iterable<? extends Object> keys)
    Returns the stripes that correspond to the passed objects, in ascending (as per getAt(int)) order.
    private static int
     
    (package private) static <L> Striped<L>
    custom(int stripes, Supplier<L> supplier)
    Creates a Striped<L> with eagerly initialized, strongly referenced locks.
    abstract L
    get(Object key)
    Returns the stripe that corresponds to the passed key.
    abstract L
    getAt(int index)
    Returns the stripe at the specified index.
    (package private) abstract int
    Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key).
    (package private) static <L> Striped<L>
    lazyWeakCustom(int stripes, Supplier<L> supplier)
    Creates a Striped<L> with lazily initialized, weakly referenced locks.
    static Striped<Lock>
    lazyWeakLock(int stripes)
    Creates a Striped<Lock> with lazily initialized, weakly referenced locks.
    lazyWeakReadWriteLock(int stripes)
    Creates a Striped<ReadWriteLock> with lazily initialized, weakly referenced read-write locks.
    lazyWeakSemaphore(int stripes, int permits)
    Creates a Striped<Semaphore> with lazily initialized, weakly referenced semaphores, with the specified number of permits.
    static Striped<Lock>
    lock(int stripes)
    Creates a Striped<Lock> with eagerly initialized, strongly referenced locks.
    readWriteLock(int stripes)
    Creates a Striped<ReadWriteLock> with eagerly initialized, strongly referenced read-write locks.
    semaphore(int stripes, int permits)
    Creates a Striped<Semaphore> with eagerly initialized, strongly referenced semaphores, with the specified number of permits.
    abstract int
    Returns the total number of stripes in this instance.
    private static int
    smear(int hashCode)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • LARGE_LAZY_CUTOFF

      private static final int LARGE_LAZY_CUTOFF
      If there are at least this many stripes, we assume the memory usage of a ConcurrentMap will be smaller than a large array. (This assumes that in the lazy case, most stripes are unused. As always, if many stripes are in use, a non-lazy striped makes more sense.)
      See Also:
    • ALL_SET

      private static final int ALL_SET
      A bit mask were all bits are set.
      See Also:
  • Constructor Details

    • Striped

      private Striped()
  • Method Details

    • get

      public abstract L get(Object key)
      Returns the stripe that corresponds to the passed key. It is always guaranteed that if key1.equals(key2), then get(key1) == get(key2).
      Parameters:
      key - an arbitrary, non-null key
      Returns:
      the stripe that the passed key corresponds to
    • getAt

      public abstract L getAt(int index)
      Returns the stripe at the specified index. Valid indexes are 0, inclusively, to size(), exclusively.
      Parameters:
      index - the index of the stripe to return; must be in [0...size())
      Returns:
      the stripe at the specified index
    • indexFor

      abstract int indexFor(Object key)
      Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key).
    • size

      public abstract int size()
      Returns the total number of stripes in this instance.
    • bulkGet

      public Iterable<L> bulkGet(Iterable<? extends Object> keys)
      Returns the stripes that correspond to the passed objects, in ascending (as per getAt(int)) order. Thus, threads that use the stripes in the order returned by this method are guaranteed to not deadlock each other.

      It should be noted that using a Striped<L> with relatively few stripes, and bulkGet(keys) with a relative large number of keys can cause an excessive number of shared stripes (much like the birthday paradox, where much fewer than anticipated birthdays are needed for a pair of them to match). Please consider carefully the implications of the number of stripes, the intended concurrency level, and the typical number of keys used in a bulkGet(keys) operation. See Balls in Bins model for mathematical formulas that can be used to estimate the probability of collisions.

      Parameters:
      keys - arbitrary non-null keys
      Returns:
      the stripes corresponding to the objects (one per each object, derived by delegating to get(Object); may contain duplicates), in an increasing index order.
    • custom

      static <L> Striped<L> custom(int stripes, Supplier<L> supplier)
      Creates a Striped<L> with eagerly initialized, strongly referenced locks. Every lock is obtained from the passed supplier.
      Parameters:
      stripes - the minimum number of stripes (locks) required
      supplier - a Supplier<L> object to obtain locks from
      Returns:
      a new Striped<L>
    • lock

      public static Striped<Lock> lock(int stripes)
      Creates a Striped<Lock> with eagerly initialized, strongly referenced locks. Every lock is reentrant.
      Parameters:
      stripes - the minimum number of stripes (locks) required
      Returns:
      a new Striped<Lock>
    • lazyWeakLock

      public static Striped<Lock> lazyWeakLock(int stripes)
      Creates a Striped<Lock> with lazily initialized, weakly referenced locks. Every lock is reentrant.
      Parameters:
      stripes - the minimum number of stripes (locks) required
      Returns:
      a new Striped<Lock>
    • lazyWeakCustom

      static <L> Striped<L> lazyWeakCustom(int stripes, Supplier<L> supplier)
      Creates a Striped<L> with lazily initialized, weakly referenced locks. Every lock is obtained from the passed supplier.
      Parameters:
      stripes - the minimum number of stripes (locks) required
      supplier - a Supplier<L> object to obtain locks from
      Returns:
      a new Striped<L>
    • semaphore

      public static Striped<Semaphore> semaphore(int stripes, int permits)
      Creates a Striped<Semaphore> with eagerly initialized, strongly referenced semaphores, with the specified number of permits.
      Parameters:
      stripes - the minimum number of stripes (semaphores) required
      permits - the number of permits in each semaphore
      Returns:
      a new Striped<Semaphore>
    • lazyWeakSemaphore

      public static Striped<Semaphore> lazyWeakSemaphore(int stripes, int permits)
      Creates a Striped<Semaphore> with lazily initialized, weakly referenced semaphores, with the specified number of permits.
      Parameters:
      stripes - the minimum number of stripes (semaphores) required
      permits - the number of permits in each semaphore
      Returns:
      a new Striped<Semaphore>
    • readWriteLock

      public static Striped<ReadWriteLock> readWriteLock(int stripes)
      Creates a Striped<ReadWriteLock> with eagerly initialized, strongly referenced read-write locks. Every lock is reentrant.
      Parameters:
      stripes - the minimum number of stripes (locks) required
      Returns:
      a new Striped<ReadWriteLock>
    • lazyWeakReadWriteLock

      public static Striped<ReadWriteLock> lazyWeakReadWriteLock(int stripes)
      Creates a Striped<ReadWriteLock> with lazily initialized, weakly referenced read-write locks. Every lock is reentrant.
      Parameters:
      stripes - the minimum number of stripes (locks) required
      Returns:
      a new Striped<ReadWriteLock>
    • ceilToPowerOfTwo

      private static int ceilToPowerOfTwo(int x)
    • smear

      private static int smear(int hashCode)