Client-Server Design Issues

Threads in Distributed Systems

  • Multithreaded clients
    • Thread can block waiting for server response but application/process is not blocked
  • Multithreaded servers
    • Simplified server code as opposed to finite-state-machine approach that users non-blocking system calls
    • Can handle multiple client requests in parallel (while making blocking ystem calls)
    • Improved performance over iterative servers on multiprocessor systems

NFS Architecture

Google File System (GFS)

Semantics of File Sharing

[Leetcode] Longest Increasing Subsequence


Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?


  • 遍历所有的数字,同时维护一个valid数组,来保存当前扫描到的有用的数
    • tail 表示当前valid数组的最后一个数, 
    • 对于当前读到的数x
      • 如果x>tail,则把x append到数组中
      • 如果x<valid数组的第一个数,则将其替换为x
      • 否则,则二分查找到valid数组中第一个大于或等于x的数,替换为x
    • 返回valid数组中有效的数个数

时间复杂度: O(nlogn)



Web Service — REST

What is REST

  • a design pattern for implementing networked systems, stands for “Representational State Transfer”
  • A client references a web resources using a URL
  • The web serves as a guiding framework for the web
  • HTTP is not just a protocol
    • It provides an API (POST, GET, PUT, DELETE) for create, read, update, and delete operations on a resource
  • Approach isolates application complexity at the end points (client and server) and keeps it out of the transport

Three Fundamental Aspects of REST

  • Resources
    • Every distinguishable entity is a resource. A resource may be a web site, an HTML page, and XML document etc.
  • URLs
    • Every resource is uniquely identified by a URL.
  • Simple operations



  • The web is the universe of globally accessible information
  • Resource oriented
  • User-driven interactions via forms
  • Few operations (generic interface) on many resources
  • URI: Consistent naming mechanism for resources
  • Focus on scalability and performance of large scale distributed hypermedia systems


  • The web is the universal transport of message
  • Activity/Service oriented
  • Orchestrated reliable event flows
  • Many operations (service interface) on few resources
  • Lack of standard naming mechanism
  • Focus on design of integrated (distributed) applications

Web Service

Web Services Fundamentals

Two Competing Approaches

  • REST-style
  • SOAP-style

Four Fundamental Technologies

  • XML
    • Describing information sent over the network
  • WSDL
    • Defining web service capability
  • SOAP
    • Accessing web services
  • UDDI
    • Finding web services

Web Service Infrastructure and Components


  • Has emerged as the standard solution for describing information exchanged between heterogeneous system
  • Can be read by programs and interpreted in an application-specific way
  • Example
    • <Account>xx</Account>

WSDL: Describing the web service

  • Provides functional description of network services
    • IDL description
    • Protocol and deployment details
    • Platform independent description
    • Extensible language
  • As extended IDL: WSDL allows tools to generate compatible client and server stubs
    • Allows industries to define standardized service interfaces
    • Allows advertisement of service descriptions, enables dynamic discovery and binding of compatible services
      • Used in conjunction with UDDI registry
  • The main elements in a WSDL description

UDDI: Finding Web Service

  • Universal Description, Discovery, Integration
  • UDDI defines the operation of a service registry
    • Data structures for registering
      • Business
      • Technical specification: tModel is a keyed reference to a technical sepcifcaiton
      • Service and service endpoints
        • Referencing the supported tModels
  • The main UDDI data structures


  • Why SOAP
    • A “wire protocol” necessary for accessing distributed object services
    • Vendor and/or platform-specific wire protocols hinder interoperability
  • SOAP
    • An Internet standard specification, the goal of which is to define a platform and vendor-neural WIRE PROTOCOL based on Internet standard protocols [HTTP & XML] to access Web Services. 
  • Features
    • Uses XML to package requests for services exposed by Web Services, and responds generates by Web services
    • Typically uses HTTP as a transport protocol
  • SOAP message
    • Convey documents
    • Support client-server communication

RESTful Approach

  • Focus on using HTTP operations (GET, PUT, POST, DELETE) to manipulate data resources represented in XML
    • No WSDL + SOAP

