TK1: Distributed Systems -

Programming & Algorithms

Chapter 2: Distributed Programming
Section 1: Mainstream Paradigms
Subsection 2:Remote Procedure Call (RPC)
Lecturer: Prof. Dr. Max Mühlhäuser
Remember Pragmatic Taxonomy
all in one, we get the following taxonomy for
distributed systems (DistSys) application development:

DistSys application development

OS ap DB ap protocol programming
proach proach approach approach

pull mobile push

code

IPC RPC DOC Publish/ Tuple Virtual

(msg passing, (→ C/S) (→ Web mobile Agents Subscribe Spaces Shared
msg queues) Services)
objects (→ CEP) Memory
‘mainstream’ ‘advanced’
Computing@Internet
(Cloud → EdgeCloud → INP)

TK1-2.1.2 Mainstream Paradigms - RPC 2

Inter Process Communication (IPC) revisited
A) Message passing …
▪ Sending messages between programs / processes
▪ Explicit communication

A1) Sockets
▪ „The message passing API for the Internet”
▪ 2 Predominant Internet Socket Types
▪ Connection-less (UDP) / Connection-oriented (TCP)
▪ → programmer must deal with Internet layer 4
A2-3) other protocols, DPL & middleware

In the Remainder: Short Look at Message Queues!

▪ Persistent queues
▪ De-coupling (asynchronous, indirect)
▪ Layer 7
B1) AMQP
TK1-2.1.2 Mainstream Paradigms - RPC 3
2.1: Mainstream Paradigms
(1) IPC: Interprocess Communication
(2) RPC: Remote Procedure Call

TK1-2.1.2 Mainstream Paradigms - RPC 4

Part I: RPC in a nutshell

TK1-2.1.2 Mainstream Paradigms - RPC 5

Remote Procedure Call (RPC)
Fundamental idea behind RPC:

Processes can call procedures on other computers

▪ Goal: syntactic and semantic uniformity of local and remote calls in terms of:
▪ Call mechanism
▪ “Expressive power“ of language
▪ Error handling
▪ Goal cannot be fully achieved

Note: Regardless of problems, RPC is widely used in the computation world

TK1-2.1.2 Mainstream Paradigms - RPC 6

RPC: Principle
client blocks

call receive reply

Client

request reply

Server
accept return reply

server executes procedure

▪ Code in client: Internet,
ISO layers Middleware
Set out-parameters
Call X(out-parameters,result)
L.7 application application

Use result
L.6 presentation rep.
L.5 session rpc
▪ Code on server:
L.4 transport transport
Proc X(parameters)
Do stuff rep.: common data representation
Return (result) rpc: rpc protocol (very simple L.5)

TK1-2.1.2 Mainstream Paradigms - RPC 7

RPC Control Flow
client node server node
net
user client stub runtime sys. runtime sys. server stub server
local call packet receive
pack transmit unpack call
call argument argument
wait work

result

importer exporter L.4 protocol importer exporter

RPC protocol
Color coding: Client code Middleware Server code
▪ Steps 1—5:
1. The client procedure calls the client stub in the normal way.
2. The client stub builds a message and forwards it to the RPC runtime system (*), which transmits it using an RPC protocol and the
underlying transport system / layer (L.4); (*: the RPC runtime system / protocol may be implemented as part of the stub code).
3. The client and server TS organize the L.4 message transfer to the server node
4. The remote RPC runtime system forwards the message to the server stub
5. The server stub unpacks the parameters and calls the server

TK1-2.1.2 Mainstream Paradigms - RPC 8

RPC Control Flow
client node server node
net
user client stub runtime sys. runtime sys. server stub server
local call packet receive
pack transmit unpack call
call argument argument
wait work

result

importer exporter L.4 protocol importer exporter

RPC protocol
Color coding: Client code Middleware Server code

▪ Steps 6—10:
6. The server does the work and returns the result to the server stub.
7. The server stub packs it in a message and forwards it to the RPC runtime system, where
8. … it is transmitted following the RPC protocol and using the L.4 (transport) service
9. Via the client side L.4 and RPC runtime system, the message gets to the client stub
10. The client stub unpacks the result and executes the “return” of the local call to the client

