001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020 package org.apache.directory.server.core.partition.impl.btree.jdbm; 021 022 023 import java.io.File; 024 import java.io.IOException; 025 026 import javax.naming.NamingException; 027 028 import jdbm.RecordManager; 029 import jdbm.helper.MRU; 030 import jdbm.recman.BaseRecordManager; 031 import jdbm.recman.CacheRecordManager; 032 033 import org.apache.directory.server.core.partition.impl.btree.IndexCursorAdaptor; 034 import org.apache.directory.server.core.partition.impl.btree.LongComparator; 035 import org.apache.directory.server.i18n.I18n; 036 import org.apache.directory.server.xdbm.Index; 037 import org.apache.directory.server.xdbm.IndexCursor; 038 import org.apache.directory.server.xdbm.Tuple; 039 import org.apache.directory.shared.ldap.cursor.Cursor; 040 import org.apache.directory.shared.ldap.entry.BinaryValue; 041 import org.apache.directory.shared.ldap.schema.AttributeType; 042 import org.apache.directory.shared.ldap.schema.MatchingRule; 043 import org.apache.directory.shared.ldap.schema.SchemaManager; 044 import org.apache.directory.shared.ldap.schema.comparators.SerializableComparator; 045 import org.apache.directory.shared.ldap.util.SynchronizedLRUMap; 046 import org.slf4j.Logger; 047 import org.slf4j.LoggerFactory; 048 049 050 /** 051 * A Jdbm based index implementation. 052 * 053 * @org.apache.xbean.XBean 054 * 055 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 056 * @version $Rev: 928296 $ 057 */ 058 public class JdbmIndex<K, O> implements Index<K, O, Long> 059 { 060 /** A logger for this class */ 061 private static final Logger LOG = LoggerFactory.getLogger( JdbmIndex.class.getSimpleName() ); 062 063 /** 064 * default duplicate limit before duplicate keys switch to using a btree for values 065 */ 066 public static final int DEFAULT_DUPLICATE_LIMIT = 512; 067 068 /** the key used for the forward btree name */ 069 public static final String FORWARD_BTREE = "_forward"; 070 071 /** the key used for the reverse btree name */ 072 public static final String REVERSE_BTREE = "_reverse"; 073 074 /** the attribute type resolved for this JdbmIndex */ 075 private AttributeType attribute; 076 077 /** 078 * the forward btree where the btree key is the value of the indexed attribute and 079 * the value of the btree is the entry id of the entry containing an attribute with 080 * that value 081 */ 082 protected JdbmTable<K, Long> forward; 083 084 /** 085 * the reverse btree where the btree key is the entry id of the entry containing a 086 * value for the indexed attribute, and the btree value is the value of the indexed 087 * attribute 088 */ 089 protected JdbmTable<Long, K> reverse; 090 091 /** 092 * the JDBM record manager for the file containing this index 093 */ 094 protected RecordManager recMan; 095 096 /** 097 * the normalized value cache for this index 098 * @todo I don't think the keyCache is required anymore since the normalizer 099 * will cache values for us. 100 */ 101 protected SynchronizedLRUMap keyCache; 102 103 /** the size (number of index entries) for the cache */ 104 protected int cacheSize = DEFAULT_INDEX_CACHE_SIZE; 105 106 /** 107 * duplicate limit before duplicate keys switch to using a btree for values 108 */ 109 protected int numDupLimit = DEFAULT_DUPLICATE_LIMIT; 110 111 /** 112 * the attribute identifier set at configuration time for this index which may not 113 * be the OID but an alias name for the attributeType associated with this Index 114 */ 115 private String attributeId; 116 117 /** whether or not this index has been initialized */ 118 protected boolean initialized; 119 120 /** a custom working directory path when specified in configuration */ 121 protected File wkDirPath; 122 123 124 /* 125 * NOTE: Duplicate Key Limit 126 * 127 * Jdbm cannot store duplicate keys: meaning it cannot have more than one value 128 * for the same key in the btree. Thus as a workaround we stuff values for the 129 * same key into a TreeSet. This is only effective up to some threshold after 130 * which we run into problems with serialization on and off disk. A threshold 131 * is used to determine when to switch from using a TreeSet to start using another 132 * btree in the same index file just for the values. This value only btree just 133 * has keys populated without a value for it's btree entries. When the switch 134 * occurs the value for the key in the index btree contains a pointer to the 135 * btree containing it's values. 136 * 137 * This numDupLimit is the threshold at which we switch from using in memory 138 * containers for values of the same key to using a btree for those values 139 * instead with indirection. 140 */ 141 142 // ------------------------------------------------------------------------ 143 // C O N S T R U C T O R S 144 // ---------------------------------------------------------------------- 145 146 public JdbmIndex() 147 { 148 initialized = false; 149 } 150 151 152 public JdbmIndex( String attributeId ) 153 { 154 initialized = false; 155 setAttributeId( attributeId ); 156 } 157 158 159 public void init( SchemaManager schemaManager, AttributeType attributeType, File wkDirPath ) throws IOException 160 { 161 LOG.debug( "Initializing an Index for attribute '{}'", attributeType.getName() ); 162 163 keyCache = new SynchronizedLRUMap( cacheSize ); 164 attribute = attributeType; 165 166 if ( attributeId == null ) 167 { 168 setAttributeId( attribute.getName() ); 169 } 170 171 if ( this.wkDirPath == null ) 172 { 173 this.wkDirPath = wkDirPath; 174 } 175 176 File file = new File( this.wkDirPath.getPath() + File.separator + attribute.getName() ); 177 String path = file.getAbsolutePath(); 178 BaseRecordManager base = new BaseRecordManager( path ); 179 base.disableTransactions(); 180 this.recMan = new CacheRecordManager( base, new MRU( cacheSize ) ); 181 182 try 183 { 184 initTables( schemaManager ); 185 } 186 catch ( IOException e ) 187 { 188 // clean up 189 close(); 190 throw e; 191 } 192 193 initialized = true; 194 } 195 196 197 /** 198 * Initializes the forward and reverse tables used by this Index. 199 * 200 * @throws IOException if we cannot initialize the forward and reverse 201 * tables 202 * @throws NamingException 203 */ 204 private void initTables( SchemaManager schemaManager ) throws IOException 205 { 206 SerializableComparator<K> comp; 207 208 MatchingRule mr = attribute.getEquality(); 209 210 if ( mr == null ) 211 { 212 throw new IOException( I18n.err( I18n.ERR_574, attribute.getName() ) ); 213 } 214 215 comp = new SerializableComparator<K>( mr.getOid() ); 216 217 /* 218 * The forward key/value map stores attribute values to master table 219 * primary keys. A value for an attribute can occur several times in 220 * different entries so the forward map can have more than one value. 221 */ 222 LongComparator.INSTANCE.setSchemaManager( schemaManager ); 223 comp.setSchemaManager( schemaManager ); 224 225 forward = new JdbmTable<K, Long>( schemaManager, attribute.getName() + FORWARD_BTREE, numDupLimit, recMan, 226 comp, LongComparator.INSTANCE, null, LongSerializer.INSTANCE ); 227 228 /* 229 * Now the reverse map stores the primary key into the master table as 230 * the key and the values of attributes as the value. If an attribute 231 * is single valued according to its specification based on a schema 232 * then duplicate keys should not be allowed within the reverse table. 233 */ 234 if ( attribute.isSingleValued() ) 235 { 236 reverse = new JdbmTable<Long, K>( schemaManager, attribute.getName() + REVERSE_BTREE, recMan, 237 LongComparator.INSTANCE, LongSerializer.INSTANCE, null ); 238 } 239 else 240 { 241 reverse = new JdbmTable<Long, K>( schemaManager, attribute.getName() + REVERSE_BTREE, numDupLimit, recMan, 242 LongComparator.INSTANCE, comp, LongSerializer.INSTANCE, null ); 243 } 244 } 245 246 247 /** 248 * @see org.apache.directory.server.xdbm.Index#getAttribute() 249 */ 250 public AttributeType getAttribute() 251 { 252 return attribute; 253 } 254 255 256 // ------------------------------------------------------------------------ 257 // C O N F I G U R A T I O N M E T H O D S 258 // ------------------------------------------------------------------------ 259 260 /** 261 * Protects configuration properties from being set after initialization. 262 * 263 * @param property the property to protect 264 */ 265 private void protect( String property ) 266 { 267 if ( initialized ) 268 { 269 throw new IllegalStateException( I18n.err( I18n.ERR_575, property ) ); 270 } 271 } 272 273 274 public boolean isCountExact() 275 { 276 return false; 277 } 278 279 280 /** 281 * Gets the attribute identifier set at configuration time for this index which may not 282 * be the OID but an alias name for the attributeType associated with this Index 283 * 284 * @return configured attribute oid or alias name 285 */ 286 public String getAttributeId() 287 { 288 return attributeId; 289 } 290 291 292 /** 293 * Sets the attribute identifier set at configuration time for this index which may not 294 * be the OID but an alias name for the attributeType associated with this Index 295 * 296 * @param attributeId configured attribute oid or alias name 297 */ 298 public void setAttributeId( String attributeId ) 299 { 300 protect( "attributeId" ); 301 this.attributeId = attributeId; 302 } 303 304 305 /** 306 * Gets the threshold at which point duplicate keys use btree indirection to store 307 * their values. 308 * 309 * @return the threshold for storing a keys values in another btree 310 */ 311 public int getNumDupLimit() 312 { 313 return numDupLimit; 314 } 315 316 317 /** 318 * Sets the threshold at which point duplicate keys use btree indirection to store 319 * their values. 320 * 321 * @param numDupLimit the threshold for storing a keys values in another btree 322 */ 323 public void setNumDupLimit( int numDupLimit ) 324 { 325 protect( "numDupLimit" ); 326 this.numDupLimit = numDupLimit; 327 } 328 329 330 /** 331 * Gets the size of the index cache in terms of the number of index entries to be cached. 332 * 333 * @return the size of the index cache 334 */ 335 public int getCacheSize() 336 { 337 return cacheSize; 338 } 339 340 341 /** 342 * Sets the size of the index cache in terms of the number of index entries to be cached. 343 * 344 * @param cacheSize the size of the index cache 345 */ 346 public void setCacheSize( int cacheSize ) 347 { 348 protect( "cacheSize" ); 349 this.cacheSize = cacheSize; 350 } 351 352 353 /** 354 * Sets the working directory path to something other than the default. Sometimes more 355 * performance is gained by locating indices on separate disk spindles. 356 * 357 * @param wkDirPath optional working directory path 358 */ 359 public void setWkDirPath( File wkDirPath ) 360 { 361 protect( "wkDirPath" ); 362 this.wkDirPath = wkDirPath; 363 } 364 365 366 /** 367 * Gets the working directory path to something other than the default. Sometimes more 368 * performance is gained by locating indices on separate disk spindles. 369 * 370 * @return optional working directory path 371 */ 372 public File getWkDirPath() 373 { 374 return wkDirPath; 375 } 376 377 378 // ------------------------------------------------------------------------ 379 // Scan Count Methods 380 // ------------------------------------------------------------------------ 381 382 /** 383 * @see org.apache.directory.server.xdbm.Index#count() 384 */ 385 public int count() throws IOException 386 { 387 return forward.count(); 388 } 389 390 391 /** 392 * @see Index#count(java.lang.Object) 393 */ 394 public int count( K attrVal ) throws Exception 395 { 396 return forward.count( getNormalized( attrVal ) ); 397 } 398 399 400 public int greaterThanCount( K attrVal ) throws Exception 401 { 402 return forward.greaterThanCount( getNormalized( attrVal ) ); 403 } 404 405 406 /** 407 * @see org.apache.directory.server.xdbm.Index#lessThanCount(java.lang.Object) 408 */ 409 public int lessThanCount( K attrVal ) throws Exception 410 { 411 return forward.lessThanCount( getNormalized( attrVal ) ); 412 } 413 414 415 // ------------------------------------------------------------------------ 416 // Forward and Reverse Lookups 417 // ------------------------------------------------------------------------ 418 419 /** 420 * @see Index#forwardLookup(java.lang.Object) 421 */ 422 public Long forwardLookup( K attrVal ) throws Exception 423 { 424 return forward.get( getNormalized( attrVal ) ); 425 } 426 427 428 /** 429 * @see org.apache.directory.server.xdbm.Index#reverseLookup(Long) 430 */ 431 public K reverseLookup( Long id ) throws Exception 432 { 433 return reverse.get( id ); 434 } 435 436 437 // ------------------------------------------------------------------------ 438 // Add/Drop Methods 439 // ------------------------------------------------------------------------ 440 441 /** 442 * @see Index#add(Object, Long) 443 */ 444 public synchronized void add( K attrVal, Long id ) throws Exception 445 { 446 forward.put( getNormalized( attrVal ), id ); 447 reverse.put( id, getNormalized( attrVal ) ); 448 } 449 450 451 /** 452 * @see Index#drop(Object,Long) 453 */ 454 public synchronized void drop( K attrVal, Long id ) throws Exception 455 { 456 forward.remove( getNormalized( attrVal ), id ); 457 reverse.remove( id, getNormalized( attrVal ) ); 458 } 459 460 461 /** 462 * {@inheritDoc} 463 */ 464 public void drop( Long entryId ) throws Exception 465 { 466 // Build a cursor to iterate on all the keys referencing 467 // this entryId 468 Cursor<Tuple<Long, K>> values = reverse.cursor( entryId ); 469 470 while ( values.next() ) 471 { 472 // Remove the Key -> entryId from the index 473 forward.remove( values.get().getValue(), entryId ); 474 } 475 476 // Remove the id -> key from the reverse index 477 reverse.remove( entryId ); 478 } 479 480 481 // ------------------------------------------------------------------------ 482 // Index Cursor Operations 483 // ------------------------------------------------------------------------ 484 @SuppressWarnings("unchecked") 485 public IndexCursor<K, O, Long> reverseCursor() throws Exception 486 { 487 return new IndexCursorAdaptor<K, O, Long>( ( Cursor ) reverse.cursor(), false ); 488 } 489 490 491 @SuppressWarnings("unchecked") 492 public IndexCursor<K, O, Long> forwardCursor() throws Exception 493 { 494 return new IndexCursorAdaptor<K, O, Long>( ( Cursor ) forward.cursor(), true ); 495 } 496 497 498 @SuppressWarnings("unchecked") 499 public IndexCursor<K, O, Long> reverseCursor( Long id ) throws Exception 500 { 501 return new IndexCursorAdaptor<K, O, Long>( ( Cursor ) reverse.cursor( id ), false ); 502 } 503 504 505 @SuppressWarnings("unchecked") 506 public IndexCursor<K, O, Long> forwardCursor( K key ) throws Exception 507 { 508 return new IndexCursorAdaptor<K, O, Long>( ( Cursor ) forward.cursor( key ), true ); 509 } 510 511 512 public Cursor<K> reverseValueCursor( Long id ) throws Exception 513 { 514 return reverse.valueCursor( id ); 515 } 516 517 518 public Cursor<Long> forwardValueCursor( K key ) throws Exception 519 { 520 return forward.valueCursor( key ); 521 } 522 523 524 // ------------------------------------------------------------------------ 525 // Value Assertion (a.k.a Index Lookup) Methods // 526 // ------------------------------------------------------------------------ 527 /** 528 * @see Index#forward(Object) 529 */ 530 public boolean forward( K attrVal ) throws Exception 531 { 532 return forward.has( getNormalized( attrVal ) ); 533 } 534 535 536 /** 537 * @see Index#forward(Object,Long) 538 */ 539 public boolean forward( K attrVal, Long id ) throws Exception 540 { 541 return forward.has( getNormalized( attrVal ), id ); 542 } 543 544 545 /** 546 * @see Index#reverse(Long) 547 */ 548 public boolean reverse( Long id ) throws Exception 549 { 550 return reverse.has( id ); 551 } 552 553 554 /** 555 * @see Index#reverse(Long,Object) 556 */ 557 public boolean reverse( Long id, K attrVal ) throws Exception 558 { 559 return forward.has( getNormalized( attrVal ), id ); 560 } 561 562 563 /** 564 * @see org.apache.directory.server.xdbm.Index#forwardGreaterOrEq(Object) 565 */ 566 public boolean forwardGreaterOrEq( K attrVal ) throws Exception 567 { 568 return forward.hasGreaterOrEqual( getNormalized( attrVal ) ); 569 } 570 571 572 /** 573 * @see org.apache.directory.server.xdbm.Index#forwardGreaterOrEq(Object, Long) 574 */ 575 public boolean forwardGreaterOrEq( K attrVal, Long id ) throws Exception 576 { 577 return forward.hasGreaterOrEqual( getNormalized( attrVal ), id ); 578 } 579 580 581 /** 582 * @see org.apache.directory.server.xdbm.Index#forwardLessOrEq(Object) 583 */ 584 public boolean forwardLessOrEq( K attrVal ) throws Exception 585 { 586 return forward.hasLessOrEqual( getNormalized( attrVal ) ); 587 } 588 589 590 /** 591 * @see org.apache.directory.server.xdbm.Index#forwardLessOrEq(Object, Long) 592 */ 593 public boolean forwardLessOrEq( K attrVal, Long id ) throws Exception 594 { 595 return forward.hasLessOrEqual( getNormalized( attrVal ), id ); 596 } 597 598 599 /** 600 * @see org.apache.directory.server.xdbm.Index#reverseGreaterOrEq(Long) 601 */ 602 public boolean reverseGreaterOrEq( Long id ) throws Exception 603 { 604 return reverse.hasGreaterOrEqual( id ); 605 } 606 607 608 /** 609 * @see org.apache.directory.server.xdbm.Index#reverseGreaterOrEq(Long,Object) 610 */ 611 public boolean reverseGreaterOrEq( Long id, K attrVal ) throws Exception 612 { 613 return reverse.hasGreaterOrEqual( id, getNormalized( attrVal ) ); 614 } 615 616 617 /** 618 * @see org.apache.directory.server.xdbm.Index#reverseLessOrEq(Long) 619 */ 620 public boolean reverseLessOrEq( Long id ) throws Exception 621 { 622 return reverse.hasLessOrEqual( id ); 623 } 624 625 626 /** 627 * @see org.apache.directory.server.xdbm.Index#reverseLessOrEq(Long,Object) 628 */ 629 public boolean reverseLessOrEq( Long id, K attrVal ) throws Exception 630 { 631 return reverse.hasLessOrEqual( id, getNormalized( attrVal ) ); 632 } 633 634 635 // ------------------------------------------------------------------------ 636 // Maintenance Methods 637 // ------------------------------------------------------------------------ 638 /** 639 * @see org.apache.directory.server.xdbm.Index#close() 640 */ 641 public synchronized void close() throws IOException 642 { 643 if ( forward != null ) 644 { 645 forward.close(); 646 } 647 648 if ( reverse != null ) 649 { 650 reverse.close(); 651 } 652 653 recMan.commit(); 654 recMan.close(); 655 } 656 657 658 /** 659 * @see Index#sync() 660 */ 661 public synchronized void sync() throws IOException 662 { 663 recMan.commit(); 664 } 665 666 667 /** 668 * TODO I don't think the keyCache is required anymore since the normalizer 669 * will cache values for us. 670 */ 671 @SuppressWarnings("unchecked") 672 public K getNormalized( K attrVal ) throws Exception 673 { 674 if ( attrVal instanceof Long ) 675 { 676 return attrVal; 677 } 678 679 K normalized = ( K ) keyCache.get( attrVal ); 680 681 if ( null == normalized ) 682 { 683 if ( attrVal instanceof String ) 684 { 685 normalized = ( K ) attribute.getEquality().getNormalizer().normalize( ( String ) attrVal ); 686 } 687 else 688 { 689 normalized = ( K ) attribute.getEquality().getNormalizer().normalize( 690 new BinaryValue( ( byte[] ) attrVal ) ).get(); 691 } 692 693 // Double map it so if we use an already normalized 694 // value we can get back the same normalized value. 695 // and not have to regenerate a second time. 696 keyCache.put( attrVal, normalized ); 697 keyCache.put( normalized, normalized ); 698 } 699 700 return normalized; 701 } 702 703 704 /** 705 * @see Object#toString() 706 */ 707 public String toString() 708 { 709 return "Index<" + attributeId + ">"; 710 } 711 }