Note: Descriptions are shown in the official language in which they were submitted.
CA 02241881 1998-06-29
CA9-98-O l 6
REMOTE PROCEDURE CALLS IN DISTRIBUTED SYSTEMS
FIELD OF THE INVENTION
The present invention is directed to an improvement in distributed systems and
in particular to
remote procedure call messages between mufti-threaded processes in a
distributed system.
BACKGROUND OF THE INVENTION
Distributed computer systems involve different processes which may execute
simultaneously. The
processes may be found on physically distinct processors or the processes may
be implemented on
a single processor. In mufti-threaded distributed systems, each process may
run one or more threads.
Such distributed mufti-threaded, mufti-process systems are well known,
particularly in real time
processing applications such as systems for telephone control and management.
Mufti-threaded,
mufti-process distributed systems raise timing, scheduling, queuing,
synchronising and
interprocess/interprocessor communications issues which must be solved to
ensure that the
distributed system runs efficiently and effectively.
In mufti-threaded, mufti-process distributed systems, one characteristic
function made available in
the system is a remote procedure call (RPC) function. An RPC permits a process
in the distributed
system to request that a different process in the system carry out a function
implemented in that
second process and, return information to the process having originated the
RPC request. The RPC
is implemented by an RPC message being transmitted across the distributed
system such that the
responding process receives the RPC and takes the appropriate steps as defined
by the RPC message.
In distributed systems implemented using a TCP/IP protocol, the RPC will take
the form of a
TCP/IP-compliant message sent in accordance with the TCP/IP protocol.
In prior art mufti-processor, mufti-threaded systems, a thread which
originates an RPC will open a
1
CA 02241881 1998-06-29
CA9-98-O 16
communication channel (in the TCP/IP protocol, a socket) which will permit the
thread in the
process to communicate the RPC to a second process. Should there be several
threads which
originate RPCs, a corresponding number of channels, (or sockets) will be
opened to permit each
thread to communicate with the appropriate process. In such systems the
channel will remain open
until the response to the RPC is received by the originating thread, or the
channel will be opened and
closed for the transmittal of the RPC, and for the receipt of the RPC,
incurring the associated
operating system overhead cost.
In such prior art systems, it is typical that the thread and process
originating an RPC request will
make use of a central registry (or broker) which provides the identity of the
process able to respond
to the RPC to the process originating the RPC. A direct connection is then
established between the
originating process and the responding process to permit the RPC request
message to be
communicated from the originating process to the responding process and the
response to likewise
be communicated.
In a distributed system where the numbers of channels (or sockets) is a
constrained resource, it will
be appreciated that the use of a communication channel (or socket) by each
thread wishing to
originate an RPC, will create resource allocation, or operating system
overhead, problems for the
distributed system. In addition, the use of a central broker or registry
creates overhead problems for
such a distributed system.
It is therefore desirable to have an improved distributed system in which it
is not necessary for each
thread in the multi-threaded multi processing distributed system to request
allocation of a channel
(or socket) to permit the transmittal of an RPC message. Similarly, it is
desirable to have a system
which does not rely upon a central broker or registry of processes to be used
by the system to
determine which processes are appropriate to receive a given RPC message.
2
CA 02241881 1998-06-29
CA9-98-O 16
SUMMARY OF THE INVENTION
According to one aspect of the present invention, there is provided an
improved mufti-threaded,
mufti process distributed system.
According to a further aspect of the present invention, there is provided an
improved mufti-threaded,
mufti-process distributed system comprising a plurality of processes, each of
the said processes
comprising a plurality of threads and a means for receiving, composing, and
forwarding remote
procedure call messages, the distributed system comprising, a queue associated
with each of the
threads, each of the queues in each of the processes being associated with a
predetermined queue
identifier selected to uniquely identify each queue within each process, a set
of connections
selectively established between the processes, each one of the set of
connections being associated
with a predetermined connection identifier selected to uniquely identify the
connection with the
distributed processing system, the remote procedure call messages each
comprising, a first data
element corresponding to a selected one of the queue identifiers, and a second
data element
corresponding to a selected one of the connection identifiers.
According to a further aspect of the present invention, the improved mufti-
threaded, mufti-process
distributed system as set out above is provided in which the set of
connections consists of
connections characterized by each pair of processes selected from the
processes in the distributed
processing system having no more than one connection between the pair of
processes at any one
time.
According to a further aspect of the present invention, the improved mufti-
threaded, mufti-process
distributed system as set out above is provided in which a one of the remote
procedure call
messages, having been forwarded over a connection by a first one of the
processes, to a second one
of the processes, for forwarding to a third one of the processes, is
characterized by, its first data
element corresponding to the queue identifier of a one of the queues in the
second one of the
3
CA 02241881 1998-06-29
CA9-98-016
processes, and its second data element corresponding to the connection
identifier of the connection
from the first one of the process to the second one of the processes, and
wherein the one of the
remote procedure call messages, when composed by an originating one of the
processes, is
characterized by its first data element corresponding to the queue identifier
of an originating one of
the queues in the originating one of the processes, and its second data
element being set to a
predefined null value.
According to a further aspect of the present invention, the improved multi-
threaded, multi-process
distributed system as set out above is provided in which in each process the
means for receiving,
composing, and forwarding remote procedure call messages comprises update
means for modifying
the second data element in a received one of the remote procedure call
messages by storing, in the
second data element, the connection identifier of the connection by which the
received one of the
remote procedure call messages was forwarded to the process, means for
determining whether the
received one of the remote procedure call messages is processable within the
process, means for
processing the received one of the remote procedure call messages when the
selected one of the
remote procedure call messages is determined to be processable within the
process, means for
composing a remote procedure call message response when the selected one of
the remote procedure
call messages has been processed within the process, means for forwarding the
remote procedure call
message response by the connection indicated by the second data element of the
received one of the
remote procedure call messages, means for selecting, from the set of the
processes of the distributed
processing system, when it is determined that the received one of the remote
procedure call messages
is not processable within the process, a further different process for
processing the received one of
the remote procedure call messages, and means for forwarding the received one
of the remote
procedure call messages to the further different process, means for storing in
a data location local
to the process, the first and second data elements of the received one of the
remote procedure call
messages, means for updating the first data element of the received one of the
remote procedure call
messages to identify a one of the queues in the process.
4
CA 02241881 1998-06-29
CA9-98-O 16
According to a further aspect of the present invention, there is provided a
method for creating and
forwarding remote procedure call messages in a distributed processing system,
the distributed
processing system comprising a plurality of processes, each of the said
processes comprising a
plurality of threads and a means for receiving, composing, and forwarding
remote procedure call
messages, a queue associated with each of the threads, each of the queues in
each of the processes
being associated with a predetermined queue identifier selected to uniquely
identify each queue
within each process, a set of connections selectively established between the
processes, each one of
the set of connections being associated with a predetermined connection
identifier selected to
uniquely identify the connection with the distributed processing system, the
method comprising the
steps of
a) selectively establishing a set of connections between the processes in the
distributed
processing system, whereby a first selected process is connected to a second
selected process by no
more than one connection, and
b) forwarding one or more remote procedure call messages in the distributed
processing
system by storing, updating and referencing queue identifier and connection
identifier data in the
remote procedure call messages.
According to a further aspect of the present invention, the method as set out
above including the
steps of:
a) responding to an originating remote procedure call in a first thread in a
first process by
creating a remote procedure call message in the first process comprising
i) a first data element corresponding to the queue identifier of the first
thread, and
ii) a second data element being set to a predefined null value.
b) selecting a second process for receipt of the remote procedure call
message,
c) forwarding the remote procedure call message to the second process,
d) in the second process, modifying the second data element to correspond to
the connection
identifier of the connection between the first process and the second process,
5
CA 02241881 1998-06-29
CA9-98-016
e) in the second process, determining whether the remote procedure call
message is
processable within the second process,
f) when the remote procedure call message is determined to be processable
within the
process:
g) processing the remote procedure call message within the process,
h) creating a response in the remote procedure call message,
i) returning the remote procedure call message by the connection indicated by
the second
data element,
j)when it is determined that the received one of the remote procedure call
messages is not
processable within the process:
i) selecting, from the set ofthe processes of the distributed processing
system, a third
process for processing the remote procedure call message,
ii) storing in a data location local to the second process, the first and
second data
elements of the remote procedure call message,
iii) updating the first data element to identify a one of the queues in the
second
process, and
iv) forwarding the remote procedure call messages to the third process.
Advantages of the present invention include a mufti-threaded, mufti-process
distributed system in
which a single communication channel between processes may be utilised to
communicate RPC
messages from different threads within the same process. Further advantages
include a multi-
threaded, mufti-process distributed system which maintains the information
relating to which process
is appropriate to respond to a given RPC, within the originating process,
rather than at a central
broker or registry.
BRIEF DESCRIPTION OF THE DRAWINGS
The preferred embodiment of the invention is shown in the drawings, wherein:
6
CA 02241881 1998-06-29
CA9-98-O 16
Figure 1 is a flow diagram showing the path of an RPC in the distributed
system of the
preferred embodiment of the invention;
Figure 2 is a block diagram showing the high level functional components, and
communication paths, in the distributed system of the preferred embodiment of
the invention.
In the drawings, the preferred embodiments of the invention are illustrated by
way of example. It
is to be expressly understood that the description and drawings are only for
the purpose of
illustration and as an aid to understanding, and are not intended as a
definition of the limits of the
invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Referring to Figure 1, there is illustrated in a flow diagram, the path an RPC
request message in the
distributed system of the preferred embodiment of the invention, from Process
1 through Process N.
The example of the preferred embodiment in Figure 1 includes a functional
block 10 which
originates the RPC request message, a block 12 which receives the RPC request
message of block
10 and forwards the RPC request message to functional block 14, which receives
the RPC request
message and functional block 16 which receives and responses to the RPC
request originated in
functional block 10. The functional block 16 which responds to the RPC request
message passes
an RPC response message back to Process N-1 which, in functional block 18
passes the RPC
response message to the previous process. Upon receipt of the RPC response
message by Process
2, functional block 20 passes the RPC response message to Process 1 which
originated the RPC
request message, initially.
In Figure 2, a block diagram shows the processes of the distributed system of
the preferred
embodiment of the invention. Figure 2 shows block 30 representing Process l,
block 32
representing process 2A, block 34 representing process 3 and block 36
representing process 2B.
Process 1 of block 30 is shown including threads and associated queues for the
threads. Thread and
7
CA 02241881 1998-06-29
CA9-98-016
queue pair 1 is shown in block 40, thread and queue pair 2 is shown in block
42 and thread and
queue pair n is shown in block 44. Similarly, with respect to process 2A shown
in block 32, the
threads and associated queue pairs l, 2...n are indicated as blocks 46, 48 and
50. For process 3,
shown in block 34, the thread and queue pairs are shown as block 52, 54 and
56. Finally, process
2B, shown in block 36 has thread queue pairs 1, 2... n as reflected in blocks
58, 60 and 62.
Process 1 is shown containing a thread and queue pairing responsible for
message receipt in block
70. The transmission of an RPC message from Process 1 may be accomplished the
block 70
including, or having associated with it, a functional component responsible
for sending messages.
Process 2A in block 32 is shown as having a message thread and associated
queue T/Qa in block 72,
thread and queue T/Qb in block 76 and thread and queue T/Qc in block 78.
Similarly, process 3 in
block 34 has message thread and queue T/Qa in block 80 and T/Qb in block 82.
Process 2B in block
36 has a message thread and queue T/Qa in block 84 and T/Qb in block 86.
In the example distributed system of the preferred embodiment, as illustrated
in Figure 2, the
connections between the processes are shown as connection 90 between Process 1
and process 2A,
connection 92 between the process 2A and process 3, connection 94 between
process 3 and 2B, and
connection 96 between process 2A and 2B.
Within process 2A is illustrated a dispatcher thread and associated queue,
shown in block 100.
Process 3 is shown as having a dispatcher thread and queue in block 102.
As will be appreciated by those skilled in the art, the numbers of threads
found in each process will
vary depending on the application. The thread and queue pairs, in blocks 40,
42, 44 as shown in
Process 1 are referred to as worker threads in the example of the preferred
embodiment. Such
threads are involved in the parallel processing of RPC request and response
messages. Similarly the
thread and queue pairs shown in blocks 46, 48, 50, 52, 54, 56, 58, 60 and 62
are worker threads and
8
CA 02241881 1998-06-29
CA9-98-O 16
queues in the illustrated example of Figure 2. A thread will be blocked, or
suspend its operation, in
waiting for the associated queue to receive a message.
Each thread and queue has an associated identifier (queue id) which is unique
within the process in
which the thread is found. In the example of the preferred embodiment the,
queue id is referred to
by the variable hQueue. As indicated above, each process may have one or more
message receiver
threads each which is responsible for receiving messages from connections made
between the
process and other processes in the distributed system. The dispatcher thread,
as shown in blocks 100
and 102, in each process is responsible for passing an RPC request message to
the appropriate
available thread from the pool of worker threads within the process to permit
the RPC message to
be processed. Alternatively, the worker thread receiving the RCP message may
indicate that
message is not in the appropriate process within the distributed system to
handle the RPC request
and that the RPC message is to be forwarded to another process.
As shown in Figure 2, each process may be connected to one or more processes,
but each process
is connected to any one process via a single connection, only. Associated with
each of the
connections in each of the processes is a connection identifier (a connection
id), referred to in the
preferred embodiment by the variable hConn).
In the preferred embodiment of the invention, each process contains a data
table or similar data
structure to permit the process to determine which of the other processes in
the distributed system
will be appropriate to receive a given RPC request. In the preferred
embodiment, it is not essential
that the process identified as being able to respond to a given RPC in the
data structure of the process
originating the RPC request in, in fact, able to directly respond to the RPC.
For example in Figure
2, Process 1 may contain data which indicates that process 2A of block 32 is
able to functionally
respond to a given RCP request. In fact, process 2A may respond to that RPC
request by passing
the RPC request on to process 3 shown in block 34. In such a case, process 2A
of block 32,
9
CA 02241881 1998-06-29
CA9-98-016
maintains within it a data structure which indicates that it is process 3 of
block 34, and not process
2B of block 36, which has the functionality to respond to the given RPC
request.
In the distributed system of the preferred embodiment of the invention, the
RPC messages contain
within them at anyone time, a value for hConn and hQueue which permits the RPC
request and
response to be efficiently passed through the distributed system to permit the
RPC request to be
responded to and the response to be communicated to the originating process.
In the example distributed system illustrated in Figure 2, the Process 1 of
block 30 which originates
an RPC request creates the RPC request message and encodes as part of the
message the hQueue
value reflecting the thread in the originating process which is blocked as a
result of initiating the
RPC request. In the example of Figure 2, a thread such as block 42 will create
an RPC request
message and the message thread of block 70 (or an associated component having
a send function)
will forward the RPC request message over connection 90 to process 2A of block
32. Message
thread of block 72 receives the RPC request and dispatcher thread of block 100
determines whether
any of worker threads of blocks 46, 48 or 50 are able to respond to the RPC
request.
When the RPC request message is forwarded via connection 90, the hConn value
of the RPC request
is set to null. As indicated above, the hQueue value in the RPC message is set
to the queue id value
of the thread which originated the RPC request (in the example the queue id of
the queue of block
42).
The message receiver thread of block 72, upon receiving the message, updates
the hConn value to
the connect id of connection 90. The dispatcher thread shown in block 100
determines which of the
worker threads found in process 2A of block 32, is appropriate to handle the
RPC request message.
The message is placed in the appropriate queue relating to the thread which
can handle the request.
If the RPC request is processed directly by that thread, the RPC response is
returned to Process 1 of
CA 02241881 1998-06-29
CA9-98-016
block 30 via connection 90. The correct connection is determined by reference
to the hConn value
found in the RPC message. The message receiving thread of block 70 receives
the RPC response
message. The hQueue value determines on what queue the message thread will
place the RPC
response message. In this manner, the RPC message is sent to process 2A from
Process 1 and
returned to Process 1 from process 2A.
In a case where an RPC request message is determined by the worker thread of
Process 2A to be one
which is not processable by that worker thread, the worker thread will
determine from data stored
in process 2A which other process in the distributed system will be able to
deal with the RPC
request. The RPC request message is then placed on the appropriate queue for
transfer to a further
process. For example, the RPC message in process 2A of block 32 can be placed
in queue Qc shown
in block 78 for transfer to process 3 of block 34 via connection 92. The
message thread, or
associated send function block, sends the RPC request message over connection
92 to process 3
where message thread in block 80 receives the message.
Before the RPC message is forwarded by process 2A of block 32, the hConn value
and the hQueue
values of the message as it was received by the message thread of block 72,
are stored in local
memory in process 2A. The hConn value in the RPC request message is updated to
reflect the
connection identifier of connection 92, by Process 3 of block 34. The hQueue
value of the RPC
request message is also updated to reflect the worker queue id in the process
2A of block 32 which
has processed the RPC request message to determine that it is not one which
can be dealt with
functionally in process 2A of block 32.
The RPC message which is communicated from process 2A to process 3, therefore
has an updated
hConn value and an updated hQueue value. Process 3 can deal with the message
in the same manner
as process 2A dealt with the message. If process 3 is able to process the RPC
request and create an
RPC response message, that message is sent back to process 2A over the
connection identified in
the RPC message, in this case connection 92. The RPC response message, when
received by process
11
CA 02241881 1998-06-29
CA9-98-016
2A will be directed to the queue identified by the hQueue variable in the RPC
response message.
The associated thread then resets the value of hConn and hQueue as stored in
its local memory, to
permit the message to be passed back to Process 1 over connection 90 to be
received by the message
thread of block 70 for transfer to the appropriate queue in Process 1 as
indicated in the restored
hQueue value of the RPC response message.
As shown in Figure 2, there are also connections established between process
2A and process 2B
(via connection 96) and process 2B and process 3 (via connection 94).
The RPC message may be originated from any of the processes shown in Figure 2,
for example. The
RPC request message will be routed to the appropriate process, by way of the
mechanism shown
above, by which the hQueue value and hConn values are updated and previous
hQueue and hConn
values stored locally by the appropriate thread, to permit the RPC to move
through the distributed
system.
As will be appreciated by those skilled in the art, this system may be used
where the mufti-threaded,
mufti process distributed system is implemented using different operating
systems and
communication protocols. For example, the distributed system of the invention
may be included in
a mufti-threaded, mufti-process distributed system in which the threads in the
processes are not
implemented with associated queues. In such a case, the remote procedure call
messages will
include identifiers which correspond directly to the appropriate threads, and
not to queues related
to the threads. Although the preferred embodiment of the invention describes
the invention as
implemented in a system which incorporates a queue for each thread this
characteristic is not
essential for the working of the invention.
The distributed system of the invention permits only one connection being
established between pairs
of processes in the mufti-process distributed system. Different RPC messages
can be transmitted
12
CA 02241881 1998-06-29
CA9-98-O 16
over the same connection between processes. The connections (in the TCP/IP
protocol, the sockets)
are established on a process to process basis rather than on a thread to
thread basis.
As has been described above, each process must maintain a data structure which
reflects which
process is able to respond to a given RPC request. The data is stored locally
in each process and
because RPC messages are forwarded through the distributed system, it is
possible for processes to
notionally perform a function where, in fact, the function is performed by
another process. In other
words, it is not necessary to update the information as to which process
handles a particular function,
even when the structure of the system is changed, as long as the correct
pointers are in place in the
various processes to permit the RPC messages to be routed through the
distributed system to
ultimately reach the appropriate process and thread.
Although a preferred embodiment of the present invention has been described
here in detail, it will
be appreciated by those skilled in the art, that variations may be made
thereto, without departing
from the spirit of the invention or the scope of the appended claims.
13
