JP6180710B2 - Data storage method and apparatus - Google Patents

Description

  The present invention relates to an apparatus and method for storing data. The present invention discloses an apparatus and method for replicating data based on a multi-master model, and more particularly, an apparatus and method for distributing and storing data in one or more storage areas using an expandable distributed index. Is disclosed.

  In order to increase the data storage capacity, “vertical extension” and “horizontal extension” may be used. Vertical extension refers to the method of using equipment with better specifications to store data. Horizontal expansion is a method of attempting to expand the data storage capacity by adding a device for storing data. Vertical expansion cannot process data that exceeds the capacity that the device can handle. Therefore, in general, a plurality of companies that have to process a large amount of data, such as Internet companies, process a large amount of data using horizontal expansion.

  In general, a relational database management system (RDBMS) requires atomicity, consistency, isolation, and durability, that is, ACID characteristics. .

When the RDBMS maintains multiple replicas for the same data, the RDBMS may designate a master and one or more slaves among the multiple replicas for replication. The RDBMS may perform synchronized write operations for consistency. The general synchronized write operation process is as follows (1) to (6).
(1) Client requests write to master (2) Master performs write requested (3) Master requests write to slave (4) Slave performs requested write (5) Master writes from slave Receive response to request (6) Master notifies client of write result

  Consistency is extremely important in RDBMS. Therefore, the slave must have exactly the same information as the master.

  Of the steps (1) to (6) described above, when a failure occurs in the slave, the RDBMS considers that the write operation itself has failed due to the architecture of the RDBMS.

  With the development of the network, a large amount of data that can be accessed via the network is generated. A distributed processing system such as a cloud computer has been introduced to process such data, but conventional RDBMS has a limitation that it cannot support extensibility for such a distributed processing system. .

  Therefore, various attempts to abandon any one of the C (consistency) and availability characteristics of conventional RDBMS and introduce the characteristics of P (Partition Tolerance) have been made. It was conducted. Among such attempts, a representative one is No-SQL (Not only SQL).

  The No-SQL may be divided into a key-value database (Database), a document-oriented DB, a graph DB, a column-oriented DB, and the like.

  Of these, the document-oriented DB replication scheme is similar to the RDBMS replication scheme. For example, document-oriented DB replication is performed by being classified into a master and a slave. However, when writing to a slave, an RDBMS performs a synchronized writing process for consistency, while a document-oriented DB (eg, MongoDB) uses synchronized writing and asynchronous writing simultaneously. Can do.

  A relational database management system cannot be expanded horizontally due to its characteristics. Therefore, when the RDBMS is used for a large amount of data, the entire capacity of the RDBMS may be expanded by sharding (or data division). That is, one or more RDBMS devices that store different data using the same schema may be used.

  When using one or more RDBMS devices, an application server that knows which RDBMS device is present may be used, and the actual data position may be concealed by separate middleware.

  When using sharding (or data partitioning), the problem is that when an RDBMS device is added to process larger volumes of data, the data must be redistributed between one or more RDBMS devices. Occur. Such data redistribution may be performed during operation of the RDBMS device. However, since data redistribution takes time, there is a problem that immediacy is reduced. A distributed key / value DB may be used to store data in a distributed manner. The distributed key / value DB may store data in a distributed manner by using a consistent hashing method. A consistent hashing scheme has structural advantages in data expansion. In other words, a data storage system using a consistent hash method can increase the total amount of data that can be processed by adding a server. However, since such a hash method does not support the concept of large and small, it is vulnerable to range search and cannot process data of two or more dimensions.

  Data in the system using the distributed key / value DB is distributed by hashing. Therefore, the search results cannot be obtained sequentially for the range search, and each key in the search range must be queried.

  For example, when searching for data in which the value of the field A is between 1 and 10, the RDBMS may use a query such as “select * from foo where A> = 1 and A <= 10” for range search. On the other hand, the key / value DB has to inquire data from 1 to 10, respectively.

  Therefore, a key / value DB using a hash cannot have a spatial index for processing data of two or more dimensions. That is, when any data in a specific space must be processed, the data in the space is distributed and stored in various nodes (that is, servers) of the key / value DB. Neither node can have a complete index.

  An object of the present invention is to provide an apparatus and method in which one or more nodes process a data access request using a messaging channel.

  An object of the present invention is to provide an apparatus and method for transmitting a data access request to a selected node and multicasting the data access request to one or more nodes according to the request of the selected node.

  An object of the present invention is to provide an apparatus and method for storing data using one or more storage areas configured in a tree structure.

  An object of the present invention is to provide an apparatus and method for determining a storage area in which data is stored using a hierarchical key.

  According to an embodiment of the present invention, a selected node of one or more nodes receives a data access request, the selected node transmits a multicast request for the data access request to a messaging channel, and the messaging A channel receiving the multicast request and multicasting the data access request to the one or more nodes, each of the one or more nodes receiving the multicast and processing the data access request; One or more nodes are provided with a data management method characterized by including a copy of the data.

  The data management method includes: a messaging channel receiving the data access request from a client; the messaging channel determining the selected node of the one or more nodes; and the messaging channel receiving the data access request. Transmitting to the selected node.

  The data access request may be any one or more of data reading, writing, insertion, deletion, and update.

  According to another embodiment of the present invention, the method includes receiving a multicast request for a data access request and transmitting the data access request to one or more nodes, the one or more nodes receiving the data access request. A data management method is provided, which is a node including a copy of data requested by.

  The data management method includes receiving the data access request from a client, determining a selected node among the one or more nodes, and transmitting the data access request to the selected node. Further, it may be included.

  Determining the node may determine the selected node of the one or more nodes based on a round robin scheme or load balancing.

  According to another embodiment of the present invention, in a method for a terminal to process a data access request from a client, a data access request transmitted by the client is transmitted, a multicast request of the data access request is transmitted to a messaging channel, and A data management method is provided that includes receiving the data access request from a messaging channel via multicast and processing the data access request.

  Transmitting the data access request may include receiving the data access request from the messaging channel.

  According to one embodiment of the present invention, comprising: one or more nodes including a copy of the same data; and a messaging channel for transmitting a data access request to the one or more nodes; Any one node transmits a multicast request for the data access request to the messaging channel, the messaging channel receives the multicast request, multicasts the data access request to the one or more nodes, and Each of the one or more nodes is provided with a data management system in which the data access request is processed by the multicast.

  The messaging channel may receive a data access request from a client, select any one of the one or more nodes, and transmit the data access request to the selected node.

  The messaging channel may select the one of the one or more nodes based on a round robin scheme or load balancing.

  According to an embodiment of the present invention, a receiving unit that receives a data access request from a client, a control unit that determines a node to be selected from one or more nodes having a data storage area in a data storage device, and data A transmission unit that transmits an access request to the selected node, wherein the reception unit receives a multicast request for the data access request from the selected node, and the transmission unit receives the first request. A messaging channel is provided that multicasts to the one or more nodes.

  According to an embodiment of the present invention, one or more storage areas configured in a tree structure are included (each storage area corresponds to one node in the tree), and each of the one or more storage areas is zero. A hierarchical key having the above subkeys is assigned, and a storage area in a subtree rooted at an arbitrary first storage area among the one or more storage areas corresponds to the first key of the first storage area The first key is a key in which one or more subkeys are chained to a second key, the second key is a key of a second storage area, and the second storage area is A data storage device is provided that is a parent storage area of the first storage area.

  Each of the one or more storage areas may be a relational database device. Each of the one or more storage areas may include middleware that understands and processes relational database indexes, keys, and instructions.

  The hierarchical key may be a character string combining alphanumeric characters and ward molecules.

  The data corresponding to the first key may mean data in which any one of the data key prefixes is the same as the first key.

  The prefix may be the previous i subkeys of the n subkeys of the data key.

  i may be 1 or more and n or less.

  The first storage area may store data that does not correspond to the key of the child storage area of the first storage area among the data corresponding to the key of the first storage area.

  When adding a third storage area to the data storage device, the data corresponding to the third key of the third storage area is moved from the first storage area to the third storage area, and the third storage area is It may be a child storage area of the first storage area.

  When the storage amount of the first storage area reaches a predefined standard, the addition of the third storage area and the data movement may be performed.

  The first storage area requests a first list of data having a key corresponding to a search range to one or more child storage areas of the first storage area, and among the data stored in the first storage area, A second list of data corresponding to the search range may be merged with the first list returned in response to the request and returned as a result for the search range.

  According to an embodiment of the present invention, one or more storage areas are configured in a tree structure (each storage area corresponds to one node in the tree), and each of the one or more storage areas includes zero or more subkeys. And assigning the data corresponding to the first key of the first storage area in the storage area in the subtree rooted at an arbitrary first storage area among the one or more storage areas. The first key is a key in which one or more subkeys are chained to a second key, the second key is a key of a second storage area, and the second storage area is A data storage method is provided which is a parent storage area of the first storage area.

  The storing may include storing, in the first storage area, data that does not correspond to the key of the child storage area of the first storage area among the data corresponding to the key of the first storage area.

  In the data storage method, as a child storage area of the first storage area, the third storage area is added to the search range in one or more storage areas, and the data corresponding to the third key of the third storage area is the first storage area. It may further include moving from the storage area to the third storage area.

  The addition of the third storage area and the movement of the data may be performed when the storage amount of the first storage area reaches a predefined standard.

  The data storage method requests one or more child storage areas of the first storage area for a first list of data having a key corresponding to a search range, and the one or more child storage areas return the first list. In addition, it may further include merging the second list of data corresponding to the search range out of the data stored in the first storage area with the returned first list as a result for the search range.

  According to the present invention, it is possible to provide an apparatus and method for maintaining data consistency by simultaneously processing data requests by one or more nodes via multicast.

  According to the present invention, it is possible to provide a data management system in which insertion, deletion, or failure of a node can be easily handled by maintaining one or more nodes only in connection with a messaging channel.

  According to the present invention, it is possible to provide an apparatus and method for selecting a node that processes a data access request of a client from one or more nodes in consideration of load balancing.

  According to the present invention, an apparatus and method for storing data using one or more storage areas configured in a tree structure can be provided.

  According to the present invention, it is possible to provide an apparatus and method for determining a storage area in which data is stored using a hierarchical key.

  According to the present invention, it is possible to provide an apparatus and method for storing data to expand a storage area in a tree structure and move the data to the expanded storage area.

  According to the present invention, it is possible to provide an apparatus and a method for transmitting a query to a child storage area corresponding to a child node, and merging and returning a data list returned from the child storage area as a query search result.

