Method and system for inserting data records into files

• US 9,116,903 B2
• Filed: 01/07/2013
• Issued: 08/25/2015
• Est. Priority Date: 10/22/2009
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Hansen, Jacob Gorm
• Primary Examiner(s): Nguyen, Loan T
• Application Number:
  US13/735,792
• Publication Number:
  US 20130124559A1
• Time in Patent Office: 960 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 16/148 File search processing
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Methods and system for adding a data record to a file comprise maintaining a data structure to track locations of data records within the file, wherein each entry in the data structure is a Bloom filter that corresponds to a different portion of the file that includes a plurality of data records. When an instruction to write data to the file is received, a data record is generated to append to the file, wherein the data record comprises a randomized unique id and the data from the received instruction. A Bloom filter bit pattern is extracted from the randomized unique id and bits in a current Bloom filter entry of the data structure are set, wherein the set bits correspond to the same bit positions as the Bloom filter bit pattern. The data record is thus able to be added to the file.

Claims

1. A method for locating a data record in a log file organized as a plurality of log segments, wherein each log segment comprises a plurality of data records and data records are indexed in the log file according to randomized unique identifiers (ids), the method comprising:

providing a Bloom filter data structure for the plurality of log segments, wherein the Bloom filter data structure includes a section in a plurality of sections for each of the plurality of log segments;

setting bits in respective sections of the Bloom filter data structure for the plurality of log segments that correspond to the values for randomized unique ids associated with data records stored in the plurality of log segments, where the set bits for each log segment in the plurality of log segments form a log segment Bloom filter bit pattern in the respective section for each log segment;

receiving a randomized unique identifier (id) associated with the data record;

generating a data record Bloom filter bit pattern of a plurality of bits from the randomized unique id;

searching the plurality of sections of the bloom filter data structure for the plurality of log segments to find a section that includes a stored bit pattern of a plurality of bits in the log segment Bloom filter pattern that has bits set in the same bit positions as bits in the plurality of bits of the data record Bloom filter bit pattern;

searching for the data record in the log segment of the log file associated with the log segment Bloom filter pattern; and

outputting the data record if the data record is found at the log segment.

2. The method of claim 1, wherein the log file is a virtual machine disk image and the data record is an update operation for the virtual machine disk image.

3. The method of claim 1, wherein the data record comprises a first data record, the randomized unique id comprises a first randomized unique id, the data record Bloom filter bit pattern comprises a first data record Bloom filter bit pattern, the method further comprising:

receiving an instruction to write data to the log file;

generating a second data record to append to the log file, wherein the second data record comprises a second randomized unique id and the data from the received instruction;

extracting a second data record Bloom filter bit pattern of a plurality of bits from the second randomized unique id;

setting bits in a current section of the Bloom filter data structure that correspond to a current data record Bloom filter entry of a plurality of bits, wherein each section in the plurality of sections has set bits from data record Bloom filter entries of data records added to the respective portion; and

adding the data record to the log file.

4. The method of claim 3, wherein adding the second data record comprises appending the second data record to the end of the log file.

5. The method of claim 4, wherein the second data record is associated with a current portion of the log file that corresponds with the current section.

6. The method of claim 3, wherein the log file is a virtual machine disk image and the second data record corresponds to a write operation issued by a virtual machine.

7. The method of claim 3, wherein the second data record Bloom filter bit pattern comprises a plurality of contiguous bit sequences of equal size that are extracted from the second randomized unique id, wherein the value of each of the bit sequences corresponds to a particular bit position in the current section.

8. The method of claim 3, wherein the current section corresponds to a plurality of data record Bloom filter entries for a newly created portion of the log file.

9. The method of claim 3, wherein the steps are performed by a hypervisor supporting execution of virtual machines.

10. The method of claim 1, wherein searching comprises:

extracting a plurality of portions from the plurality of sections; and

determining a section that includes has bits set in the plurality of portions in the same bit positions as bits in the plurality of bits of the data record Bloom filter bit pattern.

11. A non-transitory computer-readable storage medium including instructions that, when executed by a processing unit of a computer system, causes the processing unit to locate a data record in a log file organized as a plurality of log segments, wherein each log segment comprises a plurality of data records and data records are indexed in the log file according to randomized unique identifiers (ids), by performing the steps of:

providing a Bloom filter data structure for the plurality of log segments, wherein the Bloom filter data structure includes a section in a plurality of sections for each of the plurality of log segments;

setting bits in respective sections of the Bloom filter data structure for the plurality of log segments that correspond to the values for randomized unique ids associated with data records stored in the plurality of log segments, where the set bits for each log segment in the plurality of log segments form a log segment Bloom filter bit pattern in the respective section for each log segment;

receiving a randomized unique identifier (id) associated with the data record;

generating a data record Bloom filter bit pattern of a plurality of bits from the randomized unique id;

searching the plurality of sections of the bloom filter data structure for the plurality of log segments to find a section that includes a stored bit pattern of a plurality of bits in the log segment Bloom filter pattern that has bits set in the same bit positions as bits in the plurality of bits of the data record Bloom filter bit pattern;

searching for the data record in the log segment of the log file associated with the log segment Bloom filter pattern; and

