JP4754010B2 - Message linking processing program, method and apparatus - Google Patents

Description

  The present technology relates to a technology for parallelizing message linking processing.

  For example, in a system having a plurality of servers such as electronic commerce, when a request from a client is received, messages are exchanged between the servers, and processing proceeds.

  On the other hand, in order to analyze such system behavior monitoring and request delay problems, a process for associating a message for each transaction (hereinafter referred to as an association process) is performed. Note that a message required for the response of one request is recognized as one transaction by a keyword included in the message (hereinafter referred to as a linking key).

Japanese Patent Laid-Open No. 11-53323 JP-A-5-61697

  For example, in order to process a large number of messages at high speed, a configuration in which a plurality of linking servers that perform message linking processing and the like are operated in parallel is conceivable. However, when simply performing parallel processing, the number of times of communication for the linking process may increase between the linking servers, and there is a problem that the communication load hinders efficiency improvement by parallelization. In the prior art, it is not possible to parallelize message linking processes while suppressing the communication load of a linking server or the like.

  Accordingly, an object of the present technology is to enable message linking processes to be parallelized while minimizing a communication load of a linking server or the like.

This message linking processing method extracts each linking key from the key definition database that stores the linking key that is included in the message related to the protocol for each protocol and that is used in the message linking processing. A step of generating data of a structure including a node corresponding to each of the keys and a link connecting nodes of the tied keys belonging to the same protocol, and determining whether a loop is formed in the structure by the plurality of links An allocation that is a combination of a linking key allocation to each of a plurality of linking processing units that perform linking processing in cooperation with each other when it is determined that a loop is not formed in the structure. of pattern satisfy predetermined conditions allocation including a first condition that the communication load between the tying unit is minimum Identifying a turn, and a pattern specifying step of storing allocation data relating to the identified allocation pattern in the key information storage unit.

  The message linking process can be parallelized while suppressing the communication load of the linking server.

