com.orientechnologies.orient.core.storage.index.hashindex.local.v3

Class OLocalHashTableV3<K,V>

java.lang.Object

com.orientechnologies.common.concur.resource.OSharedResourceAdaptive

com.orientechnologies.orient.core.storage.impl.local.paginated.base.ODurableComponent

com.orientechnologies.orient.core.storage.index.hashindex.local.v3.OLocalHashTableV3<K,V>

All Implemented Interfaces:

OHashTable<K,V>

public class OLocalHashTableV3<K,V>
extends ODurableComponent
implements OHashTable<K,V>

Implementation of hash index which is based on extendible hashing algorithm. The directory for extindible hashing is implemented in OHashTableDirectory class. Directory is not implemented according to classic algorithm because of its big memory consumption in case of non-uniform data distribution instead it is implemented according too "Multilevel Extendible Hashing Sven Helmer, Thomas Neumann, Guido Moerkotte April 17, 2002". Which has much less memory consumption in case of nonuniform data distribution. Index itself uses so called "multilevel schema" when first level contains 256 buckets, when bucket is split it is put at the end of other file which represents second level. So if data which are put has distribution close to uniform (this index was designed to be use as rid index for DHT storage) buckets split will be preformed in append only manner to speed up index write speed. So hash index bucket itself has following structure:

1. Bucket depth - 1 byte.
2. Bucket's size - amount of entities (key, value) in one bucket, 4 bytes
3. Page indexes of parents of this bucket, page indexes of buckets split of which created current bucket - 64*8 bytes.
4. Offsets of entities stored in this bucket relatively to it's beginning. It is array of int values of undefined size.
5. Entities itself

So if 1-st and 2-nd fields are clear. We should discuss the last ones. Entities in bucket are sorted by key's hash code so each entity has following storage format in bucket: key's hash code (8 bytes), key, value. Because entities are stored in sorted order it means that every time when we insert new entity old ones should be moved. There are 2 reasons why it is bad:

1. It will generate write ahead log of enormous size.
2. The more amount of memory is affected in operation the less speed we will have. In worst case 60 kb of memory should be moved.

To avoid disadvantages listed above entries ara appended to the end of bucket, but their offsets are stored at the beginning of bucket. Offsets are stored in sorted order (ordered by hash code of entity's key) so we need to move only small amount of memory to store entities in sorted order. About indexes of parents of current bucket. When item is removed from bucket we check space which is needed to store all entities of this bucket, it's buddy bucket (bucket which was also created from parent bucket during split) and if space of single bucket is enough to save all entities from both buckets we remove these buckets and put all content in parent bucket. That is why we need indexes of parents of current bucket. Also hash index has special file of one page long which contains information about state of each level of buckets in index. This information is stored as array index of which equals to file level. All array item has following structure:

1. Is level removed (in case all buckets are empty or level was not created yet) - 1 byte
2. File's level id - 8 bytes
3. Amount of buckets in given level - 8 bytes.
4. Index of page of first removed bucket (is not split but removed) - 8 bytes

Since:

12.03.13

Author:

Andrey Lomakin (a.lomakin-at-orientdb.com)

Nested Class Summary

Nested classes/interfaces inherited from interface com.orientechnologies.orient.core.storage.index.hashindex.local.OHashTable

OHashTable.BucketPath, OHashTable.BucketSplitResult, OHashTable.Entry<K,V>, OHashTable.KeyHashCodeComparator<K>, OHashTable.NodeSplitResult, OHashTable.RawEntry

Field Summary

Fields inherited from class com.orientechnologies.orient.core.storage.impl.local.paginated.base.ODurableComponent

atomicOperationsManager, readCache, storage, writeCache

Constructor Summary

Constructors

Constructor and Description
OLocalHashTableV3(String name, String metadataConfigurationFileExtension, String treeStateFileExtension, String bucketFileExtension, String nullBucketFileExtension, OAbstractPaginatedStorage abstractPaginatedStorage)

Method Summary

Modifier and Type	Method and Description
void	acquireAtomicExclusiveLock() Acquires exclusive lock in the active atomic operation running on the current thread for this hash table.
OHashTable.Entry<K,V>[]	ceilingEntries(K key)
void	close()
void	create(OAtomicOperation atomicOperation, OBinarySerializer<K> keySerializer, OBinarySerializer<V> valueSerializer, OType[] keyTypes, OEncryption encryption, OHashFunction<K> keyHashFunction, boolean nullKeyIsSupported)
void	delete(OAtomicOperation atomicOperation)
OHashTable.Entry<K,V>	firstEntry()
OHashTable.Entry<K,V>[]	floorEntries(K key)
void	flush()
V	get(K key)
OHashTable.Entry<K,V>[]	higherEntries(K key)
OHashTable.Entry<K,V>[]	higherEntries(K key, int limit)
boolean	isNullKeyIsSupported()
OHashTable.Entry<K,V>	lastEntry()
void	load(String name, OType[] keyTypes, boolean nullKeyIsSupported, OEncryption encryption, OHashFunction<K> keyHashFunction, OBinarySerializer<K> keySerializer, OBinarySerializer<V> valueSerializer)
OHashTable.Entry<K,V>[]	lowerEntries(K key)
void	put(OAtomicOperation atomicOperation, K key, V value)
V	remove(OAtomicOperation atomicOperation, K k)
long	size()
boolean	validatedPut(OAtomicOperation atomicOperation, K key, V value, OBaseIndexEngine.Validator<K,V> validator) Puts the given value under the given key into this hash table.

Methods inherited from class com.orientechnologies.orient.core.storage.impl.local.paginated.base.ODurableComponent

addFile, addPage, calculateInsideComponentOperation, deleteFile, executeInsideComponentOperation, getExtension, getFilledUpTo, getFullName, getLockName, getName, isFileExists, loadPageForRead, loadPageForRead, loadPageForWrite, openFile, releasePageFromRead, releasePageFromWrite, setName, truncateFile

Methods inherited from class com.orientechnologies.common.concur.resource.OSharedResourceAdaptive

acquireExclusiveLock, acquireSharedLock, addUser, assertExclusiveLockHold, assertSharedLockHold, getUsers, isConcurrent, releaseExclusiveLock, releaseSharedLock, removeUser, tryAcquireExclusiveLock, tryAcquireSharedLock

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.orientechnologies.orient.core.storage.index.hashindex.local.OHashTable

getName

Constructor Detail

OLocalHashTableV3

public OLocalHashTableV3(String name,
                         String metadataConfigurationFileExtension,
                         String treeStateFileExtension,
                         String bucketFileExtension,
                         String nullBucketFileExtension,
                         OAbstractPaginatedStorage abstractPaginatedStorage)

Method Detail

create

public void create(OAtomicOperation atomicOperation,
                   OBinarySerializer<K> keySerializer,
                   OBinarySerializer<V> valueSerializer,
                   OType[] keyTypes,
                   OEncryption encryption,
                   OHashFunction<K> keyHashFunction,
                   boolean nullKeyIsSupported)
            throws IOException

Specified by:

create in interface OHashTable<K,V>

Throws:

IOException

get

public V get(K key)

Specified by:

get in interface OHashTable<K,V>

isNullKeyIsSupported

public boolean isNullKeyIsSupported()

Specified by:

isNullKeyIsSupported in interface OHashTable<K,V>

put

public void put(OAtomicOperation atomicOperation,
                K key,
                V value)

Specified by:

put in interface OHashTable<K,V>

validatedPut

public boolean validatedPut(OAtomicOperation atomicOperation,
                            K key,
                            V value,
                            OBaseIndexEngine.Validator<K,V> validator)

Description copied from interface: OHashTable

Puts the given value under the given key into this hash table. Validates the operation using the provided validator.

Specified by:

validatedPut in interface OHashTable<K,V>

key - the key to put the value under.

value - the value to put.

validator - the operation validator.

Returns:

true if the validator allowed the put, false otherwise.

See Also:

OBaseIndexEngine.Validator#validate(Object, Object, Object)

remove

public V remove(OAtomicOperation atomicOperation,
                K k)

Specified by:

remove in interface OHashTable<K,V>

higherEntries

public OHashTable.Entry<K,V>[] higherEntries(K key)

Specified by:

higherEntries in interface OHashTable<K,V>

higherEntries

public OHashTable.Entry<K,V>[] higherEntries(K key,
                                             int limit)

Specified by:

higherEntries in interface OHashTable<K,V>

load

public void load(String name,
                 OType[] keyTypes,
                 boolean nullKeyIsSupported,
                 OEncryption encryption,
                 OHashFunction<K> keyHashFunction,
                 OBinarySerializer<K> keySerializer,
                 OBinarySerializer<V> valueSerializer)

Specified by:

load in interface OHashTable<K,V>

ceilingEntries

public OHashTable.Entry<K,V>[] ceilingEntries(K key)

Specified by:

ceilingEntries in interface OHashTable<K,V>

firstEntry

public OHashTable.Entry<K,V> firstEntry()

Specified by:

firstEntry in interface OHashTable<K,V>

lastEntry

public OHashTable.Entry<K,V> lastEntry()

Specified by:

lastEntry in interface OHashTable<K,V>

lowerEntries

public OHashTable.Entry<K,V>[] lowerEntries(K key)

Specified by:

lowerEntries in interface OHashTable<K,V>

floorEntries

public OHashTable.Entry<K,V>[] floorEntries(K key)

Specified by:

floorEntries in interface OHashTable<K,V>

size

public long size()

Specified by:

size in interface OHashTable<K,V>

close

public void close()

Specified by:

close in interface OHashTable<K,V>

delete

public void delete(OAtomicOperation atomicOperation)
            throws IOException

Specified by:

delete in interface OHashTable<K,V>

Throws:

IOException

flush

public void flush()

Specified by:

flush in interface OHashTable<K,V>

acquireAtomicExclusiveLock

public void acquireAtomicExclusiveLock()

Description copied from interface: OHashTable

Acquires exclusive lock in the active atomic operation running on the current thread for this hash table.

Specified by:

acquireAtomicExclusiveLock in interface OHashTable<K,V>