1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.mavibot.btree;
21
22
23 import java.io.Closeable;
24 import java.io.IOException;
25 import java.nio.ByteBuffer;
26 import java.nio.channels.FileChannel;
27 import java.util.concurrent.ConcurrentLinkedQueue;
28
29 import org.apache.commons.collections.map.LRUMap;
30 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
31 import org.slf4j.Logger;
32 import org.slf4j.LoggerFactory;
33
34
35
36
37
38
39
40
41
42
43 public class PersistedBTree<K, V> extends AbstractBTree<K, V> implements Closeable
44 {
45
46 protected static final Logger LOG = LoggerFactory.getLogger( PersistedBTree.class );
47
48 protected static final Logger LOG_PAGES = LoggerFactory.getLogger( "org.apache.directory.mavibot.LOG_PAGES" );
49
50
51 protected LRUMap cache;
52
53
54 public static final int DEFAULT_CACHE_SIZE = 1000;
55
56
57 protected int cacheSize = DEFAULT_CACHE_SIZE;
58
59
60 private static final int DEFAULT_VALUE_THRESHOLD_UP = 8;
61
62
63 private static final int DEFAULT_VALUE_THRESHOLD_LOW = 1;
64
65
66 static int valueThresholdUp = DEFAULT_VALUE_THRESHOLD_UP;
67 static int valueThresholdLow = DEFAULT_VALUE_THRESHOLD_LOW;
68
69
70 private long btreeInfoOffset = RecordManager.NO_PAGE;
71
72
73 private RecordManager recordManager;
74
75
76
77
78
79 PersistedBTree()
80 {
81 setType( BTreeTypeEnum.PERSISTED );
82 }
83
84
85
86
87
88
89
90
91 PersistedBTree( PersistedBTreeConfiguration<K, V> configuration )
92 {
93 super();
94 String name = configuration.getName();
95
96 if ( name == null )
97 {
98 throw new IllegalArgumentException( "BTree name cannot be null" );
99 }
100
101 setName( name );
102 setPageSize( configuration.getPageSize() );
103 setKeySerializer( configuration.getKeySerializer() );
104 setValueSerializer( configuration.getValueSerializer() );
105 setAllowDuplicates( configuration.isAllowDuplicates() );
106 setType( configuration.getBtreeType() );
107
108 readTimeOut = configuration.getReadTimeOut();
109 writeBufferSize = configuration.getWriteBufferSize();
110 cacheSize = configuration.getCacheSize();
111
112 if ( keySerializer.getComparator() == null )
113 {
114 throw new IllegalArgumentException( "Comparator should not be null" );
115 }
116
117
118
119 Page<K, V> rootPage = new PersistedLeaf<K, V>( this );
120
121
122 BTreeHeader<K, V> btreeHeader = new BTreeHeader<K, V>();
123 btreeHeader.setRootPage( rootPage );
124 btreeHeader.setBtree( this );
125
126 switch ( btreeType )
127 {
128 case BTREE_OF_BTREES:
129 case COPIED_PAGES_BTREE:
130
131 init( null );
132 currentBtreeHeader = btreeHeader;
133 break;
134
135 case PERSISTED_SUB:
136 init( ( PersistedBTree<K, V> ) configuration.getParentBTree() );
137 btreeRevisions.put( 0L, btreeHeader );
138 currentBtreeHeader = btreeHeader;
139 break;
140
141 default:
142
143 init( null );
144 btreeRevisions.put( 0L, btreeHeader );
145 currentBtreeHeader = btreeHeader;
146 break;
147 }
148 }
149
150
151
152
153
154
155
156 public void init( BTree<K, V> parentBTree )
157 {
158 if ( parentBTree == null )
159 {
160
161
162
163 readTransactions = new ConcurrentLinkedQueue<ReadTransaction<K, V>>();
164
165 if ( cacheSize < 1 )
166 {
167 cacheSize = DEFAULT_CACHE_SIZE;
168 }
169
170 cache = new LRUMap( cacheSize );
171 }
172 else
173 {
174 this.cache = ( ( PersistedBTree<K, V> ) parentBTree ).getCache();
175 this.readTransactions = ( ( PersistedBTree<K, V> ) parentBTree ).getReadTransactions();
176 }
177
178
179
180
181 }
182
183
184
185
186
187 LRUMap getCache()
188 {
189 return cache;
190 }
191
192
193
194
195
196 ConcurrentLinkedQueue<ReadTransaction<K, V>> getReadTransactions()
197 {
198 return readTransactions;
199 }
200
201
202
203
204
205 public void close() throws IOException
206 {
207
208
209
210
211
212 cache.clear();
213 }
214
215
216
217
218
219 long getBtreeOffset()
220 {
221 return getBTreeHeader( getName() ).getBTreeHeaderOffset();
222 }
223
224
225
226
227
228 void setBtreeHeaderOffset( long btreeHeaderOffset )
229 {
230 getBTreeHeader( getName() ).setBTreeHeaderOffset( btreeHeaderOffset );
231 }
232
233
234
235
236
237 long getRootPageOffset()
238 {
239 return getBTreeHeader( getName() ).getRootPageOffset();
240 }
241
242
243
244
245
246
247
248 RecordManager getRecordManager()
249 {
250 return recordManager;
251 }
252
253
254
255
256
257
258
259 void setRecordManager( RecordManager recordManager )
260 {
261
262 transactionManager = recordManager;
263 this.recordManager = recordManager;
264 }
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279 Tuple<K, V> delete( K key, V value, long revision ) throws IOException
280 {
281
282
283 if ( revision == -1L )
284 {
285 revision = currentRevision.get() + 1;
286 }
287
288 try
289 {
290
291
292 DeleteResult<K, V> result = processDelete( key, value, revision );
293
294
295 if ( result instanceof NotPresentResult )
296 {
297
298
299
300 return null;
301 }
302
303
304 AbstractDeleteResult<K, V> deleteResult = ( AbstractDeleteResult<K, V> ) result;
305
306 Tuple<K, V> tuple = deleteResult.getRemovedElement();
307
308
309
310
311
312 return tuple;
313 }
314 catch ( IOException ioe )
315 {
316
317 throw ioe;
318 }
319 }
320
321
322
323
324
325 private DeleteResult<K, V> processDelete( K key, V value, long revision ) throws IOException
326 {
327
328 BTreeHeader<K, V> btreeHeader = getBTreeHeader( getName() );
329
330
331
332 DeleteResult<K, V> result = btreeHeader.getRootPage().delete( key, value, revision );
333
334 if ( result instanceof NotPresentResult )
335 {
336
337 return result;
338 }
339
340
341 BTreeHeader<K, V> newBtreeHeader = btreeHeader.copy();
342
343
344
345 if ( ( btreeType == BTreeTypeEnum.BTREE_OF_BTREES ) || ( btreeType == BTreeTypeEnum.COPIED_PAGES_BTREE ) )
346 {
347 PageIO[] pageIos = recordManager.readPageIOs( btreeHeader.getBTreeHeaderOffset(), -1L );
348
349 for ( PageIO pageIo : pageIos )
350 {
351 recordManager.freedPages.add( pageIo );
352 }
353 }
354
355
356 AbstractDeleteResult<K, V> removeResult = ( AbstractDeleteResult<K, V> ) result;
357
358
359 Page<K, V> newRootPage = removeResult.getModifiedPage();
360
361
362
363
364 writePage( newRootPage, revision );
365
366
367 newBtreeHeader.decrementNbElems();
368 newBtreeHeader.setRootPage( newRootPage );
369 newBtreeHeader.setRevision( revision );
370
371
372 long newBtreeHeaderOffset = recordManager.writeBtreeHeader( this, newBtreeHeader );
373
374
375 switch ( btreeType )
376 {
377 case PERSISTED:
378
379 recordManager.addInBtreeOfBtrees( getName(), revision, newBtreeHeaderOffset );
380
381 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
382
383
384 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
385
386 break;
387
388 case PERSISTED_SUB:
389
390 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
391
392
393
394 currentRevision.set( revision );
395
396 break;
397
398 case BTREE_OF_BTREES:
399
400 recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L );
401
402
403 recordManager.freePages( this, revision, result.getCopiedPages() );
404
405
406 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
407
408 break;
409
410 case COPIED_PAGES_BTREE:
411
412 recordManager.updateRecordManagerHeader( -1L, newBtreeHeaderOffset );
413
414
415 recordManager.freePages( this, revision, result.getCopiedPages() );
416
417
418 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
419
420 break;
421
422 default:
423
424 break;
425 }
426
427
428 return result;
429 }
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445 InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
446 {
447
448
449 if ( revision == -1L )
450 {
451 revision = currentRevision.get() + 1;
452 }
453
454 try
455 {
456
457
458
459 InsertResult<K, V> result = processInsert( key, value, revision );
460
461
462 return result;
463 }
464 catch ( IOException ioe )
465 {
466 throw ioe;
467 }
468 }
469
470
471 private BTreeHeader<K, V> getBTreeHeader( String name )
472 {
473 switch ( btreeType )
474 {
475 case PERSISTED_SUB:
476 return getBtreeHeader();
477
478 case BTREE_OF_BTREES:
479 return recordManager.getNewBTreeHeader( RecordManager.BTREE_OF_BTREES_NAME );
480
481 case COPIED_PAGES_BTREE:
482 return recordManager.getNewBTreeHeader( RecordManager.COPIED_PAGE_BTREE_NAME );
483
484 default:
485 return recordManager.getBTreeHeader( name );
486 }
487 }
488
489
490 private BTreeHeader<K, V> getNewBTreeHeader( String name )
491 {
492 if ( btreeType == BTreeTypeEnum.PERSISTED_SUB )
493 {
494 return getBtreeHeader();
495 }
496
497 BTreeHeader<K, V> btreeHeader = recordManager.getNewBTreeHeader( getName() );
498
499 return btreeHeader;
500 }
501
502
503
504
505
506 private InsertResult<K, V> processInsert( K key, V value, long revision ) throws IOException
507 {
508
509 BTreeHeader<K, V> btreeHeader = getBTreeHeader( getName() );
510 InsertResult<K, V> result = btreeHeader.getRootPage().insert( key, value, revision );
511
512 if ( result instanceof ExistsResult )
513 {
514 return result;
515 }
516
517
518 BTreeHeader<K, V> newBtreeHeader = btreeHeader.copy();
519
520
521
522 if ( ( btreeType == BTreeTypeEnum.BTREE_OF_BTREES ) || ( btreeType == BTreeTypeEnum.COPIED_PAGES_BTREE ) )
523 {
524 PageIO[] pageIos = recordManager.readPageIOs( btreeHeader.getBTreeHeaderOffset(), -1L );
525
526 for ( PageIO pageIo : pageIos )
527 {
528 recordManager.freedPages.add( pageIo );
529 }
530 }
531
532 Page<K, V> newRootPage;
533
534 if ( result instanceof ModifyResult )
535 {
536 ModifyResult<K, V> modifyResult = ( ( ModifyResult<K, V> ) result );
537
538 newRootPage = modifyResult.getModifiedPage();
539
540
541 if ( modifyResult.getModifiedValue() == null )
542 {
543 newBtreeHeader.incrementNbElems();
544 }
545 }
546 else
547 {
548
549
550 SplitResult<K, V> splitResult = ( ( SplitResult<K, V> ) result );
551
552 K pivot = splitResult.getPivot();
553 Page<K, V> leftPage = splitResult.getLeftPage();
554 Page<K, V> rightPage = splitResult.getRightPage();
555
556
557
558 PageHolder<K, V> holderLeft = writePage( leftPage, revision );
559
560 PageHolder<K, V> holderRight = writePage( rightPage, revision );
561
562
563 newRootPage = new PersistedNode<K, V>( this, revision, pivot, holderLeft, holderRight );
564
565
566 newBtreeHeader.incrementNbElems();
567 }
568
569
570 LOG_PAGES.debug( "Writing the new rootPage revision {} for {}", revision, name );
571 writePage( newRootPage, revision );
572
573
574 newBtreeHeader.setRootPage( newRootPage );
575 newBtreeHeader.setRevision( revision );
576
577
578 long newBtreeHeaderOffset = recordManager.writeBtreeHeader( this, newBtreeHeader );
579
580
581 switch ( btreeType )
582 {
583 case PERSISTED:
584
585 recordManager.addInBtreeOfBtrees( getName(), revision, newBtreeHeaderOffset );
586
587 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
588
589
590 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
591
592 break;
593
594 case PERSISTED_SUB:
595
596 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
597
598
599 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
600
601 currentRevision.set( revision );
602
603 break;
604
605 case BTREE_OF_BTREES:
606
607 recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L );
608
609
610 recordManager.freePages( this, revision, result.getCopiedPages() );
611
612
613 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
614
615 break;
616
617 case COPIED_PAGES_BTREE:
618
619 recordManager.updateRecordManagerHeader( -1L, newBtreeHeaderOffset );
620
621
622 recordManager.freePages( this, revision, result.getCopiedPages() );
623
624
625 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
626
627 break;
628
629 default:
630
631 break;
632 }
633
634
635 return result;
636 }
637
638
639
640
641
642
643
644
645
646
647 private void writeBuffer( FileChannel channel, ByteBuffer bb, byte[] buffer ) throws IOException
648 {
649 int size = buffer.length;
650 int pos = 0;
651
652
653 do
654 {
655 if ( bb.remaining() >= size )
656 {
657
658 bb.put( buffer, pos, size );
659 size = 0;
660 }
661 else
662 {
663
664 int len = bb.remaining();
665 size -= len;
666 bb.put( buffer, pos, len );
667 pos += len;
668
669 bb.flip();
670
671 channel.write( bb );
672
673 bb.clear();
674 }
675 }
676 while ( size > 0 );
677 }
678
679
680
681
682
683
684 private PageHolder<K, V> writePage( Page<K, V> modifiedPage, long revision ) throws IOException
685 {
686 PageHolder<K, V> pageHolder = recordManager.writePage( this, modifiedPage, revision );
687
688 return pageHolder;
689 }
690
691
692
693
694
695
696
697
698
699
700 public Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException
701 {
702 return recordManager.getRootPage( this, revision );
703 }
704
705
706
707
708
709
710
711 public Page<K, V> getRootPage()
712 {
713 return getBTreeHeader( getName() ).getRootPage();
714 }
715
716
717 void setRootPage( Page<K, V> root )
718 {
719 getBTreeHeader( getName() ).setRootPage( root );
720 }
721
722
723
724
725
726 public long getBtreeInfoOffset()
727 {
728 return btreeInfoOffset;
729 }
730
731
732
733
734
735 public void setBtreeInfoOffset( long btreeInfoOffset )
736 {
737 this.btreeInfoOffset = btreeInfoOffset;
738 }
739
740
741
742
743
744 protected ReadTransaction<K, V> beginReadTransaction()
745 {
746 BTreeHeader<K, V> btreeHeader = getBTreeHeader( getName() );
747
748 ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>( recordManager, btreeHeader, readTransactions );
749
750 readTransactions.add( readTransaction );
751
752 return readTransaction;
753 }
754
755
756
757
758
759 protected ReadTransaction<K, V> beginReadTransaction( long revision )
760 {
761 BTreeHeader<K, V> btreeHeader = getBtreeHeader( revision );
762
763 if ( btreeHeader != null )
764 {
765 ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>( recordManager, btreeHeader,
766 readTransactions );
767
768 readTransactions.add( readTransaction );
769
770 return readTransaction;
771 }
772 else
773 {
774 return null;
775 }
776 }
777
778
779
780
781
782 public String toString()
783 {
784 StringBuilder sb = new StringBuilder();
785
786 sb.append( "Managed BTree" );
787 sb.append( "[" ).append( getName() ).append( "]" );
788 sb.append( "( pageSize:" ).append( getPageSize() );
789
790 if ( getBTreeHeader( getName() ).getRootPage() != null )
791 {
792 sb.append( ", nbEntries:" ).append( getBTreeHeader( getName() ).getNbElems() );
793 }
794 else
795 {
796 sb.append( ", nbEntries:" ).append( 0 );
797 }
798
799 sb.append( ", comparator:" );
800
801 if ( keySerializer.getComparator() == null )
802 {
803 sb.append( "null" );
804 }
805 else
806 {
807 sb.append( keySerializer.getComparator().getClass().getSimpleName() );
808 }
809
810 sb.append( ", DuplicatesAllowed: " ).append( isAllowDuplicates() );
811
812 sb.append( ") : \n" );
813 sb.append( getBTreeHeader( getName() ).getRootPage().dumpPage( "" ) );
814
815 return sb.toString();
816 }
817 }