It is a figure for demonstrating the message correlation process used as the premise of this Embodiment. It is a figure for demonstrating the problem in the message link | linking process used as the premise of this Embodiment. It is a figure for demonstrating the message correlation process used as the premise of this Embodiment. It is a figure for demonstrating the problem in the message link | linking process used as the premise of this Embodiment. It is a figure for demonstrating the outline | summary of this Embodiment. It is a functional block diagram of the message correlation processing apparatus which concerns on this Embodiment. It is a figure which shows an example of the data stored in server DB. It is a figure which shows an example of the data stored in key definition DB. It is a figure which shows an example of the data stored in a key arrangement | positioning storage part. It is a figure which shows an example of the data stored in a key priority storage part. It is a figure which shows the main processing flow in this Embodiment. It is a figure which shows a structure. It is a figure which shows a structure. It is a figure which shows the processing flow (1st part) of a processing amount calculation process. It is a figure which shows a structure. It is a figure which shows a structure. (A) thru | or (c) is a figure for demonstrating the case where a throughput calculation process is implemented recursively. It is a figure which shows the processing flow (2nd part) of a processing amount calculation process. It is a figure which shows the example of a table of an allocation pattern table. (A) thru | or (c) is a figure which shows tied key allocation. It is a figure which shows the example of a table of an allocation pattern table. (A) And (b) is a figure for demonstrating the process in case there are three tied keys. It is a functional block diagram of a computer.

  First, message linking processing, which is a premise of the present embodiment, will be described. For example, as shown in FIG. 1, the message distribution unit sends a protocol O message (Prot.O) and a protocol R message (Prot.R) to the linking server 1 to which the linking keys Kc and Kd are assigned. And the protocol P message (Prot.P) and the protocol S message (Prot.S) are allocated to the linking server 2 to which the linking keys Ka and Kb are allocated. In addition, the linking servers 1 and 2 have a hash table for each assigned linking key. When a message is received from the message distribution unit, a hash value is calculated from the linking key, and according to the hash value. The message is stored in a hash table. Prot.O includes linking keys Kc and Ka, Prot.P includes linking keys Ka and Kd, and Prot.R includes linking keys Kd and Kb. Prot.S includes a linking key Kb. That is, Prot.O and Prot.P are linked by the linking key Ka. Further, Prot.P and Prot.R are linked by the linking key Kd. Further, Prot.R and Prot.S are linked by the linking key Kb. Therefore, Prot.O, Prot.P, Prot.R, and Prot.S are linked as messages related to the same transaction.

  For example, as shown in FIG. 2, a message linking process is performed. Specifically, first, the associating server 1 extracts Prot.O (Kc = a, Ka = 15) from the hash table (Kc). Here, Prot.O is associated with Prot.P by the association key Ka, but since Prot.P is stored in the association server 2, communication between the association servers (first time) ) Occurs. Next, the associating server 2 retrieves Prot.P (Ka = 15, Kd = 37) associated with Prot.O from the hash table (Ka). Here, Prot.P is linked to Prot.R by the linking key Kd, but since Prot.R is stored in the linking server 1, communication between the linking servers again (2 Occurs). Then, the associating server 1 extracts Prot.R (Kd = 37, Kb = x) associated with Prot.P from the hash table (Kd). Here, Prot.R is associated with Prot.S by the association key Kb, but since Prot.S is stored in the association server 2, communication between the association servers again (3 Occurs). Then, the linking server 2 extracts Prot.S (Kb = x) linked to Prot.R from the hash table (Kb), and the linking process is completed. That is, when a linking key is assigned as shown in FIG. 1, three times of communication are required between linking servers for the linking process. 1 and 2 show an example in which the number of linking keys is four. However, as the number of linking keys increases, the number of communication between the linking servers also increases, and the communication load is improved by parallel processing. Will be disturbed.

  In addition, as shown in FIG. 3, when the message distribution unit distributes a message including a plurality of association keys, for example, if the message is allocated according to the association key detected earlier in the message, The problem shown in FIG. In FIG. 3, it is assumed that the associating keys 1 are assigned to the associating server 1 and the associating keys Kd and Kb are assigned to the associating server 2. In FIG. 3, it is assumed that the linking key Kd is detected before the linking key Ka, and Prot. P is allocated to the linking server 2 according to the linking key Kd.

  When the message linking process is performed in this state, as shown in FIG. 4, the linking server 1 extracts Prot.O from the hash table of the linking key Kc, but the linking key in the linking server 1 Since Prot.P is not registered in Ka's hash table, Prot.P that should be associated with Prot.O cannot be found. In this case, registration can also be performed by registering Prot.P in the hash table of the linking key Ka, but an extra area must be secured in the hash table, and the message A communication load for copying is applied and parallelization is hindered.

  Therefore, in the present embodiment, a pattern that satisfies a predetermined condition (for example, the operation rate of each linking server) and that minimizes the communication load between the linking servers is identified from the linking key allocation patterns. Optimize the linking key assigned to each linking server. For example, key assignment as shown in FIG. 5 is performed. In FIG. 5, linking keys Kc and Ka are allocated to the linking server 1, and linking keys Kd and Kb are allocated to the linking server 2. Further, the priority of the linking key is determined so that a message including a plurality of linking keys need not be registered repeatedly. For example, when linking is performed in the order of Prot.O (Kc, Ka) → Prot.P (Ka, Kd) → Prot.R (Kd, Kb) → Prot.S (Kb), Kc (= 1), Priorities are assigned in the order of Ka (= 2), Kd (= 3), and Kb (= 4). If the message distribution unit performs message distribution according to the priority, for example, Prot.P is assigned to the linking server 1 because Ka has higher priority than Kd. Thereby, it becomes possible to perform the linking process without registering redundantly, and the number of communications that was three times in FIG. 2 can be reduced to one time. Hereinafter, an embodiment of the present technology will be described.

  First, FIG. 6 shows a system overview of a message linking processing device according to an embodiment of the present technology. The message linking processing device in the present embodiment includes a server DB 101 that stores the processing capability of each linking processing unit, a key definition DB 103 that stores a linking key included in a message related to the protocol for each protocol, Based on the data stored in the server DB 101 and the key definition DB 103, a pattern that satisfies a predetermined condition and that minimizes the communication load between the linking processing units (linking servers) among the linking key allocation patterns is identified. Based on the key arrangement stored in the key arrangement storage unit 107, the key arrangement storage unit 107 that stores the key arrangement related to the allocation pattern specified by the key arrangement optimization unit 105, and the key arrangement stored in the key arrangement storage unit 107. A key priority determination unit 109 that determines the priority of each linking key and a key priority determination unit 109 The key priority storage unit 111 for storing the priority of the determined association key, the message receiving unit 113 for receiving a message related to each transaction, and the key arrangement and key priority stored in the key arrangement storage unit 107. A message distribution unit 115 that distributes the message received by the message reception unit 113 to the associated association processing unit according to the priority stored in the degree storage unit 111, and a hash table for each associated association key And linking processing units 117 to 121 for executing message linking processing in cooperation with each other. Assume that the association processing units 117 to 121 are configured on, for example, another server.

  Further, the key arrangement optimizing unit 105 extracts each linking key from the key definition DB 103, and creates a link connecting the nodes of the linking keys belonging to the same protocol as the node corresponding to each of the extracted linking keys. The structure processing unit 1051 that performs processing related to the data of the included structure and the communication load between the linking processing unit (linking server) satisfying a predetermined condition among the linking key allocation patterns are the least A pattern specifying unit 1053 for specifying a pattern to be formed.

  FIG. 7 shows an example of data stored in the server DB 101. In the example of FIG. 7, the server DB 101 includes a server (linking processing unit) ID column and a processing capability column. The processing capability column stores a value representing the relative processing capability of each linking server (linking processing unit).

  FIG. 8 shows an example of data stored in the key definition DB 103. In the example of FIG. 8, the key definition DB 103 includes a protocol column and a key (linking key) column.

  FIG. 9 shows an example of data stored in the key arrangement storage unit 107. In the example of FIG. 9, the key arrangement storage unit 107 includes a server (linking processing unit) ID column and a key (linking key) column. In the key column, a linking key assigned to the linking server (linking processing unit) is set. The key arrangement storage unit 107 stores data of a structure corresponding to the key arrangement and a minimum communication load described later.

  FIG. 10 shows an example of data stored in the key priority storage unit 111. In the example of FIG. 10, the key priority storage unit 111 includes a key (linking key) column and a priority column.

  Next, processing contents of the message association processing apparatus shown in FIG. 6 will be described with reference to FIGS. In this embodiment, a case where there are three tying servers (1 to 3) will be described as an example. First, the structure processing unit 1051 includes each link key extracted from the key definition DB 103, and includes a link that connects between the nodes corresponding to each of the extracted link keys and the link key nodes belonging to the same protocol. Data of the structure is generated and stored in the storage device (FIG. 11: step S1). For example, when the data (P1 to P10) as shown in FIG. 8 is stored in the key definition DB 103, the data of the structure as shown in FIG. The structure shown in FIG. 12 includes the association keys Kx, Ka, Kb, Kc, Kd, Ke, Kf, Kg, Ky, and Kz in the key definition DB 103 (FIG. 8). Further, the structure shown in FIG. 12 includes links P1 to P10 corresponding to the protocols P1 to P10 in the key definition DB 103, respectively. The link P1 is a link that connects the nodes of the association keys Kx and Ka belonging to the protocol P1. The link P2 is a link that connects the nodes of the association keys Ka and Kb belonging to the protocol P2. Furthermore, the link P3 is a link that connects the nodes of the association keys Kb and Kc belonging to the protocol P3. The link P4 is a link connecting the nodes of the tying keys Kc and Kd belonging to the protocol P4. Furthermore, the link P5 is a link that connects the nodes of the association keys Kd and Ky belonging to the protocol P5. The link P6 is a link that connects the nodes of the tying keys Kc and Ke belonging to the protocol P6. Furthermore, the link P7 is a link that connects the nodes of the association keys Ke and Kf belonging to the protocol P7. The link P8 is a link connecting the nodes of the association keys Kf and Kz belonging to the protocol P8. Furthermore, the link P9 is a link that connects the nodes of the tying keys Ke and Kg belonging to the protocol P9. The link P10 is a link connecting the nodes of the tying keys Kb and Kg belonging to the protocol P10.

  And the structure process part 1051 deletes the node of the tied key which belongs to a single protocol from a structure (step S3). In FIG. 8, the linking key Kx is included only in the protocol P1, the linking key Ky is included only in the protocol P5, and the linking key Kz is included only in the protocol P8. Therefore, the nodes of the linking keys Kx, Ky, and Kz are deleted from the structure shown in FIG. 12, resulting in a structure as shown on the right side of FIG. Note that the right-side structure in FIG. 13 includes nodes for the association keys Ka, Kb, Kc, Kd, Ke, Kf, and Kg.

  Then, the structure processing unit 1051 and the pattern specifying unit 1053 use the data stored in the server DB 101 and the data of the structure stored in the storage device to specify the key arrangement. And stored in the key arrangement storage unit 107 (step S5).

  The processing amount calculation process will be described with reference to FIGS. First, the structure processing unit 1051 analyzes the structure data stored in the storage device, and determines whether or not there is a loop in the structure (FIG. 14: step S11). For example, each node is detected by tracing a link included in the structure, and a flag is set for the detected node. When a flagged node is detected again, it is determined that there is a loop. When it is determined that there is no loop in the structure (step S11: No route), the process proceeds to step S21 (FIG. 18) via the terminal A. The process of FIG. 18 will be described later.

  On the other hand, when it is determined that there is a loop in the structure (step S11: Yes route), the structure processing unit 1051 extracts a link constituting the loop as a disconnection candidate link (step S13). For example, as shown in FIG. 15, a link P3 that connects the tying key Kb and the tying key Kc, a link P6 that ties the tying key Kc and the tying key Ke, and a tying key Ke and a tying key Kg. When a loop is formed by the link P9 connecting the linking key Kg and the linking key Kb, the links P3, P6, P9 and P10 are extracted as the cutting candidate links.

  Then, the structure processing unit 1051 identifies unprocessed cutting candidate links among the extracted cutting candidate links (step S15). Here, for example, the link P10 is specified. Then, the structure processing unit 1051 considers that the specified cutting candidate link is cut, and recursively performs a processing amount calculation process (step S17). For example, when the link P10 is cut, a structure as shown on the right side of FIG. 16 is obtained, and the throughput calculation process is performed again with this structure. When the process of step S17 ends, the identified disconnection candidate link is regarded as having been reconnected.

  Note that the number of loops formed in the structure is not limited to one. For example, when two loops are formed as shown in FIG. 17A, first, a disconnection candidate link is specified for the loop formed by the links P3, P6, P9, and P10 (here, the link P10 is specified). It is assumed that the link P10 has been disconnected, and the processing amount calculation process is performed. When the link P10 is cut, a structure as shown in FIG. Next, in the structure shown in FIG. 17B, a candidate cut link is specified for the loop formed by the links P14, P16, P17, and P15 (here, it is assumed that the link P17 is specified), and the link P17 is changed. Considering that it has been cut, further processing for calculating the amount of processing is performed. When the link P17 is cut, a structure as shown in FIG. A loop is not formed in the structure of FIG. In this way, the processing amount calculation process is recursively performed until there is no loop in the structure.

  And the structure process part 1051 judges whether the process was completed about all the cutting | disconnection candidate links (step S19). If the processing has not been completed for all the disconnection candidate links (step S19: No route), the processing returns to step S15. On the other hand, when the process is completed for all the disconnection candidate links (step S19: Yes route), the process returns to the original process.

  Next, the processing after the terminal A will be described with reference to FIG. A case where the structure shown on the right side of FIG. 16 is processed will be described as an example. First, the pattern specifying unit 1053 is configured so that each linking server is based on the number of nodes (linking keys) included in the structure and the processing capability of each linking server (linking process unit) stored in the server DB 101. The processing amount in charge of the (association processing unit) is calculated and temporarily stored in the storage device (FIG. 18: step S21). Specifically, the total processing capacity is calculated by adding all the processing capacities of the linking servers, and “(total number of nodes) × (processing capacity of the linking server n) / (total processing capacity)” is calculated. , It is calculated as the processing amount in charge of the linking server n (that is, the number of linking keys handled by the linking server n). For example, when the data as shown in FIG. 7 is stored in the server DB 101 for the linking server 1 to the linking server 3, the overall processing capacity is 7 (= 2 + 2 + 3). Further, the structure shown on the right side of FIG. 16 includes seven nodes (each node of the association keys Ka, Kb, Kc, Kd, Ke, Kf, and Kg). Therefore, the processing amount in charge of the tying server 1 is “7 × 2/7 = 2”, and the processing amount in charge of the tying server 2 is “7 × 2/7 = 2”. The processing amount is “7 × 3/7 = 3”.

  And the pattern specific | specification part 1053 produces | generates an allocation pattern table, and stores it in a memory | storage device (step S23). Specifically, all the allocation patterns that are combinations of the linking keys in the case of allocating the linking keys to each linking server according to the assigned processing amount calculated in step S21 are extracted, and the allocation includes all the extracted allocation patterns. Generate a pattern table. FIG. 19 shows an example of an allocation pattern table. In the example of FIG. 19, the allocation pattern table includes a server (linking processing unit) ID column, a processing capability column, a pattern 1 column, a pattern 2 column, a pattern 3 column, and so on.・ And are included. Further, each pattern column is divided into a key arrangement column, a responsible processing amount column, a communication load column, a processing amount column, and an operation rate column. In the processing capability column, the processing capability of the linking server (linking processing unit) stored in the server DB 101 is set. A combination of linking keys in the pattern is set in the key arrangement column. The assigned processing amount calculated in step S21 is set in the assigned processing amount column. Note that each of the communication load column, the processing amount column, and the operation rate column is set by the processing in step S27 described later.

  Then, the pattern identification unit 1053 identifies an unprocessed allocation pattern in the allocation pattern table (step S25). And the pattern specific | specification part 1053 calculates the communication load of each tied server in the specified allocation pattern, a processing amount, and an operation rate, and sets it to an allocation pattern table (step S27). This process will be described with reference to FIG.

  For example, in the case of pattern 1 in the assignment pattern table shown in FIG. 19, the assignment is as shown in FIG. In FIG. 20A, there is one link straddling the tying server 1 and the tying server 2 (link that connects the node (Kb) and the node (Kc)). Here, the communication load (1 ×) between the linking server 1 and the linking server 2 is obtained by multiplying the number of links straddling the linking server 1 and the linking server 2 by a predetermined weighting value (here, 1). 1 = 1) is calculated and equally allocated to each of the linking server 1 and the linking server 2. That is, 0.5 is allocated to each of the linking server 1 and the linking server 2. In FIG. 20A, there is also one link straddling the linking server 2 and the linking server 3 (link connecting the node (Kc) and the node (Ke)). Similarly, the communication load (1 ×) between the tying server 2 and the tying server 3 is obtained by multiplying the number of links straddling the tying server 2 and the tying server 3 by a predetermined weight value (here, 1). 1 = 1) is calculated and equally allocated to each of the linking server 2 and the linking server 3. That is, 0.5 is allocated to each of the linking server 2 and the linking server 3. As a result, in the case of pattern 1, the communication load of the linking server 1 is 0.5, the communication load of the linking server 2 is 1 (= 0.5 + 0.5), and the communication load of the linking server 3 is 0.5. Become. For example, when the communication speed between the tied servers is slow, a weighting value that increases the communication load may be employed. Then, the processing amount is calculated by adding the assigned processing amount and the communication load for each linking server. That is, the processing amount of the linking server 1 is 2.5 (= 2 + 0.5), the processing amount of the linking server 2 is 3 (= 2 + 1), and the processing amount of the linking server 3 is 3.5 (= 3 + 0.5). ) Further, the ratio of the processing amount to the processing capability (= processing amount / processing capability) is calculated as the operation rate for each linking server. That is, the operating rate of the linking server 1 is 125% (= 2.5 / 2), the operating rate of the linking server 2 is 150% (= 3/2), and the operating rate of the linking server 3 is 117% (≈ 3.5 / 3).

  In the case of pattern 2 in the allocation pattern table shown in FIG. 19, the allocation is as shown in FIG. In FIG. 20B, there is one link straddling the linking server 1 and the linking server 2 (link connecting the node (Kb) and the node (Kc)). Communication load (1 × 1 = 1) between the linking server 1 and the linking server 2 by multiplying the number of links straddling the linking server 1 and the linking server 2 by a predetermined weighting value (here, 1). ) And is equally allocated to each of the linking server 1 and the linking server 2. That is, 0.5 is allocated to each of the linking server 1 and the linking server 2. In FIG. 20B, there are three links straddling the linking server 2 and the linking server 3 (links connecting the node (Kc) and the node (Kd), the node (Ke) and the node ( Kf), a link connecting node (Ke) and node (Kg)). Communication load (3 × 1 = 3) between the tying server 2 and the tying server 3 by multiplying the number of links straddling the tying server 2 and the tying server 3 by a predetermined weighting value (here, 1). ) And is equally allocated to each of the linking server 2 and the linking server 3. That is, 1.5 is allocated to each of the linking server 2 and the linking server 3. As a result, in the case of Pattern 2, the communication load of the linking server 1 is 0.5, the communication load of the linking server 2 is 2 (= 0.5 + 1.5), and the communication load of the linking server 3 is 1.5. Become. Then, the processing amount is calculated by adding the assigned processing amount and the communication load for each linking server. That is, the processing amount of the linking server 1 is 2.5 (= 2 + 0.5), the processing amount of the linking server 2 is 4 (= 2 + 2), and the processing amount of the linking server 3 is 4.5 (= 3 + 1.5). ) Further, the ratio of the processing amount to the processing capability (= processing amount / processing capability) is calculated as the operation rate for each linking server. That is, the operating rate of the linking server 1 is 125% (= 2.5 / 2), the operating rate of the linking server 2 is 200% (= 4/2), and the operating rate of the linking server 3 is 150% (= 4.5 / 3).

  Further, in the case of pattern 3 in the assignment pattern table shown in FIG. 19, the assignment is as shown in FIG. In FIG. 20C, there is one link straddling the tying server 1 and the tying server 2 (links connecting the node (Kb) and the node (Kc)). Communication load (1 × 1 = 1) between the linking server 1 and the linking server 2 by multiplying the number of links straddling the linking server 1 and the linking server 2 by a predetermined weighting value (here, 1). ) And is equally allocated to each of the linking server 1 and the linking server 2. That is, 0.5 is allocated to each of the linking server 1 and the linking server 2. In FIG. 20C, there are three links straddling the linking server 2 and the linking server 3 (links connecting the node (Kc) and the node (Kd), the nodes (Kc) and the nodes ( A link connecting Ke) and a link connecting node (Kf) and node (Ke). Communication load (3 × 1 = 3) between the tying server 2 and the tying server 3 by multiplying the number of links straddling the tying server 2 and the tying server 3 by a predetermined weighting value (here, 1). ) And is equally allocated to each of the linking server 2 and the linking server 3. That is, 1.5 is allocated to each of the linking server 2 and the linking server 3. As a result, in the case of pattern 3, the communication load of the connection server 1 is 0.5, the communication load of the connection server 2 is 2 (= 0.5 + 1.5), and the communication load of the connection server 3 is 1.5. Become. Then, the processing amount is calculated by adding the assigned processing amount and the communication load for each linking server. That is, the processing amount of the linking server 1 is 2.5 (= 2 + 0.5), the processing amount of the linking server 2 is 4 (= 2 + 2), and the processing amount of the linking server 3 is 4.5 (= 3 + 1.5). ) Further, the ratio of the processing amount to the processing capability (= processing amount / processing capability) is calculated as the operation rate for each linking server. That is, the operating rate of the linking server 1 is 125% (= 2.5 / 2), the operating rate of the linking server 2 is 200% (= 4/2), and the operating rate of the linking server 3 is 150% (= 4.5 / 3).

