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 */ 020package org.apache.directory.server.core.partition.impl.btree.jdbm; 021 022 023import java.io.File; 024import java.io.IOException; 025import java.net.URI; 026 027import jdbm.RecordManager; 028import jdbm.helper.ByteArraySerializer; 029 030import org.apache.directory.api.ldap.model.cursor.Cursor; 031import org.apache.directory.api.ldap.model.cursor.CursorException; 032import org.apache.directory.api.ldap.model.cursor.EmptyCursor; 033import org.apache.directory.api.ldap.model.cursor.Tuple; 034import org.apache.directory.api.ldap.model.exception.LdapException; 035import org.apache.directory.api.ldap.model.exception.LdapOtherException; 036import org.apache.directory.api.ldap.model.schema.AttributeType; 037import org.apache.directory.api.ldap.model.schema.MatchingRule; 038import org.apache.directory.api.ldap.model.schema.SchemaManager; 039import org.apache.directory.api.ldap.model.schema.comparators.SerializableComparator; 040import org.apache.directory.api.ldap.model.schema.comparators.UuidComparator; 041import org.apache.directory.server.core.api.partition.PartitionTxn; 042import org.apache.directory.server.core.partition.impl.btree.IndexCursorAdaptor; 043import org.apache.directory.server.i18n.I18n; 044import org.apache.directory.server.xdbm.AbstractIndex; 045import org.apache.directory.server.xdbm.IndexEntry; 046import org.slf4j.Logger; 047import org.slf4j.LoggerFactory; 048 049 050/** 051 * A Jdbm based index implementation. It creates an Index for a give AttributeType. 052 * 053 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 054 */ 055public class JdbmIndex<K> extends AbstractIndex<K, String> 056{ 057 /** A logger for this class */ 058 private static final Logger LOG = LoggerFactory.getLogger( JdbmIndex.class ); 059 060 /** default duplicate limit before duplicate keys switch to using a btree for values */ 061 public static final int DEFAULT_DUPLICATE_LIMIT = 512; 062 063 /** the key used for the forward btree name */ 064 public static final String FORWARD_BTREE = "_forward"; 065 066 /** the key used for the reverse btree name */ 067 public static final String REVERSE_BTREE = "_reverse"; 068 069 /** 070 * the forward btree where the btree key is the value of the indexed attribute and 071 * the value of the btree is the entry id of the entry containing an attribute with 072 * that value 073 */ 074 protected JdbmTable<K, String> forward; 075 076 /** 077 * the reverse btree where the btree key is the entry id of the entry containing a 078 * value for the indexed attribute, and the btree value is the value of the indexed 079 * attribute 080 */ 081 protected JdbmTable<String, K> reverse; 082 083 /** 084 * the JDBM record manager for the file containing this index 085 */ 086 protected RecordManager recMan; 087 088 /** 089 * duplicate limit before duplicate keys switch to using a btree for values 090 */ 091 protected int numDupLimit = DEFAULT_DUPLICATE_LIMIT; 092 093 /** a custom working directory path when specified in configuration */ 094 protected File wkDirPath; 095 096 097 /* 098 * NOTE: Duplicate Key Limit 099 * 100 * Jdbm cannot store duplicate keys: meaning it cannot have more than one value 101 * for the same key in the btree. Thus as a workaround we stuff values for the 102 * same key into a TreeSet. This is only effective up to some threshold after 103 * which we run into problems with serialization on and off disk. A threshold 104 * is used to determine when to switch from using a TreeSet to start using another 105 * btree in the same index file just for the values. This value only btree just 106 * has keys populated without a value for it's btree entries. When the switch 107 * occurs the value for the key in the index btree contains a pointer to the 108 * btree containing it's values. 109 * 110 * This numDupLimit is the threshold at which we switch from using in memory 111 * containers for values of the same key to using a btree for those values 112 * instead with indirection. 113 */ 114 115 // ------------------------------------------------------------------------ 116 // C O N S T R U C T O R S 117 // ---------------------------------------------------------------------- 118 /** 119 * Creates a JdbmIndex instance for a give AttributeId 120 * 121 * @param attributeId The Attribute ID 122 * @param withReverse If we have to create a reverse index 123 */ 124 public JdbmIndex( String attributeId, boolean withReverse ) 125 { 126 super( attributeId, withReverse ); 127 128 initialized = false; 129 } 130 131 132 /** 133 * Initialize the index for an Attribute, with a specific working directory (may be null). 134 * 135 * @param recMan The RecordManager 136 * @param schemaManager The schemaManager to use to get back the Attribute 137 * @param attributeType The attributeType this index is created for 138 * @throws LdapException If the initialization failed 139 * @throws IOException If the initialization failed 140 */ 141 public void init( RecordManager recMan, SchemaManager schemaManager, AttributeType attributeType ) 142 throws LdapException, IOException 143 { 144 LOG.debug( "Initializing an Index for attribute '{}'", attributeType.getName() ); 145 146 this.attributeType = attributeType; 147 148 if ( attributeId == null ) 149 { 150 setAttributeId( attributeType.getName() ); 151 } 152 153 // see DIRSERVER-2002 154 // prevent the OOM when more than 50k users are loaded at a stretch 155 // adding this system property to make it configurable till JDBM gets replaced by Mavibot 156 String cacheSizeVal = System.getProperty( "jdbm.recman.cache.size", "100" ); 157 158 int recCacheSize = Integer.parseInt( cacheSizeVal ); 159 160 LOG.info( "Setting CacheRecondManager's cache size to {}", recCacheSize ); 161 162 this.recMan = recMan; 163 164 try 165 { 166 initTables( schemaManager ); 167 } 168 catch ( IOException e ) 169 { 170 // clean up 171 close( null ); 172 throw e; 173 } 174 175 initialized = true; 176 } 177 178 179 /** 180 * Initializes the forward and reverse tables used by this Index. 181 * 182 * @param schemaManager The server schemaManager 183 * @throws IOException if we cannot initialize the forward and reverse 184 * tables 185 */ 186 private void initTables( SchemaManager schemaManager ) throws IOException 187 { 188 SerializableComparator<K> comp; 189 190 MatchingRule mr = attributeType.getEquality(); 191 192 if ( mr == null ) 193 { 194 throw new IOException( I18n.err( I18n.ERR_574, attributeType.getName() ) ); 195 } 196 197 comp = new SerializableComparator<>( mr.getOid() ); 198 199 /* 200 * The forward key/value map stores attribute values to master table 201 * primary keys. A value for an attribute can occur several times in 202 * different entries so the forward map can have more than one value. 203 */ 204 UuidComparator.INSTANCE.setSchemaManager( schemaManager ); 205 comp.setSchemaManager( schemaManager ); 206 207 if ( mr.getSyntax().isHumanReadable() ) 208 { 209 forward = new JdbmTable<>( schemaManager, attributeType.getOid() + FORWARD_BTREE, numDupLimit, 210 recMan, 211 comp, UuidComparator.INSTANCE, StringSerializer.INSTANCE, UuidSerializer.INSTANCE ); 212 } 213 else 214 { 215 forward = new JdbmTable<>( schemaManager, attributeType.getOid() + FORWARD_BTREE, numDupLimit, 216 recMan, 217 comp, UuidComparator.INSTANCE, new ByteArraySerializer(), UuidSerializer.INSTANCE ); 218 } 219 220 /* 221 * Now the reverse map stores the primary key into the master table as 222 * the key and the values of attributes as the value. If an attribute 223 * is single valued according to its specification based on a schema 224 * then duplicate keys should not be allowed within the reverse table. 225 */ 226 if ( withReverse ) 227 { 228 if ( attributeType.isSingleValued() ) 229 { 230 reverse = new JdbmTable<>( schemaManager, attributeType.getOid() + REVERSE_BTREE, recMan, 231 UuidComparator.INSTANCE, UuidSerializer.INSTANCE, null ); 232 } 233 else 234 { 235 reverse = new JdbmTable<>( schemaManager, attributeType.getOid() + REVERSE_BTREE, numDupLimit, 236 recMan, 237 UuidComparator.INSTANCE, comp, UuidSerializer.INSTANCE, null ); 238 } 239 } 240 } 241 242 243 // ------------------------------------------------------------------------ 244 // C O N F I G U R A T I O N M E T H O D S 245 // ------------------------------------------------------------------------ 246 /** 247 * Gets the threshold at which point duplicate keys use btree indirection to store 248 * their values. 249 * 250 * @return the threshold for storing a keys values in another btree 251 */ 252 public int getNumDupLimit() 253 { 254 return numDupLimit; 255 } 256 257 258 /** 259 * Sets the threshold at which point duplicate keys use btree indirection to store 260 * their values. 261 * 262 * @param numDupLimit the threshold for storing a keys values in another btree 263 */ 264 public void setNumDupLimit( int numDupLimit ) 265 { 266 protect( "numDupLimit" ); 267 this.numDupLimit = numDupLimit; 268 } 269 270 271 /** 272 * Sets the working directory path to something other than the default. Sometimes more 273 * performance is gained by locating indices on separate disk spindles. 274 * 275 * @param wkDirPath optional working directory path 276 */ 277 public void setWkDirPath( URI wkDirPath ) 278 { 279 protect( "wkDirPath" ); 280 this.wkDirPath = new File( wkDirPath ); 281 } 282 283 284 /** 285 * Gets the working directory path to something other than the default. Sometimes more 286 * performance is gained by locating indices on separate disk spindles. 287 * 288 * @return optional working directory path 289 */ 290 public URI getWkDirPath() 291 { 292 return wkDirPath != null ? wkDirPath.toURI() : null; 293 } 294 295 296 // ------------------------------------------------------------------------ 297 // Scan Count Methods 298 // ------------------------------------------------------------------------ 299 /** 300 * {@inheritDoc} 301 */ 302 public long count( PartitionTxn partitionTxn ) throws LdapException 303 { 304 return forward.count( partitionTxn ); 305 } 306 307 308 /** 309 * {@inheritDoc} 310 */ 311 public long count( PartitionTxn partitionTxn, K attrVal ) throws LdapException 312 { 313 return forward.count( partitionTxn, attrVal ); 314 } 315 316 317 /** 318 * {@inheritDoc} 319 */ 320 @Override 321 public long greaterThanCount( PartitionTxn partitionTxn, K attrVal ) throws LdapException 322 { 323 return forward.greaterThanCount( partitionTxn, attrVal ); 324 } 325 326 327 /** 328 * {@inheritDoc} 329 */ 330 @Override 331 public long lessThanCount( PartitionTxn partitionTxn, K attrVal ) throws LdapException 332 { 333 return forward.lessThanCount( partitionTxn, attrVal ); 334 } 335 336 337 // ------------------------------------------------------------------------ 338 // Forward and Reverse Lookups 339 // ------------------------------------------------------------------------ 340 341 /** 342 * {@inheritDoc} 343 */ 344 public String forwardLookup( PartitionTxn partitionTxn, K attrVal ) throws LdapException 345 { 346 return forward.get( partitionTxn, attrVal ); 347 } 348 349 350 /** 351 * {@inheritDoc} 352 */ 353 public K reverseLookup( PartitionTxn partitionTxn, String id ) throws LdapException 354 { 355 if ( withReverse ) 356 { 357 return reverse.get( partitionTxn, id ); 358 } 359 else 360 { 361 return null; 362 } 363 } 364 365 366 // ------------------------------------------------------------------------ 367 // Add/Drop Methods 368 // ------------------------------------------------------------------------ 369 370 /** 371 * {@inheritDoc} 372 */ 373 public synchronized void add( PartitionTxn partitionTxn, K attrVal, String id ) throws LdapException 374 { 375 // The pair to be added must exists 376 forward.put( partitionTxn, attrVal, id ); 377 378 if ( withReverse ) 379 { 380 reverse.put( partitionTxn, id, attrVal ); 381 } 382 } 383 384 385 /** 386 * {@inheritDoc} 387 */ 388 public synchronized void drop( PartitionTxn partitionTxn, K attrVal, String id ) throws LdapException 389 { 390 // The pair to be removed must exists 391 if ( forward.has( partitionTxn, attrVal, id ) ) 392 { 393 forward.remove( partitionTxn, attrVal, id ); 394 395 if ( withReverse ) 396 { 397 reverse.remove( partitionTxn, id, attrVal ); 398 } 399 } 400 } 401 402 403 /** 404 * {@inheritDoc} 405 */ 406 public void drop( PartitionTxn partitionTxn, String entryId ) throws LdapException 407 { 408 if ( withReverse ) 409 { 410 if ( isDupsEnabled() ) 411 { 412 // Build a cursor to iterate on all the keys referencing 413 // this entryId 414 Cursor<Tuple<String, K>> values = reverse.cursor( partitionTxn, entryId ); 415 416 try 417 { 418 while ( values.next() ) 419 { 420 // Remove the Key -> entryId from the index 421 forward.remove( partitionTxn, values.get().getValue(), entryId ); 422 } 423 424 values.close(); 425 } 426 catch ( CursorException | IOException e ) 427 { 428 throw new LdapOtherException( e.getMessage(), e ); 429 } 430 } 431 else 432 { 433 K key = reverse.get( partitionTxn, entryId ); 434 435 forward.remove( partitionTxn, key ); 436 } 437 438 // Remove the id -> key from the reverse index 439 reverse.remove( partitionTxn, entryId ); 440 } 441 } 442 443 444 // ------------------------------------------------------------------------ 445 // Index Cursor Operations 446 // ------------------------------------------------------------------------ 447 @SuppressWarnings("unchecked") 448 public Cursor<IndexEntry<K, String>> forwardCursor( PartitionTxn partitionTxn ) throws LdapException 449 { 450 return new IndexCursorAdaptor<>( partitionTxn, ( Cursor ) forward.cursor(), true ); 451 } 452 453 454 public Cursor<IndexEntry<K, String>> forwardCursor( PartitionTxn partitionTxn, K key ) throws LdapException 455 { 456 return new IndexCursorAdaptor<>( partitionTxn, ( Cursor ) forward.cursor( partitionTxn, key ), true ); 457 } 458 459 460 /** 461 * {@inheritDoc} 462 */ 463 @Override 464 public Cursor<K> reverseValueCursor( PartitionTxn partitionTxn, String id ) throws LdapException 465 { 466 if ( withReverse ) 467 { 468 return reverse.valueCursor( partitionTxn, id ); 469 } 470 else 471 { 472 return new EmptyCursor<>(); 473 } 474 } 475 476 477 public Cursor<String> forwardValueCursor( PartitionTxn partitionTxn, K key ) throws LdapException 478 { 479 return forward.valueCursor( partitionTxn, key ); 480 } 481 482 483 // ------------------------------------------------------------------------ 484 // Value Assertion (a.k.a Index Lookup) Methods // 485 // ------------------------------------------------------------------------ 486 /** 487 * {@inheritDoc} 488 */ 489 public boolean forward( PartitionTxn partitionTxn, K attrVal ) throws LdapException 490 { 491 return forward.has( partitionTxn, attrVal ); 492 } 493 494 495 /** 496 * {@inheritDoc} 497 */ 498 public boolean forward( PartitionTxn partitionTxn, K attrVal, String id ) throws LdapException 499 { 500 return forward.has( partitionTxn, attrVal, id ); 501 } 502 503 504 /** 505 * {@inheritDoc} 506 */ 507 public boolean reverse( PartitionTxn partitionTxn, String id ) throws LdapException 508 { 509 if ( withReverse ) 510 { 511 return reverse.has( partitionTxn, id ); 512 } 513 else 514 { 515 return false; 516 } 517 } 518 519 520 /** 521 * {@inheritDoc} 522 */ 523 public boolean reverse( PartitionTxn partitionTxn, String id, K attrVal ) throws LdapException 524 { 525 return forward.has( partitionTxn, attrVal, id ); 526 } 527 528 529 // ------------------------------------------------------------------------ 530 // Maintenance Methods 531 // ------------------------------------------------------------------------ 532 /** 533 * {@inheritDoc} 534 */ 535 @Override 536 public synchronized void close( PartitionTxn partitionTxn ) throws LdapException, IOException 537 { 538 if ( forward != null ) 539 { 540 forward.close( partitionTxn ); 541 } 542 543 if ( reverse != null ) 544 { 545 reverse.close( partitionTxn ); 546 } 547 } 548 549 550 /** 551 * {@inheritDoc} 552 */ 553 @Override 554 public boolean isDupsEnabled() 555 { 556 if ( withReverse ) 557 { 558 return reverse.isDupsEnabled(); 559 } 560 else 561 { 562 return false; 563 } 564 } 565 566 567 /** 568 * @see Object#toString() 569 */ 570 public String toString() 571 { 572 return "Index<" + attributeId + ">"; 573 } 574}