Browse Prior Art Database

High-Integrity Storage of Linked Lists on Disk without Logging

IP.com Disclosure Number: IPCOM000112580D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 100K

Publishing Venue

IBM

Related People

Schofield, AJ: AUTHOR

Abstract

Described is a solution to the problem of storing a list of elements of variable size on disk and maintaining maximum integrity, without the overhead of redundantly recording updates to the lists to a log, or other medium. This problem is made worse by the practice of disk drive controllers optimising the order of writing data to the disks, so as to minimise the delays of waiting for the disk to spin. For example, when a long piece of data is written to disk, the end of the data may be written before the beginning. Lists of interest are highly dynamic in nature with entries being added and removed constantly so it is not acceptable to extend the list ad infinitum, but instead a strategy for filling the gaps left by removed elements is needed.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

High-Integrity Storage of Linked Lists on Disk without Logging

      Described is a solution to the problem of storing a list of
elements of variable size on disk and maintaining maximum integrity,
without the overhead of redundantly recording updates to the lists to
a log, or other medium.  This problem is made worse by the practice
of disk drive controllers optimising the order of writing data to the
disks, so as to minimise the delays of waiting for the disk to spin.
For example, when a long piece of data is written to disk, the end of
the data may be written before the beginning.  Lists of interest are
highly dynamic in nature with entries being added and removed
constantly so it is not acceptable to extend the list ad infinitum,
but instead a strategy for filling the gaps left by removed elements
is needed.  This in turn necessitates storing some sort of linking or
index information which must stay in step with the list itself.

      Disk drives arrange data as a series of sectors, of typically
512 bytes.  Modern drives guarantee to update sectors atomically,
that is if the power fails, the sector will be written, but never
only half written.  When the power fails, the drive has enough time
to complete writing the current sector before it becomes inactive, so
this is generally not a problem.  If by some mechanical intervention
at the wrong moment, like giving the drive a jolt, the head were to
move away from the sector being written, and then the power went, it
may not be able to complete writing the sector.  In this unlikely
scenario, the checksum of the sector's data would not agree with the
data and the drive would refuse to read the data reporting disk
damage.  This invention does not deal with the case in which the disk
becomes damaged, because it does not use redundant data storage.

      The elements in the list are stored as a singly-linked list,
that is, each element has a link to the next element following it, if
there is one, or a marker indicating that it is at the end of the
list.  Each element is allocated space in the list such that no
element shares a disk sector with another element.  Also, the link
from one element to the next is not allowed to span sectors, while
the data in each element may span sectors.  There is also a record
containing the link to the start of the list, which again must not
span a sector boundary.  To add an element into the list, advantage
is taken of the following.  At any moment, the list is viewed as
those elements reachable by following the links from the start to the
end of the list.  That is, there may be data in the space allocated
to the list which is not currently reachable by following the links.
This would typically be because of elements removed from the list
which have left gaps in the space, referred to as free space.

      When an element is to be added, free space is chosen to hold
the element, either by...