DATA MANAGEMENT METHOD, DATA MANAGEMENT PROGRAM, AND DATA MANAGEMENT DEVICE

• US 20090271435A1
• Filed: 02/19/2009
• Published: 10/29/2009
• Est. Priority Date: 04/24/2008
• Status: Abandoned Application

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Sugaya, Natsuko, Ihara, Shinsuke, Iijima, Michio, YAKO, Katsushi
• Application Number:
  US12/388,726
• Publication Number:
  US 20090271435A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Provided is a data management method. Data corresponds to an entry including a reference to another entry and is managed in a set which is a collection of pieces of the data. The set corresponds to a linked list where the entry corresponding to the data is linked in order of addition of the data. The entry includes an insertion time sequence number inserted into the linked list and information indicating if the data has been deleted from the set. In that case, the entry is separated from the linked list at a predetermined timing. The linked list is traced to refer to the data. When the insertion time sequence number of the reference entry is later than the insertion time sequence number of the entry which has already been referred to, it is judged that the reference entry has been separated from the linked list.

Claims

1. A data management method which is used in a data management device comprising a data storage unit, an object referring module, and an object area reclaim module, and manages data stored in the data storage unit,

the data corresponding to an entry which includes a reference to another entry and being managed in a set which is a collection of pieces of the data,

the set corresponding to a linked list in which the entry corresponding to the data is linked in order of addition of the data to the set,

the entry including an insertion time sequence number inserted into the linked list and deletion identification information indicating whether or not the data has been deleted from the set,

the data management method including the steps of:

separating, by the object area reclaim module, the entry from the linked list in a thread different from the thread of the object referring module in a case where the data has been deleted from the set;

sequentially referring to, by the object referring module, the data corresponding to the entry by tracing the linked entries from a head entry of the linked list;

comparing, by the object referring module, the insertion time sequence number of a reference entry corresponding to the data to be referred to with the insertion time sequence number of an entry linking the reference entry; and

sequentially referring to, by the object referring module, the data corresponding to the entry from an entry linked to a referred-to entry in which the data has already been referred to in a case where the insertion time sequence number of the reference entry is later than the insertion time sequence number of the entry linking the reference entry.

2. The data management method according to claim 1, wherein:

the data management device further comprises an object insertion module; and

the data management method further includes the step of inserting, by the object insertion module, in a case where new data is added to the set, an entry corresponding to the data to be added to a head of the linked list.

3. The data management method according to claim 1, wherein:

the data management device further comprises an object deletion module; and

the data management method further includes the step of setting, by the object deletion module, the deletion identification information of an entry corresponding to the data to be deleted in a case where the data is deleted from the set.

4. The data management method according to claim 1, wherein:

the entry includes a deletion time sequence number deleted from the set as the deletion identification information; and

the data management method further includes the steps of;

judging, by the object referring module, whether or not the entry has been deleted from the set according to whether or not a valid value is set in the deletion time sequence number;

obtaining, by the object referring module, a referring start time sequence number indicating start of referring to the data included in the linked list; and

referring to, by the object referring module, the data corresponding to the reference entry in a case where no valid value is set in the deletion time sequence number of the reference entry, or the deletion time sequence number is later than the referring start time sequence number.

5. The data management method according to claim 4, further including the step of referring to, by the object referring module, the data corresponding to an entry linked to the reference entry in a case where a valid value is set in the deletion time sequence number of the reference entry, and the deletion time sequence number is earlier than the referring start time sequence number.

6. The data management method according to claim 1, wherein:

the data management device executes a plurality of threads which refer to the data;

the entry includes a deletion time sequence number deleted from the set as the deletion identification information; and

the data management method further includes the steps of;

obtaining, by the object area reclaim module, an earliest time sequence number as an earliest referring time sequence number from among time sequence numbers each indicating a last reference to the linked list in each of the plurality of threads;

sequentially obtaining, by the object area reclaim module, the deletion time sequence number included in the entry by tracing the linked entries from the head entry of the linked list; and