Then, the pattern identification unit 1053 calculates the total communication load in the identified allocation pattern and stores it in the allocation pattern table (step S28).

  Then, the pattern identification unit 1053 determines whether the processing has been completed for all the allocation patterns (step S29). If processing has not been completed for all allocation patterns (step S29: No route), the processing returns to step S25. On the other hand, when the process is completed for all the allocation patterns (step S29: Yes route), the process proceeds to step S31. When processing is completed for all allocation patterns, data as shown in FIG. 21 is stored in the allocation pattern table.

  Shifting to the process of step S31, the pattern specifying unit 1053 specifies an allocation pattern in which the operation rate satisfies a predetermined condition and the total communication load is minimized (step S31). Here, the predetermined condition is, for example, a condition that all the operating rates of the linking servers in the allocation pattern are within a predetermined reference value. If there is no allocation pattern that satisfies the predetermined condition, an allocation pattern with the smallest difference from the reference value is selected.

  Then, the pattern specifying unit 1053 determines whether the key arrangement and the minimum communication load are already stored in the key arrangement storage unit 107 (step S33). When it is determined that the key arrangement and the minimum communication load are not yet stored in the key arrangement storage unit 107 (step S33: No route), that is, in the case of the first processing, the pattern specifying unit 1053 specifies the specified allocation. The key arrangement related to the pattern is stored in the key arrangement storage unit 107, and the total communication load related to the specified allocation pattern is stored in the key arrangement storage unit 107 as the minimum communication load (step S35). The data of the current structure is also stored in the key arrangement storage unit 107. Then, it returns to FIG. 14 via the terminal B, and complete | finishes a processing amount calculation process. Then, the process returns to the original process.

  On the other hand, when it is determined that the key arrangement and the minimum communication load are already stored in the key arrangement storage unit 107 (step S33: Yes route), that is, in the case of the second and subsequent processing (when executing recursively, click here) The pattern specifying unit 1053 compares the total communication load related to the specified allocation pattern with the minimum communication load stored in the key arrangement storage unit 107, and determines the specified allocation pattern. It is determined whether the total communication load is smaller than the minimum communication load stored in the key arrangement storage unit 107 (step S37). When it is determined that the total communication load related to the specified allocation pattern is equal to or greater than the minimum communication load stored in the key arrangement storage unit 107 (step S37: No route), the process returns to FIG. The calculation process ends. Then, the process returns to the original process.

  On the other hand, if it is determined that the total communication load related to the specified allocation pattern is smaller than the minimum communication load stored in the key arrangement storage unit 107 (step S37: Yes route), the pattern specifying unit 1053 is specified The key arrangement and the minimum communication load stored in the key arrangement storage unit 107 are updated with the key arrangement and the total communication load related to the allocation pattern (step S39). Furthermore, the structure data stored in the key arrangement storage unit 107 is updated with the current structure data. Then, it returns to FIG. 14 via the terminal B, and complete | finishes a processing amount calculation process. Then, the process returns to the original process.

  By performing the processing as described above, it is possible to specify an allocation pattern that satisfies a predetermined condition and minimizes the communication load. If a loop is formed in the structure, it is assumed that the link forming the loop is cut and the processing amount calculation process is performed recursively, so the loop is formed in the structure. Even in such a case, the optimum allocation pattern can be specified. Note that in step S3, the linking key nodes (Kx, Ky, and Kz in the above example) belonging to a single protocol are deleted, and these linking keys are not included in the allocation pattern. There is no problem because these linking keys are not used in the message linking process.

  Returning to the description of FIG. 11, after performing the processing amount calculation process (step S <b> 5), the key priority determination unit 109 determines the priority of the linking key based on the data stored in the key arrangement storage unit 107. It is determined and stored in the key priority storage unit 111 (step S7). This process will be described with reference to an example in which pattern 1 in the allocation pattern table shown in FIG. 21 is specified as an allocation pattern that minimizes the communication load. First, the key priority determination unit 109 specifies a node regarded as a leaf node in the structure as a start node. For example, in the case of the pattern 1, the allocation is as shown in FIG. 20A, but in FIG. 20A, the node (Ka), the node (Kd), the node (Kf), and the node (Kg) Are considered leaf nodes. Here, it is assumed that the node (Ka) is specified as the start node. Then, the key priority determination unit 109 detects each node by following the link from the start node. For example, in FIG. 20A, nodes are detected in the order of node (Ka) → node (Kb) → node (Kc) → node (Kd). Returning to the node (Kc), the nodes are detected in the order of the node (Kc) → the node (Ke) → the node (Kf). Further, returning to the node (Ke), the nodes are detected in the order of the node (Ke) → the node (Kg). Then, consecutive numbers in the order in which the nodes are detected are assigned as the priorities of the linking keys corresponding to the nodes. Accordingly, the priority (1) of the linking key Ka is the highest, and the priority (from 2 to 7) is given in the order of the linking keys Kb, Kc, Kd, Ke, Kf, and Kg. Note that although the node (Kd) and the node (Ke) are branched from the node (Kc), there is no protocol including both the linking key Kd and the linking key Ke. The same priority may be given to the attached key Ke. The same applies to the linking key Kf and the linking key Kg. Thereafter, this process is terminated.

  By performing the processing as described above, it is possible to specify an allocation pattern that satisfies a predetermined condition and minimizes the communication load, and furthermore, it is possible to appropriately determine the priority of the binding key. The tying process can be parallelized while suppressing the communication load of the tying processing units 117 to 121. Note that the linking processing units 117 to 121 may perform the linking process according to the key arrangement stored in the key arrangement storage unit 107. Further, the message distribution unit 115 may perform message distribution according to the key arrangement stored in the key arrangement storage unit 107 and the priority stored in the key priority storage unit 111.

  Although one embodiment of the present technology has been described above, the present technology is not limited to this. For example, the configuration shown in FIG. 6 is premised on being realized by a plurality of computers, but which component is mounted on which computer is arbitrary. For example, a plurality of linking processing units may be activated by one computer. Although FIG. 6 shows an example in which the number of tying processing units is three, the number of tying processing units is not limited to three.

  In the above description, the case where two linking keys are included in the message has been described as an example, but there may be cases where three or more linking keys are included. For example, FIG. 22A shows an example in which three linking keys are included. In this case, the process may be performed according to a structure as shown in FIG. Note that the link P1 in the structure of FIG. 22B represents a conceptual link connecting three points, not a general link connecting two points. That is, in FIG. 22B, the node (Ka) and the node (Kb), the node (Kb) and the node (Kc), and the node (Ka) and the node (Kc) are connected via the link P1. However, a loop is not formed by the node (Ka), the node (Kb), and the node (Kc). As described above, when three or more linking keys are included, the structure is expressed using a conceptual link. In this way, it is possible to cope even when three or more tying keys are included.

  Further, the configuration of each table described above is an example, and the configuration as described above is not necessarily required. Further, in the processing flow, the processing order can be changed if the processing result does not change. Moreover, you may make it perform in parallel.

  The present embodiment can be summarized as follows.

  This message linking processing method extracts each linking key from the key definition database that stores the linking key that is included in the message related to the protocol for each protocol and that is used in the message linking processing. A step of generating data of a structure including a node corresponding to each of the keys and a link connecting nodes of the tied keys belonging to the same protocol, and determining whether a loop is formed in the structure by the plurality of links An allocation that is a combination of a linking key allocation to each of a plurality of linking processing units that perform linking processing in cooperation with each other when it is determined that a loop is not formed in the structure. Among the patterns, a pattern that satisfies a predetermined condition including the first condition that the communication load between the linking processing units is the smallest Identified, and a pattern specifying step of storing allocation data relating to the identified allocation pattern in the key information storage unit.

  In this way, since the allocation pattern that minimizes the communication load between the linking processing units is specified, it is possible to parallelize the message linking processing while suppressing the communication load of the linking processing unit.

  Also, when it is determined that no loop is formed in the structure, a step of identifying one of the nodes regarded as a leaf node in the structure as a start node, and following the link from the start node in the structure The method may further include a step of detecting a node, assigning consecutive numbers in the order of detection as a priority of a linking key corresponding to the node, and storing the priority in a priority storage unit. In this way, since priority is given to each linking key along the link (that is, linking of linking keys), for example, when a message including a plurality of linking keys is received, If messages are assigned to a responsible linking processing unit according to a high linking key, message linking can be appropriately processed in parallel.

  Further, when it is determined that a loop is formed in the structure, for each of the plurality of links forming the loop, the link is considered to have been disconnected, and the steps after the determination step are performed. Further, it may be included. When the pattern specifying step described above does not store the allocation data and the communication load in the key information storage unit, the allocation data and the communication load related to the specified allocation pattern are stored in the key information storage unit. When the allocation data and the communication load are already stored in the key information storage unit, the key information is compared with the communication load related to the specified allocation pattern and the communication load stored in the key information storage unit. A step of updating the key information storage unit with the allocation data and communication load related to the specified allocation pattern when the communication load related to the specified allocation pattern is smaller than the communication load stored in the storage unit; It may be included. In this way, it is possible to cope with a case where a loop is formed in the structure.

  In addition, the pattern specifying step described above connects, for each allocation pattern, a linking key node in the linking processing unit and a linking key node in another linking processing unit for each linking processing unit. A step of counting the number of links and calculating a communication load by multiplying the number of links by a predetermined weighting value may be included.

  Furthermore, the predetermined condition described above may include a second condition regarding the operating rate of the linking processing unit.

  In addition, the pattern specifying step described above adds the communication load and the number of linking keys in the linking processing unit for each linking processing unit for each allocation pattern, and the processing amount of the linking processing unit And calculating the ratio of the processing amount to the processing capability of the linking processing unit as the operation rate.

  Furthermore, the condition regarding the operating rate of the linking processing unit may be a condition that the operating rates of the linking processing units in the allocation pattern are all within a predetermined reference value. As a result, for example, an allocation pattern in which processing is concentrated on a certain linking processing unit is not adopted even if the communication load is small, and more appropriate parallel processing can be performed.

  A program for realizing the above apparatus can be created, and the program is stored in a storage medium or storage device such as a flexible disk, a CD-ROM, a magneto-optical disk, a semiconductor memory, or a hard disk. The intermediate processing result is temporarily stored in a storage device such as a main memory.

  The computer used in the configuration shown in FIG. 6 has a display connected to a memory 2501 (storage unit), a CPU 2503 (processing unit), a hard disk drive (HDD) 2505, and a display device 2509 as shown in FIG. A control unit 2507, a drive device 2513 for a removable disk 2511, an input device 2515, and a communication control unit 2517 for connecting to a network are connected by a bus 2519. Application programs including the OS and the Web browser are stored in the HDD 2505, and are read from the HDD 2505 to the memory 2501 when executed by the CPU 2503. If necessary, the CPU 2503 controls the display control unit 2507, the communication control unit 2517, and the drive device 2513 to perform necessary operations. Further, data in the middle of processing is stored in the memory 2501 and stored in the HDD 2505 if necessary. Such a computer realizes various functions as described above by organically cooperating hardware such as the CPU 2503 and the memory 2501 described above with the OS and necessary application programs.

