Updating sequential data

Transfer, storage or retrieval of data can introduce accidental errors, and it is therefore important to develop methods for detection of such errors. For this purpose, various error detecting functions have been developed (for example checksums, cyclic redundancy checks (CRC) and hash functions) and are widely employed for validating and maintaining data integrity. Such functions typically take a block of data of arbitrary length and produce an integrity measure of particular data type and length (for example a 32-bit integer). The integrity of the data can be checked at any later time by re-computing the integrity measure and comparing with the previously calculated integrity measure. If the integrity measures do not match the data has been altered.

When data is purposely modified by truncation, the corresponding integrity measure is no longer valid. It is therefore necessary to recalculate the integrity measure for the truncated data, which requires re-reading of all data up to the point of truncation. In the case of large data files, this can be a costly and time consuming operation.

The problems associated with recalculating the integrity measure of data following truncation are particularly relevant to applications where data is stored in large sequential files (for example on tape media in a tape library or in a virtual tape library) containing typically several megabytes, gigabytes or even terabytes of data.

Features and advantages of embodiments of the invention will become apparent from the following description of preferred embodiments of the invention, given by way of example only, which is made with reference to the accompanying drawings.

FIG. 1 is a block diagram showing a prior art method of storing sequential data.

FIG. 2 is a block diagram showing a method of storing sequential data according to an embodiment of the present invention.

FIG. 3A is a block diagram showing a method of truncating sequential data from the start of a file according to an embodiment of the present invention.

FIG. 3B is a block diagram showing a method of truncating sequential data from the end of a file according to an embodiment of the present invention.

FIG. 4 is a block diagram showing a method of storing sequential data according to an embodiment of the present invention.

FIG. 5 is a block diagram showing a method of storing data in a linked list according to an embodiment of the present invention.

FIG. 6 is a block diagram showing a method of storing data in a binary tree according to an embodiment of the present invention.

FIG. 7 is a block diagram showing components of a system according to an embodiment of the present invention.

FIG. 8 is a flow chart showing a method for appending and truncating a file according to an embodiment of the present invention.

Various embodiments of the present invention will now be described in more detail with reference to the accompanying figures. It will be appreciated that the invention is not limited in its application to the details of method and the arrangement of components as set forth in the following description or illustrated in the drawings. It will be apparent to a person skilled in the art that additional embodiments of the present invention not detailed in the description are possible without departing from the scope or intention of the present invention. Accordingly, the following description should not be interpreted as limiting in any way, and all such embodiments are intended to fall within the scope of the claims of the present invention.

Calculating an integrity measure of a block of data is generally performed using known methods such as a CRC, checksum, hash function or other known method. Functions of this type take as input a data block B of arbitrary length, and produce as output a value C of particular type and length (for example a 32-bit integer) which provides an integrity measure for the input data. In addition, checksum, CRC and hash functions can be seeded by a seed value S such that C=F(B,S). In practice, calculation of an n-bit CRC (for example the commonly used 32-bit CRC-32 function) is typically implemented using an n-bit shift register which is preset (seeded) to all ones (−1 in twos complement binary).

By way of example only embodiments of the invention will be explained in terms of CRC functions. However, a person skilled in the art will understand that references to the term CRC, as used in the following description, can apply equally to any integrity measure including but not limited to CRC, checksum and hash functions. Moreover, depending on the context, the term CRC can denote either the function used to calculate the integrity measure, or the value of the integrity measure itself.

The term “block” as used herein refers to a plurality of data elements stored, recorded, processed, or transmitted as a unit. The elements can be single bits or groups of bits representing (without limitation) digits, characters, words, or physical records. A block may be stored on any media suitable for storage of digital data, including but not limited to random access memory (RAM), magnetic disk, optical disk, magnetic tape and semiconductor based storage. Moreover, in the present context, a block of data may itself comprise an implicit data structure such as a database record, backup session, video frame or log entry. Therefore, a person skilled in the art will understand that the term “block” in intended generically and should be interpreted as such.

