Versioned insert only hash table for in-memory columnar stores

• US 10,255,309 B2
• Filed: 11/25/2014
• Issued: 04/09/2019
• Est. Priority Date: 11/25/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Blanco, Rolando, Schreter, Ivan, Legler, Thomas
• Primary Examiner(s): Gurmu, Muluemebet
• Application Number:
  US14/553,654
• Publication Number:
  US 20160147750A1
• Time in Patent Office: 1,596 Days
• Field of Search: 707747
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices

Abstract

At least one read operation is concurrently performed with at least one write operation that each insert a key/value pair into a backing array of a backing hash table of a hash table forming part of a columnar in-memory database. The backing array maps a plurality of pointers each to a respective bucket. Each bucket includes at least one state bit and a hashed value of a corresponding key. Thereafter, for each write operation, a first available position in the backing array at which a pointer to a new bucket containing the key/value pair can be inserted is iteratively determined (such that each first available position has no corresponding pre-existing pointer). Subsequently, for each write operation, the pointer to the new bucket containing the key/value pair is inserted at the corresponding first determined position in the backing array. Related apparatus, systems, techniques and articles are also described.

Claims

1. A method comprising:

concurrently performing at least one read operation with at least one write operation that each insert a key/value pair into a backing array of a backing hash table of a hash table forming part of a columnar in-memory database, the backing array mapping a plurality of pointers each to a respective bucket, each bucket comprising at least one state bit and a hashed value of a corresponding key;

iteratively determining, for each write operation, a first available position in the backing array at which a pointer to a new bucket containing the key/value pair can be inserted, each first available position having no corresponding pre-existing pointer, the iteratively determining comprising;

identifying a candidate position in the backing array for the bucket containing the key/value pair by applying a modulo operation of the size of the backing array to a hash of the key determined using the hash table,

iteratively, until the candidate position does not have a pre-existing pointer, (i) marking the at least one state bit for the bucket corresponding to the candidate pointer as overflown and (ii) identifying a next candidate position in the backing array, and

creating a new bucket for the candidate position that does not have a pre-existing pointer, the new bucket encapsulating at least one state bit indicating that the bucket is not overflown, and the key/value pair; and

inserting, for each write operation, the pointer to the new bucket containing the key/value pair at the corresponding first determined position in the backing array.

2. The method of claim 1, wherein the identifying the next candidate position in the backing array uses a compare-and-swap (CAS) technique to attempt to establish the pointer in the different position.

3. The method of claim 1 further comprising:

checking if there is already a pointer at the next candidate position;

creating a new bucket if there is not already a pointer at the next candidate position, the new bucket encapsulating (i) at least one state bit indicating that the bucket is not overflown, and (ii) the key/value pair.

4. The method of claim 1, wherein the iteratively identifying and marking continues for a pre-determined number of times.

5. The method of claim 1, wherein a size of the backing array is increased at such time that the pre-determined number of times is exceeded.

6. The method of claim 1 further comprising:

determining, for at least one write operation, that the value is already in the hash table; and

notifying a caller of the write operation that the value is already in the hash table.

7. The method of claim 1, wherein the at least one write operation comprises executing a write functor.

8. The method of claim 7 further comprising:

associating a semaphore with each hash table; and

assigning the semaphore to a single write operation.

9. The method of claim 8 further comprising:

releasing the semaphore after execution of the write functor.

10. The method of claim 9 further comprising:

waiting, by a subsequent write operation, the semaphore assigned to the write operation to be released; and

executing a write functor by the subsequent write operation on the backing array.

11. The method of claim 1 further comprising:

accessing, by a reader operation, a backing hash table, wherein the backing hash table is not deallocated while the reader operation accesses the backing hash table.

12. The method of claim 11, wherein the backing hash table is not deallocated if the reader operation continues to access the backing hash table and a new backing hash table is established by a writer operation.

13. A non-transitory computer program product storing instructions which, when executed by at least one data processor forming part of at least one computing device, result in operations comprising:

concurrently performing at least one read operation with at least one write operation that each insert a key/value pair into a backing array of a backing hash table of a hash table forming part of a columnar in-memory database, the backing array mapping a plurality of pointers each to a respective bucket, each bucket comprising at least one state bit and a hashed value of a corresponding key; and

iteratively determining, for each write operation, a first available position in the backing array at which a pointer to a new bucket containing the key/value pair can be inserted, each first available position having no corresponding pre-existing pointer, the iteratively determining comprising;

identifying a candidate position in the backing array for the bucket containing the key/value pair by applying a modulo operation of the size of the backing array to a hash of the key determined using the hash table,

iteratively, until the candidate position does not have a pre-existing pointer, (i) marking the at least one state bit for the bucket corresponding to the candidate pointer as overflown and (ii) identifying a next candidate position in the backing array, and

creating a new bucket for the candidate position that does not have a pre-existing pointer, the new bucket encapsulating at least one state bit indicating that the bucket is not overflown, and the key/value pair; and

inserting, for each write operation, the pointer to the new bucket containing the key/value pair at the corresponding first determined position in the backing array.

14. The computer program product of claim 13, wherein the at least one write operation comprises executing a write functor.

15. The computer program product of claim 14, wherein the operations further comprise:

associating a semaphore with each hash table; and

assigning the semaphore to a single write operation.

16. The computer program product of claim 15, wherein the operations further comprise:

releasing the semaphore after execution of the write functor.

17. The computer program product of claim 16, wherein the operations further comprise:

waiting, by a subsequent write operation, the semaphore assigned to the write operation to be released; and

executing a write functor by the subsequent write operation on the backing array.

19. The system of claim 17, wherein the at least one write operation comprises executing a write functor, and wherein the operations further comprise:

associating a semaphore with each hash table;

assigning the semaphore to a single write operation;

waiting, by a subsequent write operation, the semaphore assigned to the write operation to be released;

releasing the semaphore after execution of the write functor; and

executing a write functor by the subsequent write operation on the backing array.

18. A system comprising:

an in-memory database comprising;

at least one processor; and

memory storing instructions which, when executed by the at least one data processor, result in operations comprising;

concurrently performing at least one read operation with at least one write operation that each insert a key/value pair into a backing array of a backing hash table of a hash table forming part of a columnar in-memory database, the backing array mapping a plurality of pointers each to a respective bucket, each bucket comprising at least one state bit and a hashed value of a corresponding key;

iteratively determining, for each write operation, a first available position in the backing array at which a pointer to a new bucket containing the key/value pair can be inserted, each first available position having no corresponding pre-existing pointer, the iteratively determining comprising;

identifying a candidate position in the backing array for the bucket containing the key/value pair by applying a modulo operation of the size of the backing array to a hash of the key determined using the hash table,

iteratively, until the candidate position does not have a pre-existing pointer, (i) marking the at least one state bit for the bucket corresponding to the candidate pointer as overflown and (ii) identifying a next candidate position in the backing array, and

creating a new bucket for the candidate position that does not have a pre-existing pointer, the new bucket encapsulating at least one state bit indicating that the bucket is not overflown, and the key/value pair; and

inserting, for each write operation, the pointer to the new bucket containing the key/value pair at the corresponding first determined position in the backing array.