It is a figure for demonstrating asynchronous writing in a master-slave structure. It is a figure for demonstrating the replication method of a multi master. It is a figure which shows the structure of the data management system which concerns on an example of this invention. 5 is a signal flowchart of a data management method according to an embodiment of the present invention. 5 is a signal flowchart of a data management method according to an example of the present invention. FIG. 3 is a block diagram of a messaging channel according to an embodiment of the present invention. It is a figure showing a data storage device concerning one embodiment of the present invention. It is a figure for demonstrating the process of adding a storage area to the data storage apparatus which concerns on an example of this invention. It is a figure for demonstrating the range search with respect to the data storage apparatus which concerns on an example of this invention. 3 is a flowchart of a data storage method according to an embodiment of the present invention. It is a flowchart of the expansion method in the data storage device which concerns on one Embodiment of this invention. It is a flowchart of a range search of the data storage device according to an example of the present invention.

  Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings. However, the present invention is not limited to the following embodiments, and is not limited. The same reference numerals shown in the drawings indicate the same members.

  Embodiments of the present invention described later provide a method for realizing a distributed processing system using a key / value DB by a multi-master method.

  When realizing a data management system, a plurality of nodes having the same data need to be configured for fault tolerance, load balancing, and the like. A node means one unit for processing any work. For example, the node may be one physical or logical server (or DB).

  In the present invention, a cluster means one set composed of a plurality of replicas. A cluster may include one or more nodes. One or more nodes in the cluster provide the same data to the client.

  FIG. 1 is a diagram for explaining asynchronous writing in a master-slave structure.

  Instead of the consistency described above, various schemes are used for replication when focusing on availability or performance. For example, asynchronous writing may be applied even in a master-slave structure. If there are two or more replicas using the master-slave model in No-SQL, a synchronized write may be applied to any one (or more) of the replicas and the rest Desynchronized writing may be applied to the replica.