FIG. 1A illustrates a file F 1 comprising plurality of blocks B 1 -B 6 stored according a prior art method for sequentially storing data. Blocks of data B 1 -B 6 are stored sequentially such that a block Bx is stored at the boundary of the preceding block Bx−1. Thus, when a new block of data is appended to the file, it is stored at the boundary of the last block of data contained in the file. In order to maintain an integrity check of file F 1 , a CRC C 6 is calculated and stored. The CRC C 6 may be stored separately from the file F 1 (for example in a log file) or alternatively may be appended to the file F 1 in a known way.

FIG. 1B illustrates appending a new block of data B 7 to an append point A of file F 1 to produce an appended file F 1 A according to the prior art method. A new CRC C 7 for the appended file F 1 A as a whole is calculated using the existing CRC C 6 and the data contained in the new block B 7 . In effect, the new CRC C 7 is calculated over the data of block B 7 and by seeding the CRC function with CRC C 6 . The new CRC is stored separately to the file F 1 A, or alternatively may be appended to file F 1 A in a known way.

Truncation of file F 1 is illustrated in FIG. 1C . The truncated file F 1 T has been truncated by deletion of block B 6 (or in any other way rendering the block unreadable) and as a result the overall CRC C 6 has been rendered invalid as an integrity measure of the truncated file F 1 T. Consequently, it is necessary to calculate a new CRC for the truncated file F 1 T which, according to prior art methods, requires re-reading of the truncated file F 1 T in its entirety to the point of truncation T. In the example shown in FIG. 1C , calculation of CRC C 5 requires re-reading of blocks B 1 -B 5 . While this may otherwise appear trivial, in back-up storage systems (including but not limited to tape libraries, virtual tape libraries etc.), typically, a file may contain several million blocks of data, and the resultant CRC calculation following truncation can be costly and time consuming. To illustrate this, consider a situation where a file comprising 1 million blocks is truncated by one record thereby having to recalculate the overall CRC for the remaining 999,999 blocks.

Embodiments of the present invention provide a method and apparatus for storing sequential data such that an integrity measure of the file as a whole can be efficiently calculated following alteration of the file by truncation or appending. More specifically, an integrity measure for the file as a whole following truncation can be calculated without recalculating the integrity measure for the whole file.

FIG. 2 shows a data structure which illustrates an embodiment of the present invention. File F 2 shown in FIG. 2A comprises blocks of data B 1 -B 6 and corresponding CRC values C 1 -C 6 . The CRC values C 1 -C 6 are stored between blocks such that each block of data is followed by the corresponding CRC value. Each CRC value is an integrity measure of the sequential file up to that point in the file where the CRC is stored. For example, CRC C 2 provides an integrity measure for blocks B 1 -B 2 , CRC C 3 provides an integrity measure for blocks B 1 -B 4 and so forth. CRC C 6 provides an integrity measure for the file as a whole. Also stored at the beginning of file F 2 is a seed value S 1 used for calculation of CRC C 1 . Seed S 1 can be an arbitrary value in a data format compatible with the chosen CRC function (for example 32-bit integer represented in binary from). Typically seed S 1 will be set to −1 as described above, but may alternatively be set according to any predetermined criteria.

When a new block is appended to file F 2 at an append point A, a new CRC value is calculated using the CRC for the preceding block and the data contained in the new block. FIG. 2B illustrates storing a new block of data B 7 to produce appended file F 2 A in accordance with the present embodiment. The new block of data B 7 and the new overall CRC C 7 are stored at the end of file in a known way to produce appended file F 2 A. The new CRC C 7 provides an integrity measure of the file as a whole, and is calculated using the CRC C 6 of the preceding block B 6 and new block B 7 .