[Leetcode] Two Sum


Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2


  • 用一个hash表来围护每个数和其对应的index
    • 如果有重复的数字,则overwrite, 即保留最后出现的index
  • 然后遍历所有的数,如果 (target – 当前数)在哈希表中,且俩数的index不一样,则找到解了
  • 复杂度
    • Time: O(n)
    • Space: O(n)



Remote Method Invocation – Design & Implementation

Middleware layers

Distributed Objects 

Compile-time vs. Run-time Objects

  • Objects can be implemented in many different ways
    • Compile-time objects
      • e.g., instance of classes written in object-oriented language like Java, C++
    • Data-base objects
    • Procedural languages like C,with an appropriate “wrapper code” that gives it the appearance of an object
  • System like Java RMI support compile-time objects
  • Not possible or difficult in language-independent RMI middleware such as CORBA
    • These systems use object adapters
    • Implementations of object interfaces are registered at an object adapter, which acts as an intermediary between the client and the object implementation

Persistent vs. Transient Objects

  • Persistent objects 
    • continue to exist even if they are not contained in the address space of server process
    • the “state” of a persistent object has to be stored on a persistent store, i.e., some second storage
    • invocation requests result in an instance of the object being created in the address space of a running process
      • many policies possible for object instantiation and (de)instantiation
  • Transient objects
    • Only exist as long as their container server process are running
      • i.e., only exist in memory

Static vs Dynamic Remote Method Invocations

  • Static invocation
    • Typical ways for writing code that uses RMI is similar to the process for writing RPCC
    • declare the interface in IDL, compile the IDL file to generate client and server stubs, link them to client and server side code to generate the client and the server executables
    • requires the object interface to be known when the client is being developed
  • Dynamic invocation
    • The method invocation is composed at run-time
      • invoke (object, method, input_parameters, output_parameters)
    • Useful for applications where object interface are discovered at runtime
      • e.g., object browser, batch processing systems for object invocations

Design Issues for RMI

  • RMI invocation semantics
    • Invocation semantics depend upon implementation of Request-Reply protocol used by RMI
    • Could be MaybeAt-least-once, At-most-once

  • Transparency
    • Should remote invocations be transparent to the programmer?
      • Partial failure, higher latency
      • Different semantics for remote objects, e.g., difficult to implement “cloning” in the same way for local and remote objects or to support synchronization operations e.g., wait/notify
    • Current consensus
      • Access transparency
        • Remote invocations should be made transparent in the sense that syntax of a remote invocation is the same as the syntax of local invocation
        • Distinguish
          • But programmers should be able to distinguish between remote and local objects by looking at their interfaces, 
          • e.g., in Java RMI, remote objects implement the Remote interface

Implementing Issues for RMI

  • Parameter Passing
    • Representation of a remote object referece
  • Request/Reply protocol
    • Handling failures at client and/or server
    • Issues in marshaling of parameters and results
      • Input, output, inout parameters
      • Data representation
      • handling reference parameters
    • Distributed object references
    • handling failures in request-reply protocol
      • Partial failure
        • Client, server, network
  • Supporting persistent objects, object adapters, dynamic invocations, etc


  • Pack method arguments and results into a flat array of bytes
  • Use a canonical representation of data types
    • e.g., integers, characters, doubles
  • Example
    • Java serialization

