IP Library Granted Patent US 11,789,908
Granted Patent B2
US 11,789,908 · App. 17/095,293 · Granted Oct 17, 2023

Offloading memory maintenance for a log-structured file system

Inventors: Gabriel Zvi BenHanokh (Tel-Aviv, IL); Joshua Durgin (Canyon Country, CA)
Assignee: RED HAT, INC.
G06F16/1805G06F12/0253G06F16/116G06F16/1727G06F16/18G06F16/1815G06F2212/7205
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,789,908
App. No.
17/095,293
Granted
Oct 17, 2023
Kind
B2
Abstract

Garbage collection for a log-structured file system can be offloaded from a processor to an internal controller of a storage device, such as a solid-state drive. For example, an internal controller of a storage device can determine characteristics of a log-structured file system hosted by a processor that is external to the storage device. The characteristics can indicate how data is arranged in the log-structured file system. The internal controller can then execute, based on the characteristics, a garbage collection process with respect to the data of the log-structured file system on behalf of the processor.

Claims (58)

1. A storage device comprising:

an internal controller; and

an internal memory including instructions that are executable by the internal controller for causing the internal controller to:

receive information from a processor that is external the storage device, the information indicating characteristics of a log-structured file system hosted by the processor, the characteristics indicating how data is arranged in the log-structured file system;

determine the characteristics based on the information; and

execute, based on the characteristics, a garbage collection process with respect to the data of the log-structured file system on behalf of the processor, wherein the garbage collection process involves:

determining a plurality of data blocks associated with the log-structured file system; and

for each respective data block among the plurality of data blocks:

determining a latest sequence-number associated with the respective data block based on the information received from the processor;

determining if the respective data block is stale based on the latest sequence-number corresponding to the respective data block; and

freeing the respective data block in response to determining that the respective data block is stale, wherein freeing the respective data block involves marking the respective data block as free; or

maintaining the respective data block in response to determining that the respective data block is not stale.

2. The storage device of claim 1 , wherein the information includes a metadata layout describing a format of metadata in the log-structured file system.

3. The storage device of claim 1 , wherein the information includes a mapping of the plurality of data blocks to corresponding sequence numbers, and wherein the internal memory further includes instructions that are executable by the internal controller for causing the internal controller to determine the latest sequence-number corresponding to the respective data block based on the mapping.

4. The storage device of claim 1 , wherein the information indicates a memory location at which the latest sequence-number for the respective data block is stored, and wherein the internal memory further includes instructions that are executable by the internal controller for causing the internal controller to retrieve the latest sequence-number for the respective data block from the memory location.

5. The storage device of claim 1 , wherein the internal memory further includes instructions that are executable by the internal controller for causing the internal controller to:

receive write requests including the information from the processor;

generate a mapping based on the write requests received from the processor, the mapping correlating the plurality of data blocks to corresponding sequence numbers; and

determine the latest sequence-number for the respective data block based on the mapping.

6. The storage device of claim 1 , wherein the log-structured file system is different from a default log-structured file system maintained internally to the storage device for managing a set of data blocks within the storage device.

7. The storage device of claim 1 , wherein the garbage collection process is different from a default garbage collection process of the storage device, and wherein the internal memory further includes instructions that are executable by the internal controller for causing the internal controller to execute the default garbage collection process independently of the characteristics of the log-structured file system to internally manage a set of data blocks in the storage device.

8. The storage device of claim 1 , wherein the storage device is a solid-state drive and the processor is a central processing unit of a computing device.

9. The storage device of claim 1 , wherein the storage device is coupled to a computing device that includes the processor and a memory, the memory including program code that is executable by the processor for causing the processor to:

maintain the log-structured file system; and

transmit the information indicating the characteristics to the internal controller of the storage device for enabling the storage device to execute the garbage collection process.

10. The storage device of claim 1 , wherein the storage device is configured to free the respective data block by marking the respective data block as free in a flash translation layer of the storage device.

11. A method comprising:

receiving, by an internal controller of a storage device, information from a processor that is external to the storage device, the information indicating characteristics of a log-structured file system hosted by the processor, the characteristics indicating how data is arranged in the log-structured file system;

determining, by the internal controller, the characteristics based on the information; and

executing, by the internal controller and based on the characteristics, a garbage collection process with respect to the data of the log-structured file system on behalf of the processor, wherein the garbage collection process involves:

determining a plurality of data blocks associated with the log-structured file system; and

for each respective data block among the plurality of data blocks:

determining a latest sequence-number associated with the respective data block based on the information received from the processor;

determining if the respective data block is stale based on the latest sequence-number corresponding to the respective data block; and

freeing the respective data block in response to determining that the respective data block is stale, wherein freeing the respective data block involves marking the respective data block as free; or

maintaining the respective data block in response to determining that the respective data block is not stale.

12. The method of claim 11 , wherein the information includes a metadata layout describing a format of metadata in the log-structured file system.

13. The method of claim 11 , wherein the information includes a mapping of the plurality of data blocks to corresponding sequence numbers, and further comprising determining the latest sequence-number corresponding to the respective data block based on the mapping.

14. The method of claim 11 , wherein the information indicates a memory location at which the latest sequence-number for the respective data block is stored, and further comprising retrieving the latest sequence-number for the respective data block from the memory location.

15. The method of claim 11 , further comprising:

receiving, by the internal controller, write requests including the information from the processor;

generating, by the internal controller, a mapping based on the write requests received from the processor, the mapping correlating the plurality of data blocks to corresponding sequence numbers; and

determining, by the internal controller, the latest sequence-number for the respective data block based on the mapping.

16. The method of claim 11 , wherein the log-structured file system is different from a default log-structured file system maintained internally to the storage device for managing a set of data blocks within the storage device, and wherein the garbage collection process is different from a default garbage collection process of the storage device, and further comprising:

executing, by the internal controller, the default garbage collection process independently of the characteristics of the log-structured file system to internally manage the set of data blocks in the storage device.

17. The method of claim 11 , wherein freeing the respective data block comprises marking the respective data block as free in a flash translation layer of the storage device.

18. A non-transitory computer-readable medium comprising instructions that are executable by an internal controller of a storage device for causing the internal controller to:

receive information from a processor that is external the storage device, the information indicating characteristics of a log-structured file system hosted by the processor, the characteristics indicating how data is arranged in the log-structured file system;

determine the characteristics based on the information; and

execute, based on the characteristics, a garbage collection process with respect to the data of the log-structured file system on behalf of the processor, wherein the garbage collection process involves:

determining a plurality of data blocks associated with the log-structured file system; and

for each respective data block among the plurality of data blocks:

determining a latest sequence-number associated with the respective data block based on the information received from the processor;

determining if the respective data block is stale based on the latest sequence-number corresponding to the respective data block; and

freeing the respective data block in response to determining that the respective data block is stale, wherein freeing the respective data block involves marking the respective data block as free; or

maintaining the respective data block in response to determining that the respective data block is not stale.

19. The non-transitory computer-readable medium of claim 18 , wherein the information includes a metadata layout describing a format of metadata in the log-structured file system.

20. The non-transitory computer-readable medium of claim 18 , wherein the log-structured file system is different from a default log-structured file system maintained internally to the storage device for managing a set of data blocks within the storage device.

Assignments (2)
CHANGE OF NAME Recorded Mar 3, 2026
From: RED HAT, INC.
To: RED HAT, LLC
Reel/Frame 074913/0759 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 11, 2020
From: DURGIN, JOSHUA; BENHANOKH, GABRIEL ZVI
To: RED HAT, INC.
Reel/Frame 054385/0354 →