FIG. 2C shows truncation of file F 2 at truncation point Ta to produce a truncated file F 2 T. CRC C 6 and block B 6 are deleted in a known way so that the truncated file now contains seed S 1 , blocks B 1 to B 5 and CRCs C 1 to C 5 . CRC C 5 is now the overall CRC for the truncated file F 2 T and no further CRC calculation is necessary. Hence the requirement to recalculate the CRC for the truncated file F 2 T has been obviated. If required, subsequent appending of a new block to the truncated file F 2 T may be performed as described in the preceding paragraph with reference to FIG. 2B . If the truncation point does not correspond to a stored CRC value the integrity measure can still be efficiently calculated according to the present embodiment. For example, if file F 2 of FIG. 2A is truncated to a point Tb within block B 6 such that a portion of B 6 remains, the overall CRC for the truncated file can be easily calculated using CRC C 5 and the remaining portion of block B 6 . Again, rereading of the whole truncated file has been obviated.

FIGS. 3A and 3B illustrate deletion of a block of data B 1 from the beginning of sequential file F 3 to truncation point T to produce truncated file F 3 T, such that the overall integrity check of the resulting truncated file F 3 T is maintained. Seed S 1 and block B 1 are deleted but CRC C 1 corresponding to deleted block B 1 is retained in the truncated file F 3 T. CRC C 1 is now effectively a seed value for all subsequent integrity checks on the truncated file F 3 T. For example, CRC C 2 is equivalent to a CRC calculated on block B 2 seeded with CRC C 1 . Similarly, CRC C 6 provides an integrity measure of the truncated file F 3 T as a whole, and is equivalent to a CRC calculated on blocks B 2 -B 6 seeded with CRC C 1 . Thus, the CRC values C 1 -C 6 after truncation provide a valid integrity measure of the truncated file F 3 T, and recalculating the CRC is not required.

FIG. 4A illustrates an alternative way of storing data according to an embodiment of the present invention, whereby the seed S 1 and intermediate CRC values C 1 -C 6 are stored in a sequential CRC file CF 4 separate from blocks B 1 -B 6 which are stored in file F 4 . The first CRC value C 1 stored in file CF 4 corresponds with the first block B 1 of file F 4 , CRC C 2 corresponds to block B 2 and so forth. When file F 4 is appended or truncated according to the previously described examples, the appropriate CRC value (or seed S 1 ) is deleted (in the case of truncation) or added (in the case of appending) as required.

When a new block is appended to file F 4 at an append point A, a new CRC value is calculated using the CRC C 6 (as the seed) for the data up to and including the preceding block and the data contained in a new block B 7 . FIG. 4B illustrates storing the new block of data B 7 to produce appended file F 4 A in accordance with the present embodiment. The new block of data B 7 is stored at the end of file F 4 in a known way to produce appended file F 2 A. The new overall CRC C 7 is stored at the end of file CF 4 A in a known way. The new CRC C 7 provides an integrity measure of file F 4 A as a whole, and is calculated using the CRC C 6 of the preceding block B 6 and new block B 7 .

FIG. 4C shows truncation of file F 2 at truncation point T to produce a truncated file F 4 T. CRC C 6 and block B 6 are deleted (from file CF 4 and F 4 respectively) in a known way so that the truncated file F 4 T now contains blocks B 1 to B 5 and file CF 4 T contains seed S 1 and CRCs C 1 to C 5 . CRC C 5 is now the overall CRC for the truncated file F 4 T and no further CRC calculation is necessary. Hence the requirement to recalculate the CRC for the truncated file F 4 T has been obviated. If required, subsequent appending of a new block to the truncated file F 4 T may be performed as described in the preceding paragraph with reference to FIG. 4B .

In the previously described examples the blocks of data B 1 -B 6 are stored sequentially in physical memory. However, in other embodiments data is stored using alternative structures including but not limited to linked lists and binary trees, as will now be discussed.

FIG. 5 shows a singly linked list LL 1 according to an embodiment of the invention. The list comprises nodes N 1 -N 6 and each node comprises a block of data B 1 -B 6 , a corresponding CRC value C 1 -C 6 and a reference R 2 -R 5 to the next block in the linked list LL 1 (node N 6 is the last node in the list and contains a NULL reference). Also included in the linked list is a seed node N 0 comprising a seed S 1 and reference R 1 to node N 1 . Alternatively, each node may include two references such that the list may be doubly linked in a known way. The CRC stored at each node provides an integrity check for all data blocks stored in nodes up to and including the node at which the CRC is stored.

