News Column

Patent Issued for Data Management Method and Node Apparatus

July 1, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- A patent by the inventor Kobashi, Hiromichi (Kawasaki, JP), filed on March 23, 2011, was published online on June 17, 2014, according to news reporting originating from Alexandria, Virginia, by VerticalNews correspondents.

Patent number 8756343 is assigned to Fujitsu Limited (Kawasaki, JP).

The following quote was obtained by the news editors from the background information supplied by the inventors: "In recent years, for example, in recent years, a key-value store method for managing data in key-and-value pairs has been known as a data storage method. FIG. 1 illustrates an example of a key-value store method. In the example in FIG. 1, records such as a record that includes key A and the value 'hello' of the key A, and a record that includes key B and the value 'world' of the key B are stored in a database. For example, when an inquiry (e.g. a get command 'get (key=A)') about key A is transmitted to the database, the value 'hello' of the key A is returned from the database.

"Furthermore, a distributed-type key-value store method is also known. FIG. 2 illustrates an example of a distributed processing system that uses a distributed-type key-value store method. In the example in FIG. 2, the distributed processing system includes node A to node D, and these nodes cooperate with each other to carry out a processing together. Also, in the example in FIG. 2, it is assumed that node A is in charge of the record for key A, node B is in charge of the record for key B and so on. For example, in the case of acquiring the value of the key A, an inquiry about the key A (i.e. a get command 'get (key=A)') is transmitted to one of the nodes. Here, it is assumed that an inquiry about the key A was transmitted to the node D. The node D receives the inquiry about the key A, searches for the node that is in charge of the key A, and transfers the inquiry to the node A, which is the node that is in charge of the key A. After receiving the inquiry about the key A, the node A reads out the value 'hello' of the key A, from the database that the node A manages, and sends a response to the node D. Then, the node D receives the value 'hello' of the key A from the node A and transmits that value to the user terminal. In this way, the user is able to obtain the desired value.

"On the other hand, a method (for example, the Lamport algorithm) of expressing the order relationship of the processing between nodes using a logical clock in a distributed processing system is known. For example, as illustrated in FIG. 3, the node on the sender side sets the logical clock value at the time of transmission in a message as a time stamp and then transmits the message. The node on the receiver side calculates the new logical clock value by adding a predetermined value ('1' in FIG. 3) to the time stamp that was set in the message. Therefore, in the logical clock, time continues to advance, and time does not go backward (in other words, the logical clock value continues to advance, and that logical clock value is not reduced). In FIG. 3, a numerical value on the starting side of an arrow represents the logical clock value at a sender-side node, and a numerical value at the ending side of the arrow represents the logical clock value at a receiver-side node. In addition, the numerical value that is attached onto the arrow represents the time stamp that was set by the sender-side node (in other words, the logical clock value at the transmission time).

"For example, in FIG. 3, when an event occurs at the node A and the logical clock value of the node A is 1, a message (a timestamp indicating 1) is transmitted from the node A to the node B. The logical clock value at the node B is 0 before reception of the message. After reception of the message, however, the node B determines that the logical clock value has increased to 1 since the timestamp included in the received message is 1 and thus uses, as a new logical clock value, a value (=2) obtained by adding 1 to the timestamp. Subsequently, when an event occurs at the node A and the logical clock value of the node A is 2, a message (a timestamp indicating 2) is transmitted from the node A to the node C. The logical clock value at the node C is 0 before reception of the message. After reception of the message, however, the node C determines that the logical clock value has increased to 2 since the timestamp included in the received message is 2 and thus uses, as a new logical clock value, a value (=3) obtained by adding 1 to the timestamp. Subsequently, when an event occurs at the node C and the logical clock value of the node C is 4, a message (a timestamp indicating 4) is transmitted from the node C to the node D. The logical clock value at the node D is 0 before reception of the message. After reception of the message, however, the node D determines that the logical clock value has increased to 4 since the timestamp included in the received message is 4 and thus uses, as a new logical clock value, a value (=5) obtained by adding 1 to the timestamp. When an event occurs at the node B and the logical clock value of the node B is 3, a message (a timestamp indicating 3) is transmitted from the node B to the node C. Although the timestamp included in the message received by the node C is 3, the logical clock value of the node C has increased to 4. Thus, the node C uses, as a new logical clock value, a value (=5) obtained by adding 1 to the logical clock value of the node C. Subsequently, when an event occurs at the node D and the logical clock value of the node D is 6, a message (a timestamp indicating 6) is transmitted from the node D to the node A. The logical clock value at the node A is 2 before reception of the message. After reception of the message, however, the node A determines that the logical clock value has increased to 6 since the timestamp included in the received message is 6 and thus uses, as a new logical clock value, a value (=7) obtained by adding 1 to the timestamp. Subsequently, when an event occurs at the node A and the logical clock value of the node A is 8, a message (a timestamp indicating 8) is transmitted from the node A to the node C. The logical clock value at the node C is 5 before reception of the message. After reception of the message, however, the node C determines that the logical clock value has increased to 8 since the timestamp included in the received message is 8 and thus uses, as a new logical clock value, a value (=9) obtained by adding 1 to the timestamp. When an event occurs at the node D and the logical clock value of the node D is 7, a message (a timestamp indicating 7) is transmitted from the node D to the node C. Although the timestamp included in the message received by the node C is 7, the logical clock value of the node C has increased to 9. Thus, the node C uses, as a new logical clock value, a value (=10) obtained by adding 1 to the logical clock value of the node C. As described above, each node performs the processing while changing the logical clock value.

