Method and apparatus for fault-tolerant memory management

摘要

A device and method for providing a fault-tolerant file system. The fault-tolerant file system attempts to minimize the number of writes used when updating file system data structures. In one embodiment, file system data, including file system metadata, is stored in a fault-tolerant tree including a working state and a transacted state. In one embodiment, a change list is used to track blocks that have been updated, instead of cascading updates to leaf nodes up the tree, and a delta block is used to further minimize block updates when adding or removing nodes from the tree. In one embodiment, a Q-Block is used to prevent cycles when adding and removing free blocks from an allocation tree. Metadata values are stored in the tree in a way that allows certain metadata values to be inferred when not present in the tree, thus conserving space and lowering query time.

主权项

1. A computer-implemented method of storing and updating data, the method comprising:
storing, on a computer-readable storage medium, a plurality of logical nodes, wherein each logical node includes one or more key-value pairs, and wherein each logical node includes a first block and a second block; updating a key-value pair of a first logical node of the plurality of logical nodes by overwriting the first block of the first logical node on the computer-readable storage medium, wherein a second logical node of the plurality of logical nodes includes a reference to the second block of the first logical node as a current block of the first logical node; modifying an entry in a change list to indicate that the reference in the second logical node to the second block of the first logical node as the current block of the first logical node should be redirected to the first block of the first logical node without modifying the second logical node; and removing an entry from the change list when an available space in the change list is less than a threshold amount; wherein removing an entry from the change list includes:
choosing an entry from the change list to remove based on predetermined criteria, the entry indicating that references to a second block of a previously updated logical node should be redirected to a first block of the previously updated logical node;removing the chosen entry from the change list; andfor each logical node in the plurality of logical nodes containing a reference to the second block of the previously updated logical node:
updating a first block of the referring logical node;overwriting the first block of the referring logical node on the computer-readable storage medium; andmodifying an entry in the change list to indicate that references to a second block of the referring logical node should be redirected to the first block of the referring logical node.