Cache for efficient record lookups in an LSM data structure

1. A method, comprising:

maintaining a log-structured merge-tree (LSM tree) that includes a plurality of levels that store files of a database, wherein a first one of the files is included in a first level of the LSM tree and stores a record having data and a key;

maintaining a cache whose entries store, for keys, indications of locations of corresponding records in the LSM tree, wherein a particular one of the entries stores, for the key, an indication of a location of the record of the first file in the first level of the LSM tree;

performing a merge operation in which the record is copied into a second file of a second level of the LSM tree, wherein the merge operation is performed without invalidating the particular entry;

after performing the merge operation:

receiving a request to access the record using the key;

retrieving, from the particular entry of the cache based on the key, the indication of the location of the record in the first file; and

accessing, based on the indication, the record from the first file of the first level instead of the second file of the second level.

2. The method of claim 1 , further comprising:

performing an atomic store operation to store, in the particular entry of the cache, an alias name for the first file, wherein the alias name is the indication of the location of the record and is smaller in memory size than a file name of the first file.

3. The method of claim 2 , further comprising:

subsequent to retrieving the indication of the location, identifying the file name of the first file based on a mapping between file names and alias names, wherein the record is accessed from the first file using the file name of the first file.

4. The method of claim 1 , further comprising:

invalidating the particular entry that includes the indication in response to determining that the first file is inaccessible through the LSM tree.

5. The method of claim 1 , further comprising:

invalidating the particular entry that includes the indication in response to determining that a new record has been written that updates content of the record.

6. The method of claim 1 , further comprising:

prior to the particular entry storing the indication of the location of the record:

performing a search of the LSM tree for the record; and

in response to locating the record, storing the indication in the particular entry.

7. The method of claim 1 , further comprising:

in response to receiving another request to access the record using a different key:

scanning an index structure using the different key to obtain the key; and

accessing, based on the particular entry and the key, the record from the first file of the first level.

8. A non-transitory computer-readable medium having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:

maintaining a log-structured merge-tree (LSM tree) that includes a plurality of levels that store files of a database, wherein a first one of the files is included in a first level of the LSM tree and stores a record having data and a key;

maintaining a cache whose entries store, for keys, indications of locations of corresponding records in the LSM tree, wherein a particular one of the entries stores, for the key, an indication of a location of the record of the first file in the first level of the LSM tree;

performing a merge operation in which the record is copied into a second file of a second level of the LSM tree, wherein the merge operation is performed without invalidating the particular entry;

after performing the merge operation:

receiving a request to access the record using the key;

retrieving, from the particular entry of the cache using the key, the indication of the location of the record in the first file; and

accessing, based on the indication, the record from the first file of the first level instead of the second file of the second level.

9. The medium of claim 8 , wherein the operations further comprise:

performing a hash derivation function using the key to derive a hash value indicative of the particular entry to be used for storing the indication of the location of the record; and

storing, based on the hash value, the indication in the particular entry.

10. The medium of claim 8 , wherein the operations further comprise:

overwriting, in the particular entry of the cache, the indication of the location of the record with an indication of a location of a different record based on a key of the different record hashing to a same hash value associated with the record of the first file.

11. The medium of claim 8 , wherein the operations further comprise:

invalidating the particular entry that includes the indication in response to determining that the first file is inaccessible through the LSM tree.

12. The medium of claim 8 , wherein the operations further comprise:

writing an additional file to a top level of the LSM tree, wherein the additional file includes a different record associated with the key; and

subsequent to writing the additional file, invalidating the particular entry of the cache that includes the indication.

13. The medium of claim 8 , wherein indications of locations are stored within the entries of the cache using atomic store instructions.

14. The medium of claim 8 , wherein the operations further comprise:

prior to the particular entry storing the indication of the location of the record:

performing a search of the LSM tree for the record; and

in response to locating the record, storing the indication in the particular entry.

15. A system, comprising:

at least one processor; and

memory having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:

maintaining a log-structured merge-tree (LSM tree) that includes a plurality of levels that store files of a database, wherein a first one of the files is included in a first level of the LSM tree and stores a record having data and a key;

maintaining a cache whose entries store, for keys, indications of locations of corresponding records in the LSM tree, wherein a particular one of the entries stores, for the key, an indication of a location of the record of the first file in the first level of the LSM tree;

performing a merge operation in which the record is copied into a second file of a second level of the LSM tree, wherein the merge operation is performed without invalidating the particular entry;

after performing the merge operation:

receiving a request to access the record using the key;

retrieving, from the particular entry of the cache using the key, the indication of the location of the record in the first file; and

accessing, based on the indication, the record from the first file of the first level instead of the second file of the second level.

16. The system of claim 15 , wherein the operations further comprise:

invalidating the particular entry that includes the indication in response to determining that a new record has been written that updates content of the record.

17. The system of claim 15 , wherein the indication is an alias name of the first file, and wherein the operations further comprise identifying a file name of the first file based on a mapping of alias names to file names.

18. The system of claim 17 , wherein the alias name of the first file is smaller in memory size than the file name of the first file.

19. The system of claim 15 , wherein the operations further comprise:

in response to determining that no in-progress threads reading the LSM tree can access the record:

invalidating the particular entry of the cache; and

deleting the record of the first file in the first level.

20. The system of claim 15 , wherein information is stored within the entries of the cache using atomic store instructions.