Information storage system and data replication method thereof

CLAIM OF PRIORITY

The present application claims priority from Japanese patent application JP2011-89420 filed on Apr. 13, 2011, the content of which is hereby incorporated by reference into this application.

BACKGROUND

The present invention relates to an information storage system and a data replication method thereof, and particularly, relates to data replication in an information storage system including a plurality of information storage nodes.

In a computing system, information required by a system is often stored in a database. A relational database is one of the most widely known databases. A relational database offers excellent functions such as data coupling and consistency of data in transactions. On the one hand, the relational database does not necessarily have high scalability.

With advancement of the distribution technology over Internet such as the cloud technology, a system is required that can increase the number of servers on demand, while enabling a multitude of servers to perform high-speed distributed processing. As a technology that can meet such a need, a key value store is attracting attention. A key value store stores a pair of a key and a value. A system specifies a key of a target value to acquire the value. By changing, depending on a key value, a destination server (node) in which a key is saved depending on a key value, the key value store can distribute data and save them in a plurality of servers. Thus, the key value store can easily construct a scale-out system which processes a large amount of data. The consistent hashing is known as a technique to determine a responsible node depending on a key value (See Non-Patent Literature 1, for example.)

In addition, Non-Patent Literature 2 discloses a technology to achieve high availability in a key value store. Specifically, the literature discloses replications of data by a plurality of hosts to achieve high availability and durability. Each data item is replicated and stored in N units of hosts which are set with respect to each instance. A coordinator node is assigned to each key. The coordinator node is responsible for replication of a data item which is assigned thereto. In addition to storing of each of the keys for which it is responsible in its own memory, the coordinator node replicates the keys to adjacent N−1 units of nodes in a clockwise direction in a ring arrangement.

Non-Patent Literature 2 discloses a method for adding a new node X and a method for removing a node from a system. By adding the new node X, a specific key range is assigned to X. Some existing nodes, which have retained keys newly assigned to the node X, no longer need to have those keys. The existing nodes transfer to the node X the keys which they no longer need to keep. Similarly, when a node is removed from a system, keys are relocated in reverse steps to the node addition.

In Non-Patent Literature 3, in order to improve data availability, one key is mapped to k points in a coordinate space by means of k different hash functions so as to replicate and store one key value pair in k different nodes in a system.

Non-Patent Literature 1: Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin and R. Panigrahy, In: Proc. 29th Ann. ACM Symp. On Theory of Computing, 1997, pp. 654-663

Non-Patent Literature 2: Dynamo: amazon's highly available key value store, G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, W. Vogels : In: SOSP. Pp. 205-220 (2007)

Non-Patent Literature 3: A Scalable Content-Addressable Network, Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, SIGCOMM'01, Aug. 27-31, 2001, San Diego, Calif., USA

SUMMARY

In a distributed data store, it is important to keep the replication value of each data when a node is added or deleted. In a system including a plurality of nodes, when one of data is replicated and stored in some nodes in the system, the replication value means the number of nodes in which the one of data is stored.

For example, a system includes a multitude of nodes and data stored in 3 nodes in the system is in the condition that “the replication value is 3”. One of the 3 nodes stores original data, while other 2 nodes store replicated data. When one of the 3 nodes fails and becomes unusable, the number of nodes which store the data decreases by 1, and thus the number of data replications is reduced to 2.

As noted above, Non-Patent Literature 1 describes a consistent hashing technique. However, since the consistent hashing of Non-Patent Literature 1 stores information only in 1 node, the information is lost if the node fails and becomes unusable.

In Non-Patent Literature 2, identical data are stored in N units of nodes. Specifically, identical data are stored in a certain coordinator node and in following N−1 units of nodes. This enables the data to be read from any of the nodes following the coordinator node even if the coordinator node becomes unusable.

However, all replicated data of original data stored in the coordinator node is stored in the nodes following it. Thus, when the replication value decreases due to a node failure, only nodes around a failed node contribute to processing of recovering the replication value, while nodes remote from the failed node cannot contribute to the process. Therefore the nodes in the neighborhood of the failed node must transmit and receive much data to recover the replication value.

Thus, in Non-Patent Literature 2, only a small number of nodes in the system contribute to the recovery process to recover the replication value, thus resulting in a disbalance in the amount of processing over the system. Accordingly, response time fluctuates depending on whether or not a node processing a request from a client is performing the recovery process, resulting in a fluctuation in the response time of a system. Furthermore, since the recovery process needs to be performed only by the small number of nodes, it takes much time before the replication value is recovered.

Now, a specific example will be shown. An example of a system will be described in which the number of nodes is 1000, each node is connected to a network of 1 Gbps (Giga Bit per Second), original data of 1 TB (Tera Byte) per node is retained (that is to say, data of 1 TB exists in a responsible range of each node), and the replication value is kept to 3.