Linked list LL 1 of FIG. 5 can be appended and truncated in accordance with embodiments of the present invention as described above. For example, if node N 6 is deleted, CRC C 5 of node N 5 is a valid integrity measure for the linked list LL 1 as a whole and reference R 6 is set to NULL. If a new node N 7 (not shown in FIG. 5 ) is appended to list LL 1 after node N 6 , reference R 6 is updated to refer to the memory address of node N 7 and a new CRC C 7 is calculated using CRC C 6 and the data contained in block B 7 of the appended node N 7 . Furthermore if node N 1 is deleted from the front of list LL 1 , the seed S 1 is updated to equal CRC C 1 and reference R 1 is updated to equal R 2 . In this way the continuity of the truncated link list LL 1 is preserved and the CRCs stored at each node remain valid.

FIG. 6 illustrates a further embodiment of the present invention implemented as a binary tree BT 1 comprising six nodes N 1 -N 6 . Each node includes a block B 1 -B 6 , a CRC C 1 -C 6 and references to the left and right child nodes R 2 -R 6 . Where a node does not link to a left child node or to a right child node, the appropriate reference is NULL. Also included in the binary tree is a seed node N 0 comprising a seed S 1 and reference R 1 to node N 1 . In FIG. 6 , nodes N 2 and N 3 are the children of node 1 ; nodes N 4 and N 5 are the child nodes of node N 2 ; and, node N 6 is the child node of node N 3 . The CRC values stored at the end of each branch of binary tree BT 1 provide an integrity measure of the blocks contained in that branch. For example, CRC C 4 is an integrity measure for the branch containing blocks B 1 , B 2 and B 4 . Binary tree BT 1 of FIG. 6 can be appended and truncated in accordance with embodiments of the present invention as described above. For example, if node N 6 is deleted, CRC C 3 of node N 3 is a valid integrity measure for the branch containing block B 1 and B 3 , and reference R 6 is set to NULL. If a new node N 7 (not shown in FIG. 5 ) is appended to binary tree BT 1 as a left child node of node N 6 , the appropriate reference of node N 6 is updated to refer to the memory address of node N 7 and a new CRC C 7 is calculated using CRC C 6 and the data contained in block B 7 of the appended node N 7 . Truncation of node N 1 from the front of binary tree BT 1 results in two separate binary trees, the first containing nodes B 2 , B 4 & B 5 , the second B 3 and B 6 . In this instance, seed S 1 is updated to equal CRC C 1 , reference R 1 is updated to equal R 2 and the NULL reference is updated to equal R 3 . Alternatively, a second seed node can be created so that each binary tree has a separate seed node. In both cases, the seed of both seed nodes is set to equal CRC C 1 and the integrity of both binary trees is preserved.

FIG. 7 show an exemplary hardware apparatus 700 for enacting the embodiments previously described. An interface 703 is adapted to receive data 701 and send data 702 . The interface 703 is operably connected to a processor 704 which comprises a CRC logic 705 and is in turn operably connected to flash memory 707 . CRC may include registers 706 a and 706 b which are configured to store the first and last CRC values of a file 710 stored in disk storage 709 (CRC C 7004 and CRC C 7852 respectively). For reasons of clarity, file 710 in FIG. 7 is shown with only two blocks of data (B 7005 and B 7852 ), but it will be understood that the file 710 may contain many thousands, millions or billions of blocks. The processor 704 is operably connected to disk storage 709 via storage adapter 708 . The storage adapter 708 is typically a dedicated processor, such as an ASIC, which is programmed to handle high speed read and write operations. The processor 704 is a general purpose programmable processor, such as an Intel Pentium™ processor, which controls overall operation of the system 700 according to a control program stored in and loaded from flash memory 707 . Alternatively, the flash memory 707 may be replaced by random access memory, and the control program may be stored elsewhere and loaded to the random access memory when the system is initiated (booted). The control program may be written in any suitable programming language including but not limited to Java, C++, C#, or combinations thereof. A person skilled in the art will realise that the present invention is not limited to a particular programming language. Alternatively or additionally, the control program may also be embodied in hardware such as a dedicated ASIC.