separating, by the object area reclaim module, the entry corresponding to the obtained deletion time sequence number from the linked list in a case where the obtained deletion time sequence number is earlier than the earliest referring time sequence number.

7. The data management method according to claim 6, wherein:

the entry separated from the linked list is reutilized in a case where new data is stored in the set; and

the data management method further includes the step of updating, by the object insertion module, when new data is added to the set, the insertion time sequence number of the entry before an entry corresponding to the data to be added is linked to the linked list.

8. The data management method according to claim 1, wherein:

the entry includes update history of the data corresponding to the entry;

the update history is added with a corresponding version each time the data is updated;

the version includes a version setting time sequence number indicating when the data corresponding to the version is set; and

the deletion identification information is identified as indicating that the entry has been deleted from the set in a case where no data corresponding to a latest version included in the entry is present.

9. The data management method according to claim 8, further including the steps of:

obtaining, by the object referring module, a referring start time sequence number indicating start of referring to the data included in the linked list; and

setting, by the object referring module, from among versions of the reference entry each having the version setting time sequence number earlier than the referring time start sequence number, a latest version as a referring target version, and referring to the data corresponding to the referring target version.

10. The data management method according to claim 9, further including the step of referring to, by the object referring module the data corresponding to the entry linked to the reference entry in a case where no data corresponding to the referring target version is present.

11. The data management method according to claim 8, wherein:

the data management device executes a plurality of threads which refer to the data; and

the data management method further includes the steps of;

obtaining, by the object area reclaim module, an earliest time sequence number as an earliest referring time sequence number from among time sequence numbers each indicating a last reference to the linked list in each of the plurality of threads;

sequentially obtaining, by the object area reclaim module, an entry deleted from the linked list by tracing the linked entries from the head entry of the liked list; and

separating, by the object area reclaim module the obtained entry from the linked list in a case where the deletion time sequence number of the obtained entry is earlier than the earliest referring time sequence number.

12. A storage medium recorded with a data management program which is used in a data management device comprising a data storage unit and an object area reclaim module, and is executed for managing data stored in the data storage unit,

the data corresponding to an entry which includes a reference to another entry and being managed in a set which is a collection of pieces of the data,

the set corresponding to a linked list in which the entry corresponding to the data is linked in order of addition of the data to the set,

the entry including an insertion time sequence number inserted into the linked list and deletion identification information indicating whether or not the data has been deleted from the set,

the object area reclaim module separating the entry from the linked list in a thread different from the thread in which the program is being executed in a case where the data has been deleted from the set,

the program including procedures of:

sequentially referring to the data corresponding to the entry by tracing the linked entries from a head entry of the linked list;

comparing the insertion time sequence number of a reference entry corresponding to the data to be referred to with the insertion time sequence number of an entry linking the reference entry; and

sequentially referring to the data from an entry linked to a referred-to entry in which the data has already been referred to in a case where the insertion time sequence number of the reference entry is later than the insertion time sequence number of the entry linking the reference entry.

13. A data management device, comprising:

a data storage unit;

an object referring module; and

an object area reclaim module,

the data management device managing data stored in the data storage unit, wherein;

the data corresponds to an entry which includes a reference to another entry and is managed in a set which is a collection of pieces of the data;

the set corresponds to a linked list in which the entry corresponding to the data is linked in order of addition of the data to the set;

the entry includes an insertion time sequence number inserted into the linked list and deletion identification information indicating whether or not the data has been deleted from the set;

the object area reclaim module separates the entry from the linked list in a thread different from the thread of the object referring module in a case where the data has been deleted from the set; and

the object referring module is configured to;

sequentially refer to the data corresponding to the entry by tracing the linked entries from a head entry of the linked list;

compare the insertion time sequence number of a reference entry corresponding to the data to be referred to with the insertion time sequence number of an entry linking the reference entry; and

sequentially refer to the data corresponding to the entry from an entry linked to a referred-to entry in which the data has already been referred to in a case where the insertion time sequence number of the reference entry is later than the insertion time sequence number of the entry linking the reference entry.