Client-Server Design Issues

Posted on December 28, 2015 by admin

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

Posted on December 27, 2015 by admin

Problem

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?

Analysis

遍历所有的数字，同时维护一个valid数组，来保存当前扫描到的有用的数

tail 表示当前valid数组的最后一个数，
对于当前读到的数x

如果x>tail，则把x append到数组中
如果x<valid数组的第一个数，则将其替换为x
否则，则二分查找到valid数组中第一个大于或等于x的数，替换为x

返回valid数组中有效的数个数

时间复杂度: O(nlogn)

Code

Reference
[1] http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
[2] https://leetcode.com/problems/longest-increasing-subsequence/

Web Service — REST

Posted on December 27, 2015 by admin

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

REST vs. SOAP

REST

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

SOAP

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

Posted on December 27, 2015 by admin

Web Services Fundamentals

Two Competing Approaches

REST-style
SOAP-style

Four Fundamental Technologies

Describing information sent over the network

WSDL

Defining web service capability

SOAP

Accessing web services

UDDI

Finding web services

Web Service Infrastructure and Components

XML

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

SOAP

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

Security blogs

Posted on December 26, 2015 by admin

IT

IT技术博客大学习 http://blogread.cn/it/
网络安全研究国际学术论坛 http://www.inforsec.org/wp/
腾讯安全应急响应中心 http://security.tencent.com/index.php/blog
LinkedIn安全中心 https://security.linkedin.com/blog-archive

Security blog
– https://luyixing.wordpress.com/

[Leetcode] Two Sum

Posted on December 26, 2015 by admin

Problem

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

Analysis

用一个hash表来围护每个数和其对应的index

如果有重复的数字，则overwrite，即保留最后出现的index

然后遍历所有的数，如果（target – 当前数）在哈希表中，且俩数的index不一样，则找到解了
复杂度

Time: O(n)
Space: O(n)

Code

Reference
[1] https://leetcode.com/problems/two-sum/

Remote Method Invocation – Design & Implementation

Posted on December 26, 2015 by admin

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 Maybe, At-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

Marshalling

Pack method arguments and results into a flat array of bytes
Use a canonical representation of data types

e.g., integers, characters, doubles

Example

CORBA CDR
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

Note

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

Posted on December 26, 2015 by admin

lecture 4

Features

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

Define the remote interfaces
Implement the remote objects and server
Implement the client
Compile the remote interface, server and client
Generate the stub and skeleton using rmic
Start the RMI registry
Start the server
Run the client

[Leetcode] Reverse Words in a String

Posted on December 25, 2015 by admin

Problem

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Analysis

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

Code

Reference

[1] https://leetcode.com/problems/reverse-words-in-a-string/

[Code Interview] Count number of ones

Posted on December 25, 2015 by admin

Problem

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

Analysis

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)

Code

Reference

[1] http://www.geeksforgeeks.org/count-set-bits-in-an-integer/