Methods and systems for efficient learned index on log-structured merge-tree KV-stores

1 . A method of double-objective learned indexing in a log-structured merge-tree based key store, the method comprising, by an electronic device:

providing a plurality of keys;

generating a sorted string table (SST) by arranging key values of the plurality of keys in an ascending sequence, wherein a first key of a first block-sequence is a first spline point of the first block-sequence, wherein a last key of each block-sequence is a spline point of the each block-sequence;

using a count sequence of positive integers to index respective keys of the SST;

receiving a request;

requesting and receiving from a reinforcement learning (RL) agent a maximum block size value (Bmax) and a model error value (E);

dividing the SST into data blocks, each data block includes one or more respective keys;

generating a piecewise linear approximation (PLA) function, wherein the PLA function is built on the spline point of the each block-sequence and the first spline point of the first block-sequence; and

storing the data blocks, the PLA function, and the E.

2 . The method of claim 1 , wherein a sum of values of the one or more respective keys of the each data block being equal to or less than the Bmax.

3 . The method of claim 1 ,

wherein a maximum interpolation error of the PLA function is equal to or less than the E.

4 . The method of claim 1 further comprising:

receiving an indication of a target key, the indication being based, at least in part, on a pointer, a realized data, or a combination thereof;

receiving a lookup query request to find the target key in the plurality of keys;

determining if a value of the target key being within a range of key values of the SST;

if the value of the target key being withing the range of the key values of the SST, initiating a discovery operation to discover a data block among the data blocks;

inputting the value of the target key to a function and operating the function to generate a value (V) of a center of a search range;

generating the search range for the data block;

initiating a discovery operation to discover the target key in the search range;

determining if the target key was discovered in the search range; and

if the target key was discovered in the search range, reporting the target key together with a respective pointer to a value block.

5 . The method of claim 4 wherein the function being the PLA function or a piecewise regression approximation (PRA) function.

6 . The method of claim 4 , wherein the data block has a respective range of key values, the respective range overlaps with the value of the target key.

7 . The method of claim 4 , wherein the search range of the data block being defined between (the V−the E) and (the V+the E).

8 . The method of claim 1 , wherein the data blocks, the PLA function, and the E being stored in a persistent storage.

9 . The method of claim 4 further comprising:

prior said initiating the discovery operation to discover the data block among the data blocks, retrieving a leaned index model from a persistent storage.

10 . The method of claim 4 further comprising:

following the discovery operation to discover the data block among the data blocks, retrieving the data block from a persistent storage.

11 . The method of claim 4 , wherein the discovery operation to discover the target key being a binary search or a linear search.

12 . The method of claim 4 further comprising:

prior said initiating the discovery operation to discover the target key, requesting and receiving from the RL agent an indication of a most significant bit.

13 . The method of claim 12 ,

wherein the discovery operation to discover the target key comprises: selecting an instant key in the search range and comparing each bit of a portion of a value of the instant key to respective bits of the value of the target key, and

wherein the portion of the value of the instant key is defined by a first bit and the most significant bit.

14 . The method of claim 4 further comprising:

recording by the RL agent a latency of the lookup query request and adjusts parameters for future lookup query requests.

15 . A storage system, the storage system being a log-structured merge-tree based storage system, the storage system comprising an electronic device, wherein the electronic device configured to:

provide a plurality of keys;

generate a sorted string table (SST) by arranging key values of the plurality of keys in an ascending sequence, wherein a first key of a first data block is a first spline point of the first data block, wherein a last key of each data block is a spline point of the each data block;

use a count sequence of positive integers to index respective keys of the SST;

receive a request;

request and receive from a reinforcement learning (RL) agent a maximum block size value (Bmax) and a model error value (E);

divide the SST into data blocks, each data block includes one or more respective keys;

generate a piecewise linear approximation (PLA) function, wherein the PLA function is built on the spline point of the each data block and the first spline point of the first data block; and

store the data blocks, the PLA function, and the E.

16 . The storage system of claim 15 , wherein the electronic device further configured to:

receive an indication of a target key, the indication being based, at least in part, on a pointer, a realized data, or a combination thereof;

receive a lookup query request to find the target key in the plurality of keys;

determine if a value of the target key being within a range of key values of the SST;

if the value of the target key being withing the range of key values of the SST, initiating a discovery operation to discover a data block among the data blocks;

input the value of the target key to a function and operating the function to generate a value (V) of a center of a search range;

generate the search range for the data block;

initiate a discovery operation to discover the target key in the search range;

determine if the target key was discovered in the search range; and

if the target key was discovered in the search range, report the target key together with a respective pointer to a value block.

17 . The storage system of claim 16 , wherein the function being the PLA function or a piecewise regression approximation (PRA) function.

18 . The storage system of claim 15 , wherein a sum of values of the one or more respective keys of the each data block being equal to or less than the Bmax.

19 . The storage system of claim 15 ,

wherein a maximum interpolation error of the PLA function is equal to or less than the E.

20 . The storage system of claim 16 , wherein the search range of the data block being defined between (the V−the E) and (the V+the E).