TK1-2.1.2 Mainstream Paradigms - RPC 9

RPC: Basic Properties
Basic Properties (in simplest & ideal form of RPC):
▪ Synchronous communication (caller blocked until callee is done)
▪ Only one (~“atomic”) call needed to access remote procedure & get result
▪ Other approaches (e.g., IPC) require more
▪ System takes care of all “small details”
▪ Message assembly and disassembly, etc.
▪ Complexity same as normal procedure call
▪ Only one call in progress at a time
▪ Transparent to distribution
▪ As long as client can find a server, it does not matter where it is

TK1-2.1.2 Mainstream Paradigms - RPC 10

RPC: Basic Functionality
Basic functionality of core RPC middleware (including stubs, [IDL/pre-]compiler see below):
1. Binding: “find appropriate server”
(ex-/implicit, may involve trader)
2. Stub generation and (pre)compiler support (IDLs: Interface Definition Languages)
(stubs take over most work done by IPC programmers before!)
▪ Within stub & runtime support:
3. Marshalling / Unmarshalling
pack and unpack call (proc_name, parameters) and result, cope with complex data structures (see below)

4. Presentation (L.6: translate between heterogeneous OS / [Link]. / HW)

5. RPC Protocol and error handling → enforcement of “failure semantics”, see below
TK1-2.1.2 Mainstream Paradigms - RPC 11
Part II: RPC Binding, Stubs & IDLs,
Marshalling & Presentation

TK1-2.1.2 Mainstream Paradigms - RPC 12

RPC: Binding
▪ Binding matches Clients and Servers in 2 steps:
▪ Locate the server’s node (computer / IP address)

▪ Locate the server on that computer

▪ Binding may distinguish just name of server or more (up to: program, version, protocol, …)

▪ Three possibilities
1. Static (at compilation time): fast, no middleware overhead

2. Semi-dynamic (at startup time): via logical name or DB or multicast or broker/directory/trader service

3. Dynamic (= per call); like semi-dynamic, but adds: fault tolerance, load balancing

TK1-2.1.2 Mainstream Paradigms - RPC 13

RPC: Binding
▪ Binding via intermediate service (“trader”, “broker”, “directory” service):
▪ cf. “yellow pages” (search via attributes, description) → considered ‘powerful’, but …
▪ may become a bottleneck
▪ expensive (execution time, triangle communication)

TK1-2.1.2 Mainstream Paradigms - RPC 14

RPC: Binding

TK1-2.1.2 Mainstream Paradigms - RPC 15

RPC: Binding Examples
Binding for (rather simple) Internet RPC (e.g., based on SUN-RPC / XDR):
▪ “you are supposed to know your RPC server node” (IP address); then: use port mapper rpcbind:
▪ Name service for RPC servers on server node: port #111
▪ Server registers program & version numbers with local port mapper (rpcbind)
▪ Check out all registered RPC servers with: rpcinfo –p
▪ when client calls clnt_create, a standardized RPC request is sent to
server’s port mapper, asking for info for given program, version, & protocol
▪ this RPC request returns server’s port number to client

For Java: “You’re supposed to know your URLs”

For Corba:
▪ May use naming service to translate logical name
▪ May use trader service for yellow pages
TK1-2.1.2 Mainstream Paradigms - RPC 16
RPC: Stubs
▪ Stubs:
▪ Mimic local procedure call, hide “networking”
▪ Pack / unpack messages (call, reply, ...): Marshalling
▪ May convert to / from network data representation
▪ Support mapping from client to server: Binding
▪ Binding usually initiated outside stubs
▪ If not ‘outsourced’ to separate RPC runtime system: carry out RPC protocol
▪ Client stub is proxy for server at client side
▪ Server stub is proxy for client at server side
client node server node
net
user client stub runtime sys. runtime sys. server stub server
local call packet receive
pack transmit unpack call
call argument argument
wait work

result

importer exporter L.4 protocol importer exporter

