1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.hadoop.hbase.io.hfile;
21
22 import java.nio.ByteBuffer;
23 import java.util.Random;
24
25 import org.apache.hadoop.hbase.io.HeapSize;
26 import org.apache.hadoop.hbase.util.ClassSize;
27
28 import junit.framework.TestCase;
29
30
31
32
33
34
35
36
37 public class TestLruBlockCache extends TestCase {
38
39 public void testBackgroundEvictionThread() throws Exception {
40
41 long maxSize = 100000;
42 long blockSize = calculateBlockSizeDefault(maxSize, 9);
43
44 LruBlockCache cache = new LruBlockCache(maxSize,blockSize);
45
46 Block [] blocks = generateFixedBlocks(10, blockSize, "block");
47
48
49 for(Block block : blocks) {
50 cache.cacheBlock(block.blockName, block.buf);
51 }
52
53
54 int n = 0;
55 while(cache.getEvictionCount() == 0) {
56 System.out.println("sleep");
57 Thread.sleep(1000);
58 assertTrue(n++ < 2);
59 }
60 System.out.println("Background Evictions run: " + cache.getEvictionCount());
61
62
63 assertEquals(cache.getEvictionCount(), 1);
64 }
65
66 public void testCacheSimple() throws Exception {
67
68 long maxSize = 1000000;
69 long blockSize = calculateBlockSizeDefault(maxSize, 101);
70
71 LruBlockCache cache = new LruBlockCache(maxSize, blockSize);
72
73 Block [] blocks = generateRandomBlocks(100, blockSize);
74
75 long expectedCacheSize = cache.heapSize();
76
77
78 for(Block block : blocks) {
79 assertTrue(cache.getBlock(block.blockName, true) == null);
80 }
81
82
83 for(Block block : blocks) {
84 cache.cacheBlock(block.blockName, block.buf);
85 expectedCacheSize += block.heapSize();
86 }
87
88
89 assertEquals(expectedCacheSize, cache.heapSize());
90
91
92 for(Block block : blocks) {
93 ByteBuffer buf = cache.getBlock(block.blockName, true);
94 assertTrue(buf != null);
95 assertEquals(buf.capacity(), block.buf.capacity());
96 }
97
98
99 for(Block block : blocks) {
100 try {
101 cache.cacheBlock(block.blockName, block.buf);
102 assertTrue("Cache should not allow re-caching a block", false);
103 } catch(RuntimeException re) {
104
105 }
106 }
107
108
109 assertEquals(expectedCacheSize, cache.heapSize());
110
111
112 for(Block block : blocks) {
113 ByteBuffer buf = cache.getBlock(block.blockName, true);
114 assertTrue(buf != null);
115 assertEquals(buf.capacity(), block.buf.capacity());
116 }
117
118
119 assertEquals(0, cache.getEvictionCount());
120 Thread t = new LruBlockCache.StatisticsThread(cache);
121 t.start();
122 t.join();
123 }
124
125 public void testCacheEvictionSimple() throws Exception {
126
127 long maxSize = 100000;
128 long blockSize = calculateBlockSizeDefault(maxSize, 10);
129
130 LruBlockCache cache = new LruBlockCache(maxSize,blockSize,false);
131
132 Block [] blocks = generateFixedBlocks(10, blockSize, "block");
133
134 long expectedCacheSize = cache.heapSize();
135
136
137 for(Block block : blocks) {
138 cache.cacheBlock(block.blockName, block.buf);
139 expectedCacheSize += block.heapSize();
140 }
141
142
143 assertEquals(1, cache.getEvictionCount());
144
145
146 assertTrue(expectedCacheSize >
147 (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
148
149
150 assertTrue(cache.heapSize() < maxSize);
151
152
153 assertTrue(cache.heapSize() <
154 (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
155
156
157 assertTrue(cache.getBlock(blocks[0].blockName, true) == null);
158 assertTrue(cache.getBlock(blocks[1].blockName, true) == null);
159 for(int i=2;i<blocks.length;i++) {
160 assertEquals(cache.getBlock(blocks[i].blockName, true),
161 blocks[i].buf);
162 }
163 }
164
165 public void testCacheEvictionTwoPriorities() throws Exception {
166
167 long maxSize = 100000;
168 long blockSize = calculateBlockSizeDefault(maxSize, 10);
169
170 LruBlockCache cache = new LruBlockCache(maxSize,blockSize,false);
171
172 Block [] singleBlocks = generateFixedBlocks(5, 10000, "single");
173 Block [] multiBlocks = generateFixedBlocks(5, 10000, "multi");
174
175 long expectedCacheSize = cache.heapSize();
176
177
178 for(Block block : multiBlocks) {
179 cache.cacheBlock(block.blockName, block.buf);
180 expectedCacheSize += block.heapSize();
181 assertEquals(cache.getBlock(block.blockName, true), block.buf);
182 }
183
184
185 for(Block block : singleBlocks) {
186 cache.cacheBlock(block.blockName, block.buf);
187 expectedCacheSize += block.heapSize();
188 }
189
190
191 assertEquals(cache.getEvictionCount(), 1);
192
193
194 assertEquals(cache.getEvictedCount(), 2);
195
196
197 assertTrue(expectedCacheSize >
198 (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
199
200
201 assertTrue(cache.heapSize() <= maxSize);
202
203
204 assertTrue(cache.heapSize() <=
205 (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
206
207
208
209
210
211 assertTrue(cache.getBlock(singleBlocks[0].blockName, true) == null);
212 assertTrue(cache.getBlock(multiBlocks[0].blockName, true) == null);
213
214
215 for(int i=1;i<4;i++) {
216 assertEquals(cache.getBlock(singleBlocks[i].blockName, true),
217 singleBlocks[i].buf);
218 assertEquals(cache.getBlock(multiBlocks[i].blockName, true),
219 multiBlocks[i].buf);
220 }
221 }
222
223 public void testCacheEvictionThreePriorities() throws Exception {
224
225 long maxSize = 100000;
226 long blockSize = calculateBlockSize(maxSize, 10);
227
228 LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
229 (int)Math.ceil(1.2*maxSize/blockSize),
230 LruBlockCache.DEFAULT_LOAD_FACTOR,
231 LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
232 0.98f,
233 0.99f,
234 0.33f,
235 0.33f,
236 0.34f);
237
238
239 Block [] singleBlocks = generateFixedBlocks(5, blockSize, "single");
240 Block [] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
241 Block [] memoryBlocks = generateFixedBlocks(5, blockSize, "memory");
242
243 long expectedCacheSize = cache.heapSize();
244
245
246 for(int i=0;i<3;i++) {
247
248
249 cache.cacheBlock(singleBlocks[i].blockName, singleBlocks[i].buf);
250 expectedCacheSize += singleBlocks[i].heapSize();
251
252
253 cache.cacheBlock(multiBlocks[i].blockName, multiBlocks[i].buf);
254 expectedCacheSize += multiBlocks[i].heapSize();
255 cache.getBlock(multiBlocks[i].blockName, true);
256
257
258 cache.cacheBlock(memoryBlocks[i].blockName, memoryBlocks[i].buf, true);
259 expectedCacheSize += memoryBlocks[i].heapSize();
260
261 }
262
263
264 assertEquals(0, cache.getEvictionCount());
265
266
267 assertEquals(expectedCacheSize, cache.heapSize());
268
269
270 cache.cacheBlock(singleBlocks[3].blockName, singleBlocks[3].buf);
271
272
273 assertEquals(1, cache.getEvictionCount());
274 assertEquals(1, cache.getEvictedCount());
275
276
277 assertEquals(null, cache.getBlock(singleBlocks[0].blockName, true));
278
279
280 cache.getBlock(singleBlocks[1].blockName, true);
281
282
283 cache.cacheBlock(singleBlocks[4].blockName, singleBlocks[4].buf);
284
285
286 assertEquals(2, cache.getEvictionCount());
287 assertEquals(2, cache.getEvictedCount());
288
289
290 assertEquals(null, cache.getBlock(multiBlocks[0].blockName, true));
291
292
293 cache.cacheBlock(memoryBlocks[3].blockName, memoryBlocks[3].buf, true);
294
295
296 assertEquals(3, cache.getEvictionCount());
297 assertEquals(3, cache.getEvictedCount());
298
299
300 assertEquals(null, cache.getBlock(memoryBlocks[0].blockName, true));
301
302
303 Block [] bigBlocks = generateFixedBlocks(3, blockSize*3, "big");
304 cache.cacheBlock(bigBlocks[0].blockName, bigBlocks[0].buf);
305
306
307 assertEquals(4, cache.getEvictionCount());
308 assertEquals(6, cache.getEvictedCount());
309
310
311 assertEquals(null, cache.getBlock(singleBlocks[2].blockName, true));
312 assertEquals(null, cache.getBlock(singleBlocks[3].blockName, true));
313 assertEquals(null, cache.getBlock(singleBlocks[4].blockName, true));
314
315
316 cache.getBlock(bigBlocks[0].blockName, true);
317
318
319 cache.cacheBlock(bigBlocks[1].blockName, bigBlocks[1].buf);
320
321
322 assertEquals(5, cache.getEvictionCount());
323 assertEquals(9, cache.getEvictedCount());
324
325
326 assertEquals(null, cache.getBlock(singleBlocks[1].blockName, true));
327 assertEquals(null, cache.getBlock(multiBlocks[1].blockName, true));
328 assertEquals(null, cache.getBlock(multiBlocks[2].blockName, true));
329
330
331 cache.cacheBlock(bigBlocks[2].blockName, bigBlocks[2].buf, true);
332
333
334 assertEquals(6, cache.getEvictionCount());
335 assertEquals(12, cache.getEvictedCount());
336
337
338 assertEquals(null, cache.getBlock(memoryBlocks[1].blockName, true));
339 assertEquals(null, cache.getBlock(memoryBlocks[2].blockName, true));
340 assertEquals(null, cache.getBlock(memoryBlocks[3].blockName, true));
341
342
343 }
344
345
346 public void testScanResistance() throws Exception {
347
348 long maxSize = 100000;
349 long blockSize = calculateBlockSize(maxSize, 10);
350
351 LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
352 (int)Math.ceil(1.2*maxSize/blockSize),
353 LruBlockCache.DEFAULT_LOAD_FACTOR,
354 LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
355 0.66f,
356 0.99f,
357 0.33f,
358 0.33f,
359 0.34f);
360
361 Block [] singleBlocks = generateFixedBlocks(20, blockSize, "single");
362 Block [] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
363
364
365 for(Block block : multiBlocks) {
366 cache.cacheBlock(block.blockName, block.buf);
367 cache.getBlock(block.blockName, true);
368 }
369
370
371 for(int i=0;i<5;i++) {
372 cache.cacheBlock(singleBlocks[i].blockName, singleBlocks[i].buf);
373 }
374
375
376 assertEquals(1, cache.getEvictionCount());
377
378
379 assertEquals(4, cache.getEvictedCount());
380
381
382 assertEquals(null, cache.getBlock(singleBlocks[0].blockName, true));
383 assertEquals(null, cache.getBlock(singleBlocks[1].blockName, true));
384 assertEquals(null, cache.getBlock(multiBlocks[0].blockName, true));
385 assertEquals(null, cache.getBlock(multiBlocks[1].blockName, true));
386
387
388
389
390
391
392
393
394 for(int i=5;i<18;i++) {
395 cache.cacheBlock(singleBlocks[i].blockName, singleBlocks[i].buf);
396 }
397
398
399 assertEquals(4, cache.getEvictionCount());
400 assertEquals(16, cache.getEvictedCount());
401
402
403 assertEquals(7, cache.size());
404
405 }
406
407
408 public void testResizeBlockCache() throws Exception {
409
410 long maxSize = 300000;
411 long blockSize = calculateBlockSize(maxSize, 31);
412
413 LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
414 (int)Math.ceil(1.2*maxSize/blockSize),
415 LruBlockCache.DEFAULT_LOAD_FACTOR,
416 LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
417 0.98f,
418 0.99f,
419 0.33f,
420 0.33f,
421 0.34f);
422
423 Block [] singleBlocks = generateFixedBlocks(10, blockSize, "single");
424 Block [] multiBlocks = generateFixedBlocks(10, blockSize, "multi");
425 Block [] memoryBlocks = generateFixedBlocks(10, blockSize, "memory");
426
427
428 for(int i=0;i<10;i++) {
429
430
431 cache.cacheBlock(singleBlocks[i].blockName, singleBlocks[i].buf);
432
433
434 cache.cacheBlock(multiBlocks[i].blockName, multiBlocks[i].buf);
435 cache.getBlock(multiBlocks[i].blockName, true);
436
437
438 cache.cacheBlock(memoryBlocks[i].blockName, memoryBlocks[i].buf, true);
439 }
440
441
442 assertEquals(0, cache.getEvictionCount());
443
444
445 cache.setMaxSize((long)(maxSize * 0.5f));
446
447
448 assertEquals(1, cache.getEvictionCount());
449
450
451 assertEquals(15, cache.getEvictedCount());
452
453
454 for(int i=0;i<5;i++) {
455 assertEquals(null, cache.getBlock(singleBlocks[i].blockName, true));
456 assertEquals(null, cache.getBlock(multiBlocks[i].blockName, true));
457 assertEquals(null, cache.getBlock(memoryBlocks[i].blockName, true));
458 }
459
460
461 for(int i=5;i<10;i++) {
462 assertEquals(singleBlocks[i].buf, cache.getBlock(singleBlocks[i].blockName, true));
463 assertEquals(multiBlocks[i].buf, cache.getBlock(multiBlocks[i].blockName, true));
464 assertEquals(memoryBlocks[i].buf, cache.getBlock(memoryBlocks[i].blockName, true));
465 }
466 }
467
468 private Block [] generateFixedBlocks(int numBlocks, int size, String pfx) {
469 Block [] blocks = new Block[numBlocks];
470 for(int i=0;i<numBlocks;i++) {
471 blocks[i] = new Block(pfx + i, size);
472 }
473 return blocks;
474 }
475
476 private Block [] generateFixedBlocks(int numBlocks, long size, String pfx) {
477 return generateFixedBlocks(numBlocks, (int)size, pfx);
478 }
479
480 private Block [] generateRandomBlocks(int numBlocks, long maxSize) {
481 Block [] blocks = new Block[numBlocks];
482 Random r = new Random();
483 for(int i=0;i<numBlocks;i++) {
484 blocks[i] = new Block("block" + i, r.nextInt((int)maxSize)+1);
485 }
486 return blocks;
487 }
488
489 private long calculateBlockSize(long maxSize, int numBlocks) {
490 long roughBlockSize = maxSize / numBlocks;
491 int numEntries = (int)Math.ceil((1.2)*maxSize/roughBlockSize);
492 long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD +
493 ClassSize.CONCURRENT_HASHMAP +
494 (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
495 (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
496 long negateBlockSize = (long)(totalOverhead/numEntries);
497 negateBlockSize += CachedBlock.PER_BLOCK_OVERHEAD;
498 return ClassSize.align((long)Math.floor((roughBlockSize - negateBlockSize)*0.99f));
499 }
500
501 private long calculateBlockSizeDefault(long maxSize, int numBlocks) {
502 long roughBlockSize = maxSize / numBlocks;
503 int numEntries = (int)Math.ceil((1.2)*maxSize/roughBlockSize);
504 long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD +
505 ClassSize.CONCURRENT_HASHMAP +
506 (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
507 (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
508 long negateBlockSize = totalOverhead / numEntries;
509 negateBlockSize += CachedBlock.PER_BLOCK_OVERHEAD;
510 return ClassSize.align((long)Math.floor((roughBlockSize - negateBlockSize)*
511 LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
512 }
513
514 private static class Block implements HeapSize {
515 String blockName;
516 ByteBuffer buf;
517
518 Block(String blockName, int size) {
519 this.blockName = blockName;
520 this.buf = ByteBuffer.allocate(size);
521 }
522
523 public long heapSize() {
524 return CachedBlock.PER_BLOCK_OVERHEAD +
525 ClassSize.align(blockName.length()) +
526 ClassSize.align(buf.capacity());
527 }
528 }
529 }