"Furthermore, some systems in distributed processing systems are applied eventual consistency as the data consistency model. Eventual Consistency is a consistency model that does not guarantee immediate consistency among all the replicas in a certain data store but does guarantee that they will all eventually reach the same value.

"For example, FIG. 4 illustrates a distributed processing system in which eventual consistency has been applied. In the example in FIG. 4, it is assumed that the distributed processing system includes nodes A to G, and the node A is in charge of the record for key A. For example, in order to set a value for the key A, a user B operates the user terminal and inputs a set command 'set (key=A, value=Y)', after which the user terminal receives that input from the user B and sends the command to node F. Also, for example, in order to acquire the value of the key A, a user A operates the user terminal and inputs a get command 'get (key=A)', after which the user terminal receives the input from the user A and sends the get command to node C. Incidentally, for each command, at the instant that the command reaches a node, the node assigns a time stamp. In the example in FIG. 4, t=9 is assigned to the get command, and t=7 is assigned to the set command. In other words, in terms of the time stamp, the set command is older than the get command.

"After that, as illustrated in FIG. 5, the node C searches for the node in charge of the key A, and transfers the get command to the node A, which is the node in charge of the key A. Similarly, the node F searches for the node in charge of the key A, and transfers the set command to the node A, which is the node in charge of the key A. Here, as illustrated in FIG. 5, it is assumed that a delay due to some reasons occur in the set command, so the get command arrives at the node A before the set command. In this case, as illustrated in FIG. 6, 'X', which was originally set, is acquired as the value of the key A. After that, when the set command arrives at the node A, the value of the key A is updated from 'X' to 'Y'. However, when the user A tries to acquire the value of the key A again after a certain period of time has elapsed, it is then possible to acquire the updated value 'Y'. In this way, in a distributed processing system in which eventual consistency has been applied, as long as the newest value can finally be obtained, it is acceptable even if the newest value cannot be obtained a certain point in time.

"However, as described above, from the point of view of eventual consistency, it is considered to be acceptable as long as the consistency in data eventually is obtained. Therefore, there was no viewpoint as to what point in time data consistency was obtained (or in other words, when data was 'fixed'). Therefore, in distributed processing systems that have applied eventual consistency and a distributed-type key-value store method, it is impossible to identify how far data has been fixed at the present time in the overall system, and it is also impossible to know multiple data values (i.e. plural data values) at a certain period of time, while the logical clock value continues to advance.

"In other words, in a distributed processing system managing a data value corresponding to each of plural keys, it is impossible to grasp the plural data values at a certain time point."

In addition to the background information obtained for this patent, VerticalNews journalists also obtained the inventor's summary information for this patent: "A data management method according to one aspect of this technique is a data management method executed by a node apparatus managing a data value corresponding to each of a plurality of keys. Moreover, this data management method includes: upon receipt of a predetermined command relating to an assigned key that is a key of which the node apparatus is in charge among a plurality of keys, first registering, into a first storage unit, a history element including a first logical clock value at a first time when the predetermined command was received, and a data value at a second time represented by the first logical clock value or information concerning the predetermined command; upon receipt of a reference request to reference a data value at a third time represented by a specific logical clock value, second registering, into the first storage unit or a second storage unit different from the first storage unit, a first marker that includes, as the specific logical clock value, a second logical clock value at a fourth time when the reference request was received or a third logical lock value designated by the reference request, and further includes information concerning the reference request; and upon detecting that a fixed logical clock value in a system to which the node apparatus belongs becomes equal to or greater than the specific logical clock value included in the first marker stored in the first storage unit or the second storage unit, identifying a data value corresponding to the assigned key at the third time from the history elements including first logical clock values that are equal to or less than the specific logical clock value in the first storage unit.

"The object and advantages of the embodiment will be realized and attained by means of the elements and combinations particularly pointed out in the claims.

"It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the embodiment, as claimed."

URL and more information on this patent, see: Kobashi, Hiromichi. Data Management Method and Node Apparatus. U.S. Patent Number 8756343, filed March 23, 2011, and published online on June 17, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8756343.PN.&OS=PN/8756343RS=PN/8756343

Keywords for this news article include: Fujitsu Limited, Information Technology, Information and Data Management.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters