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

Class OLocalHashTable<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.index.hashindex.local.OLocalHashTable<K,V>

All Implemented Interfaces:

OHashTable<K,V>

public class OLocalHashTable<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 (not splitted but removed) - 8 bytes

Since:

12.03.13

Author:

Andrey Lomakin

Nested Class Summary

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

OHashTable.BucketPath, OHashTable.BucketSplitResult, OHashTable.KeyHashCodeComparator<K>, OHashTable.NodeSplitResult

Field Summary

Fields

Modifier and Type	Field and Description
static int	HASH_CODE_SIZE
static int	LEVEL_MASK
static int	MAX_LEVEL_DEPTH
static int	MAX_LEVEL_SIZE

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

atomicOperationsManager, extension, performanceStatisticManager, readCache, storage, writeCache

Constructor Summary

Constructors

Constructor and Description
OLocalHashTable(String name, String metadataConfigurationFileExtension, String treeStateFileExtension, String bucketFileExtension, String nullBucketFileExtension, OHashFunction<K> keyHashFunction, boolean durableInNonTxMode, 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.
OHashIndexBucket.Entry<K,V>[]	ceilingEntries(K key)
void	clear()
void	close()
void	create(OBinarySerializer<K> keySerializer, OBinarySerializer<V> valueSerializer, OType[] keyTypes, boolean nullKeyIsSupported)
void	delete()
void	deleteWithoutLoad(String name, OAbstractPaginatedStorage storageLocal)
OHashIndexBucket.Entry<K,V>	firstEntry()
OHashIndexBucket.Entry<K,V>[]	floorEntries(K key)
void	flush()
V	get(K key)
OBinarySerializer<K>	getKeySerializer()
OBinarySerializer<V>	getValueSerializer()
OHashIndexBucket.Entry<K,V>[]	higherEntries(K key)
OHashIndexBucket.Entry<K,V>[]	higherEntries(K key, int limit)
boolean	isNullKeyIsSupported()
OHashIndexBucket.Entry<K,V>	lastEntry()
void	load(String name, OType[] keyTypes, boolean nullKeyIsSupported)
OHashIndexBucket.Entry<K,V>[]	lowerEntries(K key)
void	put(K key, V value)
V	remove(K key)
void	setKeySerializer(OBinarySerializer<K> keySerializer)
void	setValueSerializer(OBinarySerializer<V> valueSerializer)
long	size()
protected void	startOperation()
boolean	validatedPut(K key, V value, OIndexEngine.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

acquireExclusiveLock, addFile, addPage, completeOperation, deleteFile, endAtomicOperation, getChanges, getExtension, getFilledUpTo, getFullName, getLockName, getName, isFileExists, isFileExists, loadPage, loadPage, openFile, pinPage, releasePage, setName, startAtomicOperation, truncateFile

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

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.index.hashindex.local.OHashTable

getName

Field Detail

HASH_CODE_SIZE

public static final int HASH_CODE_SIZE

See Also:

Constant Field Values

MAX_LEVEL_DEPTH

public static final int MAX_LEVEL_DEPTH

See Also:

Constant Field Values

MAX_LEVEL_SIZE

public static final int MAX_LEVEL_SIZE

See Also:

Constant Field Values

LEVEL_MASK

public static final int LEVEL_MASK

See Also:

Constant Field Values

Constructor Detail

OLocalHashTable

public OLocalHashTable(String name,
                       String metadataConfigurationFileExtension,
                       String treeStateFileExtension,
                       String bucketFileExtension,
                       String nullBucketFileExtension,
                       OHashFunction<K> keyHashFunction,
                       boolean durableInNonTxMode,
                       OAbstractPaginatedStorage abstractPaginatedStorage)

Method Detail

create

public void create(OBinarySerializer<K> keySerializer,
                   OBinarySerializer<V> valueSerializer,
                   OType[] keyTypes,
                   boolean nullKeyIsSupported)

Specified by:

create in interface OHashTable<K,V>

getKeySerializer

public OBinarySerializer<K> getKeySerializer()

Specified by:

getKeySerializer in interface OHashTable<K,V>

setKeySerializer

public void setKeySerializer(OBinarySerializer<K> keySerializer)

Specified by:

setKeySerializer in interface OHashTable<K,V>

getValueSerializer

public OBinarySerializer<V> getValueSerializer()

Specified by:

getValueSerializer in interface OHashTable<K,V>

setValueSerializer

public void setValueSerializer(OBinarySerializer<V> valueSerializer)

Specified by:

setValueSerializer in interface OHashTable<K,V>

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(K key,
                V value)

Specified by:

put in interface OHashTable<K,V>

validatedPut

public boolean validatedPut(K key,
                            V value,
                            OIndexEngine.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>

Parameters:

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:

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

remove

public V remove(K key)

Specified by:

remove in interface OHashTable<K,V>

clear

public void clear()

Specified by:

clear in interface OHashTable<K,V>

higherEntries

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

Specified by:

higherEntries in interface OHashTable<K,V>

higherEntries

public OHashIndexBucket.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)

Specified by:

load in interface OHashTable<K,V>

deleteWithoutLoad

public void deleteWithoutLoad(String name,
                              OAbstractPaginatedStorage storageLocal)

Specified by:

deleteWithoutLoad in interface OHashTable<K,V>

ceilingEntries

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

Specified by:

ceilingEntries in interface OHashTable<K,V>

firstEntry

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

Specified by:

firstEntry in interface OHashTable<K,V>

lastEntry

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

Specified by:

lastEntry in interface OHashTable<K,V>

lowerEntries

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

Specified by:

lowerEntries in interface OHashTable<K,V>

floorEntries

public OHashIndexBucket.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()

Specified by:

delete in interface OHashTable<K,V>

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>

startOperation

protected void startOperation()

Overrides:

startOperation in class ODurableComponent