[분산처리] Distributed System Concepts 1단원, 2단원 정리

분산 시스템 : concurrency, no global clock, independent failure

cloud computing : scalable, eleastic, pay-per-use, rental, utility, private

horizontal allocation : scaling out/scaling in (add or remove)

vertical scaling : scaling up/scailing down (CPU의 성능을 늘리거나 줄임)

challenge : Heterogeniety, openness, security, scalability, failure handling, concurrency, transparency, quality of service

Heterogeniety : 서로 다른 컴퓨터, 네트워크를 Middleware를 통해 통합하여 상위 레이어에선 구별하지 않아도 되도록.

Openness : 다 공유가 되므로 공격에 대한 방어가 필요함.

Security : confidentiality(모르는 사용자에 대한 노출 방지), Integrity(원본을 지키는 특성), availability(간섭으로 인한 사용불능)

Scalability : resource의 증감. 이용률에 따라서 성능이 너무 급격하게 변하면 안 되고 일정한 성능을 유지해야 한다. 그리고, reasonable cost

Failure handling :  문제 상황에 대한 대처. detect failure, masking failure, tolerating failure, recovery from failure. redundancy, availability

Concurrency : share resource에 대한 process는 한 clinet request at a time. (limitation of 성능)

Transparency : 인지하지 못하게 한다.

 

분산시스템의 문제점

Widely varying modes of use

Wide range of system environents

Internal problems

External threats

 

Physical model : representation of the underlying hardware elements of distributed system

Architecture model : make the system reliable, manageable, adaptable and cost-effective

looking at core underlying architectural elements

examining composite architectural patterns

considering middleware platforms

Fundamental model : processes that communicate with one another by sending messages over a computer network

to make explicit all the relevant assumptions about the systems we are modeling

to make generalizations concerning what is possible or ipossible.

Interaction, failure, security(cryptography, encryption)

performance of communication channel : latency, bandwidth, jitter

clock drift rate : perfect reference clock과의 차이.

 

algorithm : a sequence of steps to be taken in order to perform a desired computation

distributed algorithm : definition of the steps to be taken by each of the processes of which the system is composed

 

 

client/server -> invocation/result

 

proxy server : cache server. increase availability and performance of the service by reducing the load on the wide-area network and web servers.

central server로 모든 server와 interact 한다.

 

mobile code : code가 browser에 다운로드된 후 브라우저에서 실행된다. -> interactive response가 좋음. dealy나 variability of bandwidth를 겪지 않음.

그러나, 최신의 코드로 유지하는 consistency문제가 발생.

applet code는 web server에 있다가 client server로 다운로드됨.

 

layer : vertical organization

tier : 기능에 따라 layer를 나누어 server에 배정한다.

 

Thin client : code를 다운로드하지 않고 server에서 실행하여 결과만 가져온다. delay의 문제. Mobile code와 반대.

 

Fundamental model : synchronous distributed system, asynchronous distributed systems(no bound) -> event ordering

Omission failure : crash. 정상적인 문제. 문제가 발생하면 멈춘다. (Time out) FAIL STOP -> communication channel에서 발생 가능. Message의 loss

Arbitrary failure : 문제가 발생돼도 계속 실행돼서 큰 문제를 야기한다. omits/takes unintended processing step을 야기함. messge가 여러 번 전송되거나 존재하지 않는 게 전송됨.

 

clock resolution : periods between updates of the clock value

같은 시간데에 event가 2개가 발생하면 안 되고, 연속적으로 발생하는 두 이벤트 사이의 간격은 clock resolution보다 커야 한다.

clock skew : the difference between the reading of any two clocks

clock drift rate : the change in the offset between the clock and a nominal perfect reference clock per unit of time measured by the reference clock

utc: Coordinated universal time

 

External synchronization : 외부 server와 시간을 맞추는 것

Internal synchronization : 분산 시스템을 구성하는 components끼리 시간을 맞추는 것