outputting the data record if the data record is found at the log segment.

12. The non-transitory computer-readable storage medium of claim 11, wherein the data record comprises a first data record, the randomized unique id comprises a first randomized unique id, the data record Bloom filter bit pattern comprises a first data record Bloom filter bit pattern, further comprising

receiving an instruction to write data to the log file;

generating a second data record to append to the log file, wherein the second data record comprises a second randomized unique id and the data from the received instruction;

extracting a second data record Bloom filter bit pattern of a plurality of bits from the second randomized unique id;

setting bits in a current section of the Bloom filter data structure that correspond to a current data record Bloom filter entry of a plurality of bits, wherein each section in the plurality of sections has set bits from data record Bloom filter entries of data records added to the respective portion; and

adding the data record to the log file.

13. The non-transitory computer-readable storage medium of claim 12, wherein adding the second data record comprises appending the second data record to the end of the log file.

14. The non-transitory computer-readable storage medium of claim 13, wherein the second data record is associated with a current portion of the log file that corresponds with the current section.

15. The non-transitory computer-readable storage medium of claim 12, wherein the log file is a virtual machine disk image and the second data record corresponds to a write operation issued by a virtual machine.

16. The non-transitory computer-readable storage medium of claim 12, wherein the second data record Bloom filter bit pattern comprises a plurality of contiguous bit sequences of equal size that are extracted from the second randomized unique id, wherein the value of each of the bit sequences corresponds to a particular bit position in the current section.

17. The non-transitory computer-readable storage medium of claim 12, wherein the current section corresponds to a plurality of data record Bloom filter entries for a newly created portion of the log file.

18. The non-transitory computer-readable storage medium of claim 12, wherein the steps are performed by a hypervisor supporting execution of virtual machines.

19. The non-transitory computer-readable storage medium of claim 11, wherein the log file is a virtual machine disk image and the data record is an update operation for the virtual machine disk image.

20. The non-transitory computer-readable storage medium of claim 11, wherein searching comprises:

extracting a plurality of portions from the plurality of sections; and

determining a section that includes has bits set in the plurality of portions in the same bit positions as bits in the plurality of bits of the data record Bloom filter bit pattern.

24. The computer system of claim 12, wherein the second data record is associated with a current portion of the log file that corresponds with the current section.

21. A computer system configured to locate a data record in a log file organized as a plurality of log segments, wherein each log segment comprises a plurality of data records and data records are indexed in the log file according to randomized unique identifiers (ids), the computer system comprising:

a computer processor; and

a non-transitory computer-readable storage medium including instructions that, when executed by the computer processor, cause the computer processor to perform the steps of;

providing a Bloom filter data structure for the plurality of log segments, wherein the Bloom filter data structure includes a section in a plurality of sections for each of the plurality of log segments;

setting bits in respective sections of the Bloom filter data structure for the plurality of log segments that correspond to the values for randomized unique ids associated with data records stored in the plurality of log segments, where the set bits for each log segment in the plurality of log segments form a log segment Bloom filter bit pattern in the respective section for each log segment;

receiving a randomized unique identifier (id) associated with the data record;

generating a data record Bloom filter bit pattern of a plurality of bits from the randomized unique id;

searching the plurality of sections of the bloom filter data structure for the plurality of log segments to find a section that includes a stored bit pattern of a plurality of bits in the log segment Bloom filter pattern that has bits set in the same bit positions as bits in the plurality of bits of the data record Bloom filter bit pattern;

searching for the data record in the log segment of the log file associated with the log segment Bloom filter pattern; and

outputting the data record if the data record is found at the log segment.

22. The computer system of claim 21, wherein the data record comprises a first data record, the randomized unique id comprises a first randomized unique id, the data record Bloom filter bit pattern comprises a first data record Bloom filter bit pattern, further comprising:

receiving an instruction to write data to the log file;

generating a second data record to append to the log file, wherein the second data record comprises a second randomized unique id and the data from the received instruction;

extracting a second data record Bloom filter bit pattern of a plurality of bits from the second randomized unique id;

setting bits in a current section of the Bloom filter data structure that correspond to a current data record Bloom filter entry of a plurality of bits, wherein each section in the plurality of sections has set bits from data record Bloom filter entries of data records added to the respective portion; and

adding the data record to the log file.

23. The computer system of claim 22, wherein adding the second data record comprises appending the second data record to the end of the log file.

25. The computer system of claim 22, wherein the log file is a virtual machine disk image and the second data record corresponds to a write operation issued by a virtual machine.

26. The computer system of claim 22, wherein the second data record Bloom filter bit pattern comprises a plurality of contiguous bit sequences of equal size that are extracted from the randomized unique id, wherein the value of each of the bit sequences corresponds to a particular bit position in the current section.

27. The computer system of claim 21, wherein the log file is a virtual machine disk image and the data record is an update operation for the virtual machine disk image.

28. The computer system of claim 21, wherein searching comprises:

extracting a plurality of portions from the plurality of sections; and

determining a section that includes has bits set in the plurality of portions in the same bit positions as bits in the plurality of bits of the data record Bloom filter bit pattern.