The processor 704 is arranged to receive a block of data via the interface 703 . Typically the received block will be accompanied by an instruction associated with the way in which the block is to be appended to the file. CRC logic 705 is configured to calculate a new CRC for file 710 using the received block of data and, where necessary, using the first and last CRC values stored in registers 706 a and 706 b respectively. Where the accompanying instruction comprises truncation of file 710 , processor 704 is configured to retrieve the CRC value before the point of the truncation from disk storage 709 via controller 708 . When calculation of the updated CRC is completed by processor 704 and CRC logic 706 , the block of data and updated CRC are sent to storage adapter 708 and stored at the appropriate logical location in disk storage 709 .

A method of storing and truncating sequential data according to an embodiment of the present invention is illustrated in FIG. 8 . According to FIG. 8 , the processor 704 receives a block of data and an associated instruction via interface 703 [step 801 ]. The processor determines if the instruction is associated with an append operation or a truncation operation [step 802 ]. In the case of an append operation, the instruction comprises data specifying the point in file 710 at which the accompanying data is to be appended (for example, append point A in FIG. 7 ). The apparatus then retrieves the CRC associated with the append position (CRC C 7852 ) from storage 709 via storage adapter 708 , and stores it in register 706 a [step 803 ]. CRC logic 705 calculates a new CRC for the appended file using the retrieved CRC and data contained in the received block [step 804 ]. The calculated CRC provides a valid integrity measure for all blocks in file 710 up to and including the appended block of data. The received block and calculated CRC are then stored at the location specified by the associated instruction (append point A in file 710 ) [step 804 ] and the process is ended [step 805 ]. Alternatively, if the instruction relates to a truncate operation [step 802 ] the processor 704 then truncates file 710 by flagging, or otherwise rendering, by a known method, the relevant areas of storage 709 as available for overwriting. In some embodiments truncation may additionally (or alternatively) comprise overwriting the truncated block using random or pseudo random data such that the truncated blocks are rendered unreadable. Following truncation, processor 704 determines if the truncate instruction is also associated with a subsequent append operation [step 808 ]. If there is an associated append operation the processor proceeds to append data as described above [step 808 ], otherwise the process ends [step 809 ].

In other embodiments, truncation and appending may be embodied as a single operation, whereby appending occurs from a point (for example T), thereby over-writing previously stored data blocks. A skilled person will understand that many different arrangements of components from those shown in FIG. 7 are possible for implementing embodiments of the present invention. For example, the entire architecture may be implemented as a dedicated ASIC, obviating the need for a central processor. Moreover, disk storage 709 may be replaced by random access memory, tape media or indeed any form of storage media suitable for storing digital data.

Embodiments of the invention herein described provide a method and apparatus for efficient truncation and appending of data to a sequential file, such that intermediate integrity checks are preserved and recalculation of the overall integrity measure is not required. According to embodiments of the invention, where the file is large (thousands, millions or billions of blocks) significant time savings are achieved with negligible overhead in terms of additional storage for, and calculation of the intermediate integrity measures. The improved efficiency provided by embodiments of the invention is advantageous in applications where an integrity check of a sequential file is required (for example, backup sessions in a tape library or virtual tape library, a log file, video and audio streaming).

The above embodiments are to be understood as illustrative examples of the invention. Further embodiments of the invention are envisaged. For example, the intermediate checksum does not necessarily need to be stored after each block, but may instead be stored less frequently (for example, after every 10 blocks). It is to be understood that any feature described in relation to any one embodiment may be used alone, or in combination with other features described, and may also be used in combination with one or more features of any other of the embodiments, or any combination of any other of the embodiments. Furthermore, equivalents and modifications not described above may also be employed without departing from the scope of the invention, which is defined in the accompanying claims.