(Appendix 1)
Each linking key is extracted from a key definition database that stores a linking key included in a message related to the protocol and used in the linking process of the message for each protocol, and corresponds to each of the extracted linking keys Generating data of a structure including a link connecting nodes of the tying key belonging to the same protocol as the node to be
A determination step of determining whether a loop is formed in the structure by a plurality of the links;
When it is determined that no loop is formed in the structure, an assignment pattern that is a combination of assignment of the linking keys to each of a plurality of linking processes that perform the linking process in cooperation with each other. Among these, a pattern that specifies a pattern that satisfies a predetermined condition including a first condition that the communication load between the linking processing units is minimum, and stores allocation data related to the specified allocation pattern in a key information storage unit Specific steps,
Message linking processing program for causing a computer to execute

(Appendix 2)
If it is determined that no loop is formed in the structure, specifying any of the nodes regarded as leaf nodes in the structure as a start node;
The node is detected by tracing the link from the start node in the structure, and a consecutive number in the detected order is assigned as the priority of the linking key corresponding to the node, and stored in the priority storage unit Steps,
The message linking process program according to supplementary note 1 for causing the computer to further execute.

(Appendix 3)
When it is determined that a loop is formed in the structure, each of the plurality of links forming the loop is regarded as a link cut, and the processing after the determination step is performed. Is further executed on the computer,
The pattern specifying step includes
Storing the allocation data and the communication load related to the specified allocation pattern in the key information storage unit when the allocation data and the communication load are not stored in the key information storage unit;
When the allocation data and the communication load are already stored in the key information storage unit, the communication load related to the specified allocation pattern is compared with the communication load stored in the key information storage unit When the communication load related to the specified allocation pattern is smaller than the communication load stored in the key information storage unit, the allocation data and the communication load related to the specified allocation pattern Updating the key information storage unit with:
The message linking process program according to supplementary note 1 or 2 including:

(Appendix 4)
The pattern specifying step includes
For each of the allocation processing units, for each allocation pattern, the number of the links that connect the node of the association key in the association processing unit and the node of the association key in the other association processing unit is counted. The message linking processing program according to any one of appendices 1 to 3, further comprising: calculating the communication load by multiplying the number of the links by a predetermined weighting value.

(Appendix 5)
The message linking process program according to any one of appendices 1 to 4, wherein the predetermined condition includes a second condition related to an operation rate of the linking process unit.

(Appendix 6)
The pattern specifying step includes
For each of the allocation patterns, for each of the linking processing units, the processing load of the linking processing unit is calculated by adding the communication load and the number of linking keys in the linking processing unit, and the linking The message linking process program according to appendix 5, including a step of calculating a ratio of the processing amount to the processing capacity of the processing unit as the operation rate.

(Appendix 7)
The message linking process program according to appendix 5, wherein the second condition is a condition that all the operating rates of the linking process unit in the allocation pattern are within a predetermined reference value.

(Appendix 8)
Each linking key is extracted from a key definition database that stores a linking key included in a message related to the protocol and used in the linking process of the message for each protocol, and corresponds to each of the extracted linking keys Generating data of a structure including a link connecting nodes of the tying key belonging to the same protocol as the node to be
A determination step of determining whether a loop is formed in the structure by a plurality of the links;
When it is determined that no loop is formed in the structure, an assignment pattern that is a combination of assignment of the linking keys to each of a plurality of linking processes that perform the linking process in cooperation with each other. Among these, a pattern that specifies a pattern that satisfies a predetermined condition including a first condition that the communication load between the linking processing units is minimum, and stores allocation data related to the specified allocation pattern in a key information storage unit Specific steps,
A message linking processing method executed by a computer.