Each of nodes has original data of 1 TB, a replica 1 of 1 TB, and a replica 2 of 1 TB. In fact, a total amount of data in each node is 3 TB. For illustrative purposes, a number from node <b>1</b> to node <b>1000</b> is assigned to each of the 1000 nodes in a clockwise direction. For example, a first replica of the original data retained in a node <b>1</b> (this shall be referred to as data in a node <b>1</b>'s responsible range) is retained in a node <b>2</b>, and a second replica is retained in a node <b>3</b>.

In other words, the node <b>3</b> retains a replica of the second original data of the node <b>1</b>, a first replica of the original data of the node <b>2</b>, and the original data of the node <b>3</b>. In fact, the node <b>3</b> retains the data in the node <b>1</b>'s responsible range, data in a node <b>2</b>'s responsible range, and data in a node <b>3</b>'s responsible range. Similarly, a node <b>4</b> retains a second replica of the original data of the node <b>2</b>, a first replica of the original data of the node <b>3</b>, and the original data of the node <b>4</b>. So do other nodes.

Now suppose that a node <b>5</b> becomes unusable due to a failure. A node <b>5</b>'s responsible range is newly added to a node <b>6</b>'s responsible range. In fact, the node <b>6</b> treats data which it retains as a first replica of the original data of the node <b>5</b>, as the original data of the node <b>6</b>. The node <b>6</b> further treats data which it retains as a second replica of the node <b>4</b>, as a first replica of the node <b>4</b>. Then, the node <b>6</b> newly replicates data in the node <b>3</b>'s responsible range from any node (node <b>3</b> or node <b>4</b>), and retains the data as a second replica of the node <b>3</b>.

Similarly, a node <b>7</b> needs to newly retain data in the node <b>4</b>'s responsible range, and a node <b>8</b> needs to newly retain data in the node <b>5</b>'s responsible range. Here, for example, data in the node <b>3</b>'s responsible range is replicated from the node <b>3</b> to the node <b>6</b>, data in the node <b>4</b>'s responsible range is replicated from the node <b>4</b> to the node <b>7</b>, and data in a range for which the node <b>5</b> is conventionally responsible (which is now data of a part of the node <b>6</b>'s responsible range) is replicated from the node <b>6</b> to the node <b>8</b>. (The “processing of recovering the original replication value” shall be simply referred to as a “recovery process”.)

Then, the node <b>3</b> must transmit 1 TB which corresponds to one-thirds of the data of 3 TB retained by it. Similarly, the node <b>4</b> and the node <b>6</b> must also transmit 1 TB which corresponds to one-thirds of the data retained by them. Furthermore, the node <b>6</b>, node <b>7</b>, and node <b>8</b> must respectively receive new data of 1 TB.

In particular, the node <b>6</b>'s responsible range is doubled. In addition, the node <b>6</b> must transmit data of 1 TB to the node <b>8</b> while receiving data of 1 TB from the node <b>3</b>, thus often becoming highly-loaded. In addition, time for recovering the replication value to 3 is time for transferring data of 1 TB. Since the system uses the 1 Gbps network, the recovery process takes about 2 hours and 13 minutes. From the standpoint of data redundancy, it is very long time. It is desirable to recover the replication value more quickly.

In addition, a failure probability of an external storage device represented by a hard disk drive is higher as load increases. During the recovery process described above, although the node <b>3</b>, the node <b>4</b>, the node <b>6</b> and the node <b>7</b> retain precious data for which the replication value is “2”, their accesses to the storage device increase. (Shortly, the load on the storage device increases.)

The high the load becomes, the more the failure probability increases. If any of the nodes mentioned above fails, data of 1 TB whose replication value is “1” is generated. Since the node retaining the data becomes further highly-loaded, the failure probability thereof further increases. Consequently, if the node fails, the data are permanently lost. Therefore, it is important to cut off the chain of the increasing failure probability.

As described above, Non-Patent Literature 3 discloses storage of identical data in k units of nodes (1 original data and k−1 replicas) by means of k different functions. The literature does not disclose addition and deletion of a node, however. If a certain node becomes unusable due to a failure, the replication value of data stored in that node decreases to k−1 in the entire system. Furthermore, if the k units of nodes fail, the data will be lost from the system.

The present invention has been made in light of such circumstances. One object thereof is to promptly recover the replication value when the replication value decreases due to a failure or deletion of a node, and the like.

To solve the problems, for, example, the configuration disclosed in the claims is employed. The present invention includes means to solve the problems and an example is an information storage system storing received data. The information storage system includes a network, a plurality of information storage nodes communicatably connected by the network, and an administration part communicatably connected with the plurality of information storage nodes. Each of the received data is replicated to a defined number of data having an identical content, and stored in one of the plurality of information storage nodes. The administration part is configured to provide the replicated data having the identical content with different categories. The administration part is configured to make a determination of information storage nodes for storing the data having the identical content and provided with the different categories from the plurality of information storage nodes. The administration part is configured to make the determination so that data which correspond to respective data belonging to one category and to be stored by one information storage node, have identical contents to the respective data and belong to a different category from the one category, are distributed in a plurality of information storage nodes other than the one information storage node. The administration part is configured to make the determination by substituting some or all of information contained in the received data into arithmetic expressions defined for respective categories. In a case where use of a first information storage node in the plurality of information storage nodes is interrupted, each of the plurality of information storage nodes is configured to extracts, from data stored in the each of the plurality of information storage nodes, one of data which has an identical content to data stored in the first information storage node and whose category is pre-associated with a category of the data stored in the first information storage node. Each of the plurality of information storage nodes is configured to replicate the extracted data to an information storage node selected according to a predetermined sequence.

According to an aspect of the present invention, in an information storage system including a plurality of information storage nodes, if the number of the information storage nodes which store data decreases, time necessary for data replication to increase the decreased replication value can be reduced. Any problem, configuration or effect other than those described above will become apparent through the following description of embodiments.

BRIEF DESCRIPTION OF DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> is a view schematically showing a logical configuration of information storage nodes of a first embodiment.

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram showing a configuration example of an information storage system of the first embodiment and peripheral devices thereof.

<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram schematically showing a configuration example of a client of the first embodiment.

<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram schematically showing a configuration example of an administration node of the first embodiment.

<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram schematically showing a configuration example of the information storage node of the first embodiment.

<figref idref="DRAWINGS">FIG. 6</figref> is a view showing an example of a node management table for managing the responsible hash value ranges and life-and-death information of respective information storage nodes in the first embodiment.

<figref idref="DRAWINGS">FIG. 7</figref> is an example of a data storage table which stores data of a node <b>2</b> in the first embodiment.

<figref idref="DRAWINGS">FIG. 8</figref> is an example of a data storage table which stores data of a node <b>4</b> in the first embodiment.

<figref idref="DRAWINGS">FIG. 9</figref> is a flow chart showing a processing when a node N dies in the first embodiment.

<figref idref="DRAWINGS">FIG. 10</figref> is a flow chart of extracting data related to the node N, from the data owned by the information storage nodes themselves, in the first embodiment.

<figref idref="DRAWINGS">FIG. 11</figref> is a flow chart of determining an information storage node which the date is stored in or written into, from a key value in the first embodiment.

<figref idref="DRAWINGS">FIG. 12</figref> is a flow chart showing an example of a processing in which a client writes a value by means of a key, in the first embodiment.

<figref idref="DRAWINGS">FIG. 13</figref> is a flow chart showing an example of a processing in which the client reads information from the information storage system, in the first embodiment.

<figref idref="DRAWINGS">FIG. 14</figref> is a flow chart of finding an information storage node from which data should be read, by using a key, from nodes in ALIVE state, in the first embodiment.

<figref idref="DRAWINGS">FIG. 15</figref> is a flow chart showing an example of processing in which the information storage node from which data should be read is found by using a key from backup destination information storage nodes of information storage nodes in SUBSTITUTED state, in the first embodiment.

<figref idref="DRAWINGS">FIG. 16</figref> is a flow chart showing a processing of inserting other information storage node between 2 information storage nodes in the first embodiment.

<figref idref="DRAWINGS">FIG. 17</figref> is a flow chart showing a processing of extracting the data related to the inserted information storage node from the data stored by the information storage node.

<figref idref="DRAWINGS">FIG. 18</figref> is a flow chart showing a processing when another information storage node dies while data relocation resulted from death of an information storage node is being executed, in a second embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Hereinafter, embodiments of the invention are described with reference to the accompanying drawings. For clear description, specific details of the following description and the drawings are omitted and simplified where appropriate. Further, throughout the drawings, the same elements are denoted by the same reference symbols, and redundant description is omitted where necessary for clear description.

&lt;First Embodiment&gt;

In the following, a first embodiment will be described. In the embodiment, a distributed data store (distributed information storage system) is described. In a distributed data store, original data is replicated, and the original data and one or more replicated data are stored in different information storage nodes. This allows high-speed processing and high failure resistance.

The present invention is preferable for a key value store which manages data with a pair of 2 data as a unit. Then, an example of a key value store is described in the embodiment. The present invention is also applicable to any distributed system other than the key value store. The key value store stores a pair of a key and a value. A user specifies a key of a target value to acquire the value (and the key).

Depending on a key value, a distributed key value store changes a destination server (node) in which original data and replicas thereof (replicated data of the original data) are saved. With reference to <figref idref="DRAWINGS">FIG. 1</figref>, a method with which a system of the embodiment determines nodes to store original data and replicas thereof will be described. <figref idref="DRAWINGS">FIG. 1</figref> describes an example in which a storage destination of data “Tokyo” <b>110</b>, which is a key, is determined. Selected servers respectively store a pair of the key and a value (an original pair or a replicate of the pair) (not shown). In the description of <figref idref="DRAWINGS">FIG. 1</figref>, a mention for the value is omitted.

<figref idref="DRAWINGS">FIG. 1</figref> shows an example of a logical configuration of information storage nodes (hereinafter also referred to as nodes) included in the information storage system of the embodiment. The system is provided with a plurality of information storage nodes. <figref idref="DRAWINGS">FIG. 1</figref> illustrates the ring-like arranged 7 information storage nodes from an information storage node <b>1</b> (<b>101</b>) to an information storage node <b>7</b> (<b>107</b>). The arrangement of the information storage nodes shows arrangement of nodes (logical positions) in a logical space for determining the information storage nodes which store data (original data and replicas), and does not mean a physical arrangement of the information storage nodes in the system.

<figref idref="DRAWINGS">FIG. 1</figref> schematically shows a method for assigning user data (key) “Tokyo” <b>110</b> to the information storage nodes in the system. An original node for the data “Tokyo” <b>110</b> is a node <b>2</b> (<b>102</b>), which stores the original data <b>111</b>.

A first replica storage node is a node <b>4</b> (<b>104</b>), which stores a first replica (data “Tokyo”) <b>112</b>. A second replica storage node is a node <b>7</b> (<b>107</b>), which stores a second replica (data “Tokyo”) <b>113</b>.

The information storage system uses 3 different arithmetic expressions to determine the information storage nodes for storing data of each of 3 categories (the original data, the first replica, and the second replica) of the user data. Using the arithmetic expressions enables acquisition of different computed values from the user data.

For example, the information storage system uses a hash function to determine the information storage nodes to which the original data and the 2 replicas are assigned. As a hash function, MD5, SHA-1, SHA-256, and the like are well known. For example, the information storage system of the embodiment prepares a different hash function for each of the original data, the first replica, and the second replica, and determines the information storage nodes for storing the original data and the replicas, respectively, according to a hash value of the key (the data “Tokyo” in this example) based on each hash function.

Alternatively, the information storage system calculates 3 different values from the key with a specified computing method (a combination of different values, for example), and substitutes the values into identical hash functions to obtain 3 different hash values.

Thus, types of hash functions needed to determine the information storage nodes for storing data can be reduced by calculating different values from a key associated with each of data categories (original data, a first replica, a second replica). Different hash functions may also be applied to some categories in a method for calculating different substituted values. In addition, the information storage nodes for storing data may be determined by using functions different from the hash functions.

On the circle (line showing logical positions of the information storage nodes) in <figref idref="DRAWINGS">FIG. 1</figref>, numbers from a minimum hash value to a maximum a hash value have been assigned in advance in the clockwise direction. A hash value means a value obtained by substituting a value into a hash function. Each of the node <b>1</b> (<b>101</b>) to the node <b>7</b> (<b>107</b>) arranged on the circle has a responsible range of hash values.

For example, the node <b>2</b> (<b>102</b>) is responsible for a range of hash values from the node <b>1</b> (<b>101</b>) to the node <b>2</b> (<b>102</b>) on the circle. A responsible node for storing data is determined, for example, by reference to a table in which responsible ranges and responsible nodes are associated with hash values of data. A logical position of each information storage node may differ by category of data.

Even if original data is identical for any 2 data, the first replica storage nodes may not always be identical, and rather differs in many cases. Similarly, the second replica storage nodes often differ.

For example, the first replica storage node for the data “Tokyo” <b>110</b> is the node <b>4</b> (<b>104</b>), and the second replica storage node therefor is the node <b>7</b> (<b>107</b>). However, other data for which an original storage node is the node <b>2</b> (<b>102</b>) may be assigned to a node which is different from the information storage node <b>4</b> (<b>104</b>), as the first replica storage node, and to a node which is different from the information storage node <b>7</b> (<b>107</b>), as the second replica storage node. For example, for data “Paris”, although an original node therefor is the node <b>2</b>, the first replica storage nodes are the nodes <b>5</b>, <b>2</b>, <b>1</b>, and the second storage nodes are the nodes <b>5</b>, <b>4</b>, <b>3</b>.

Thus, a plurality of the first replicas of different original data of respective nodes are distributed to and stored in a plurality of other nodes. Similarly, a plurality of the second replicas of different original data are also distributed to and stored in a plurality of other nodes.

In the example of <figref idref="DRAWINGS">FIG. 1</figref>, a hash value of the data “Tokyo” <b>110</b> enters between the information storage node <b>1</b> (<b>101</b>) and the information storage node <b>2</b> (<b>102</b>). Therefore, the node <b>2</b> (<b>102</b>) is an original storage node (node storing the original data) of the data <b>110</b>. The responsible hash value range of the node N (N is a natural number which is below a total number of nodes), which is other than the information storage node <b>1</b>, is between a value obtained by adding 1 to an end value of the node N−1's responsible hash value range and an end value of the node N's responsible hash value range.

The information storage node <b>1</b>'s responsible range is a combination of both ranges from a minimum hash value to an end value of the information storage node <b>1</b>'s responsible hash value and from a value obtained by adding 1 to an end value of a last node's responsible hash value to a maximum hash value. In <figref idref="DRAWINGS">FIG. 1</figref>, data <b>121</b>A to data <b>121</b>F shown by circles respectively represent a set of data which each information storage node replicates to other information storage nodes (adjacent information storage nodes in <figref idref="DRAWINGS">FIG. 1</figref>), in response to removal of the node <b>2</b> (<b>102</b>) from the system due to a failure or any other reason. Data to be replicated <b>121</b>A to <b>121</b>F includes the original data, the first replica and the second replica.

According to specified regulations, respective information storage nodes replicate data related to the information storage node, use of which is interrupted, to other information storage nodes. The data to be replicated will be described below. In the example of <figref idref="DRAWINGS">FIG. 1</figref>, the first replica <b>112</b> in the node <b>4</b> (<b>104</b>) is included in the data <b>121</b>B to be replicated, while the second replica <b>113</b> in the node <b>7</b> (<b>107</b>) is not included in the data <b>121</b>E to be replicated.

In the example of <figref idref="DRAWINGS">FIG. 1</figref>, although all the information storage nodes as shown, excluding the node <b>2</b> (<b>102</b>), are illustrated to replicate the data to other information storage nodes, all information storage nodes in the system do not necessarily have data to be replicated.

Respective information storage nodes secure storage areas for temporarily replicating data accompanying removal of the information storage node. In <figref idref="DRAWINGS">FIG. 1</figref>, a storage area <b>124</b> secured in the node <b>5</b> (<b>105</b>) is given a symbol by way of example. Similarly, other information storage nodes secure storage areas for storing replicated data. A method for using the storage areas will be described below.

Thus, the information storage system stores a plurality of data which are identical to the user data. In the above example, it stores 3 identical data of the original data, the first replica, and the second replica. The replication value depends on a system design.

Thus, the 3 identical data to be stored are given categories (original, a first replica, and the like) which are different from each other, and belong to different groups, basically, an original data group, a first replica group, and a second replica group.

As described above, given a plurality of data of any category (original data, for example) to be stored in one information storage node, a plurality of identical data of other category (first replica, for example) corresponding thereto are not concentrated in one other information storage node, but arranged so that they are distributed to and stored in a plurality of information storage nodes. By using different arithmetic expressions in determination of the information storage nodes for data in each data category, identical data of different categories are distributed to and stored in a plurality of other information storage nodes. The arithmetic expressions mentioned above include a hash function.

Next, with reference to <figref idref="DRAWINGS">FIG. 2</figref>, an overview of a configuration of the information storage system of the embodiment will be given. <figref idref="DRAWINGS">FIG. 2</figref> is a block diagram schematically showing a configuration example of the information storage system <b>209</b> and peripheral devices thereof in the embodiment. The information storage system <b>209</b> comprises information storage nodes (servers) <b>201</b>, <b>201</b>, <b>203</b>, an administration node (administration server) <b>204</b>, and a communication controller <b>205</b>. While <figref idref="DRAWINGS">FIG. 2</figref> shows 3 information storage nodes <b>201</b>, <b>202</b>, <b>203</b> by way of example, an actual system typically comprises more than <b>100</b> information storage nodes.

Each of the information storage nodes <b>201</b>, <b>202</b>, <b>203</b> is communicatably connected via the communication controller <b>205</b>, and the administration node <b>204</b> is further communicatably connected with the information storage nodes <b>201</b>, <b>202</b>, <b>203</b> via the communication controller <b>205</b>. The information storage system <b>209</b> is connected to an external network <b>206</b> by the communication controller <b>205</b>. Clients <b>207</b>, <b>208</b> are connected to the external network <b>206</b> and can communicate with the information storage nodes <b>201</b>, <b>202</b>, <b>203</b> and the administration node <b>204</b> via the communication controller <b>205</b>.

In this system, a user operates the clients <b>207</b>, <b>208</b> to write data into the information storage nodes <b>201</b>, <b>202</b>, <b>203</b> and then reads data from the information storage nodes <b>201</b>, <b>202</b>, <b>203</b>.

When writing data, the clients <b>207</b>, <b>208</b> transmit a “key” to the administration node <b>204</b> via the network <b>206</b> and the communication controller <b>205</b>, requesting it to show 3 nodes to which data (a pair of a key and a value) is to be written. In response to the request involving the key from the clients <b>207</b>, <b>208</b>, the administration node <b>204</b> determines the nodes to store data from a value of the received key according to specified calculations, and returns identifiers of the determined nodes to the clients <b>207</b>, <b>208</b>.

The clients <b>207</b>, <b>208</b> transmit the original data and the replica to the instructed nodes. Each node receives the data via the network <b>206</b> and the communication controller <b>205</b> and stores it.

Differently, the original node may allow the first and second replica nodes to store replicates (a first replica and a second replica) of the original data. In this configuration, in response to a request for a storage node from the clients <b>207</b>, <b>208</b>, the administration node <b>204</b> returns only an identifier of the original node to the clients <b>207</b>, <b>208</b>.

The clients <b>207</b>, <b>208</b> transmit the key value pair to the specified original node together with an instruction for writing data and write (store) the key value pair to the original node. Upon receipt of the instruction for writing data and the data, the original node stores the received data in its storage device, and determines nodes respectively storing the first and the second replicas by either inquiring to the administration node <b>204</b> or with an approach similar to that of the administration node <b>204</b>. The original node transmits the instruction for writing data and the data to the determined nodes via the communication controller <b>205</b>. Upon receipt, the nodes respectively store the data in the storage devices.

When reading data, the clients <b>207</b>, <b>208</b> communicate a “key” to the administration node <b>204</b>, requesting it to show nodes from which the data should be read. In response to the request involving the key from the clients <b>207</b>, <b>208</b>, the administration node <b>204</b> identifies from the key the nodes which store the data according to the specified computation. The administration node <b>204</b> returns to the clients <b>207</b>, <b>208</b>, identifiers of the nodes from which the data is read. The clients <b>207</b>, <b>208</b> transmit a read request together with the key to the nodes specified by the administration node <b>204</b> and receives the key value pair from the nodes.

As described above, using the clients <b>207</b>, <b>208</b>, the user performs writing and reading of data. <figref idref="DRAWINGS">FIG. 3</figref> is a block diagram schematically showing a configuration of the client <b>207</b>. The client <b>208</b> has a similar configuration to the client <b>207</b>. The client <b>207</b> is a computing machine, including an input device <b>271</b>, a processor <b>272</b>, a network interface <b>273</b>, a display <b>274</b>, a main storage device <b>275</b>, and secondary storage device <b>276</b>. They are communicatably connected by a bus <b>278</b>.

The client <b>207</b> is connected to the network <b>206</b> via the network interface <b>273</b> to communicate with other computing machines. The user inputs necessary information with the input device <b>271</b> (a mouse and a keyboard, for example) and can visually recognize necessary information with the display <b>274</b>.

The processor <b>272</b> implements a predetermined function of the client <b>207</b> by executing a program stored in the main storage device <b>275</b>. The main storage device <b>275</b> stores the program to be executed by the processor <b>272</b> and data necessary for execution of the program. The program includes a read-write client program <b>277</b>, in addition to an OS (Operating System) not shown. The processor <b>272</b> can include a plurality of chips and a plurality of packages.

For convenience of the description, although the read-write client program <b>277</b> is shown in the main storage device <b>275</b>, a program is typically loaded from a storage area of the secondary storage device <b>276</b> to a storage area of the main storage device <b>275</b>. The storage devices <b>275</b>, <b>276</b> can act as one storage device. The secondary storage device <b>276</b> is a storage device including a non-volatile persistent storage medium for storing a program and data needed to implement the predetermined function of the client <b>207</b>. The secondary storage device <b>276</b> may be an external storage device connected via a network.

Using the read-write client program <b>277</b>, the user communicates with the administration node <b>204</b> and the information storage nodes <b>201</b>, <b>202</b>, <b>203</b>. In response to the read-write client program <b>277</b>, input of the user with the input device <b>271</b>, or input from other program, the user transmits information necessary for writing and reading of data to the administration node <b>204</b> and the information storage nodes <b>201</b>, <b>202</b>, <b>203</b> and receives information therefrom. The display <b>274</b> displays data received from the information storage nodes <b>201</b>, <b>202</b>, <b>203</b>.

Next, with reference to <figref idref="DRAWINGS">FIG. 4</figref>, a configuration of the administration node <b>204</b> will be described. <figref idref="DRAWINGS">FIG. 4</figref> is a block diagram schematically showing a configuration of the administration node <b>204</b>. The administration node <b>204</b> is a computing machine which manages the information storage nodes <b>201</b>, <b>202</b>, <b>203</b> and processing thereof. The administration node <b>204</b> may consist of a plurality of computing machines (computer systems). The administration node <b>204</b> manages accesses (writing of data and reading of data) to the information storage nodes <b>201</b>, <b>202</b>, <b>203</b>, and manages processing involved in addition and deletion of a node operating in the system.

The administration node <b>204</b> includes a network interface <b>241</b>, a processor <b>242</b>, a main storage device <b>243</b>, and a secondary storage device <b>244</b>. They are communicatably connected by a bus <b>249</b>. The processor <b>242</b> implements a predetermined function of the administration node <b>204</b> by executing a program stored in the main storage device <b>243</b>. The processor <b>242</b> can include a plurality of chips and a plurality of packages.

The main storage device <b>243</b> stores a program to be executed by the processor <b>242</b> and data necessary for execution of the program. A program includes a node management program <b>245</b>, a read-write management program <b>246</b>, and a data relocation management program <b>247</b>, in addition to the OS not shown.

The node management program <b>245</b> performs processing of managing information storage nodes, and manages responsible ranges of the information storage nodes included in the system, status thereof, and the like. The read-write management program <b>246</b> performs processing of managing writing of data to the information storage nodes and reading of data (access to the nodes). The data relocation management program <b>247</b> manages relocation of data among nodes, involved in addition/deletion of a node. The processing to be performed by these programs <b>245</b> to <b>247</b> will be described below in detail. For convenience of the description, in <figref idref="DRAWINGS">FIG. 4</figref>, the programs <b>245</b> to <b>247</b> are shown to be in the main storage device <b>243</b>. Typically, a program is loaded from a storage area of the secondary storage device <b>244</b> to a storage area of the main storage device <b>243</b>. The storage devices <b>243</b>, <b>244</b> can act as one storage device.

The secondary storage device <b>244</b> is a storage device including a non-volatile persistent storage medium for storing a program and data needed to implement the predetermined function of the administration node <b>204</b>, in addition to a node management table <b>248</b> as shown. The node management table <b>248</b> will be described below with reference to <figref idref="DRAWINGS">FIG. 6</figref>. Alternatively, the secondary storage device <b>244</b> may be an external storage device connected via a network. The administration node <b>204</b> may execute the read-write client program <b>277</b> to accept user operations via an input/output device.

Next, with reference to <figref idref="DRAWINGS">FIG. 5</figref>, a configuration of the information storage node <b>201</b> will be described. Other information storage nodes <b>202</b>, <b>203</b> also have an identical configuration to the information storage node <b>201</b>, and a description thereof will be omitted. <figref idref="DRAWINGS">FIG. 5</figref> is a block diagram schematically showing a configuration of the information storage node <b>201</b>. The information storage node (server) <b>201</b> is a computing machine which stores a key value pair. The information storage node may include a plurality of computing machines.

The information storage node <b>201</b> includes a network interface <b>211</b>, a processor <b>212</b>, a main storage device <b>213</b>, and a secondary storage device <b>214</b>. They are communicatably connected by a bus <b>215</b>. The processor <b>212</b> implements a predetermined function of the information storage node <b>201</b> by executing a program stored in a storage area of the main storage device <b>213</b>.

The main storage device <b>213</b> stores a program to be executed by the processor <b>212</b> and data necessary for execution of the program. The program includes a read-write processing program <b>216</b> and a data relocation processing program <b>217</b>, in addition to the OS not shown. The processor <b>212</b> can include a plurality of chips and a plurality of packages.

The read-write processing program <b>216</b> performs processing of writing and reading data as per a request from the clients <b>207</b>, <b>208</b>. The data relocation processing program <b>217</b> performs data relocation among nodes involved in deletion/addition of a node in the system. The processing to be performed by these programs <b>216</b>, <b>217</b> will be described below in detail.

For convenience of the description, in <figref idref="DRAWINGS">FIG. 5</figref>, the programs <b>216</b>, <b>217</b> are shown to be in the main storage device <b>213</b>. Typically, a program is loaded from a storage area of the secondary storage device <b>214</b> to a storage area of the main storage device <b>213</b>. The storage devices <b>213</b>, <b>214</b> can act as one storage device.

The secondary storage device <b>214</b> is a storage device including a non-volatile persistent storage medium for storing a program and data needed to implement the predetermined function of the information storage node <b>201</b>, in addition to a data storage table <b>218</b> as shown. The data storage table <b>218</b> will be described below with reference to <figref idref="DRAWINGS">FIG. 7</figref>. The secondary storage device <b>214</b> may be an external storage device connected via a network.

As described above, the programs are executed by the processor so as to perform defined processes by means of the memories and a communication port (communication device). Therefore, a description in this and other embodiments in which a subject is a program may be a description in which a subject is a processor. Alternatively, processing executed by a program is processing to be performed by a computing machine in which the program operates. By operating in accordance with the program, the processor operates as a function unit to implement the predetermined function.

At least a part of a program may be implemented by dedicated hardware. A program can be installed in each computing machine by a program distributing server or a persistent storage medium which can be read by the computing machine. It can be stored in a non-volatile memory of each computing machine.

<figref idref="DRAWINGS">FIG. 6</figref> is a view showing an example of the node management table <b>248</b> stored in the administration node <b>204</b>. The node management table <b>248</b> is a table for the node management program <b>245</b> (administration node <b>204</b>) to manage each information storage node, specifically, a responsible hash value range and life-and-death status of each information storage node. Each row (record) stores information on one node, and the node management table <b>248</b> of the example manages <b>1000</b> nodes. Shortly, the information storage system <b>209</b> includes <b>1000</b> nodes.

A column <b>601</b> for “Node Name” stores node names of respective nodes. Specifically, a row (entry) <b>604</b> is a description of a node whose “node name” is a “node <b>1</b>”. A row <b>605</b> is a description of a node whose “node name” is a “node <b>2</b>”. A row <b>606</b> is a description of a node whose “node name” is a “node <b>3</b>”. A row <b>607</b> is a description of a node whose “node name” is a “node <b>4</b>”. A row <b>608</b> is a description of a node whose “node name” is a “node <b>5</b>”.

A row <b>609</b> is a description of a node whose “node name” is a “node <b>6</b>”. A row <b>610</b> is a description of a node whose “node name” is a “node <b>7</b>”. A row <b>611</b> is a description of a node whose “node name” is a “node <b>8</b>”. A row <b>612</b> is a description of a node whose “node name” is a “node <b>9</b>”. A row <b>613</b> is a description of a node whose “node name” is a “node <b>10</b>”.

A row <b>614</b> is a description of a node whose “node name” is a “node <b>11</b>”. A row <b>615</b> is a description of a node whose “node name” is a “node <b>12</b>”. A row <b>616</b> indicates the mid-entries are omitted in <figref idref="DRAWINGS">FIG. 6</figref>. A row <b>617</b> is a description of a node whose “node name” is a “node <b>999</b>”. A row <b>618</b> is a description of a node whose “node name” is a “node <b>1000</b>”.

A column <b>602</b> for “End Value in Responsible Hash Value Range” stores a last value of a responsible hash value range of each node. Specifically, an “end value in a responsible hash value range” of the “node <b>1</b>” is “<b>226</b>”. An “end value in a responsible hash value range” of the “node <b>2</b>” is “<b>535</b>”. The fact that the “end value in the responsible hash value range” of the “node <b>1</b>” being “<b>226</b>” means that the “end value in the responsible hash value range” of the “node <b>2</b> is <b>227</b> (which is the value following the end value “<b>226</b>” of the node <b>1</b>) to <b>535</b>.

Similarly, an “end value in a responsible hash value range” of the node whose “node name” is “node <b>3</b>” is “<b>842</b>”. It means that the responsible hash value range of “node <b>3</b>” is <b>536</b> to <b>842</b>. Similarly, an “end value in a responsible hash value range” of the node whose “node name” is “node <b>4</b>” is “<b>1231</b>”. An “end value in a responsible hash value range” of the node “the node name whose “node name” is “node <b>5</b>” is “<b>2145</b>”. An “end value in a responsible hash value range” of the node whose “node name” is “node <b>6</b>” is “<b>2352</b>”.

An “end value in a responsible hash value range” of the node whose “node name” is “node <b>7</b>” is “<b>3125</b>”. An “end value in a responsible hash value range” of the node whose “node name” is “node <b>8</b>” is “<b>4231</b>”. An “end value in a responsible hash value range” of the node whose “node name” is “node <b>9</b>” is “<b>4845</b>”. An “end value in a responsible hash value range” of the node whose “node name” is “node <b>10</b>” is “<b>5252</b>”.

An “end value in a responsible hash value range” of the node whose “node name” is “node <b>11</b>” is “<b>6625</b>”. An “end value in a responsible hash value range” of the node whose “node name” is “node <b>12</b>” is “<b>6752</b>”. An “end value in a responsible hash value range” of the node whose “node name” is “node <b>999</b>” is “<b>64523</b>”. An “end value in a responsible hash value range” of the node whose “node name” is “node <b>1000</b>” is “<b>65123</b>”.

A column <b>603</b> for “life-and-death information” stores information indicating a life-and-death state of each node. Specifically, it indicates whether each node is alive (ALIVE state), dead (DEAD state) or substituted (SUBSTITUTED state). The ALIVE state indicates that the information storage node operates normally. The DEAD state indicates that the information storage node does not operate normally due to a failure or any other reason, does not accept any access, and its responsible data is not relocated in other information storage node (before being relocated).

A storage node in the SUBSTITUTED state means that after it is once in the DEAD state, its responsible data is now relocated in other information storage node in the ALIVE state. If an information storage node in the ALIVE state enters the DEAD state due to a failure or any other reason.

Then, if its responsible data is relocated in other information storage node, it changes to the SUBSTITUTED state. These states and state changes will be described below in detail.

In the node management table <b>248</b> of the example, the “life-and-death information” for the node whose “node name” is the “node <b>1</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>2</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>3</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>4</b>” is “ALIVE”.

The “life-and-death information” for the node whose “node name” is the “node <b>5</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>6</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>7</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>8</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>9</b>” is “DEAD”.

The “life-and-death information” for the node whose “node name” is the “node <b>10</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>11</b>” is “SUBSTITUTED”. The “life-and-death information” for the node whose “node name” is the “node <b>12</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>999</b>” is “ALIVE”. The “life-and-death information” for the node whose “node name” is the “node <b>1000</b>” is “ALIVE”.

<figref idref="DRAWINGS">FIG. 7</figref> is a view showing an example of the data storage table <b>218</b> that the information storage nodes have. The data storage table <b>218</b> not only stores a value of each key value pair stored by an information storage node, but also associates the storage node storing the key value pair, with the key value pair, and stores it.

<figref idref="DRAWINGS">FIG. 7</figref> illustrates the data storage table <b>218</b> retained by the information storage node <b>2</b> (<b>102</b>) in <figref idref="DRAWINGS">FIG. 1</figref>. A column <b>701</b> for “Key” is a column indicating a key of a corresponding item. A row (entry) <b>706</b> is a description of a pair for which the “key” is “Tokyo”. A row <b>707</b> is a description of a pair for which the “key” is “Paris”. A row <b>708</b> is a description of a pair for which the “key” is “London”.

A row <b>709</b> is a description of a pair for which the “key” is “Berlin”. A row <b>710</b> is a description of a pair for which the “key” is “Washington”. A row <b>711</b> is a description of a pair for which the “key” is “San Jose”. A row <b>712</b> is a description of a pair for which the “key” is “Shanghai”. A row <b>713</b> indicates that in-between entries are omitted. A row <b>714</b> is a description of a pair for which the “key” is “Hiroshima”. A row <b>715</b> is a description of a pair for which the “key” is “Nagasaki”.

A column <b>702</b> for “Original Node” describes the names of nodes storing original data. For example, the “original node” of the pair for which the “key” is “Tokyo” is the “node <b>2</b>”. The “original node” of the pair for which the “key” is “Paris” is the “node <b>2</b>”. The “original node” of the pair for which the “key” is “London” is the “node <b>2</b>”. The “original node” of the pair for which the “key” is “Berlin” is the “node <b>2</b>”.

The “original node” of the pair for which the “key” is “Washington” is the “node <b>62</b>”. The “original node” of the pair for which the “key” is “San Jose” is the “node <b>4</b>”. The “original node” of the pair for which the “key” is “Shanghai” is the “node <b>475</b>”. The “original node” of the pair for which the “key” is “Hiroshima” is the “node <b>754</b>”. The “original node” of the pair for which the “key” is “Nagasaki” is the “node <b>352</b>”.

A column <b>703</b> for “First Replica Storage Node” describes the names of nodes storing the first replicas. For example, the “first replica storage node” of the pair for which the “key” is “Tokyo” is the “node <b>4</b>”. The “first replica storage node” of the pair for which the “key” is “Paris” is the “node <b>521</b>”. The “first replica storage node” of the pair for which the “key” is “London” is the “node <b>36</b>”.

The “first replica storage node” of the pair for which the “key” is “Berlin” is the “node <b>965</b>”. The “first replica storage node” of the pair for which the “key” is “Washington” is the “node <b>2</b>”. The “first replica storage node” of the pair for which the “key” is “San Jose” is the “node <b>2</b>”. The “first replica storage node” of the pair for which the “key” is “Shanghai” is the “node <b>234</b>”. The “first replica storage node” of the pair for which the “key” is “Hiroshima” is the “node <b>854</b>”. The “first replica storage node” of the pair for which the “key” is “Nagasaki” is the “node <b>120</b>”.

A column <b>704</b> for “Second Replica Storage Node” describes the names of nodes storing the second replicas. For example, the “second replica storage node” of the pair for which the “key” is “Tokyo” is the “node <b>7</b>”. The “second replica storage node” of the pair for which the “key” is “Paris” is the “node <b>543</b>”. The “second replica storage node” of the pair for which the “key” is “London” is the “node <b>339</b>”.

The “second replica storage node” of the pair for which the “key” is “Berlin” is the “node <b>145</b>”. The “second replica storage node” of the pair for which the “key” is “Washington” is the “node <b>4</b>”. The “second replica storage node” of the pair for which the “key” is “San Jose” is the “node <b>305</b>”.

The “second replica storage node” of the pair for which the “key” is “Shanghai” is the “node <b>2</b>”. The “second replica storage node” of the pair for which the “key” is “Hiroshima” is the “node <b>2</b>”. The “second replica storage node” of the pair for which the “key” is “Nagasaki” is the “node <b>2</b>”.

A column <b>705</b> for “Value” stores the values for the keys. For example, the “value” of the pair for which the “key” is “Tokyo” is “sunny”. The “value” of the pair for which the “key” is “Paris” is “rainy”. The “value” of the pair for which the “key” is “London” is “cloudy”. The “value” of the pair for which the “key” is “Berlin” is “snowy”.

The “value” of the pair for which the “key” is “Washington” is “sunny”. The “value” of the pair for which the “key” is “San Jose” is “sunny”. The “value” of the pair for which the “key” is “Shanghai” is “clear”. The “value” of the pair for which the “key” is “Hiroshima” is “cloudy”. The “value” of the pair for which the “key” is “Nagasaki” is “rainy”.

<figref idref="DRAWINGS">FIG. 8</figref> illustrates the data storage table <b>218</b> retained by the information storage node <b>4</b> (<b>104</b>) in <figref idref="DRAWINGS">FIG. 1</figref>. A column <b>801</b> for “Key” stores keys of entries. A row (entry) <b>806</b> is a description of the pair for which the “key” is “San Jose”. A row <b>807</b> is a description of the pair for which the “key” is “Tokyo”. A row <b>808</b> is a description of a pair for which the “key” is “Ottawa”. A row <b>809</b> is a description of the pair for which the “key” is “Washington”. A row <b>810</b> indicates the following entries are omitted in <figref idref="DRAWINGS">FIG. 8</figref>.

A column <b>802</b> for “Original Node” describes the names of nodes storing original data. For example, the “original node” of the pair for which the “key” is “San Jose” is the “node <b>4</b>”. The “original node” of the pair for which the “key” is “Tokyo” is the “node <b>2</b>”. The “original node” of the pair for which the “key” is “London” is the “node <b>2</b>”. The “original node” of the pair for which the “key” is “Ottawa” is the “node <b>475</b>”. The “original node” of the pair for which the “key” is “Washington” is the “node <b>62</b>”.

A column <b>803</b> for “First Replica Storage Node” describes the names of nodes storing the first replicas. For example, the “first replica storage node” of the pair for which the “key” is “San Jose” is the “node <b>2</b>”. The “first replica storage node” of the pair for which the “key” is “Tokyo” is the “node <b>4</b>”. The “first replica storage node” of the pair for which the “key” is “Ottawa” is the “node <b>4</b>”. The “first replica storage node” of the pair for which the “key” is “Washington” is the “node <b>2</b>”.

A column <b>804</b> for “Second Replica Storage Node” describes the names of nodes storing the second replicas. For example, the “second replica storage node” of the pair for which the “key” is “San Jose” is the “node <b>305</b>”. The “second replica storage node” of the pair for which the “key” is “Tokyo” is the “node <b>7</b>”. The “second replica storage node” of the pair for which the “key” is “Ottawa” is the “node <b>256</b>”. The “second replica storage node” of the pair for which the “key” is “Washington” is the “node <b>4</b>”.

A column <b>805</b> for “Value” stores the values for the keys. For example, the “value” of the pair for which the “key” is “San Jose” is “sunny”. The “value” of the pair for which the “key” is “Tokyo” is “sunny”. The “value” of the pair for which the “key” is “Ottawa” is “clear”. The “value” of the pair for which the “key” is “Washington” is “sunny”.

As described above, the administration node <b>204</b> performs processing by using the node management table <b>248</b>, and the information storage nodes <b>201</b>, <b>202</b>, <b>203</b> performs processing by using the data storage table <b>218</b>. In this and other embodiments, information (information for node management or information and the like related to data being stored) to be used by the information storage system may be represented in any data structure, without depending on a data structure. For example, a data structure which is appropriately selected from a table, a list, a database, or a queue can store information. The information to be used by the information storage system is stored in a corresponding data storage area in a data memory.

In the following, processing to be performed by the information storage system <b>209</b> will be described with reference to the flow charts in <figref idref="DRAWINGS">FIG. 9</figref> to <figref idref="DRAWINGS">FIG. 17</figref>. <figref idref="DRAWINGS">FIG. 9</figref> and <figref idref="DRAWINGS">FIG. 10</figref> show examples of processing when a node N which was normally operating has died due to a failure or any other reason.

<figref idref="DRAWINGS">FIG. 11</figref> and <figref idref="DRAWINGS">FIG. 12</figref> show examples of processing of writing data into the information storage node of the information storage system <b>209</b>. <figref idref="DRAWINGS">FIG. 13</figref> to <figref idref="DRAWINGS">FIG. 15</figref> show examples of processing of reading data from the information storage node of the information storage system <b>209</b>. <figref idref="DRAWINGS">FIG. 16</figref> and <figref idref="DRAWINGS">FIG. 17</figref> show examples of processing of inserting a node X between a node N (N being a node number) and a node N+1.

(Interruption of Information Storage Node)

First, with reference to <figref idref="DRAWINGS">FIG. 9</figref>, processing to be performed by the information storage system <b>209</b> when the node N dies will be described. When an information storage node dies, respective numbers of replications for data (typically, including a plurality of original data, a plurality of first replicas, and a plurality of second replicas) stored by the information storage node decrease only by 1 from a defined value (3 in this example).

In order to return the decreased replication value to the defined value, the information storage system <b>209</b> performs relocation of the data stored in the dead information storage node by replicating data identical to the data stored in the dead information storage node (its responsible data) to other information storage node, and returns the decreased replication value to the defined value.

<figref idref="DRAWINGS">FIG. 9</figref> is a flow chart showing an example of processing of the information storage system <b>209</b> when the node N dies, focusing on processing of the administration node <b>4</b>. In step S<b>901</b>, the node management program <b>245</b> of the administration node <b>204</b> detects that the node N has died.

Since technologies of detecting that the node N has died are widely known and thus a detailed description thereof will be omitted. Typically, the node management program <b>245</b> transmits to each information storage node a reply request for life-and-death monitoring, and determines that the information storage node has died when it does not receive a normal reply to the request.

In step S<b>902</b>, the node management program <b>245</b> changes the value of the life-and-death information field in the node N entry from “ALIVE” to “DEAD” in the node management table <b>248</b>. The node management program <b>245</b> notifies the data relocation management program <b>247</b> of the administration node <b>204</b> that the node N has entered “DEAD” state.

In step S<b>903</b>, the data relocation management program <b>247</b> refers to the node management table <b>248</b> to identify information storage nodes whose life-and-death field is “ALIVE”, and transmits to those information storage nodes an instruction for extracting data related to the node N of data stored by them and to replicate the extracted data to the information storage nodes adjacent to them (adjacent information storage nodes in the ALIVE state) in the clockwise direction.

Although they are not shown, the administration node <b>204</b> has addresses of respective information storage nodes and transmits the above-mentioned instruction to the addresses of the identified information storage nodes. The administration node <b>204</b> may transmit information specifying ALIVE information storage nodes adjacent to data replication destinations to respective information storage nodes in the ALIVE state or only to information storage nodes whose adjacent information storage nodes are not in the ALIVE state. Alternatively, each information storage node may obtain and retain a replicate of the node management table <b>248</b> from the administration node <b>204</b> on a regular basis and/or at the time of updating.

In step S<b>904</b>, the data relocation management program <b>247</b> waits till replications of the all information storage nodes end. Each information storage node can refer to the data storage table <b>218</b> to identify data related to the dead node N. The processing of extracting related data by the information storage nodes will be described in detail with reference to the flow chart in <figref idref="DRAWINGS">FIG. 10</figref>.

When the replications of the all information storage nodes end, the numbers of replications of respective data stored in the node N return to the defined value of 3. When the replication ends, each information storage node notifies the administration node <b>204</b> accordingly. In step S<b>905</b>, when receiving the notification on the end of replications of all information storage nodes, the data relocation management program <b>247</b> changes the entry for the node N in the life-and-death field in the node management table <b>248</b> from “DEAD” to “SUBSTITUTED”.

Then, in step S<b>906</b>, the data relocation management program <b>247</b> instructs a node N+1 which is adjacent to the node N in the clockwise direction to collect data. Specifically, the data relocation management program <b>247</b> instructs the node N+1 to collect data (original data, a first replica and a second replica) for which the node N was responsible, from the information storage nodes whose life-and-death field in the node management table <b>248</b> is ALIVE. Specifically, the administration node <b>204</b> transmits to the node N+1 a data collection instruction involving identifiers of the information storage nodes in the ALIVE state.

In response to the instruction from the administration node <b>204</b>, the data relocation processing program <b>217</b> of the node N+1 starts to collect the node N′s responsible data. Specifically, the data relocation processing program <b>217</b> requests the information storage nodes in the ALIVE state which are shown by the instruction from the administration node <b>204</b> to transmit the replicated data (“related data” in step S<b>903</b>) to the node N+1.

Upon receipt of the request, the information storage nodes transmit the replicated data (data identical to the data which the node N stored (was responsible for)) to the requesting node N+1. Then, the data relocation processing program <b>217</b> changes the field of the “node N” to the “node N+1” in the data storage table <b>218</b>. In addition, the operation may take such a form that it is performed by an instruction from the data relocation management program <b>247</b> after execution of step S<b>907</b>.

In step S<b>907</b>, when the node N+1 which is adjacent to the node N in the clockwise direction collects all of the node N's responsible data (receives the notification from the data relocation processing program <b>217</b> of the node N+1), the data relocation management program <b>247</b> deletes the entry for the node N from the node management table <b>248</b>. The data relocation management program <b>247</b> may change the life-and-death field in the entry for the node N from “SUBSTITUTED” to “DELETED”. With the above processing, the processing that the information storage system <b>209</b> should perform when the node N dies can be fulfilled.

Next, processing of the information storage node to extract the “related data” from data owned by it will be described with reference to <figref idref="DRAWINGS">FIG. 10</figref>. The processing is performed in step S<b>904</b> in the flow chart of <figref idref="DRAWINGS">FIG. 9</figref>. Of data owned by the information storage node, the “related data” is the data a replicate of which the information storage node must transmit to the adjacent information storage node because other information storage node has died.

<figref idref="DRAWINGS">FIG. 10</figref> is a view showing a flow chart of an example of processing to extract the related data of data owned by the information storage node. In step <b>51001</b>, the data relocation processing program <b>217</b> of the information storage node extracts, from the data storage table <b>218</b>, an entry in which the “original node” is the dead node N and the “first replica storage node” is itself.

In step S<b>1002</b>, the data relocation processing program <b>217</b> extracts, from the data storage table <b>218</b>, an entry in which the “first replica storage node” is the dead node N and the “second replica storage node” is itself.

In step S<b>1003</b>, the data relocation processing program <b>217</b> extracts, from the data storage table <b>218</b>, an entry in which the “second replica storage node” is the dead node N and the “original node” is itself.

In step S<b>1004</b>, the data relocation processing program <b>217</b> assembles the entries extracted in the above-mentioned 3 steps from S<b>1001</b> to S<b>1003</b> and stores them as the “related data” in the main memory <b>213</b>. With the above processing, the information storage node can extract the “related data” of the data owned by it.

What has been described above is the flow of the data relocation processing involved in the deletion of the information storage node. In order to describe the processing in a more understandable manner, by way of example, processing when the information storage node <b>2</b> has died (i.e., processing till the information storage node <b>2</b> changes from the ALIVE state to the DEAD state and then to the SUBSTITUTED state) will be explained.

First, in step S<b>901</b>, the node management program <b>245</b> of the administration node <b>204</b> detects that the node <b>2</b> has died. In step S<b>902</b>, the node management program <b>245</b> changes the life-and-death field of the node <b>2</b> in the node management table <b>248</b> from “ALIVE” to “DEAD”.

In step S<b>903</b>, the node management program <b>245</b> instructs the information storage nodes whose life-and-death field in the node management table <b>248</b> is “ALIVE” to extract the “related data”, of the data stored by them and replicate it to the information storage node adjacent to them in the clockwise direction.

In the following, by way of example, processing of the node <b>4</b> will be described. The extraction was described in detail with reference to the flow chart of <figref idref="DRAWINGS">FIG. 10</figref>. The data storage table <b>218</b> which stores data of the node <b>4</b> was shown in <figref idref="DRAWINGS">FIG. 8</figref>. A specific description will be given. The processing to be described hereinafter with reference to <figref idref="DRAWINGS">FIG. 10</figref> is performed by the data relocation processing program <b>217</b> of the node <b>4</b>. In step S<b>1001</b> in the flow chart of <figref idref="DRAWINGS">FIG. 10</figref>, the node <b>4</b> extracts an entry in which the “original node” is the dead node <b>2</b> and the “first replica storage node” is itself (information storage node <b>4</b>) from the data storage table <b>218</b> of <figref idref="DRAWINGS">FIG. 8</figref>. For example, an entry <b>807</b> whose key is “Tokyo” is extracted. This is the data “Tokyo” <b>112</b> in <figref idref="DRAWINGS">FIG. 1</figref>.

In step S<b>1002</b>, the node <b>4</b> extracts an entry in which the “first replica storage node” is the dead node <b>2</b> and the “second replica storage node” is itself (information storage node <b>4</b>) from the data storage table <b>218</b>. For example, an entry <b>809</b> whose key is “Washington” is extracted.

In step S<b>1003</b>, the node <b>4</b> an entry in which the “second replica storage node” is the dead node <b>2</b> and the “original node” is itself (node <b>4</b>) extracts from the data storage table <b>218</b>. Such an entry does not exist in the entries clearly shown, except the omitted entry shown by the row <b>810</b>.

In step S<b>1004</b>, the node <b>4</b> assembles the entries extracted from the above-mentioned 3 steps from step S<b>1001</b> to step S<b>1103</b> and stores them as the “related data” in a storage area of the main memory. In fact, the node <b>4</b> extracts the data with the key “Tokyo” and the data with the key “Washington” as the “related data”. The data corresponds to the data set <b>121</b>B in <figref idref="DRAWINGS">FIG. 1</figref>.

In this example, the node <b>4</b> replicates the extracted data to the adjacent node in the clockwise direction. Basically, the node <b>4</b> replicates the data to the node <b>5</b>. This means that the data set <b>121</b>B in <figref idref="DRAWINGS">FIG. 1</figref> is replicated to the storage area <b>124</b>. The node <b>5</b> may reserve the storage area <b>124</b> in advance or actively reserve it when performing replication.

If the node <b>5</b> reserves the storage area <b>124</b> in advance, the node <b>5</b> may reserve it as an “area for data of the node <b>4</b> for which “the original node is the dead node <b>2</b>”” or an “area for some replicated data to be replicated from the node <b>4</b>”. Alternatively, the node <b>5</b> may reserve it as an “area to replicate some replicated data from an information storage node somewhere”.

In addition, as examples of data then to be replicated similarly, <figref idref="DRAWINGS">FIG. 1</figref> shows data to be replicated from the node <b>3</b> to the node <b>4</b>, data to be replicated from the node <b>5</b> to the node <b>6</b>, data to be replicated from the node <b>6</b> to the node <b>7</b>, and data to be replicated from the node <b>1</b> to the node <b>3</b>.

As described above, in this system, a data set being identical to a data set of an arbitrary category retained by one information storage node, and belonging to other category is distributed to and stored in a plurality of information storage nodes, rather than being concentrated in one other information storage node. In particular, use of a hash function whose bias is small enables data stored in one storage information node to be averagely allocated to all other information storage nodes.

Suppose that in the system, the node <b>2</b> has data of 3 TB. When the node <b>2</b> dies, an amount of data owned by any information storage node other than the node <b>2</b>, such as the node <b>4</b> in the above example, as “data related to the node <b>2</b>”, is 3 GB which is one-thousandth of 3 TB (1000 is the total number of nodes). In step S<b>903</b>, the information storage nodes replicate the data to the adjacent information storage nodes. If the network is 1 Gbps, transfer time in the replication is about 24 seconds.

In fact, time taken to return the replication value from 2 to 3 is about 1/333 compared with the conventional example. Furthermore, in the processing described above, since load is evenly generated in the entire system rather than being concentrated only in some information storage nodes, there is no fluctuation in a response to a request from a client due to a reason like the conventional example. In addition, the probability of failure occurrence in information storage nodes due to the replication can also be reduced.

In the processing described above, following the data replications by the plurality of information storage nodes, the node N+1 collects the node N's responsible data. Since the replication value has already been recovered, the node N+1 can perform the data collection, depending on status of the system.

Thus, the embodiment can reduce the time needed to recover the replication value than ever before when the number of nodes for storing data in the system decreases. In addition, the embodiment can control concentration of system load till the replication value is recovered. Additionally, the embodiment can level any fluctuation in the system response time till the system returns to its steady state.

As described with reference to <figref idref="DRAWINGS">FIG. 10</figref>, information storage nodes extract data related to a node use of which is interrupted, in accordance with regulations set in advance. The regulations associate each category of data with other category. The information storage nodes identify a category of each data stored in the node use of which is interrupted and replicate data of a category associated with that category to other information storage nodes.

In the above example, the category of the original data is associated with the category of the first replica, the category of the first replica is associated with the category of the second replica, and the category of the second replica is associated with the category of the original data. The association is one example, and other correspondence may be acceptable.

The above configuration detects that the node N has died, determines that the node N is an unusable node, and stops use of the information storage node. Unlike this, the administration node <b>204</b> may detect that the response time of the node N is longer or that CPU load of the node N is higher than a threshold. Alternatively, the administration node <b>204</b> may detect any condition which is different from other normal condition.

Although the above configuration detects that the node N has died and determines that the node N is an unusable node, it may determine that the node N is an unusable node from a state of any information storage node other than the node N. For example, if the node N belongs to a specific node group G, the information storage system may detect that the node group G enters a state which is different from the normal state, determine that the node N or one or more information storage nodes belonging to the node group G are unusable nodes, and perform replication. The information storage system may detect that the node N enters a state which is different from the normal state, determine that some or all of the information storage nodes in the node group G are unusable nodes, and perform replication.

In the above example, the node N died due to an unpredictable failure. Even if the node N is stopped as scheduled, the data replication as described above can be similarly applied. In this case, the node N may operate from step S<b>901</b> to step S<b>907</b>, following which use of the node N will be stopped.

In the above processing, respective information storage nodes replicate data related to the node N to the storage information nodes which are located in logically adjacent positions. Relative logical positions of the information storage nodes for which respective information storage nodes replicate data may be other positions. For example, they may be every other or every third information storage node, or an information storage node on the opposite side of the logical circle. Alternatively, information storage nodes at data replication destinations may be determined with some function f.

If it is possible to learn a replication destination node later, the information storage node may use a method for determining an information storage node for replication destination by using a random number or by considering load of each information storage node and replicating to a node with small load. In this case, a table may be provided so that a name of a node (or a node ID) which is a destination of replication can be learned from a name of a node (or a node ID) which is a source of replication.

With autonomous replication of data (extraction of replicated data and replication to other information storage nodes) involved in interruption of use an information storage node being performed by information storage nodes, prompt and efficient processing is enabled. Unlike this, the administration node <b>204</b> may instruct each information storage node on information storage nodes which are destinations of replications.

In the above configuration, the information storage nodes replicate data related to the node N to the information storage nodes located at specified relative positions. Information storage nodes at replication destinations may store data identical to the replicated data. In this case, the replication value of the identical data remains unchanged at 2 and does not revert to 3. Thus, a new replication destination node is determined with a method similar to a method to be described below with reference to <figref idref="DRAWINGS">FIG. 11</figref>. This secures the replication value of 3.

Since the possibility (frequency of occurrence) that replication destination nodes store identical data is small, the data may be replicated to specified information storage nodes, irrespective of whether or not there is the identical data. Unlike this, if information storage nodes at specified relative positions store the identical data, the information storage node may replicate the data to an information storage node which is different from it, for example, an information storage node adjacent to the information storage node storing the identical data. By referring to the data storage table <b>218</b>, the information storage node can identify the information storage node which stores the data identical to the data to be replicated.

In the above configuration, the node N+1 adjacent to the node N in the clockwise direction is newly responsible for the node N's responsible range. Unlike this, for example, a node X (which has been reserved as a spare) is added in place of the node N, and the node X may collect data for which the information storage node N was originally responsible, and then perform the processing for which the node N was originally responsible. This enables the information storage system to return to the state prior to the interruption of the use of the node N. A plurality of existing information storage nodes or a plurality of information storage nodes including a newly added information storage node may collect data.

In the above example, the node N+1 acquires data identical to the replicated data from the information storage node in which the data is replicated. The node N+1 may collect node N′s responsible data, from any information storage node. For example, from the information storage nodes at the replication destinations, the node N+1 can acquire data stored in their storage areas (for example, the storage area <b>124</b> of the node <b>5</b> in <figref idref="DRAWINGS">FIG. 1</figref>). In addition to this, the information storage system <b>209</b> may finish the processing without collecting responsible data of the interrupted node in one information storage node, after causing a plurality of information storage nodes to replicate the data related to the interrupted node (after recovering the replication value).

(Writing of Data)

In the following, processing of writing data to the information storage system <b>209</b> will be described with reference to <figref idref="DRAWINGS">FIG. 11</figref> and <figref idref="DRAWINGS">FIG. 12</figref>. First, with reference to <figref idref="DRAWINGS">FIG. 11</figref>, processing of the read-write management program <b>246</b> of the administration node <b>204</b> to determine an information storage node in which data is stored (written) from a key value will be described.

<figref idref="DRAWINGS">FIG. 11</figref> shows a flow chart of processing of the read-write management program <b>246</b> to determine a storage node from a key value. In step S<b>1101</b>, the read-write management program <b>246</b> calculates a hash value of a key from a defined hash function and a key received from a client.

Furthermore, the read-write management program <b>246</b> uses the hash value to search an original node in the node management table <b>248</b>. As a hash function to be used by the read-write management program <b>246</b>, any one of or a combination of a plurality (of functions) of MD5, SHA-1, SHA-256 and the like may be used. Any function other than them may also be used.

In step S<b>1102</b>, the read-write management program <b>246</b> calculates a hash value (computed value) by using an arithmetic expression which combines “1” to the key and substitutes the value into the hash function. The hash function to be used is identical to the function for determination of the original node. The read-write management program <b>246</b> uses the hash value to search a candidate for a first replica storage node in the node management table <b>248</b>. The computation of combining “1” to the key generates a character string “Tokyo 1” if the key is “Tokyo”, for example, and a character string “New York 1” if the key is “New York”, for example.

In step S<b>1103</b>, the read-write management program <b>246</b> checks if the original node is equal to the candidate for the first replica storage node. If the original node and the candidate for the first replica storage node are equal (S<b>1103</b>: YES), the read-write management program <b>246</b> proceeds to step S<b>1104</b>. If the original node and the candidate for the first replica storage node are not equal (S<b>1103</b>: NO), the read-write management program <b>246</b> proceeds to step S<b>1105</b>.

In step S<b>1104</b>, the read-write management program <b>246</b> determines that the first replica storage node is a node adjacent to the candidate for the first replica storage node in the clockwise direction. In step S<b>1105</b>, the read-write management program <b>246</b> determines that the first replica storage node is the candidate node for the first replica storage node.

In step S<b>1106</b>, the read-write management program <b>246</b> combines “2” to the key to calculate its hash value. The hash function is same as the above-mentioned function. Using the hash value, the read-write management program <b>246</b> searches a candidate for a second replica storage node in the node management table <b>248</b>.

In step S<b>1107</b>, the read-write management program <b>246</b> checks if the original node or the first replica storage node is equal to the candidate for the second replica storage node. If the original node or the first replica storage node is equal to the candidate for the second replica storage node (S<b>1107</b>: YES), the read-write management program <b>246</b> proceeds to step S<b>1108</b>. If the candidate for the second replica storage node is not equal to any of the original node and the first replica storage node (S<b>1107</b>: NO), the read-write management program <b>246</b> proceeds to step S<b>1109</b>.

In step S<b>1108</b>, the read-write management program <b>246</b> determines that a new candidate for the second replica storage node is a node adjacent to the last candidate for the second replica storage node in the clockwise direction. In step S<b>1109</b>, the read-write management program <b>246</b> determines that the second replica storage node is the candidate node for the second replica storage node.

With the processing described above, the storage node can be determined from the key value. In addition, in the above example, although the “key”, the “value obtained by combining 1 to the key”, and the “value obtained by combining 2 to the key” were used to search the “original node”, the “first replica storage node”, and the “second replica storage node”, other character string may be combined or a key character string may be changed according to a certain law. For example, the read-write management program <b>246</b> can shift the character strings, specifically, change “Tokyo” to “OKYOT” or “KYOTO”.

Alternatively, rather than changing the key, the read-write management program <b>246</b> may use a different hash value to determine a different candidate node. For example, it can calculate MD5 (“New York”) to search the original node, calculate SHA-1 (“New York”) to search the first replica storage node, and calculate SHA-256 (“New York”) to search the second replica storage node. Or, the read-write management program <b>246</b> may take a form of a combination of them.

In the configuration example, the system determines a plurality of information storage nodes for storing identical data, by repeatedly substituting a value into the same hash function for different numbers of times. For example, the configuration is such that “SHA1 (KEY)” is used to determine the original node, “SHA1 (SHA1 (KEY))” is used to determine the first replica node, and “SHA1 (SHA 1 (SHA 1 (KEY)))” is used to determine the second replica node. This enables even a system with a large replication value to easily and appropriately determine a plurality of information storage nodes for storing data. In addition, this also makes it possible to easily cope with an increase in the replication value of the system.

Next, processing of the client <b>207</b> in writing of data will be described with reference to <figref idref="DRAWINGS">FIG. 12</figref>. Processing of other clients is also similar. <figref idref="DRAWINGS">FIG. 12</figref> shows a flow chart for the client <b>207</b> to write a value (and a key) by using the key. The flow chart includes steps of the administration node <b>204</b> and the client <b>207</b>.

In step S<b>1201</b>, the read-write client program <b>277</b> transmits a “key” to the administration node <b>204</b>, requesting it to show 3 information storage nodes in which data should be stored. In step S<b>1202</b>, the administration node <b>204</b> determines from the “key” that the 3 information storage nodes in which data should be stored are an “original node”, a “first replica storage node” and a “second replica storage node”.

In step S<b>1203</b>, using the node management table <b>248</b>, the administration node <b>204</b> checks if the “original node”, the “first replica storage node”, and the “second replica storage node” are all “ALIVE”.

If the administration node <b>204</b> can confirm from the node management table <b>248</b> that the “original node”, the “first replica storage node”, and the “second replica storage node” are all “ALIVE” (S<b>1203</b>: YES), the processing proceeds to step S<b>1204</b>. If the administration node <b>204</b> cannot confirm from the node management table <b>248</b> that any one of the “original node”, the “first replica storage node”, or the “second replica storage node” is “ALIVE” (S<b>1203</b>: NO), the processing proceeds to step S<b>1209</b>.

In step S<b>1204</b>, the administration node <b>204</b> replies to the client <b>207</b> that the nodes to which data should be written are the 3 nodes: “original node”, the “first replica storage node”, and the “second replica storage node”.

In step S<b>1205</b>, the read-write client program <b>277</b> of the client <b>207</b> instructs the 3 nodes shown as the nodes to which the data should be written to write a “key”, a “value”, an “original node name”, a “first replica storage node name”, and a “second replica storage node name”.

In step S<b>1206</b>, the read-write client program <b>277</b> checks if the administration node <b>204</b> has received a reply from the 3 information storage nodes that it could normally perform the writing. If it receives a reply from the 3 information storage nodes that it could normally perform the writing (S<b>1206</b>: YES), the processing proceeds to step S<b>1207</b>. If it cannot receive a reply from any one of the 3 information storage nodes that it could normally perform the writing (S<b>1206</b>: NO), the processing proceeds to step S<b>1208</b>.

In step S<b>1207</b>, the read-write client program <b>277</b> determines that the writing is successful. In step S<b>1208</b>, the read-write client program <b>277</b> determines that the writing has failed. In step S<b>1209</b>, the read-write client program <b>277</b> determines that the writing has failed. A description of processing of coping with a judgment on failure of writing is omitted since it is not highly relevant to the present invention. What has been described above is the flow of the processing. In order to describe the processing in a more understandable manner, by way of example, processing of the client <b>207</b> to store the data “Tokyo” <b>110</b> will be explained. First, in step S<b>1201</b>, the client <b>207</b> transmits the “key” to the administration node <b>204</b>, requesting it to show 3 information storage nodes to which data should be stored.

Then, in step S<b>1202</b>, the administration node <b>204</b> searches from “Tokyo”, which is the key“, nodes in which the data should be stored. This is the processing illustrated in <figref idref="DRAWINGS">FIG. 11</figref>. The administration node <b>204</b> determines the “original node” by substituting the key “Tokyo” into the hash function, determines the “first replica storage node” by substituting the key “Tokyo 1” into the hash function, and determines the “second replica storage node” by substituting the key “Tokyo 2” into the hash function. (Processing when the hash values collide is as described in <figref idref="DRAWINGS">FIG. 11</figref>.)

In this example, suppose that “300” is obtained as the hash value for “Tokyo”, “1000” as the hash value for “Tokyo 1”, and “3000” as the hash value for “Tokyo 2”. Then, in step S<b>1203</b>, using the node management table <b>248</b>, the administration node <b>204</b> checks if the original node, the first replica storage node, and the second replica storage node are all in the ALIVE state.

The node management table <b>248</b> of <figref idref="DRAWINGS">FIG. 6</figref> shows that the node <b>2</b> is responsible for the range from 227 to 535. The administration node <b>204</b> determines that the “original node” with the hash value being 300 is the information storage node <b>2</b>. The life-and-death information thereof is “ALIVE”. Similarly, the “first replica storage node” with the hash value being 1000 is the information storage node <b>4</b>. The life-and-death information thereof is “ALIVE”. Similarly, the life-and-death information of the “second replica storage node” with the hash value being 3000 is “ALIVE”. Since the 3 information storage nodes are “ALIVE”, the processing proceeds to step S<b>1204</b>.

Then, in step S<b>1204</b>, the administration node <b>204</b> replies to the client <b>207</b> that the original node, the first replica storage node, and the second replica storage node are the node <b>2</b>, the information storage node <b>4</b>, and the information storage node <b>7</b>, respectively.

Then, in step S<b>1205</b>, the client <b>1207</b> instructs the 3 information storage nodes (the information storage node <b>2</b>, the information storage node <b>4</b>, the information storage node <b>7</b>) shown as the information storage node into which data should be written to write “Tokyo” as the “key”, “fine” as the “value”, the “node <b>2</b>” as the “original node name”, the “node <b>4</b>” as the “first replica storage node name”, and the “node <b>7</b>” as the “second replica storage node name”.

Then, in step S<b>1206</b>, the administration node <b>204</b> receives from the 3 information storage nodes (the node <b>2</b>, the node <b>4</b>, the node <b>7</b>) a reply that it could normally perform the writing. When the administration node <b>204</b> receives from the 3 information storage nodes the reply that it could normally perform the writing, the processing proceeds to step S<b>1207</b>. Lastly, in step S<b>1207</b>, the client <b>207</b> determines that the writing is successful. With the above processing, the client <b>207</b> can write the data “Tokyo” <b>110</b> into the information storage system <b>209</b>.

If the information storage node which was selected with the method described above and into which data is written is in the DEAD state or the SUBSTITUTED state, the processing of writing fails. Unlike this, if the selected information storage node into which data is written is in the SUBSTITUTED state, the information storage node <b>209</b> may write data to a specific information storage node.

For example, the administration node <b>204</b> returns identifiers of 2 ALIVE information storage nodes to the client <b>207</b>. The client <b>207</b> writes data into the 2 information storage nodes. Like the processing described with reference to <figref idref="DRAWINGS">FIG. 9</figref> and <figref idref="DRAWINGS">FIG. 10</figref>, the information storage node which stores data of a category (for example, the second replica) pre-associated with a category (for example, the first replica) of the data which should be stored in the information storage node in the SUBSTITUTED state replicates the data in an information storage node to an adjacent logical position.

(Reading of Data)

In the following, processing of the clients <b>207</b>, <b>208</b> to read data from the information storage system <b>209</b> will be described with reference to <figref idref="DRAWINGS">FIG. 13</figref> to <figref idref="DRAWINGS">FIG. 15</figref>. In the following, an example of processing of the client <b>207</b> will be described. <figref idref="DRAWINGS">FIG. 13</figref> shows a flow chart of an example of processing whereby the client <b>207</b> reads information from the information storage system <b>209</b>. In step S<b>1301</b>, the read-write client program <b>207</b> of the client <b>207</b> conveys the “key” to the administration node <b>204</b>, requesting it to show nodes from which data should be read.

In step S<b>1302</b>, the administration node (the read-write management program <b>246</b>) searches nodes from which data should be read, from information storage nodes in the ALIVE state, through processing (to be described below) as shown in <figref idref="DRAWINGS">FIG. 14</figref>. In step S<b>1303</b>, the read-write management program <b>246</b> checks if the information storage node from which data should be read is found. If the information storage node from which data should be read is not found (S<b>1303</b>: NO), the processing proceeds to step S<b>1304</b>. If information storage node from which data should be read is found (S<b>1303</b>: YES), the processing proceeds to step S<b>1305</b>.

In step S<b>1304</b>, the read-write management program <b>246</b> searches a node from which data should be read, from information storage nodes at backup destinations of information storage nodes in the SUBSTITUTED state, through processing as shown in <figref idref="DRAWINGS">FIG. 15</figref> (to be described below). In step S<b>1305</b>, the administration node <b>204</b> checks if a nodes from which data should be read have been found. If the node from which data should be read has not been found (S<b>1305</b>: NO), the processing proceeds to the step S<b>1306</b>. If the node from which data should be read has been found (S<b>1305</b>: YES), the processing proceeds to step S<b>1308</b>.

In step S<b>1306</b>, the read-write management program <b>246</b> replies to the client <b>207</b> that the information storage node from which data should be read is not found. In step S<b>1307</b>, the read-write client program <b>207</b> of the client <b>270</b> determines that the processing of reading has failed.

In step S<b>1308</b>, the read-write management program <b>246</b> replies to the client <b>207</b> about the information storage nodes from which data should be read. In step S<b>1309</b>, the read-write client program <b>277</b> of the client <b>207</b> uses the key to read the value from the node from which data should be read. With the above processing, the client <b>207</b> can read information from the information storage system <b>209</b>.

Then, processing of using a key to find an information storage node from which data should be read, from nodes in ALIVE state will be described hereinafter with reference to <figref idref="DRAWINGS">FIG. 14</figref>. <figref idref="DRAWINGS">FIG. 14</figref> shows a flow chart of processing in which the administration node <b>204</b> uses a key to find a node from which data should be read, from nodes in ALIVE state.

In step S<b>1401</b>, the read-write management program <b>246</b> of the administration node <b>204</b> determines an original node, a first replica storage node, and a second replica storage node from the key. Details of the processing are as per the description with reference to <figref idref="DRAWINGS">FIG. 11</figref>.

In step S<b>1402</b>, the read-write management program <b>246</b> checks whether the original node is “ALIVE” or not. If the original node is not “ALIVE” (S<b>1402</b>: NO), the processing proceeds to step S<b>1403</b>. If the original node is “ALIVE” (S<b>1402</b>: YES), the processing proceeds to the step S<b>1408</b>.

In step S<b>1403</b>, the read-write management program <b>246</b> checks whether the first replica storage node is “ALIVE” or not. If the first replica storage node is not “ALIVE” (S<b>1403</b>: NO), the processing proceeds to step S<b>1404</b>. If the first replica storage node is “ALIVE” (S<b>1403</b>: YES), the processing proceeds to step S<b>1407</b>.

In step S<b>1404</b>, the read-write management program <b>246</b> checks whether the second replica storage node is “ALIVE” or not. If the second replica storage node is not “ALIVE” (S<b>1404</b>: NO), the processing proceeds to step S<b>1405</b>. If the second replica storage node is “ALIVE” (S<b>1404</b>: YES), the processing proceeds to step S<b>1406</b>.

In step S<b>1405</b>, the read-write management program <b>246</b> determines that information storage node from which data should be read is not found. In step S<b>1406</b>, the read-write management program <b>246</b> determines that the second replica storage node is the information storage node from which data should be read.

In step S<b>1407</b>, the read-write management program <b>246</b> determines that the first replica storage node is the information storage node from which data should be read. In step S<b>1408</b>, the read-write management program <b>246</b> determines that the original node is the information storage node from which data should be read.

In step S<b>1409</b>, the read-write management program <b>246</b> returns a node name of the information storage node from which data should be read, as a return value (If it is not found, the read-write management program <b>246</b> returns a reply that “the information storage node is not found”.) With the above processing, the read-write management program <b>246</b> can find a node from which data should be read, from nodes in the ALIVE state, by using a key.

Next, processing in which the administration node <b>204</b> finds a node from which data should be read from information storage nodes in the SUBSTITUTED state by using a key will be described with reference to <figref idref="DRAWINGS">FIG. 15</figref>. <figref idref="DRAWINGS">FIG. 15</figref> is a flow chart showing an example of processing of using a key to find an information storage node from which data should be read from information storage nodes which are backup destinations of information storage nodes in the SUBSTITUTED state.

In step S<b>1501</b>, from a key, the read-write management program <b>246</b> determines an original node, a first replica storage node, and a second replica storage node. Details of the processing are as shown in <figref idref="DRAWINGS">FIG. 11</figref>.

In step S<b>1502</b>, the read-write management program <b>246</b> checks whether the original node is “SUBSTITUTED” or not. If the original node is not “SUBSTITUTED” (S<b>1502</b>: NO), the processing proceeds to step S<b>1503</b>. If the original node is “SUBSTITUTED” (S<b>1502</b>: YES), the processing proceeds to step S<b>1508</b>.

In step S<b>1503</b>, the read-write management program <b>246</b> checks whether or not the first replica storage node is “SUBSTITUTED”. If the first replica storage node is not “SUBSTITUTED” (S<b>1503</b>: NO), the processing proceeds to step S<b>1504</b>. If the first replica storage node is “SUBSTITUTED” (S<b>1503</b>: YES), the processing proceeds to step S<b>1507</b>.

In step S<b>1504</b>, the read-write management program <b>246</b> checks whether the second replica storage node is “SUBSTITUTED” or not. If the second replica storage node is not “SUBSTITUTED” (S<b>1504</b>: NO), the processing proceeds to step S<b>1505</b>. If the first replica storage node is “SUBSTITUTED” (S<b>1504</b>: YES), the processing proceeds to step S<b>1506</b>.

In step S<b>1505</b>, the read-write management program <b>246</b> determines that an information storage node from which data should be read is not found. In step S<b>1506</b>, the read-write management program <b>246</b> determines that a node adjacent to the original node is the information storage node from which data should be read.

In step S<b>1507</b>, the read-write management program <b>246</b> determines that a node adjacent to the second replica storage node is the information storage node from which data should be read. In step S<b>1508</b>, the read-write management program <b>246</b> determines that a node adjacent to the first replica storage node is the information storage node from which data should be read.

In step S<b>1509</b>, the read-write management program <b>246</b> returns a node name of the information storage node from which data should be read, as a return value. (If it is not found, the read-write management program <b>246</b> replies that “the information storage node is not found”.) With the above processing, the read-write management program <b>246</b> can find the node from which data should be read, from the nodes in the SUBSTITUTED state, by using the key.

What has been described is the flow of the processing. In order to describe the processing in a more understandable manner, by way of example, processing of the client <b>207</b> to read the data “Tokyo” <b>110</b> will be explained. First, in step S<b>1301</b>, the client <b>207</b> transmits “Tokyo”, which is the “key”, to the administration node <b>204</b>, requesting it to show an information storage node from which data should be read.

Then, in step S<b>1302</b>, through the processing as shown in <figref idref="DRAWINGS">FIG. 14</figref>, the administration node <b>204</b> searches the information storage node, from which data should be read, from information storage nodes in the ALIVE state. In step S<b>1401</b>, the administration node <b>204</b> calculates hash values from “Tokyo”, “Tokyo 1”, and “Tokyo <b>2</b>”, and obtains the “node <b>2</b>”, the “node <b>4</b>”, and the “node <b>7</b>” from the node management table <b>248</b>.

In step S<b>1402</b>, the administration node <b>204</b> searches a life-and-death state of the node <b>2</b> in the node management table <b>248</b>. Since the node <b>2</b> is in the “ALIVE” state, the administration node determines in step S<b>1408</b> that the information storage node from which data should be read is the information storage node <b>2</b>.

In step S<b>1303</b>, the administration node <b>204</b> checks if the information storage node from which data should be read is found. Since it is found, the processing proceeds to step S<b>1305</b>. In step S<b>1305</b>, the administration node <b>204</b> checks if the information storage node from which data should be read is found. Since it is found, the processing proceeds to step S<b>1308</b>.

In step S<b>1308</b>, the administration node <b>204</b> replies to the client <b>207</b> that the information storage node from which data should be read is the information storage node <b>2</b>. Then, in step S<b>1309</b>, the client <b>207</b> uses the key “Tokyo” to read a value from the information storage node <b>2</b> from which data should be read. With the above processing, the client <b>207</b> can read information from the information storage system <b>209</b>.

(Addition of Information Storage Node)

Next, processing of inserting a node X between the node N and the node N+1 will be described with reference to <figref idref="DRAWINGS">FIG. 16</figref> and <figref idref="DRAWINGS">FIG. 17</figref>. <figref idref="DRAWINGS">FIG. 16</figref> is a flow chart showing an example of processing of inserting a node X between the node N and the node N+1.

In step S<b>1601</b>, the node management program <b>245</b> of the administration node <b>204</b> determines an “end value of a responsible hash value range” of the node X. This is a value between an end value of a responsible hash value range of the node N and an end value of a responsible hash value range of the node N+1.

In step S<b>1602</b>, the node management program <b>245</b> instructs the information storage nodes whose life-and-death state field in the node management table <b>248</b> is “ALIVE” to extract data to which the node X is related of data owned by them and replicate (transmit) it to the node X. The responsible hash value range of the node X is added to the instruction.

In step S<b>1603</b>, respective information storage nodes which receive the instruction extract data to which the node X is related from the data owned by them, and replicate it to the node X. The processing will be described with reference to the flow chart in <figref idref="DRAWINGS">FIG. 17</figref>.

In step S<b>1701</b>, the data relocation processing program <b>217</b> of each information storage node extracts, from the data storage table <b>218</b>, an entry in which the original node is the node N+1 and the first replica storage node is itself. In addition, the data relocation processing program <b>217</b> calculates a hash value for a key extracted by each information storage node and extracts data in the responsible hash value range of the node X. In this example, the data relocation processing program <b>217</b> knows a computation method for determining the original node, the first replica storage node, and the second replica storage node (specified in the program).

In step S<b>1702</b>, the data relocation processing program <b>217</b> of each information storage node extracts, from the data storage table <b>218</b>, an entry in which the first replica storage node is the node N+1 and the second replica storage node is itself. In addition, the data relocation processing program <b>217</b> calculates a hash value for a key of data extracted by each information storage node and extracts data in the responsible hash value range of the node X.

In step S<b>1703</b>, the data relocation storage program <b>217</b> extracts, from the data storage table <b>218</b>, an entry in which the second replica storage node is the node N+1 and the original node is itself. Furthermore, the data relocation processing program <b>217</b> calculates a hash value for a key of data extracted by each information storage node and extracts data in the responsible hash value range of the node X.

In step S<b>1704</b>, the data relocation processing program <b>217</b> assembles the entries extracted in the 3 steps described above, and stores them as “related data” in a storage area of the main storage device. The data relocation processing program <b>217</b> replicates the data extracted from step S<b>1701</b> to step S<b>1704</b> to the node X. The data relocation processing program <b>217</b> inserts the node X as well as updates the data storage table <b>218</b>.

With reference back to <figref idref="DRAWINGS">FIG. 16</figref>, in step S<b>1604</b>, the node management program <b>245</b> of the administration node <b>204</b> waits for termination of replications to the node X by all of the instructed information storage nodes. In step S<b>1605</b>, the node management program <b>245</b> adds an entry for the node X between the node N and the node N+1 in the node management table <b>248</b>, enters an end value of responsible hash value range, and enters “ALIVE” in the life-and-death field.

In step S<b>1606</b>, the node management program <b>245</b> instructs the node N+1 to delete data for which the node X is newly responsible. With the above processing, the processing of inserting the node X between the node N and the node N+1 can be fulfilled. In contrast to the processing of replicating data only from the node N+1 to the node X, the processing enables distribution of the replications among a plurality of information storage nodes, thus being able to reducing load per information storage node.

&lt;Second Embodiment&gt;

The embodiment describes processing to be performed when a failure further occurs in the course of the processing to recover the replication value in the first embodiment. <figref idref="DRAWINGS">FIG. 18</figref> is a flow chart showing an example of processing when a node M dies during execution of the step S<b>904</b> of the flow chart shown in <figref idref="DRAWINGS">FIG. 9</figref>.

In step S<b>1801</b>, the node management program <b>245</b> of the administration node <b>204</b> detects that the node M has died during execution of the step S<b>904</b>. In step S<b>1802</b>, the node management program <b>245</b> changes the life-and-death information field of the entry for the node M in the node management table <b>248</b> from “ALIVE” to “DEAD”.

In step S<b>1803</b>, the data relocation management program <b>247</b> of the administration node <b>204</b> instructs information storage nodes whose life-and-death information field is “ALIVE” in the node management field <b>248</b> to extract data related to both node N and node M of data owned by them, and replicate it to the information storage nodes adjacent to them. The data relocation management program <b>247</b> gives an instruction that this instruction takes precedence over the instruction for replicating of the step <b>903</b>.

The replication value of data for which the node N and the node M are both responsible (for example, data for which the node N is the original node and the node M is the first replica storage node) decreases from 2 to 1 when the node M dies. On the one hand, the replication value of data which is related to only one of the node N or the node M (only one of them is responsible for), specifically, data of the original data and either the first replica or the second replica stored by only one of them is 2.

Thus, since the replication value of the data for which the node N and the node M are both responsible is smaller than the replication value of other data, it is important to increase the replication value of the former data in preference to the latter data. Hence, as one method, the embodiment gives priority to extraction and replication of the data related to both node M and node N of the data owned by the information storage node, over the instruction for replicating in the step S<b>903</b>.

In the data storage table <b>218</b>, each information storage node searches an entry including both node N and node M and replicates the entry to the information storage node adjacent to it. The entry including both the node N and the node M satisfies the regulation of “related data” described for any of the node N or the node M, with reference to <figref idref="DRAWINGS">FIG. 10</figref>. In step S<b>1804</b>, the administration node <b>204</b> waits for termination of the replications of data related to both node M and node N by all the information storage nodes. With the steps described so far, the replication value of the data whose number of replication is 1 is increased to 2 only by 1.

In step S<b>1805</b>, the data relocation management program <b>247</b> instructs the information storage nodes whose life-and-death field in the node management table <b>248</b> is “ALIVE” to extract data related to the node M of data owned by them and replicate it to the information storage nodes adjacent to them. The instruction only applies to the data that has not been replicated, specifically, the data for which the node N is not responsible, of the data related to the node M.

Specification of data related to the node M follows the regulation shown in <figref idref="DRAWINGS">FIG. 10</figref>. Specifically, as described with reference to <figref idref="DRAWINGS">FIG. 10</figref>, the first replica, the second replica and the original data of the original data, the first replica and the second replica stored by the node M are the data related to the node M. In entries of these data, entries which do not include the node N are the entries that have not been replicated.

The data relocation management program <b>247</b> may be in such a form that it gives priority to either data only node M is related or data to only node N is related to. Shortly, the information storage node may be in such a form that it first replicates either the data only node M is related to or the data only node N is related to.

In the data storage table <b>218</b>, each information storage node replicates, to the adjacent information storage node, an entry which includes the node M but does not include the node N and which satisfies the regulation described with reference to <figref idref="DRAWINGS">FIG. 10</figref>. In step <b>1806</b>, the data relocation management program <b>247</b> waits termination of step S<b>1805</b> by all of the information storage nodes.

In step S<b>1807</b>, the data relocation management program <b>247</b> changes the life-and-death information in the entry for the node M in the node management table <b>248</b> from “DEAD” to “SUBSTITED”. With the steps described so far, the replication value of the data for which the node M is responsible and for which the node N is not responsible can be returned to the defined number of 3.

After step S<b>1806</b> and step S<b>1807</b> in the flow chart of <figref idref="DRAWINGS">FIG. 9</figref>, in step S<b>1808</b>, the data relocation management program <b>247</b> instructs the node M+1 which is adjacent to the node M to collect data for which the node M was originally responsible from information storage nodes whose life-and-death information field in the node management table <b>248</b> is “ALIVE”.

Specifically, the data relocation management program <b>247</b> transmits to the node M+1 the instruction for collecting data, together with information identifying the “ALIVE” information storage nodes. The instruction may precede or follow the instruction for collecting the node N's responsible data. The node M+1 requests the information storage nodes in the ALIVE state to transmit (replicate) the replicated node M's responsible data (the data replicated in response to death of the node M).

In step S<b>1809</b>, when the node M+1 adjacent to the node M collects all the data for which the node M was originally responsible, the data relocation management program <b>247</b> deletes the entry for the node M in the node management table <b>248</b>. The data relocation management table <b>247</b> may change the value in the life-and-death information field of the entry for the node M from “SUBSTITUTED” to “DELETED”.

Although the above processing replicates data identical to data stored in both node N and node M to only one information storage node, the data may be replicated to 2 different information storage nodes. This can return the replication value of the data stored in both node N and node M to 3.

What has been described so far is the flow of the processing. In order to describe the processing in a more understandable manner, by way of example, processing when the node <b>5</b> dies during execution of the step <b>904</b> for the dead node <b>2</b> will be explained hereinafter.

In step S<b>1801</b>, during execution of the step <b>904</b>, the administration node <b>4</b> detects that the information storage node <b>5</b> has died. Then, in step S<b>1802</b>, the administration node <b>204</b> changes the life-and-death field for the node <b>5</b> in the node management table <b>248</b> to “DEAD”.

Then, in step S<b>1803</b>, the administration node <b>204</b> instructs information storage nodes whose life-and-death information field in the node management table <b>248</b> is “ALIVE” to extract data related to both node <b>2</b> and node <b>5</b> and replicate it to the information storage nodes adjacent to them. The administration node <b>204</b> gives an instruction that this instruction takes precedence over the instruction of the step S<b>903</b>.

Upon receipt of the instruction, respective information storage nodes extract an entry in which 2 fields of the original node, the first replica storage node, and the second replica storage node store the node <b>2</b> and the node <b>5</b> from the data storage table <b>218</b>, and transmit the entry to adjacent information storage nodes. In step S<b>1804</b>, the administration node <b>204</b> waits for termination of the replications of the data for which both node <b>2</b> and node <b>5</b> are responsible, by all of the information storage nodes.

In step S<b>1805</b>, the administration node <b>204</b> instructs information storage nodes whose life-and-death information field in the node management table <b>248</b> is “ALIVE” to extract data related to the node <b>5</b> of data owned by them, and replicate it to the information storage nodes adjacent to them. The instruction only applies to data which has not been replicated, specifically, data for which the node <b>2</b> is not responsible, of data related to the node <b>5</b>.

In the data storage table <b>218</b>, respective information storage nodes extract an entry which is related to the node <b>5</b> from entries which do not include the node <b>2</b> and transmit the entry to adjacent information storage nodes. In step S<b>1806</b>, the administration node <b>204</b> waits for termination of the replications of the data related to the node M which has not been replicated, by all of the information storage nodes.

In step S<b>1807</b>, the administration node <b>204</b> changes the life-and-death field of the entry for the node <b>5</b> in the node management table <b>248</b> from “DEAD” to “SUBSTITUTED”.

After the step S<b>904</b> and the step S<b>905</b> (replication of the node <b>2</b>'s responsible data and updating of the node management table) in the flow chart of <figref idref="DRAWINGS">FIG. 9</figref>, in step S<b>1808</b>, the administration node <b>204</b> instructs a node <b>6</b> adjacent to the node <b>5</b> to collect data for which the node <b>5</b> was originally responsible, from the information storage nodes whose life-and-death information field in the node management table <b>248</b> is “ALIVE”. Specifically, the administration node <b>204</b> transmits to the node <b>6</b> an instruction for collecting data, together with information identifying the “ALIVE” information storage nodes.

In step S<b>1809</b>, when the node <b>6</b> adjacent to the node <b>5</b> collects all the data for which the node <b>5</b> was originally responsible, the administration node <b>204</b> deletes the entry for the node <b>5</b> in the node management table <b>248</b>.

Time taken from step S<b>1801</b> to step S<b>1804</b> will be calculated. Similar to the conventional examples of calculation, suppose that the number of information storage nodes is 1000, each information storage node is connected to a network of 1 Gbps, and each information storage node retains 1 TB (terabyte) of original data. (In fact, the data of 1 DB is present in each node's responsible range.)

“Data which should be replicated” instructed to each node in step S<b>1803</b> is one-thousands of data which is one-thousands of 3TB, i.e., about 3 MB. Time taken to replicate this is about 0.024 seconds. Compared with 2 hours and 13 minutes needed in the conventional examples, it is about one three-hundred-thousandths. In fact, in a very short period of time, it is possible to escape from the situation of “the replication value of 1” in which the risk of data loss is high.

While the embodiments of the present invention have been so far described, the present invention shall not be limited to the embodiments described above. Those skilled in the art can easily change, add, or transform each element of the embodiments within a scope of the present invention.

Although the present invention is preferable to the key value system, it can also be applied to any information storage system other than this. For example, it can apply to a system which manages data by a group consisting of 3 or more data items or a system which manages data by a single data item. Computations to determine an information storage node to which data is stored may be performed by using any function other than the hash function.

Each configuration, function, processing section, processing means, and the like as described above may be implemented by hardware through designing of some or all of them in an integrated circuit, for example. Information on a program, a table, a file, and the like which implement each function can be stored in a storage device such as a memory, a hard disk, an SSD (SolidStateDrive), or a persistent data storage medium such as an IC card, an SC card, a DVD, and the like.

It is possible to replace a part of a configuration of one embodiment with a configuration of another embodiment, as well as to add a configuration of other configuration to a configuration of one embodiment. For a part of a configuration of each embodiment, it is possible to add/delete/replace other configuration.