Repurposing log files

• US 10,474,656 B1
• Filed: 02/21/2017
• Issued: 11/12/2019
• Est. Priority Date: 02/21/2017
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Bronnikov, Dmitri
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US15/438,703
• Time in Patent Office: 994 Days
• Field of Search: 707741, 711103, 711100
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/465 Structured object, e.g. database record
• CPC Class Codes: G06F 2212/466 Metadata, control data
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0649 Lifecycle management
• CPC Class Codes: G06F 3/0658 Controller construction arrangements
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Systems and methods for key-value pair management. A method embodiment commences upon receiving data records comprising key-value pairs. The key-value pairs are stored in two locations, (1) in an in-memory data structure in a first storage tier, and (2) in a log file in a second storage tier. At some moment in time, an event causes a flush of the in-memory data structure. The flush operations comprise renaming the log file to refer to it as a uniquely identifiable data file in the second storage tier, and populating an index file in the second storage tier. Requests for a value corresponding to a key is satisfied by using the index file to access the uniquely identifiable data file by byte or word offset to a location in the data file so as to retrieve the value of the corresponding key.

Claims

1. A method, comprising:

receiving a data record comprising a key-value pair;

storing the key-value pair in an in-memory data structure in a first storage tier, wherein the in-memory data structure is used to access the data record;

storing a log entry for the key-value pair in a log file in a second storage tier;

renaming the log file in place in the second storage tier, said renaming comprising assignment of a new filename to the log file, wherein an index file points to the log entry in the log file corresponding to the new filename, the index file being used to access the key-value pair; and

storing a new log entry in a new log file, the new log file storing the new log entry comprising a key-value pair.

2. The method of claim 1, wherein at least one of, the in-memory data structure, the log file, or the index file, is partitioned across a storage pool.

3. The method of claim 1, wherein the in-memory data structure associates a value from the key-value pair or a pointer to the value with a key from the key-value pair.

4. The method of claim 1, wherein renaming the log file is responsive to a flush event invoked based at least in part on a memory utilization threshold or a search efficiency threshold.

5. The method of claim 1, wherein the index file is configured to point to the log entry in the log file by populating the index file with a file pointer and offset to a data value in the log file corresponding to the new filename.

6. The method of claim 1, further comprising performing a maintenance operation on an instance of the log file or the index file.

7. The method of claim 1, further comprising performing a maintenance operation on an instance of the log file or the index file, and wherein the maintenance operation comprises at least one of, a sort operation, a merge operation, a delete operation, a compact operation, a compress operation, a partition operation, or a distribute operation.

8. The method of claim 1, further comprising performing a partition operation on an instance of the log file or the index file, and wherein the partition operation comprises assigning a first portion of keys to a first node in a computing cluster and distributing a second portion of keys to a second node in the computing cluster.

9. The method of claim 1, wherein the key-value pair is one of a plurality of key-value pairs organized in the in-memory data structure in a binary search tree structure.

10. The method of claim 1, wherein the key-value pair is one of a plurality of key-value pairs in the in-memory data structure comprise heterogeneous key-value pairs.

11. A non-transitory computer readable medium having stored thereon a sequence of instructions which, when executed by a processor performs a set of acts, comprising:

receiving a data record comprising a key-value pair;

storing the key-value pair in an in-memory data structure in a first storage tier, wherein the in-memory data structure is used to access the data record;

storing a log entry for the key-value pair in a log file in a second storage tier;

renaming the log file in place in the second storage tier, said renaming comprising assignment of a new filename to the log file, wherein an index file points to the log entry in the log file corresponding to the new filename, the index file being used to access the key-value pair; and

storing a new log entry in a new log file, the new log file storing the new log entry comprising a key-value pair.

12. The computer readable medium of claim 11, wherein at least one of, the in-memory data structure, the log file, or the index file, is partitioned across a storage pool.

13. The computer readable medium of claim 11, wherein the in-memory data structure associates a value from the key-value pair or a pointer to the value with a key from the key-value pair.

14. The computer readable medium of claim 11, wherein renaming the log file is responsive to a flush event invoked based at least in part on a memory utilization threshold or a search efficiency threshold.

15. The computer readable medium of claim 11, wherein the index file is configured to point to the log entry in the log file by populating the index file with a file pointer and offset to a data value in the log file corresponding to the new filename.

16. The computer readable medium of claim 11, the set of acts further comprising performing a maintenance operation on an instance of the log file or the index file.

17. The computer readable medium of claim 11, the set of acts further comprising performing a maintenance operation on an instance of the log file or the index file, and wherein the maintenance operation comprises at least one of, a sort operation, a merge operation, a delete operation, a compact operation, a compress operation, a partition operation, or a distribute operation.

18. The computer readable medium of claim 11, the set of acts further comprising performing a partition operation on an instance of the log file or the index file, and wherein the partition operation comprises assigning a first portion of keys to a first node in a computing cluster and distributing a second portion of keys to a second node in the computing cluster.

19. A system, comprising:

a storage medium having stored thereon a sequence of instructions; and

a processor that executes the sequence of instructions to cause a set of acts, comprising,

receiving a data record comprising a key-value pair;

storing the key-value pair in an in-memory data structure in a first storage tier, wherein the in-memory data structure is used to access the data record;

storing a log entry for the key-value pair in a log file in a second storage tier;

renaming the log file in place in the second storage tier, said renaming comprising assignment of a new filename to the log file, wherein an index file points to the log entry in the log file corresponding to the new filename, the index file being used to access the key-value pair; and

storing a new log entry in a new log file, the new log file storing the new log entry comprising a key-value pair.

20. The system of claim 19, wherein at least one of, the in-memory data structure, the log file, or the index file, is partitioned across a storage pool.