The asynchronous writing process in the master-slave structure is as follows from step (1) to step (4).
(1) The client 110 writes 150
(2) The master 120 performs the requested write 160
(3) Master 120 requests asynchronous write to slave 130 (or one or more slaves 132, 134 and 136) 170
(4) The master 120 notifies the client 110 of the write result 180

  In the above-described steps, when input / output (Input / Output; IO) is performed in the slave 130, it overlaps with when the client 110 grasps the result of the write request. Therefore, if writing is not performed correctly due to a failure in the slave 130, a problem in consistency will occur later.

  FIG. 2 illustrates a multi-master replication scheme.

  An RDBMS in which data consistency is important (that is, it is important that all of a plurality of data are correct data) uses a master-slave model, while a DB using No-SQL is a multi-master ( Alternatively, a No-master) replication method may be used.

  If a multi-master model is used, the number of replicas must be specified initially.

  Each of the first node 210, the second node 220, and the third node 230 is a duplicate of the multi-master model.

  In a system using a multi-master model, inconsistent information may be transmitted to various clients by accessing different replicas storing the same contents and updating the information.

  When the two clients request the first node 210 and the third node 230 to update the information A, respectively, the client that has read the information A next becomes which node (for example, the first node 210 or the third node). Different values are obtained depending on whether the information A is accessed via the node 230). When the client reads the information A before all the updated contents for the information A are copied at different nodes, the client acquires different values depending on the node through which the information A is accessed. Alternatively, when updates to A are performed differently in the first node 210 and the third node 230, the client acquires different values depending on which node accessed the information A.

  As described above, when information update is requested almost simultaneously to each of a plurality of different nodes in a replication relationship without an explicit master, it is necessary to know which node has correct information.

  Therefore, a system using a multi-master model corrects information when reading the information. Such a correction is a read correction, and the read correction may reduce the read performance of the system.

  FIG. 3 is a diagram showing a structure of a data management system according to an example of the present invention.

  The data management system 300 (hereinafter, referred to as the system 300) is a system that stores data using replication. The system 300 includes a messaging channel 320 and one or more nodes 330. The system 300 may further include a level (L) 4 switch 325.

  For convenience of explanation, the illustrated one or more nodes 330 represent replicas (clusters) that store and provide the same data. One or more nodes 330 may be operated in a multi-master manner. Although not shown, the system 300 may further include a plurality of nodes including replicas for other data.

  The system 300 processes a data access request from the client 310. The data access request may be a read, a write, an insert, a delete, or an update request for specific data in the system 300.

  There may be a plurality of clients 310. That is, the system 300 may receive a data access request from each client 310 and may process the data access request. The client 310 requests data from the system 300 by transmitting a request message indicating a request for data.

  The messaging channel 320 serves as a middle-tier that processes messages between the client 310 and one or more nodes 330 storing data in the system. The messaging channel 320 may be a message-based middleware (MOM) or a server equipped with message-based middleware that functions as a router. The messaging channel 320 may be composed of a plurality of servers or software daemons to expand the processing capacity.

  One or more nodes 330 connected to the messaging channel 320 use a unique address scheme. A method for specifying an address for sending a message to each node on the messaging channel 320 is any one of (1) unicast, (2) anycast, and (3) multicast (or broadcast). Or more than one. Depending on the method of specifying the address, the method of sending a message to the node to which the messaging channel 320 is connected differs.

  Unicast is a scheme in which the messaging channel 320 transmits a message to only one node specified by a unique address. Anycast is a scheme in which the messaging channel 320 sends a message only to one node in any domain. The messaging channel 320 sends and receives messages or data with each node 332, 334, or 336 in unicast or anycast. For example, the messaging channel 320 transmits a request message using a unicast or anycast method to a selected specific node in order to process a data access request.

  Multicast is a method of sending a message to all nodes in any group. Messaging channel 320 may designate one or more nodes (ie, clusters) having the same data as a group and multicast messages. Accordingly, the messaging channel 320 multicasts a specific data access request so that all nodes in the corresponding cluster can receive the data access request. The messaging channel 320 may further include a management unit that manages information about the group or a separate server that manages the information (not shown), and updates information about a new node when a node is added or removed. May be.

  Here, each node 332, 334, or 336 is only connected to the messaging channel 320, and cannot communicate with each other. In this case, when a node addition or deletion occurs, information about the new or deleted node may be sent only to the messaging channel 320.

  If client 310 knows the protocol of messaging channel 320, client 310 may send a data access request directly to messaging channel 320. Alternatively, the client 310 may transmit a data access request directly to each node 332, 334 or 336. In this process, the access request may pass through the L4 switch 325 located on the network. The L4 switch 325 manages one or more nodes 330 using a virtual IP (VIP). When the client 310 transmits a data access request using the VIP, the L4 switch 325 having the VIP appropriately distributes the received data access request at the one or more nodes 330 after receiving the data access request.

  In the following, a method is described in which all of one or more nodes 330 maintain and provide the same data using messaging channel 320. In addition, multi-master replication can be realized by using the following method.

  FIG. 4 is a signal flowchart of a data management method according to an embodiment of the present invention.

  In the present embodiment, the terminals (that is, the first node 332, the second node 334, and the third node 336) process the data access request from the client 310.

  In step S410, the client 310 makes a data access request to the messaging channel 320. The data access request may be any one or more of reading, writing, inserting, deleting, or updating specific data (for example, an object). Messaging channel 320 receives a data access request from client 310.

  In step S420, the messaging channel 320 selects one node from a cluster composed of nodes including specific data in response to the data access request. For convenience of explanation, one or more of the nodes 330 shown in FIG. 4 (ie, a cluster including the first node 332, the second node 334, and the third node 336) are connected to the node including the requested data. It is called a set. Accordingly, the messaging channel 320 selects a node from one or more nodes 330. The messaging channel 320 may determine a selected node based on load balancing using a round-robin method or the like. In the present embodiment, a case where the second node 334 is selected will be described.

  In step S430, the messaging channel 320 sends a data access request to the selected node (ie, the second node 334).

  The selected node (ie, second node 334) receives the data access request sent by client 310 from messaging channel 320. Here, the selected node (second node 334) that has received the data access request may not immediately perform processing (for example, insertion or deletion of data) in response to the data access request.

  If the data access request is a read request for data, the following steps S440, S450, S462, S464, and S466 may not be performed. In this case, the data may be sent from the selected node (second node 334) to the client 310 via the messaging channel 320 or directly to the client 310.

  In step S440, the selected node (second node 334) transmits a multicast request for the data access request to the messaging channel 320. The messaging channel 320 receives a multicast request from the selected node (second node 334).

  In step S450, the messaging channel 320 multicasts the data access request to one or more nodes 330. The target of multicast is one or more nodes 330 (ie, all replicas of the selected node). A data access request is also transmitted via multicast to the selected node (second node 334) itself requesting multicast. Each of the one or more nodes 330 receives a multicast data access request.

  Data access requests multicasted by messaging channel 320 arrive at one or more nodes 330 simultaneously (logically). Each of the one or more nodes 330 may actually process the data access request when receiving the data access request via multicast.

  In steps S462, S464, and S466, each of the one or more nodes 330 processes the multicast data access request. For example, each of the one or more nodes 330 performs data writing, insertion, deletion, or update operation in response to the received data access request.

  Accordingly, the messaging channel 320 sequentially multicasts a plurality of data access requests so that one or more nodes 330 can process the plurality of data access requests in the same order. The system 300 may time-synchronize all the nodes in the system 300 in order to grasp the order of access requests, and may use a time stamp for each request. The system 300 may use NTP (Network Time Protocol) for time synchronization. Therefore, one or more nodes 330 can maintain the consistency of the data managed.

  FIG. 5 is a signal flowchart of a data management method according to an example of the present invention.

  In step S510, the selected node (ie, the second node 334) receives the data access request.

  The data access request may be sent directly from the client 310.

  The data access request may be transmitted via the L4 switch 325. The L4 switch 325 receives a data access request from the client 310. The L4 switch 325 selects one of the one or more nodes 330 and transmits a data access request to the selected node. The L4 switch 325 may use a round robin method or the like, or may determine a selected node based on load balancing.

  Here, the selected node (second node 334) that has received the data access request may not immediately process the data access request.

  In step S520, the selected node (second node 334) requests the messaging channel 320 for multicast for the data access request. That is, the selected node (second node 334) transmits a multicast request for a data access request to the messaging channel 320. The messaging channel 320 receives a multicast request for a data access request from a selected node (ie, the second node 334).

  In step S540, the messaging channel 320 multicasts the data access request to one or more nodes 330. The target of the multicast is one or more nodes 330 (ie, all replicas of the selected node). A data access request is also transmitted via multicast to the selected node (second node 334) itself requesting multicast. Each of the one or more nodes 330 receives a multicast data access request.

  In step S552, step S554, and step S556, each of the one or more nodes 330 processes a data access request received via multicast.

  For example, each of the one or more nodes 330 performs a data insertion, deletion, or update operation in response to the received data access request. Each node (eg, the first node 332, the second node 334, or the third node 336) processes the data access request after receiving the data access request via multicast. The messaging channel 320 for multicasting data access requests can grasp the order of data access requests at the standpoint of each node. In order to grasp the order of access requests, the system 300 may synchronize all nodes in the system 300 with time, or may use a time stamp for each request. The system 300 may use NTP (Network Time Protocol) for time synchronization. Therefore, the messaging channel 320 can always know which data is correct data when a plurality of nodes provide different data. Thus, the system 300 can provide data to the client 310 without performing read correction despite using a multi-master model.

  A messaging channel when a particular node of one or more nodes 330 fails, when a particular node is deleted from one or more nodes 330, or when a particular node is added to one or more nodes 330 320 can keep track of information regarding failures, deletions, or additions.

  Therefore, the method described above with reference to FIG. 4 and FIG. 5 can provide flexible extensibility in which replicas (ie, nodes) can be freely added and deleted in the cluster according to convenience or purpose. Also, the above-described method can provide the same result regardless of whether the data query is processed at any node in the cluster. Therefore, a load balancing effect is provided.

  In the embodiment described above with reference to FIGS. 4 and 5, each of the one or more nodes 330 does not communicate directly with the other nodes, and it is not possible to know what other nodes are present. Operate.

  Thus, when a particular node (ie, a replica) is added or removed from one or more nodes 330, the addition or removal process is only performed on the messaging channel 320, and other nodes affect the addition or removal. Can operate without receiving.

  For example, when one node is added for system expansion, the corresponding node transmits information on the corresponding node to the messaging channel 320 and creates a connection with the messaging channel 320. Thereafter, a request for data access included in the corresponding node may be received.

  Meanwhile, the messaging channel 320 may check the status of each node. For example, the messaging channel 320 periodically receives a heartbeat message and determines the presence or absence of a system failure based on the presence or absence of a response to message transmission. Alternatively, when a specific node is removed as necessary on the system, information regarding the removed node may be transmitted to the messaging channel 320. If it is determined that one node has failed or a specific node is removed, the messaging channel 320 does not send any more messages to that node. If there are no nodes in this way, the messaging channel 320 may direct a move operation to maintain the number of replicas as needed.

  In this way, the system 300 can easily handle node insertion, deletion, or failure.

  FIG. 6 is a block diagram of a messaging channel 320 according to one embodiment of the invention.

  The messaging channel 320 includes a reception unit 610, a control unit 620, and a transmission unit 630.

  The receiving unit 610 receives data via a network. For example, the reception unit 610 receives a data access request from the client 310 in steps S410 and S510. In step S440 and step S540, the receiving unit 610 receives a multicast request from the selected node to one or more nodes 330 for a data access request.

  For example, in step S420, the control unit 620 determines a node to be selected from the one or more nodes 330. The controller 620 may determine a node to be selected from the one or more nodes 330 based on round robin or load balancing.

  The transmission unit 630 transmits data via the network. For example, in step S430, the transmission unit 630 transmits a data access request to the selected node. In step S450 and step S540, the transmission unit 630 multicasts a data access request to one or more nodes 330.

  Meanwhile, the messaging channel 320 may further include a management unit (not shown) that manages node information. The management unit may manage node information and cluster information that is a duplicate of the same data, and allows the messaging channel 320 to handle the cluster as a group and perform broadcasting. The management unit may update information on a new node when adding or removing a node.

  The technical contents according to the embodiment of the present invention described above with reference to FIGS. 1 to 5 may be directly applied to the present embodiment. Therefore, this detailed description is omitted below.

  FIG. 7 is a diagram showing a data storage device according to an embodiment of the present invention.

  The data storage device 700 may include one or more storage areas 710, 720, 730, 740 and 750. Here, the “storage area” means a physical or logical space for storing data. For example, the “storage area” may be one relational database or file system, or a distributed cluster that is a collection of replicas for the same data.

  The data storage device 700 may correspond to one or more of the first node 332, the second node 334, and the third node 336 described with reference to FIGS.

  Each storage area may have a logical tree-like hierarchical structure. In other words, each storage area corresponds to one node in the tree, and a parent-child relationship or a sibling relationship is established between any two storage areas depending on the relationship between the nodes corresponding to the two storage areas.

  Referring to FIG. 7, the first storage area 710 corresponds to the root node of the tree structure, and the second storage area 720 and the third storage area 730 correspond to the right child node and the left child node of the first storage area 710, respectively. . The first storage area 710 is a parent storage area for the second storage area 720 and the third storage area 730. The second storage area 720 is a (left side) child storage area of the first storage area 710. The second storage area 720 is a sibling storage area of the third storage area 730. The fourth storage area 740 and the fifth storage area 750 correspond to the left child node and the right child node of the third storage area 730, respectively.

  Each of the storage areas 710, 720, 730, 740 and 750 may be assigned a key for identifying each storage area. This key is configured in a form that can represent a hierarchical structure with the storage area. For example, one key may be configured to include one or more sub-keys and a separator that separates the sub-keys. Here, the subkey is a value representing all nodes in an arbitrary subtree. Referring to FIG. 7, “corea” is a key representing a subtree whose root is the first storage area 710, and “seoul” is a key representing a subtree whose root is the third storage area 730. In FIG. 7, “korea”, “kyeongi”, “seoul“ kangbuk ”,“ kangnam ”, and the like are each one subkey, and one key such as“ korea.seoul. Configure.