Handling failures

  • Client unable to locate server
    • Reasons
      • Server has crashes
      • Server has moved
      • (RPC systems) client compiled using old version of service interfance
      • System must report error (remote exception) to client 
        • Loss of transparency
      • Request message lost
        • Retransmit a fixed number of times before throwing an exception
        • Reply message lost
          • Client resubmits request
          • Server choices
            • Re-execute procedure
              • Server should be idempotent so that it can be repeated safely
              • Filter duplicates
                • Server should hold on to results until ackowledged
            • Server crashes after receiving a request
              • At least once
                • Keep trying till server comes up again
                • At most once
                  • Return immediately
                  • Exactly once impossible to achieve
                  • Client crashes after sending a request
                    • If a client crashes before RPC returns, we have an “orphan” computation at server
                      • Waste resources, could also start other comutations
                      • Orphan detection
                        • Reincarnation
                          • Client broadcasts new epoch when it comes up again
                          • Expiration
                            • RPC has fixed amount of time to do work


                        • Implementing the request-reply protocol on top of TCP
                          • Does not help in providing applications with different invocation semantics
                            • TCP does not help with server crashes
                            • If a connection is broken, the end points do not have any guarantees about the delivery of messages that may have been in transit

                          RMI Software Components

                          • Communication module
                            • Implements the request-reply protocol
                          • Remote reference module
                            • Responsible for translating between local and remote object references and for creating remote object references
                              • Maintains remote object table that maintains a mapping between local&remote object references
                              • E.g., Object Adapter in CORBA

                          RMI – Object Activation

                          • Activation of remote objects
                            • Some applications require that information survive for long periods of time
                            • However, objects not in user all the time, so keeping them in running processes is a potential waste of resources
                            • Object can be activated on demand
                              • E.g., standard TCP services such as FTP on UNIX machines are activated by inetd
                          • Active and passive objects
                            • Active objects
                              • Instantiated in a running processes
                            • Passive objects
                              • Not currently active but can be made active
                              • Implementation of its methods, and marshalled state stored on disk
                          • Activator responsible for
                            • Registering passive objects that are available for activation
                            • Starting named server processes and activating remote objects in them
                            • Keeping track of locations of servers for mote objects that it has already activated
                          • Examples
                            • CORBA implementation repository
                            • JAVA RMI has once activator on each server computer

                          RMI – Other Topics

                          • Persistent object stores
                            • An object that is guaranteed to live between activations of process is called a persistent object
                            • Stored the state of an object in a marshalled (serialized) form on disk
                          • Location service
                            • Objects can be migrated from one system to another during their lifetime
                            • Maintains mapping between object references and the location of an object
                          • Distributed Garbage Collection
                            • Needed for reclaiming space on servers
                          • Passing “behavior”
                            • Java allows objects (data+code) to be passed by value
                              • If the class for an object passed by value is not present in a JVM, its code is downloaded automatically
                          • Use of reflection in Java RMI
                            • Allows construction of generic dispatcher and skeleton

                          Distributed Garbage Collection

                          • Java approach based on reference counting
                            • Each server process maintains a list of remote processes that hold remote object references for its remote objects
                            • When a client first acquires a remote reference to an object, it make addRef() invocation to server before creating a proxy
                            • When a clients local garbage collector notices that a proxy is no longer reachable, it makes a removeRef() invocation to the server before deleting the proxy
                            • When the local garbage collector on the server notices that the list of client processes that have a more reference to an object is empty, it will delete the object (unless there are any local objects that have a reference to the object)
                          • Other approaches
                            • Evictor pattern
                            • Leases

                          Java RMI

                          lecture 4


                          • Integrate with Java language and libraries
                            • Security, write once run anywhere, multithreaded
                            • Object oriented
                          • Can pass “behavior”
                            • Mobile code
                            • Not possible in CORBA, traditional RPC systems
                          • Distributed garbage collection
                          • Remoteness of objects intentionally not transparent
                            • Good for handling failures

                          Remote Interfaces, Objects, and Methods

                          • Object becomes remote by implementing a remote interface
                            • A remote interface extends the interface java.rmi.Remote
                            • Each method of the interface declares java.rmi.RemoteException in its throws clause in addition to any application-specific clauses

                          Creating distributed applications using RMI

                          1. Define the remote interfaces
                          2. Implement the remote objects and server
                          3. Implement the client
                          4. Compile the remote interface, server and client 
                          5. Generate the stub and skeleton using rmic
                          6. Start the RMI registry
                          7. Start the server
                          8. Run the client

                          [Leetcode] Reverse Words in a String


                          Given an input string, reverse the string word by word.
                          For example,
                          Given s = “the sky is blue“,
                          return “blue is sky the“.


                          • 首先split string by space
                          • 然后 append word in reverse order
                          • 注意 如果当前非空,在append下一个word之前,需要append空格



                          [Code Interview] Count number of ones


                          Counting the number of 1 bits in the binary representation of a given integer.  


                          Method 1: 

                          • shift the number right by one bit each time, and check whether the right-most bit is 1
                            • If yes, count++

                          Method 2:

                            • if n is not 0, count++
                            • assign n = n & (n-1), repeat until n is 0

                            Time complexity
                            • method 1: theta(n)
                            • method 2: O(n)