[GitHub] keith-turner commented on a change in pull request #990: Avoid multiple threads loading same cache block

[GitBox <gi...@apache.org>]

keith-turner commented on a change in pull request #990: Avoid multiple threads loading same cache block
URL: https://github.com/apache/accumulo/pull/990#discussion_r260819750
 
 

 ##########
 File path: core/src/main/java/org/apache/accumulo/core/file/blockfile/cache/LruBlockCache.java
 ##########
 @@ -143,6 +144,9 @@
   /** Overhead of the structure itself */
   private long overhead;
 
+  /** Locks used when loading data not in the cache. Size is prime number. */
 
 Review comment:
   The fact that is a prime is relevant.  When doing mod operations, if the data happen to share a subset of prime factors with the divisor the data will only bin to a few buckets.  So only having one prime factors lowers the chance of this.  For example `(x*5*5) % 100` will always bin to 4 buckets because 100 has the factors 5*5.  If for some reason the data is more likely to share subsets of the prime factors of 100 (2,2,5,5), then it will not evenly spread over the 100 buckets.
   
   For example the following little program skews the data to more likely share some of the prime factors of 100.
   
   ```java
       Random random = new Random();
   
       Map<Integer,Integer> counts = new HashMap<>();
   
       for(int i = 0; i < 10000; i++) {
         int r;
   
         switch(random.nextInt(3)) {
           case 0:
             r = (i * 25) % 100;
             break;
           case 1:
             r = (i * 10) % 100;
             break;
           case 2:
             r = (i * 4) % 100;
             break;
          default:
            r = i;
         }
   
         int c = counts.getOrDefault(r, 0);
         counts.put(r, c+1);
       }
   
   
       System.out.println(new TreeMap<>(counts));
   ```
   
   It outputs the following 
   
   ```
   {0=1297, 4=139, 8=130, 10=359, 12=124, 16=123, 20=475, 24=128, 25=806, 28=130, 30=345, 32=131, 36=122, 40=478, 44=130, 48=147, 50=1177, 52=132, 56=133, 60=466, 64=140, 68=142, 70=329, 72=145, 75=836, 76=136, 80=455, 84=137, 88=125, 90=319, 92=134, 96=130}
   ```
   
   If the data ever consistently was a multiple of this prime I chose, then things would go really really badly.  I wanted to use the Guava library which according to it internal comments copied some java code for smearing hashes, that is probably better than this.  However the Guava library was `@Beta`.

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services