RPC protocol Color coding: Client code Middleware Server code

TK1-2.1.2 Mainstream Paradigms - RPC 17

RPC: IDLs
▪ Automatic generation of stub code: stub compiler struct Person { Typical IDL
string name;
example
▪ Basis: IDL (Interface definition language) string place;
long year;
▪ Specify the interface between client and server };

▪ One middleware-specific extension to interface AddressBook {

void addPerson(
many programming languages in Person p);
void getPerson(
▪ Corba-IDL, DCE-IDL, SUN’s XDR (external data rep.), in string name,
XML, Google ProtoBuf out Person p);
long size();
▪ May use libraries in order to insert code for: };
format conversion, marshalling, transmission control, ...
/* SearchRequest represents a search query, with pagination ProtoBuf example
* options to indicate which results to include in response. */

message SearchRequest {
Note: tags managed by developer 
required string query = 1;
optional int32 page_number = 2; // Which page number do we want?
optional int32 result_per_page = 25; // Number of results to return per page.
}
TK1-2.1.2 Mainstream Paradigms - RPC 18
RPC: Marshalling and Presentation
▪ Marshalling challenge: Flatten (serialize) complex / dynamic data structures
▪ Basic data types plus structure/type info.—challenging (unbounded data, rings …)
▪ Full flexibility/dynamics → complex, verbose tags/representations (see ISO ASN.1/BER)
▪ Accommodate presentation
in different OSes, languages, and hardware architectures:
▪ integer (size?, 1’s /2’s complement?) / float / real (size?, IEEE?, ...)
▪ character (ASCII, unicode?) / string (`\0´ end-flag or byte-count?)
▪ array (row- /column-based), struct / union / set ... (organization?)
▪ Issues like little-endian vs. big-endian, bit order (MSB→LSB or inverse)

▪ Worst-case: n systems → need ~n2 conversions

▪ Reality: Often 2 possibilities (next slides)
TK1-2.1.2 Mainstream Paradigms - RPC 19
RPC: Marshalling and Presentation
Two possibilities:
1.“Receiver makes it right”
▪ Mark representation type
▪ Between client and server with same representation, no need for translation
(80% of the cases?)
[Link] syntax (IDL, or ISO ASN.1) plus:
standardized network data representation
▪ For ISO-ASN.1 (abstract syntax notation #1): called BER (basic encoding rules)
▪ For SUN-XDR: same name as for IDL, adopted by DCE
▪ For Corba-IDL: CDR (Common data representation)
▪ For Java-RMI: “Java serialized form”
▪ For XML RPC: XML

TK1-2.1.2 Mainstream Paradigms - RPC 20

Marshalling: CORBA
IDL example: Common Data Representation (CDR):
struct Person {
string name; struct with value: {‘Smith’, ‘London’, 1934}
string place; index in notes
sequence of bytes 4 bytes on representation
long year;
}; 0–3 5 length of string
4–7 "Smit" ‘Smith’
interface AddressBook { 8–11 "h___"
12–15 6 length of string
void addPerson(
in Person p); 16–19 "Lond" ‘London’
20-23 "on__"
void getPerson(
24–27 1934 unsigned long
in string name,
out Person p);
• Primitive types: short…double, char, bool
long size();
}; • Written in sender’s byte order
• Constructed types: sequence, string, array, struct, enumerated, union
ProtoBuf Wire format is very compact!
• No structural info in CDR, since both sides know from IDL “what comes next” in msg.
… but at the price of letting the • BER (from ASN.1) carries both length and data type info. (besides data i.e. ‘content’)
programmer account for tag numbers

TK1-2.1.2 Mainstream Paradigms - RPC 21

Part III: RPC Protocols, Errors, & Failure Semantics

TK1-2.1.2 Mainstream Paradigms - RPC 22

RPC: Protocols
▪ Must realize three functions:
▪ client: do_operation (callee, op_id, *in_args)
▪ server: getRequest(...) and sendReply (caller, *results)
▪ Possible errors:
▪ (1) request omission, (2) reply omission (both mean: lost messages)
▪ (3) server crash, (4)client crash
▪ Error handling:
▪ Omissions may be masked, but …
tradeoffs: „stateful server“ (&client), protocol overhead … see below
▪ Server crash commonly not masked (maybe via “dynamic binding”)
▪ Distinguish two kinds of RPC protocols
▪ RR: request-reply
▪ RRA: request-reply-ack (ACK by client!)
TK1-2.1.2 Mainstream Paradigms - RPC 23
RPC Errors: Request Omission
Request omission:
▪ 1st obvious countermeasure: set timeout!
▪ In case of timeout → resend request
▪ However, 4 possible cases:

1 2
?

3 4

▪ Server must recognize duplicate requests →Unique ID for requests

▪ Server must keep state (memorize IDs)
▪ length of state-keeping time determines residual error probability

TK1-2.1.2 Mainstream Paradigms - RPC 24

RPC Errors: Reply Omission
▪ For client, indistinguishable from request omission & delays
▪ Same countermeasure as for request omission (timeout)
▪ For server, means to memorize results,too, for potential 2nd reply
▪ More states, more memory, especially if parallel calls per client
▪ Also scalability problem: What if server has thousands of clients?
▪ Now we see why request-reply-ack (RRA) makes sense:
▪ If client acknowledges reception of reply, server can throw away stored result
timeout

Client

reply
Server

TK1-2.1.2 Mainstream Paradigms - RPC 25

RPC Errors: Crashes
Server crash: crucial question is “how far did it get?”
▪ How to distinguish from omissions (via n timeouts with “sufficiently large” n?)
▪ If another server takes over, how should it know the progress of failed server?
▪ For restart, how to cope with locks, dirty states, information recovery?

timeout
Client
request no reply
Server
crash!

Client crash: may lead to server executing an “orphan”, whereby …

▪ … procedure execution maybe erroneous, “costly” if lengthy, ...
▪ Restarted client should not be puzzled by orphan-results
▪ … and might even tell server to stop them?
▪ Note: for lengthy procedures, server may poll client (still alive?)
TK1-2.1.2 Mainstream Paradigms - RPC 26
RPC Failure Semantics
1. Maybe Semantics: No repeated requests (replies, ...)
▪ Simple, fast, efficient but often not sufficient
▪ Idea: User will try again in case of failure (check email, ...)
2. At-Least-Once Semantics: Infinite retry
▪ Repeated requests, but stateless servers (no duplicates recognized)
▪ Restricted to idempotent operations (basically, “read”-operations)
3. At-Most-Once Semantics: Tolerate omissions
▪ Repeated requests & replies, duplicates recognized → execute only once
▪ Server crash → no result (no reply), server may have executed or not
4. Exactly-Once Semantics: Tolerates crashes
▪ For normal commercial RPC systems, this remains a dream
▪ Transactional systems, fail-safe solutions needed
▪ Solutions above in order of increasing effort
▪ Offer the choice to programmer
▪ Commercial systems usually offer some choice of 1/2/3
▪ In summary: Forget transparency, accept: RPC  local calls

TK1-2.1.2 Mainstream Paradigms - RPC 27

RPC: Failure Semantics
Type of for absence in case of in case of
Error Sem. of errors omissions [Link]

maybe 1 proc-exec. 0|1 proc-exec. 0|1 proc-exec.

1 result 0 results 0 results
returned returned returned
at-least- 1 proc-exec. 1 proc-exec. 0 proc-exec.
once 1 result 1 result 0 result
returned returned returned
at-most- 1 proc-exec. 1 proc-exec. 0|1 proc-exec.
once 1 result 1 result 0 results
returned returned returned
exactly- 1 proc-exec. 1 proc-exec. 1 proc-exec.
once 1 result 1 result 1 result
returned returned returned

▪ Exactly-once: can be approached via redundancy, but expensive!

TK1-2.1.2 Mainstream Paradigms - RPC 28
Part IV: Asynchronous RPC

TK1-2.1.2 Mainstream Paradigms - RPC 29

RPC: Asynchronous Calls
▪ ... Note: parallelism is ‚natural‘ in DistSys (e.g., parallel loading of images in http) …
▪ ...and a nightmare for RPC (wrt. transparency, statefulness, ...)
Serialised invocations Concurrent invocations
example: process args process args
marshal marshal
comparison for Send transmission Send
process args
just two calls marshal
Send Receive
Receive
unmarshal
;( unmarshal
exec ute request exec ute request
marshal marshal
Send Send
Receive
unmarshal
Receive Receive exec ute request
unmarshal unmarshal marshal
process results process results Send
process args
marshal Receive
Send
unmarshal
process results
Receive time
unmarshal
exec ute request
marshal
Send

Receive
unmarshal
process results
Client Server Client Server
TK1-2.1.2 Mainstream Paradigms - RPC 30
RPC: Asynchronous Calls

synchronous asynchronous
(discussed up to now)

TK1-2.1.2 Mainstream Paradigms - RPC 31

RPC: Asynchronous Calls

(b), continued

TK1-2.1.2 Mainstream Paradigms - RPC 32

RPC: Asynchronous Calls
▪ Why client side multithreading for RPC? Enables asynchronous calls! (similar arguments in other DistSys)
▪ Asynchronous Call: how to realize?
1. Asynch. RPC, result obtained by callback … (→ ‘callback hell’, same for asynchronous RPC)
2. Synch. RPC: “join” in multi-threaded language (fork/join in parallel programming language)
… or: polling (more flexible but less ‘elegant’)
3. Via compiler support (futures / promises, see below)
client client
start new thread start new thread

caller caller
or: fork/join in
parallel [Link].
remote remote
call call

join polling

TK1-2.1.2 Mainstream Paradigms - RPC 33

RPC: Parallel Handlers
▪ Why server side multithreading for RPC? Enables parallel handlers
▪ E.g., an earlier compute-intensive RPC will not delay a later ‘short’ RPC

server
new thread
incoming
calls
handler handler handler

TK1-2.1.2 Mainstream Paradigms - RPC 34

RPC: Futures
▪ Example from SCALA

TK1-2.1.2 Mainstream Paradigms - RPC 35

Inlet: Concurrency
What?
▪ Traditionally, concurrency was issue of OS
▪ Became issue of concurrent languages when threads were introduced there, too
▪ Thread: light-weight process
▪ Has own registers & stack, but not own address space (well, maybe TLS: thread local storage)
▪ ‘coroutines’, ‘blocks’ don’t have separate registers & stack (usually; meanwhile, terminology is blurred)
▪ Much shorter creation time than processes
▪ Threads in same process / on same VM → much more efficient synchronization concepts
▪ Reduced „security“ (same user address space)
Why here?
1. Parallelism essential for DistSys
▪ DistSys is inherently parallel
▪ E.g., we’ll receive RPC requests in parallel to the main control flow
2. Concurrency models to be „inherited“ into DistSys?
▪ Yes: Monitor, Semaphor, Lock “& friends”

TK1-2.1.2 Mainstream Paradigms - RPC 36

Concurrency: Problems
(for your records/understanding only; should be known)

▪ Deadlock
▪ 2 processes are waiting for each other to complete before proceeding → both hang!
(>2 processes: wait conditions interwoven in ring / graph).
▪ Classical example (assume concurrent, ‘almost parallel’ execution of P1 & P2):
▪ P1: lock(X); lock(Y); … unlock(Y); unlock(X) || P2: lock(Y); lock(X); … unlock(X); unlock(Y); (Solution for classical example: define order for locks)
▪ Four necessary conditions for deadlocks (Coffman et al. 1971):
1. Usage of claimed resource is exclusive
2. Multiple resources can be claimed
3. Claimed resources cannot be forcibly removed
4. A circular chain of dependencies exist
▪ Livelock / Starvation
▪ ≥ 2 processes continually change state in response to changes in the other processes, without real progress → none of them will complete.
▪ Unfairness
▪ Fairness: related to scheduling, concerned w/ guaranteeing the processes get a (fair?) chance to proceed
(just the chance is called liveness; some form of ‘sufficiently fast/often’ [in relation to others] is called fairness, cf. chapter 3)
▪ Race Conditions
▪ In this context here, defined to be a timing-related flaw in a system: result (/termination) of a computation
depends unexpectedly & critically on the sequence or timing of events
▪ Race conditions arise not because of message delay per se, but because of varying processing/scheduling/transmission timings

TK1-2.1.2 Mainstream Paradigms - RPC 37

Concurrency: Synchronization
▪ Monitor (according to Tanenbaum; terms in literature not 100% consistent)
▪ Programming-language construct
▪ A monitor is a „module“ (e.g., object in O-O) containing variables and procedures
▪ Variables can only be accessed via procedures (data encapsulation)
▪ If process A executes a procedure (enters the monitor), then:
a process B trying to execute a procedure of the same monitor, will be blocked until A exits.
▪ Every Java object has a built-in monitor lock: use synchronized, e.g.:
public class CountingIntMonitor {
private int value;
public synchronized int value() { return value; }
public synchronized void increment() { value = value + 1; }
}

▪ Synchronized has two effects:

▪ Concurrent invocations cannot interleave
▪ Establishes a happened-before relationship with any subsequent call
▪ guarantees that changes to object state are visible to all threads
TK1-2.1.2 Mainstream Paradigms - RPC 38
Block-level Concurrency
▪ Finer-grained concept than threads
▪ Use block objects and execution queues instead of threads
▪ reduced memory penalty: blocks don’t have separate stack (→ no recursion!)
▪ less overhead: No thread creation / cleanup / synchronization; simpler scheduling
▪ Examples
▪ Apple Grand Central dispatch Path Expressions: explicit notation
▪ Support for block objects in C, C++, and ObjC
▪ Unified dispatch method for CPUs and GPUs for sequential / parallel execution
▪ Microsoft .NET Task Parallel Library (TPL) a
▪ Support for Action objects = lambda expressions

a(); b c
[Link](
() => { b(); d(); },
() => { c(); [Link]( d e f
() => e(),
() => f()); g(); g
});
h(); h

TK1-2.1.2 Mainstream Paradigms - RPC 39

RPC: Known Issues
RPC is not equal to local procedure call:
▪ vast area of error semantics & error control vs. all-or-nothing
▪ separate address spaces → how are parameters/return values passed?
▪ call by value/copy … /reference?
▪ request/reply vs. request/reply/restore
▪ serialization, ability to „transmit“ complex data structures (list? tree? w/ ref’s?)
▪ (usually) no support for variable parameter lists
▪ (usually) no support for pointers as parameters
▪ lack of shared variables (→ of side effects)
▪ lack of performance transparency
▪ WANs: extremely long and varying response times
▪ performance degradation via indirections (traders, ORBs, software busses, etc.)
▪ overhead for marshalling, serialization, etc.
▪ problems w/ mass data, multimedia
▪ security aspects
▪ integrate authentication, authorization, key exchange w/ binding?
TK1-2.1.2 Mainstream Paradigms - RPC 40
RPC: Summary
▪ Powerful tool for medium sized problems
▪ “Does the plumbing for you”
▪ Stubs, Marshalling, Binding etc.
▪ Good libraries for most languages
▪ Beware: substantial differences between local and remote calls
▪ Syntactic equality is doable, semantic equality remains a ‘marketing ploy’
▪ RPC deemed outdated (mobile objects, advanced paradigms) but: it is alive!
▪ if RMI (method invocation) is counted as RPC: Java has it, and many other languages do, too
▪ plus: in recent years, new ‘technologies’ introduced (in part quite ‘special’):
▪ Apache Thrift (Facebook), Protocol Buffers (Google), Finagle (Twitter), …
▪ Support for high level of concurrency meanwhile wide spread
▪ either: asynchronous RPC ‘by design’
▪ or: use of lightweight threads
▪ protocol overhead is often relatively small meanwhile
TK1-2.1.2 Mainstream Paradigms - RPC 41