The following formula (1) is an example of a regular expression indicating a hierarchical key in this way.

(1)
Here, “key” indicates a hierarchical key, and “key” is a character string (string) formed by combining alphanumeric and “.”

  In the case of using general English letters, numbers, and the numerator “.”, The key can be expressed as Equation (1), but the present invention is not limited thereto and includes other characters, or Other types of molecules may be used. Further, the key is not necessarily composed of one character string, and may be composed in a form such as a linked list. In the following, subkeys divided into compartments and the like are sequentially assigned to a first subkey, a second subkey,. . And the nth sub key. When the level of the root node is 1, the key for identifying the storage area corresponding to the node located at level n includes n subkeys.

  On the other hand, the key of the storage area corresponding to the root node may be null. In such a case, the root node may include 0 subkeys, and the key for identifying the storage area corresponding to the node located at level n may include n-1 subkeys. For example, the hierarchical key may be a character string or a blank character string generated by the regular expression of Equation (1).

  In FIG. 7, the key 715 assigned to the first storage area 710 is “korea”. The key 715 has only the first subkey “korea”.

  The key 725 assigned to the second storage area 720 is “corea.gyeongi”. The key 725 has a first subkey “korea” and a second subkey “gyeongi”. The key 735 assigned to the third storage area 730 is “corea.seoul”. The key 735 has a first subkey “korea” and a second subkey “seoul”. The key 745 assigned to the fourth storage area 740 is “corea.seoul.kangbuk”. The key 735 has a first subkey “korea”, a second subkey “seoul”, and a third subkey “kangbuk”. The key 755 assigned to the fifth storage area 750 is “corea.seoul.kangnam”. The key 755 has a first subkey “korea”, a second subkey “seoul”, and a third subkey “kannam”.

  The key assigned to the storage area may be a key in which one or more subkeys are chained to the key of the parent storage area of the storage area. For example, the key assigned to the fourth storage area 740 is a key in which the sub-key “kangbuk” is chained to the key “corea.seul” of the third storage area 730 that is the parent storage area of the fourth storage area.

  That is, when the storage area p and the storage area c are in the relationship between the parent storage area and the child storage area, if the key kp of the parent storage area p includes the first subkey sk1 to the nth subkey skn (where n is The key kc of the child storage area c may include the first subkey sk1 to nskn, and the (n + 1) th subkey sk (n + 1) to the mth subkey skm. Here, m is an integer of n + 1 or more.

  According to an embodiment of the present invention, the data storage device 700 stores data classified according to the key of each storage area. The data has a key. The data key is an identifier used in the data classification system. The key of the data may represent the upper position of the data classification system. When the tree structure in the data storage device 700 represents a classification system, the data corresponds to a specific storage area (or storage area key) according to the key value of the data.

  In a subtree rooted at a node indicating a specific storage area, the storage area in the subtree stores data corresponding to the key of the specific storage area.

  For example, in the subtree 760 rooted at the third storage area 730, the storage areas 730, 740, and 750 in the subtree 760 store data corresponding to the key 735 “corea.seul” of the third storage area 730.

  Further, the subtree having the fourth storage area 740 as a root includes only the fourth storage area 740. Therefore, the fourth storage area 740 may store data corresponding to the key 745 “corea.seoul.kangbuk” of the fourth storage area 740.

  Further, the subtree having the fifth storage area 750 as a root includes only the fifth storage area 750. Therefore, the fifth storage area 750 may store data corresponding to the key 755 “corea.seoul.kannam” of the fifth storage area 750.

  Here, the data corresponding to the storage area key means data in which one of the data key prefixes is the same as the storage area key.

  The key x prefix means that the hierarchical key x has n subkeys x1, x2, x3,. . . , Xn means a key including i subkeys of x (i is 1 or more and n or less). For example, the prefix of the hierarchical key “abc” may be “a”, “ab” and “abc”.

  For example, if the data key is “corea.seoul.kannam”, “korea” and “corea.seul” may be one of the key prefixes. Accordingly, the data corresponds to the key 715 “korea” in the first storage area 710 and the key 735 “korea.seoul” in the third storage area 730, and the key 745 and the fifth storage area 750 in the fourth storage area 740. This key 755 does not correspond.

  For example, if the key of the data is “corea.seoul.kannam.shinsa”, the prefix of the key may be “corea”, “corea.seoul”, “corea.seoul.kannam”. The data corresponds to the key 715 in the first storage area 710, the key 735 in the third storage area 730, and the key 755 in the fifth storage area 750.

  The data may be stored in any one of the one or more storage areas 710, 720, 730, 740, and 750 of the data storage device 700 according to its own key.

  For example, the storage area may store data that does not correspond to (1) the key of the storage area and (2) the key of the child storage area of the storage area.

  The data corresponding to the parent storage area p also corresponds to the child storage area c of the parent storage area p. When the data corresponds to the storage area p and the storage area c, the data may be stored in any one of the storage areas in the subtree rooted at the storage area c that is not the storage area p.

  If the key of the data is “corea.seul.kannam.shinsa” or “corea.seoul.kannam.shinsa.1”, the data is stored in the first storage area 710, the third storage area 730, and the fifth storage area 750. Corresponding to Data may be stored in the fifth storage area 750.

  If the data key is “corea.gangwon”, the data corresponds to the first storage area 710. Data may be stored in the first storage area 710.

  When the storage method as described above is used, a storage area in which actual data is located may be searched by a hierarchical key. That is, the storage area where the actual data is located may be searched by the entire hierarchical key or the key prefix.

  In the following, an example will be described in which data whose data key is “corea.seoul.kannam.shinsa” is searched. The key 715 in the first storage area 710 corresponding to the root node is compared with the data key. “Korea”, which is one of the data key prefixes, is the same as the key 715 in the first storage area 710. The third storage area 730 and the first storage area 710 are in a child-parent relationship. “Corea.seoul”, which is one of the data key prefixes, is the same as the key 735 in the third storage area 730. The fifth storage area 750 and the first storage area 710 are in a child-parent relationship. One of the data key prefixes, “corea.seoul.gangnam”, is the same as the key 755 in the fifth storage area 750. Accordingly, the data whose key is “corea.seoul.kannam.shinsa” may be searched in the fifth storage area 750 via the first storage area 710 and the third storage area 730.

  The following describes a case where data whose data key is “corea.jejudo” is searched. “Korea”, which is one of the data key prefixes, is the same as the key 715 in the first storage area 710. The data key prefixes “korea” and “korea.jejudo” are not the same as the key 725 in the second storage area 720 and the key 735 in the third storage area 730. Therefore, the data whose key is “corea.jejudo” may be searched in the first storage area 710.

  FIG. 8 is a diagram for explaining a process of adding a storage area to the data storage device according to an example of the present invention.

  Since the data storage device 700 described above with reference to FIG. 7 stores data corresponding to “corea” that is a key of the storage area, it can be considered that the storage area has been added.

  In the initial state 810, the data storage device 700 has only the first storage area 710.

  The key 715 of the first storage area 710 is “korea”. Therefore, data whose key is “corea”, data whose key starts from “corea.gyeongi”, and data whose key starts from “corea.seoul” are all stored in the first storage area 710.

  When the data storage device 700 is operated, if the data having a key having a specific prefix (that is, starting with a specific character string) (for example, “corea.seoul”) increases, the data storage device 700 A storage area having a specific prefix as a key may be added. This addition means that the tree structure of the data storage device 700 is expanded. That is, expansion means that a new storage area (or a node indicating a new storage area) is added to the tree structure of the data storage device 700.

  In the state 820 in which data is stored, the first storage area 710 stores one or more data 860 corresponding to the key 715.

  If the first storage area 710 cannot process one or more pieces of data 860, the addition of a new storage area is requested. For example, the data storage device 700 may be expanded via the following states 830, 840, and 850.

  As indicated by the node generation state 830, the data storage device 700 may generate a third storage area 730 that is a child storage area of the first storage area 710.

  That is, data corresponding to the third key 735 (that is, data whose data key starts with “corea.seoul”) may be separately separated into the third storage area 730, and may be separated by the third storage area 730 after the separation. May be processed.

  In the addition notification state 840, the newly generated third storage area 730 may notify the first storage area 710, which is its own parent storage area, of the key that it processes (that is, the third key 735). This notification notifies the addition of the storage area.

  In the data movement state 850, the first storage area 710 that has received the notification moves the data 870 corresponding to the notified third key 735 among the data stored therein to the third storage area 730. For example, the first storage area 710 that has received the notification may copy the data 870 corresponding to the notified third key 735 among the data stored therein to the third storage area 730. When the copying is completed, the first storage area 710 does not need to hold the data held in the child storage area (that is, the third storage area 730) redundantly. Therefore, one storage area 710 may delete data copied to the third storage area 730 among the data stored by itself. After the deletion, the first storage area 710 stores data not corresponding to the third key 735 among the data corresponding to the first key 715.

  By moving the data 870 corresponding to the third key 735 of the third storage area from the first storage area 710 to the third storage area 730, the storage amount of the first storage area 710 decreases.

  When new data is inserted into the first storage area 710 and the storage amount of the first storage area 710 reaches a predefined standard, the data storage device 700 generates the third storage area 730 and generates the third storage area 730 described above. 3 Data movement to the storage area 730 may be performed.

  During expansion, the data storage device 700 may not be interrupted (partially or entirely). Further, the data may be automatically copied by the extension.

  During expansion, new inflow data corresponding to the third key 735 is transmitted to the third storage area 730 corresponding to the child node generated by the expansion.

  The reduction of the data storage device 700 (that is, the deletion of the tree node) may be performed in the reverse order of the expansion of the data storage device 700 described above.

  FIG. 9 is a diagram for explaining a range search for a data storage device according to an example of the present invention.

  Queries may be used to query data that satisfies certain conditions. The query may be a sentence that queries a data list having a key corresponding to a specific search range.

  All or part of the storage areas 710, 720, 730, 740, and 750 of the data storage device 700 may retrieve data for a query. Data that is not stored in a specific storage area 710, 720, 730, 740, or 750 is also searched by merging the results searched by all or part of the storage areas 710, 720, 730, 740, and 750. May be.

  In the query provision state 910, the query may be provided to any storage area 710, 720, 730, 740 or 750.

  In the embodiment of the present invention, a case where a query is provided to the first storage area 710 corresponding to the root node will be described.

  The first storage area 710 determines whether or not its first key 715 corresponds to the query by analyzing the transmitted query. Here, the fact that the first key 715 corresponds to the query means that there is data included in the query search range among the data corresponding to the first key.

  For example, if the search range of the query is “usa.ar” to “usa.ca”, the data corresponding to the first key 715 “korea” is not included in the search range. Accordingly, the first key 715 does not correspond to a query.

  If there is no data corresponding to the query, the first storage area 710 may return a null for the query, or no further processing is required.

  In the query transmission state 920, the first storage area 710 may transmit a query to the second storage area 720 and the third storage area 730, which are its child storage areas. That is, the first storage area 710 may request an inventory of data having a key corresponding to the search range in one or more child storage areas (that is, the second storage area 720 and the third storage area 730).

  The second storage area 720 and the third storage area 730 may also send queries to their child storage areas. That is, the transmission of the query may be performed hierarchically. (Not shown)

  In the inventory return state 930, a list of data having a key corresponding to the search range is returned from one or more child storage areas (eg, the second storage area 720 and the third storage area 730) of the first storage area 710. Also good.

  When queries are transmitted hierarchically, the second storage area 720 and the third storage area 730 also return a list of data having keys corresponding to the search ranges from one or more child storage areas of the second storage area 720 and the third storage area 730, respectively. May be.

  In the list merge and search result return state 940, the first storage area 710 may return the data list merged as a result of the search term search range.

  The list of data returned by the second storage area 720 and the third storage area 730 may also be a merged data list. That is, the merged data list may be returned hierarchically.

  The first storage area 710 may be merged as a returned first list of data corresponding to the search range among the data stored in the first storage area 710, or generated and merged by the merge. The inventory may be returned as a result of the search term search range.

  As described above, an example of the present invention can support range search and spatial index without using a key-value DB or hash.

  FIG. 10 is a flowchart of a data storage method according to an embodiment of the present invention.

  In step S1010, one or more storage areas are configured in a tree structure. Each of the one or more storage areas may be an RDBMS.

  In step S1020, a hierarchical key is assigned to each of the one or more storage areas. A hierarchical key may have zero or more subkeys. The hierarchical key may be a character string generated by the regular expression of Equation (1) or a blank character string.

  In step S1030, the data corresponding to the first key of the first storage area is stored in the storage area in the server tree rooted at the first node indicating an arbitrary first storage area among the one or more storage areas. Is done.

  The first key is a key in which one or more subkeys are chained to the second key in the second storage area indicating the parent node of the first node.

  Data corresponding to the first key means data in which one of the data key prefixes is identical to the first key.

  If one of the data key prefixes is the same as the storage area key, the data can be considered to correspond to the storage area.

  Of the data corresponding to the first storage area, data corresponding to the third storage area indicating the child node of the first node is stored in the third storage area, and data not corresponding to the third storage area is stored in the first storage area. Stored. Therefore, step S1030 may include a step of storing, in the first storage area, data that does not correspond to the storage area indicating the child node of the first node among the data corresponding to the first storage area.

  The technical contents according to the embodiment of the present invention described above with reference to FIGS. 7 to 9 may be applied to the present embodiment as they are. Therefore, this detailed description is omitted below.

  FIG. 11 is a flowchart of an expansion method in the data storage device according to the embodiment of the present invention.

  Steps S1110, S1120, S1130, and S1140, which will be described later, may be included in step S1030 described above.

  In step S1110, it is determined whether the storage amount of the first storage area reaches a predefined standard.

  If the storage amount of the first storage area reaches a predefined standard, step S1120 is performed. If not, data is stored and the process ends.

  In step S1120, a third storage area of the child storage area of the first storage area is generated.

  In step S1130, the third storage area notifies its own third key to the first storage area.

  In step S1140, data corresponding to the third key in the third storage area moves from the first storage area to the third storage area.

  Step S1140 includes (1) a step of copying data corresponding to the third key of the third storage area from the first storage area to the third storage area, and (2) third storage of the data in the first storage area. A step of deleting data copied to the area may be included.

  The technical contents according to the embodiment of the present invention described above with reference to FIGS. 7 to 10 may be directly applied to the present embodiment. Therefore, this detailed description is omitted below.

  FIG. 12 is a flowchart of range search of the data storage device according to an example of the present invention.

  In step S1210, a query is provided to the first storage area.

  The query is a sentence requesting data having a key corresponding to the search range in the query in the storage area.

  In step S1220, the query is transmitted to the child storage area of the first storage area. That is, the first storage area requests a first list of data having a key corresponding to the search range in one or more child storage areas.

  Step S1220 may be performed recursively. The child storage area of the first storage area to which the query has been sent may retransmit the query to its one or more child storage areas.

  In step S1230, one or more storage areas return the first inventory.

  In step S1240, a merged catalog is generated by merging the second catalog of data having a key corresponding to the search range among the data stored in the first storage area with the returned first catalog.

  Steps S1230 and S1240 may be performed recursively. In the child storage area of the first storage area, a third list of data corresponding to the search range may be returned from one or more child storage areas of the first storage area. In the child storage area of the first storage area, the returned third list may be merged with the first list, or the merged first list may be returned to the first storage area.

  In step S1250, the merged inventory is returned as a result for the search range.

  The technical contents according to the embodiment of the present invention described above with reference to FIGS. 7 to 11 may be applied to the present embodiment as they are. Therefore, this detailed description is omitted below.

  The method according to an embodiment may be implemented in the form of program instructions that can be performed by various computer means and recorded on a computer-readable medium. The recording medium may include a program instruction, a data file, a data structure, etc., alone or in combination. The recording medium and the program instructions may be specially designed and configured for the purpose of the present invention, and may be known and usable by those skilled in the art having computer software technology. . Examples of computer-readable recording media include magnetic media such as hard disks, floppy (registered trademark) disks and magnetic tapes, optical recording media such as CD-ROMs and DVDs, and magnetic-lights such as floppy disks. The medium and hardware devices specially configured to store and execute program instructions such as ROM, RAM, flash memory, etc. may be included. Examples of program instructions include not only machine language code generated by a compiler but also high-level language code that can be executed by a computer using an interpreter or the like. The hardware devices described above may be configured to operate as one or more software modules to perform the operations of the present invention, and vice versa.

  As described above, the present invention has been described with reference to the limited embodiments and drawings. However, the present invention is not limited to the above-described embodiments, and any person having ordinary knowledge in the field to which the present invention belongs can be used. Various modifications and variations are possible from such an embodiment.

  Therefore, the scope of the present invention is not limited to the disclosed embodiments, but is defined by the claims and equivalents of the claims.

310 Client 320 Messaging Channel 332 First Node 334 Second Node 336 Third Node 700 Data Storage Device 710 First Storage Area 715 First Key

Claims (8)

Selecting one of the plurality of nodes operated by multimaster system in accordance with the data access request from the client, the selected node receives the data access request,
Before the selected node processes the data access request , it sends a multicast request for the data access request to a messaging channel;
The messaging channel receives the multicast request and multicasts the data access request to the plurality of nodes;
Processing the data access request when each of the plurality of nodes receives the multicast;
Including
The plurality of nodes includes a copy of the data access request data;
Each of the plurality of nodes does not directly communicate with other nodes and does not transmit the data access request to each other . The messaging channel receives the data access request from a client;
The messaging channel determines the selected node of the plurality of nodes;
The messaging channel sends the data access request to the selected node;
The data management method according to claim 1, further comprising: Receiving a data access request via a messaging channel ;
Transmitting the data access request from the messaging channel to a node selected from a plurality of nodes operating in a multi-master manner;
Before the selected node processes the data access request, it sends a multicast request for the data access request to a messaging channel;
Transmits the data access request by said messaging channel to the plurality of nodes,
Each of the plurality of nodes processing the data access request when receiving the data access request ;
The plurality of nodes are nodes including a copy of data requested by the data access request;
Each of the plurality of nodes does not directly communicate with other nodes and does not transmit the data access request to each other . 3. The data management method according to claim 2, wherein the step of determining the node determines the selected node among the plurality of nodes based on a round robin method or load balancing. In response to a data access request from a client , the data access request is transmitted through a messaging channel to a selected node among a plurality of nodes operating in a multi-master scheme .
Before the selected node to process the data access request, and sends to the messaging channel multicast request for the data access request by said selected node,
Said data access request via multicast from the messaging channel received by the plurality of nodes,
Processing the data access request when each of the plurality of nodes receives the multicast ;
Including
Each of the plurality of nodes does not directly communicate with other nodes and does not transmit the data access request to each other . Multiple nodes containing duplicates of the same data;
A messaging channel for transmitting a data access request to the plurality of nodes;
Including
After receiving the data access request from the messaging channel , any one of the plurality of nodes transmits a multicast request for the data access request to the messaging channel before processing the data access request. The messaging channel receives the multicast request and multicasts the data access request to the plurality of nodes, and each of the plurality of nodes processes the data access request when receiving the multicast,
Each of the plurality of nodes does not directly communicate with other nodes and does not transmit the data access request to each other . Wherein the messaging channel receives a data access request from the client, to claim 6, characterized in that by selecting one of the nodes of said plurality of nodes transmitting the data access request to the selected node The data management system described. The data management system according to claim 7, wherein the messaging channel selects the one node among the plurality of nodes based on a round robin method or load balancing.