Method and system for implementing lock free shared memory with single writer and multiple readers

Patent metadata

Field	Value
Publication number	US-10235292-B2
Application number	US-201615134537-A
Country	US
Kind code	B2
Filing date	Apr 21, 2016
Priority date	Apr 21, 2016
Publication date	Mar 19, 2019
Grant date	Mar 19, 2019

Abstract

A method and a system for implementing a lock-free shared memory accessible by a plurality of readers and a single writer are provided herein. The method including: maintaining a memory accessible by the readers and the writer, wherein the memory is a hash table having at least one linked list of buckets, each bucket in the linked list having: a bucket ID, a pointer to an object, and a pointer to another bucket; calculating a pointer to one bucket of the linked list of buckets based on a hash function in response to a read request by any of the readers; and traversing the linked list of buckets, to read a series of objects corresponding with the traversed buckets, while checking that the writer has not: added, amended, or deleted objects pointed to by any of said traversed buckets, wherein said checking is carried out in a single atomic action.

First claim

The invention claimed is:

1. A system for implementing a lock-free shared memory accessible by a plurality of readers and a single writer, the system comprising:
a plurality of readers and a single writer, wherein the readers and the writer are running on a computer processor; and
a memory accessible by a plurality of the readers and the single writer
wherein the memory comprises a hash table having at least one linked list of buckets, each bucket in the linked list having: a bucket ID of the bucket, a pointer to an object, and a pointer to the next bucket on the linked list of buckets, the pointer to the next bucket comprising an ID for the next bucket;
wherein in response to a read request by any of the plurality of readers, the computer processor is configured to:
calculate a pointer to one bucket of the linked list of buckets based on a hash function, and
traverse the linked list of buckets, to read a series of objects corresponding with the traversed buckets, while checking that the writer has not: added, amended, or deleted objects pointed to by any of said traversed buckets, wherein said checking is carried out by comparing the pointer to the next bucket and the ID of the next bucket in a single atomic action.

2. The system according to claim 1 , wherein the reader retries the operation in case that the checking indicates the ID of the next bucket comprised in the pointer is not the same as the ID of the next bucket stored in the next bucket.

3. The system according to claim 1 , wherein a number of buckets is limited to a maximal number of objects capable of being stored on the shared memory.

4. The system according to claim 1 , wherein in response to a request by the single writer to add a new object, the computer processor is configured to:
allocate space for object data of the new object on the shared memory;
update data version of the new object;
allocate a new bucket to point the new object; and
update the pointer to a next bucket on the bucket that points to the bucket allocated for the new object, wherein the update is carried out in a single atomic action.

5. The system according to claim 1 , wherein in response to a request by the single writer to modify an object, the computer processor is configured to:
allocate space for object data of the modified object on the shared memory;
update data version of the modified object; and
update the object pointer on the bucket associated with the modified object, wherein the update is carried out in a single atomic action.

6. The system according to claim 1 , wherein in response to a request by the single writer to delete an object, the computer processor is configured to:
indicate object data of the object to be deleted as invalid;
free space associated with the object to be deleted on the shared memory; and
update the pointer to a next bucket on the bucket that points to the bucket associated with the object to be deleted, to a pointer to a child bucket of the bucket of the object to be deleted, wherein the update is carried out in a single atomic action.

7. A method of implementing a lock-free shared memory accessible by a plurality of readers and a single writer, wherein the readers and the writer are running on a computer processor, the method comprising:
maintaining a memory accessible by the plurality of the readers and the single writer, wherein the memory comprises a hash table having at least one linked list of buckets, each bucket in the linked list having: a bucket ID of the bucket, a pointer to an object, and a pointer to the next bucket on the linked list of buckets, the pointer to the next bucket comprising an ID for the next bucket;
calculating a pointer to one bucket of the linked list of buckets based on a hash function in response to a read request by any of the plurality of readers; and
traversing the linked list of buckets, to read a series of objects corresponding with the traversed buckets, while checking that the writer has not: added, amended, or deleted objects pointed to by any of said traversed buckets, wherein said checking is carried out by comparing the pointer to the next bucket and the ID of the next bucket in a single atomic action.

8. The method according to claim 7 , wherein the reader retries the operation in case that the checking indicates the ID of the next bucket comprised in the pointer is not the same as the ID of the next bucket stored in the next bucket.

9. The method according to claim 7 , wherein a number of buckets is limited to a maximal number of objects capable of being stored on the shared memory.

10. The method according to claim 7 , wherein in response to a request by the single writer to add a new object, the method further comprises:
allocating space for object data of the new object on the shared memory;
updating data version of the new object;
allocating a new bucket to point the new object; and
updating the pointer to a next bucket on the bucket that points to the bucket allocated for the new object, wherein the update is carried out in a single atomic action.

11. The method according to claim 7 , wherein in response to a request by the single writer to modify an object, the method further comprises:
allocating space for object data of the modified object on the shared memory;
updating data version of the modified object; and
updating the object pointer on the bucket associated with the modified object, wherein the update is carried out in a single atomic action.

12. The method according to claim 7 , wherein in response to a request by the single writer to delete an object, the method further comprises:
indicating object data of the object to be deleted as invalid;
freeing space associated with the object to be deleted on the shared memory; and
updating the pointer to a next bucket on the bucket that points to the bucket associated with the object to be deleted, to a pointer to a child bucket of the bucket of the object to be deleted, wherein the update is carried out in a single atomic action.

13. A non-transitory computer readable medium for implementing a lock-free shared memory accessible by a plurality of readers and a single writer, wherein the readers and the writer are running on a computer processor, the non-transitory computer readable medium comprising a set of instructions that when executed cause at least one processor to:
maintain a memory accessible by the plurality of the readers and the single writer, wherein the memory comprises a hash table having at least one linked list of buckets, each bucket in the linked list having: a bucket ID of the bucket, a pointer to an object, and a pointer to the next bucket on the linked list of buckets, the pointer to the next bucket comprising an ID for the next bucket;
calculate a pointer to one bucket of the linked list of buckets based on a hash function in response to a read request by any of the plurality of readers, and
traverse the linked list of buckets, to read a series of objects corresponding with the traversed buckets, while checking that the writer has not: added, amended, or deleted objects pointed to by any of said traversed buckets, wherein said checking is carried out by comparing the pointer to the next bucket and the ID of the next bucket in a single atomic action.

14. The non-transitory computer readable medium according to claim 13 , wherein the reader retries the operation in case that the checking indicates the ID of the next bucket comprised in the pointer is not the same as the ID of the next bucket stored in the next bucket.

15. The non-transitory computer readable medium according to cl

Assignees

• Dell Products Lp

Inventors

• HAKIMI Michael
• Shifrin Max

Classifications

• G06F12/0804

  with main memory updating (G06F12/0806 takes precedence) · CPC title

• G06F2212/6042

  Allocation of cache space to multiple users or processors · CPC title

• G06F12/0842

  for multiprocessing or multitasking · CPC title

• G06F9/526

  Mutual exclusion algorithms · CPC title

• G06F12/084 Primary

  with a shared cache · CPC title