Seek minimized recoverable streaming file system

• US 7,949,776 B2
• Filed: 09/16/2008
• Issued: 05/24/2011
• Est. Priority Date: 06/10/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Swan, Paul R.
• Primary Examiner(s): Ismail; Shawki S
• Assistant Examiner(s): KOROBOV, VITALI A
• Application Number:
  US12/211,317
• Publication Number:
  US 20090012929A1
• Time in Patent Office: 980 Days
• Field of Search: 709/230, 709/231, 709/233, 709/236, 709/246
• US Class Current: 709/231
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0676 Magnetic disk device

Abstract

A method for storing data, comprising the steps of (A) receiving a stream of data, (B) storing the stream of data in a series of data clusters each comprising (i) a predecessor link, (ii) a data portion, and (iii) a successor link, where the predecessor links and successor links are configured to minimize seek time between the clusters during contiguous stream operations.

Claims

1. A method for storing data, comprising the steps of:

(A) receiving a stream of data;

(B) storing said stream of data as a file in a series of data clusters each comprising (i) a predecessor link, (ii) a data portion, and (iii) a successor link, wherein said predecessor links and said successor links are configured to minimize seek time between accesses to said data clusters during contiguous stream operations by storing an address of a second data cluster within said successor link of a first data cluster; and

(C) appending to said file during one or more write-append operations by writing to a second series of data clusters each comprising (i) a predecessor link, (ii) a data portion, and (iii) a successor link, wherein (a) said appending occurs without recording said successor links of said second series of data clusters when said file is in use and (b) said appending allows an append recovery to be performed on said file after a potential power interruption.

2. The method according to claim 1, wherein said series of data clusters comprises a bi-directionally linked chain.

3. The method according to claim 2, wherein (i) a head pointer comprises a predecessor link configured to link a current one of said clusters to a predecessor one of said cluster and (ii) a tail pointer comprises a successor link configured to link said current cluster to a successor one of said clusters.

4. The method according to claim 3, further comprising the step of:

transforming said successor data cluster into said current data cluster when said predecessor link in said successor data cluster links to said predecessor data cluster and when said predecessor data cluster is not a tail pointer.

5. The method according to claim 3, further comprising the step of:

linking an alternate data cluster to said predecessor link in said successor data cluster if said successor data cluster does not link to said current data cluster.

6. The method according to claim 5, wherein:

if said successor link in said alternate data cluster links to said successor data cluster then said current data cluster becomes a tail data cluster of said chain.

7. The method according to claim 5, wherein:

if the successor link of said alternate data cluster does not link to said successor data cluster then (i) said current data cluster is not the tail of said chain, (ii) said predecessor link in said successor data cluster is overwritten to link to said current data cluster, and (iii) said successor data cluster becomes said current data cluster.

8. The method according to claim 1, said method further comprising (i) checking linkage from a current one of said clusters to a successor one of said clusters and (ii) reading said stored data when said linkage is correct in response to a read pointer reaching an end of said current cluster.

9. The method according to claim 1, said method further comprising (i) checking linkage from a current one of said cluster to a successor one of said clusters and (ii) writing said data to said successor cluster when said linkage is correct in response to a write pointer reaching an end of said current cluster.

10. The method according to claim 1, said method further comprising, when a write pointer reaches an end of a tail cluster of said clusters (i) overwriting a link to a free cluster, wherein said free cluster is not in said series of clusters, (ii) reading a predecessor link in said free cluster, and (iii) overwriting said predecessor link to generate a link to said tail cluster.

11. The method according to claim 1, wherein said method operates in (i) a forward streaming data transfer mode, (ii) a reverse streaming data transfer mode, (iii) a forward streaming data over-write mode and (iv) a reverse streaming data over-write mode.

12. The method according to claim 1, further comprising the step of:

operating within the context of a streaming video application.

13. The method according to claim 1, wherein (a) said predecessor link is physically located immediately before a first portion of file data to be written in said first data cluster and a seek to a central file table is not needed to obtain data from said second data cluster and (b) said successor link is physically located immediately after said first portion of said file data to be written in said first data cluster and a seek to said central file table is not needed to access said data.

14. The method according to claim 1, wherein said predecessor link and said successor link operate without referencing a central file table.

15. The method according to claim 1, wherein said first data cluster stores an (i) an address of a data cluster before said first data cluster within a predecessor link of said first data cluster and (ii) said address of said second data cluster within a successor link of said first data cluster.

16. The method according to claim 1, wherein said series of data clusters form a file system and said series of data clusters that are consecutively accessed without referencing a central file table to further minimize seek time between said data clusters.

17. An apparatus for storing a stream of data comprising a plurality of data clusters, wherein each of said data clusters comprises (i) a predecessor link, (ii) a data portion, and (iii) a successor link and said plurality of clusters are stored as a file and configured in series to minimize seek time between accesses to said clusters by storing an address of a second data cluster within said successor link of a first data cluster, wherein (a) said apparatus appends to said file during one or more write-append operations by writing to a series of append data clusters, and each of said append data clusters comprises (i) a predecessor link, (ii) a data portion, and (iii) a successor link, (b) said append occurs without recording said successor links of said append data clusters when said file is in use and (c) said append allows an append recovery to be performed on said file after a potential power interruption.

18. The apparatus according to claim 17, wherein said series of data clusters form a file system and said series of data clusters are consecutively accessed without referencing a central file table to further minimize seek time between said data clusters.

19. The apparatus according to claim 17, wherein said apparatus is configured to operate in (i) a forward streaming data transfer mode, (ii) a reverse streaming data transfer mode, (iii) a forward streaming data over-write mode and (iv) a reverse streaming data over-write mode.

20. An apparatus for storing data comprising:

means for receiving a stream of data;

means for storing said stream of data in a series of data clusters stored as a file and each comprising (i) a predecessor link, (ii) a data portion, and (iii) a successor link, wherein said predecessor links and said successor links are configured to minimize seek time between accesses to said data clusters during contiguous stream operations by storing an address of a second data cluster within said successor link of a first data cluster; and

means for appending to said file during one or more write-append operations by writing to a second series of data clusters each comprising (i) a predecessor link, (ii) a data portion, and (iii) a successor link, wherein (a) said appending occurs without recording said successor links of said second series of data clusters when said file is in use and (b) said appending allows an append recovery to be performed on said file after a potential power interruption.