(Appendix 9)
Each linking key is extracted from a key definition database that stores a linking key included in a message related to the protocol and used in the linking process of the message for each protocol, and corresponds to each of the extracted linking keys A structure processing means for generating data of a structure including a link connecting nodes of the linking key belonging to the same protocol as the node to be
It is determined whether a loop is formed in the structure by the plurality of links, and when it is determined that a loop is not formed in the structure, a plurality of strings that perform the linking process in cooperation with each other A pattern satisfying a predetermined condition including a first condition that the communication load between the linking processing means is the minimum among the allocation patterns that are combinations of the linking keys assigned to each of the linking processing means; Pattern specifying means for storing allocation data related to the specified allocation pattern in a key information storage unit;
A message linking processing apparatus.

101 Server DB 103 Key definition DB
105 Key arrangement optimization unit 107 Key arrangement storage unit 109 Key priority determination unit 111 Key priority storage unit 113 Message reception unit 115 Message distribution unit 117, 119, 121 Association processing unit 1051 Structure processing unit 1053 Pattern specifying unit

Claims (5)

For each protocol, each of the linking keys is extracted from a key definition database that stores a linking key that is included in a message related to the protocol and is used in a linking process that is a process of associating messages related to the same transaction, and generating a node corresponding to each of the extraction the link key that is, a link connecting the nodes corresponding to the link key belonging to the same of the protocol, the data structure including,
A determination step of determining whether a loop is formed in the structure by a plurality of the links;
When it is determined that no loop is formed in the structure, an assignment pattern that is a combination of assignment of the linking keys to each of a plurality of linking processes that perform the linking process in cooperation with each other. Among them, an allocation pattern that satisfies a predetermined condition including a first condition that the communication load between the linking processing units is minimum is specified, and allocation data related to the specified allocation pattern is stored in the key information storage unit A pattern identification step;
Message linking processing program for causing a computer to execute If it is determined that no loop is formed in the structure, specifying any of the nodes regarded as leaf nodes in the structure as a start node;
The node is detected by tracing the link from the start node in the structure, and a consecutive number in the detected order is assigned as the priority of the linking key corresponding to the node, and stored in the priority storage unit Steps,
The message linking processing program according to claim 1, further causing the computer to execute. When it is determined that a loop is formed in the structure, it is assumed that each of the plurality of links forming the loop is disconnected, and the processing after the determination step is performed. Let the computer perform more steps,
The pattern specifying step includes
Storing the allocation data and the communication load related to the specified allocation pattern in the key information storage unit when performing the processing in the implementation step for the first time;
When the process in the implementation step is performed for the second time or later, the communication load related to the specified allocation pattern is compared with the communication load stored in the key information storage unit, and the key information storage unit When the communication load related to the specified allocation pattern is smaller than the stored communication load, the key information storage unit is updated with the allocation data and the communication load related to the specified allocation pattern And steps to
The message linking processing program according to claim 1 or 2, comprising: For each protocol, each of the linking keys is extracted from a key definition database that stores a linking key that is included in a message related to the protocol and is used in a linking process that is a process of associating messages related to the same transaction, and generating a node corresponding to each of the extraction the link key that is, a link connecting the nodes corresponding to the link key belonging to the same of the protocol, the data structure including,
A determination step of determining whether a loop is formed in the structure by a plurality of the links;
When it is determined that no loop is formed in the structure, an assignment pattern that is a combination of assignment of the linking keys to each of a plurality of linking processes that perform the linking process in cooperation with each other. Among them, an allocation pattern that satisfies a predetermined condition including a first condition that the communication load between the linking processing units is minimum is specified, and allocation data related to the specified allocation pattern is stored in the key information storage unit A pattern identification step;
A message linking processing method executed by a computer. For each protocol, each of the linking keys is extracted from a key definition database that stores a linking key that is included in a message related to the protocol and is used in a linking process that is a process of associating messages related to the same transaction, a node corresponding to each of the extracted the link key, and the structure processing means for generating a data structure comprising a link connecting the nodes corresponding to the link key belonging to the same of the protocol, and
It is determined whether a loop is formed in the structure by the plurality of links, and when it is determined that a loop is not formed in the structure, a plurality of strings that perform the linking process in cooperation with each other An assignment pattern that satisfies a predetermined condition including a first condition that a communication load between the association processing means is the minimum is specified among assignment patterns that are combinations of assignment of the association keys to each of the association processing means. Pattern specifying means for storing allocation data related to the specified allocation pattern in a key information storage unit;
A message linking processing apparatus.

Images