Internal synchronization이 되면 external은 굳이 필요 없다.

System P가 externally synchronized with a bound D -> internally synchronized with a bound of 2D

 

Synchronizing physical clock  Cristian's method. Accuracy = (+-) Tround/2-min

Berkeley algorithm : slave, master가 있고 slave들이 master에게 시간 정보를 보내서 master가 수합하여 평균 내고 조절해줌.

NTP : synchronized accurately to UTC. 서버에 문제 생기면 하위 서버가 역할을 하고 그런 식으로 내려간다. 다만 내려갈수록 error는 누적된다.

 

Logical clock : LAMPORT (happened before) 다만 dependency가 있는 event 간에서만 happend before관계를 파악할 수 있다.

vector clock : L(c1)<L(c2) 면 c1 <c2임을 알 수 있도록. 

global state : 모든 process의 상태 정보를 모아둔 것. P2P 관계에서는 불가능.

consistent cut 이전까진 global state

consistent cut : cut에 포함되는 event의 happend-before event를 모두 포함. 

Snapshot algorithm : Marker message. 항상 consistent.

 

global state의 특성

stable : once system enters a state in which the predicates associated is True, it remains true in all future states reachable from that state

safety : deadlock에 빠지지 않는다.

stable ; S0, Sl까지 모든 state는 true

 

분산 시스템의 해결 과제

failure detection : unreliable failure detector(time limit. T가 너무 크면 crashed process를 unsuspected로 보고할 수 있음. unsuspected_evidence만 가지고 이야기한다. suspeted_기미가 있다.), Relialbe failure detector (구현 어려움)

mutual exclusion : Safety(CS는 한 process만), liveness(요정 하면 CS 할 수 있어야 함.), ordering(요청한 순서대로 CS를 한다.). Evaluation(bandwidth, client delay, throughput)

election

multicast

consensus

 

Mutual exclusion

Central server : safety, liveness (request to server and token(grant)을 줌으로써 알 수 있다. 요청이 도착한 순서로 진행되기 때문에 ordering 보장 X). client server의 fault만 tolerance

ring based : token을 서로 넘겨주면서 가진 애만 할 수 있다. (safety, liveness) ordering은 절대 아님. Synchronization delay : 다음 P가 CS 하는데 걸리는 시간. fault tolerance 불가.

Ricart and Agrawala(multicast and logical clock) : 모두에게 해도 되는지 물어보고 나를 제외한 모두의 reply를 기다린다. time stamp를 같이 보내서 여러 개면 time stamp가 낮은 사람한테 답장을 해줌. RELEASED, WANTED, HELD. safety, liveness, ordering. N-1 to multicast, N-1 to replyss

Maekawa : voting set을 만든다. group의 개수는 전체 P의 수의 루트이고, 한 그룹당 그룹의 개수만큼의 원소를 가진다. logical clock을 사용하지 않고 한 P는 한 번의 답장만 보낼 수 있다. CS를 하고자 하는 P는 자신의 voting set의 모든 동의를 얻어야 한다. safety만 만족. vlting set에 따라서 deadlock이 가능(prone). ordering은 안됨. logical clock을 사용하지 않으니까. 다만, fault tolerance.

 

Election : safety(elect 된 애는 crash 되지 않았다., liveness(participate 하고, elected 된다.)

ring based : 돌아가면서 id가 큰 애가 elect 된다. 자기 자신으로 돌아오면 terminate 된다. elected message는 한 바퀴를 무조건 돈다. safety, liveness. 3N-1. 2N

bully algorithm : election, answer, coordinator. higher id한테만 물어본다. election->answer 받으면 높은 애가 election을 시작한다. timeout을 두어 answer가 올 때까지 시간을 기다리고 아무것도 안 오면 걔가coordinator가 된다. safety(no process is replaced), liveness(reliable message delivery) N-2, 2(N-1)^2

answer는 왔는데 coordinate message가 안오면 restart another election