System and method for managing memory for large keys and values

Patent metadata

Field	Value
Publication number	US-10838875-B2
Application number	US-201816033311-A
Country	US
Kind code	B2
Filing date	Jul 12, 2018
Priority date	May 11, 2018
Publication date	Nov 17, 2020
Grant date	Nov 17, 2020

Abstract

Methods, systems, and programming for accessing data are described herein. In a non-limiting embodiment, a request associated with a key may be received. A memory chunk in a first memory site associated with the key may be located. An entry in the memory chunk corresponding to the key may be determined. A first pointer to the key corresponding to a first location of the key within a buffer at a second memory site may be obtained from the entry. The key stored at the first location may be retrieved from the buffer at the second memory site.

First claim

What is claimed is:

1. A method for accessing data implemented on at least one computing device, each computing device comprising at least one processor and memory, the method comprising:
receiving a request associated with a key;
locating a memory chunk in a first memory site associated with the key;
determining an entry in the memory chuck corresponding to the key;
obtaining, from the entry, a first pointer and a second pointer, wherein the first pointer points to a first location in a second memory site where the key is stored, and the second pointer points to a second location in the first memory site where a handle is stored, wherein the handle is to be used to access a value associated with the key stored in the second memory site; and
retrieving, from a buffer at the second memory site, the key stored at the first location.

2. The method of claim 1 , wherein:
the first memory site corresponds to an on-heap memory; and
the second memory site corresponds to an off-heap memory.

3. The method of claim 1 , wherein the handle comprises a reference to the value associated with the key, the value being stored at a third location in the second memory site.

4. The method of claim 3 , wherein the key and the value are stored in a buffer at the second memory site, the method further comprises:
obtaining, from the entry, the second pointer; and
obtaining, based on the handle, the third location of the value in the buffer, wherein the first location of the key comprises a location of the key within the buffer and the third location of the value comprises a location of the value within the buffer.

5. The method of claim 1 , wherein:
the request indicates an operation to be performed with respect to the value associated with the key; and
the operation is to be performed based on the handle of the value associated with the key.

6. The method of claim 5 , wherein if the operation corresponds to one of a data view operation or data update operation, the operation is performed when the handle indicates that the value associated with the key exists.

7. The method of claim 5 , wherein if the operation corresponds to a data insertion operation, the operation is performed when the handle indicates that the value associated with the key is not present.

8. A system for accessing data, the system having at least one processor and storage, and the system comprising:
a request classifier configured to receive a request associated with a key;
a chunk locator configured to locate a memory chunk in a first memory site associated with the key; and
an entry searcher configured to:
determine an entry in the memory chunk corresponding to the key,
obtain, from the entry, a first pointer and a second pointer, wherein the first pointer points to a first location in a second memory site where the key is stored, and the second pointer points to a second location in the first memory site where a handle is stored, wherein the handle is to be used to access a value associated with the key stored in the second memory site, and
retrieve, from a buffer at the second memory site, the key stored at the first location.

9. The system of claim 8 , wherein:
the first memory site corresponds to an on-heap memory; and
the second memory site corresponds to an off-heap memory.

10. The system of claim 8 , wherein the handle comprises a reference to the value associated with the key, the value being stored at a third location in the second memory site.

11. The system of claim 10 , wherein the key and the value are stored in a buffer at the second memory site, the entry searcher is further configured to:
obtain, from the entry, the second pointer; and
obtain, based on the handle, the third location of the value in the buffer, wherein the first location of the key comprises a location of the key within the buffer and the third location of the value comprises a location of the value within the buffer.

12. The system of claim 8 , wherein:
the request indicates an operation to be performed with respect to the value associated with the key; and
the operation is to be performed based on the handle of the value associated with the key.

13. The system of claim 12 , wherein if the operation corresponds to one of a data view operation or data update operation, the operation is performed when the handle indicates that the value associated with the key exists.

14. The system of claim 12 , wherein if the operation corresponds to a data insertion operation, the operation is performed when the handle indicates that the value associated with the key is not present.

15. A non-transitory computer readable medium comprising one or more computer programs for accessing data, wherein the one or more computer programs, when executed by at least one processor of a machine, cause the machine to:
receive a request associated with a key;
locate a memory chunk in a first memory site associated with the key;
determine an entry in the memory chuck corresponding to the key;
obtain, from the entry, a first pointer and a second pointer, wherein the first pointer points to a first location in a second memory site where the key is stored, and the second pointer points to a second location in the first memory site where a handle is stored, wherein the handle is to be used to access a value associated with the key stored in the second memory site; and
retrieve, from a buffer at the second memory site, the key stored at the first location.

16. The non-transitory computer readable medium of claim 15 , wherein:
the first memory site corresponds to an on-heap memory;
the second memory site corresponds to an off-heap memory;
the handle comprises a reference to the value associated with the key; and
the value being stored at a third location in the second memory site.

17. The non-transitory computer readable medium of claim 16 , wherein the key and the value are stored in a buffer at the second memory site, and wherein the one or more computer programs, when executed by the at least one processor, further cause the machine to:
obtain, from the entry, the second pointer; and
obtain, based on the handle, the third location of the value in the buffer, wherein the first location of the key comprises a location of the key within the buffer and the third location of the value comprises a location of the value within the buffer.

18. The non-transitory computer readable medium of claim 15 , wherein:
the request indicates an operation to be performed with respect to the value associated with the key; and
the operation is to be performed based on the handle of the value associated with the key.

19. The non-transitory computer readable medium of claim 18 , wherein if the operation corresponds to one of a data view operation or data update operation, the operation is performed when the handle indicates that the value associated with the key exists.

20. The non-transitory computer readable medium of claim 18 , wherein if the operation corresponds to a data insertion operation, the operation is performed when the handle indicates that the value associated with the key is not present.

Assignees

• Oath Inc

Inventors

• Bortnikov Edward
• Braginsky Anastasia
• Keidar Idit
• Basin Dmitry
• Meir Hagar
• Hillel Eshcar
• Sheffi Gali

Classifications

• G06F16/22 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/245

  Query processing · CPC title

• G06F12/1018 Primary

  involving hashing techniques, e.g. inverted page tables · CPC title

• G06F16/23

  Updating · CPC title

• G06F2212/1041

  Resource optimization · CPC title