System and method for storing a database on flash memory or other degradable storage

• US 10,359,962 B1
• Filed: 09/21/2016
• Issued: 07/23/2019
• Est. Priority Date: 09/21/2015
• Status: Active Grant

• Current Assignee: Yellowbrick Data Co.
• Original Assignee: Yellowbrick Data, Inc.
• Inventors: Peterson, Jim
• Primary Examiner(s): Arjomandi, Noosha
• Application Number:
  US15/272,259
• Time in Patent Office: 1,035 Days
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A system and method stores a database file into Flash memory or other write-constrained storage.

Claims

1. A system for writing a database to a computer memory that degrades when written, comprising:

a data file receiver/portioner having an input for receiving at least a column of the database, the data file receiver/portioner for dividing the column into a plurality of portions and for providing at an output the plurality of portions, each of the portions in the plurality comprising more than a specified number of rows of the column of the database;

a compression unit manager having an input coupled to the data file receiver/portioner output for receiving the plurality of portions, and for selecting and providing at an output a first group of the specified number of rows of the column of the database; and

a buffer manager having an input coupled to the compression unit manager output for receiving the first group of the specified number of rows of the column of the database, the buffer manager for compressing the selected rows of the column to produce a compressed version of the rows of the column, and for storing via an output into the computer memory, the compressed version of the rows of the column into as many one or more buffers of a given size as are required to hold all of the compressed version of the rows of the column, each of the one or more buffers not used to hold rows of any column outside of the first group;

and

wherein;

the compression unit manager and the buffer manager are additionally for repeating the selecting, compressing and storing for each of a plurality of other groups of the column;

the buffer manager is additionally for storing via the buffer manager output into one or more pointer buffers, each of a certain size, pointers to each of the one or more buffers in the computer memory holding the compressed versions of the first group and each of the plurality of other groups, with an indicator of a one of the pointers to a first buffer of the first group, and for storing in the computer memory, metadata that applies to all of;

the first group and the plurality of other groups, and for storing via the buffer manager output in the computer memory, with the metadata, a pointer to the one of the pointers in one of the one or more pointer buffers pointing to the first buffer of the first group and

the first group and the plurality of other groups are all part of a single one of the plurality of portions.

2. The system of claim 1:

additionally comprising a compression strategy identifier having an input coupled to the data file receiver/portioner output for receiving the plurality of portions, for identifying and providing at an output a compression strategy for the single one of the plurality of portions, and

wherein;

the buffer manager input is additionally coupled to the compression strategy identifier output for receiving the compression strategy for the single one of the plurality of portions; and

the metadata stored by the buffer manager includes the compression strategy that the buffer manager used to compress some, but not all, of;

the first group and the plurality of other groups.

3. The system of claim 2, wherein:

the compression unit manager is additionally for identifying and providing at the compression unit manager output an additional compression strategy used to compress rows in one of A) the first group and B) one of the plurality of other groups, the additional compression strategy different from the compression strategy;

the buffer manager input is additionally for receiving the additional compression strategy;

the buffer manager compresses the rows of the one of the first group and the one of the plurality of other groups responsive to the additional compression strategy; and

the buffer manager stores the additional compression strategy with the one of;

the first group and the one of the plurality of other groups.

4. The system of claim 2, wherein:

the compression strategy provided by the compression strategy identifier comprises a dictionary; and

the buffer manager performs the compressing the some but not all of;

the first group and the plurality of other groups, responsive to the dictionary.

5. The system of claim 4, wherein the buffer manager is additionally for:

storing via the buffer manager output in the computer memory the dictionary;

storing via the buffer manager output a pointer to the dictionary in the one or more pointer buffers; and

storing via the buffer manager output in the computer memory, with the metadata, a pointer to said pointer to the dictionary.