반응형
컴퓨터 또는 시스템간 동기가 필요하다.
서로 다른 프로그램 (컴파일러와 에디터)끼리의 로컬클록이 다르기에 동기가 필요하다.
컴파일러를 (A)머신, 에디터를 (B)머신에서 동작한다고 한다
A와 B머신의 로컬클럭은 2초차이가 난다.
A의 로컬클럭은 2144 , 2145, 2146...
B의 로컬클럭은 2142, 2143, 2144...
A가 2초 늦다.
B의 컴퓨터에서 2143초에 에디터를 사용하였다. 2143= B의 로컬클록
A는 2144에서 아웃풋을 하지만 되지 않는데. 2144초로써 더 이전이기 때문이다.
○ 시간(Clock or Time)의 중요성
- 컴퓨터에서 일어난 이벤트 발생시간 파악
- Data Consistency 유지 등 각종 시스템 알고리즘 구현에 이벤트 시간이 중요
○ Clock Sync(시간 동기)의 필요성
- 각각의 컴퓨터마다 자체 Clock을 사용
- 자체 Clock 사용으로 인하여 분산시스템상에서 각 작업 간 Clock 및 시간 동기가 어긋나 문제 발생
○ Clock 종류
- Physical(물리적): 태양력, 원자시계(TAI)
- Logical(논리적)
•Lamport: 시간의 선/후 파악
•Vector Clock: Event의 인과관계 파악
Physical Clocks
○ 태양력: 지구의 공전주기 활용
- 하루 중 태양이 가장 높이 뜬 시점부터 측정
- n번째 날짜까지 초 단위로 Count
- 영국 그리니치 천문대가 표준 측정지점
360도= 1년
하루= 태양이 가장 높이 떳을때 오늘과 내일의 시간차
○ 원자시계
- 1948년 고안
- 세슘 원자의 진동수를 기준으로 시간 측정
(초당 92억회 진동)0
- TAI; International Atomic Time의 역자
○ 세계표준시(UTC;UniversalTimeCoordinate)
- TAI 방식으로 측정
현재 원자시계를 사용중이다. 태양시계와 동기를 맞추기 위해서 마치 윤년을 두듯이 9~11 19~21로 점프한다.
이것을 Leaf second 라 한다.
https://www.youtube.com/watch?v=RwfkFcQX4wg
인공위성의 위치에있는 데이터가 수신기에 도달하기까지 시간이 걸립니다. 수신기의 시계는 일반적으로 위성의 시계와 동기화되지 않습니다.
○ GPS는 4개의 원자시계를 사용함
○ 저궤도 인공위성을 사용하여 3각 측량법으로 위치측정, 이를 이용한 특정 Node와 GPS 간 시간 동기 수행
○ GPS 시간 동기 Issue
- 전파지연: 위성에서 지구까지 전파가 도달하는 시간 보정 필요
- Clock차이:수신자와위성의Clock차이보정
○ 그래프상 x는 UTC, y는 Local Clock
○ 이들 기울기가 1로 수렴하게 맞추는것이 목표
○ 종류 및 기법
- GPS를 이용한 시각 동기
- Berkeley Algorithm
- Network Time Protocol
- Synchronization in Ad-hoc Wireless Algorithms
• FTSP(Flooding Time Synchronization Protocol)
• Harmonia
Network Time Protocol (PASSIVE 형식- 물어볼때 알려줌)
A클라이언트 B서버
A의 로컬클럭
B의경우 타임서버를 가지고 있다.
A와 B 둘사이의 클락옵셋을 구하여 동기화
○ 유선 인터넷에서 사용
○ 원자시계 수준의 정밀한 시간을 유지하는 Time Server 존재
- Server의 동작은 Passive 방식(Client 요청 에 대해서만 동작)
○ 원리
- A축: Local Clock
- B축: Time Server Clock, 매우 정확
- Clock Offset을 이용해 Time Server와
Local 동기화
- Clock Offset이 0이면 시간 일치
• 0보다 작으면 Server 시간이 빠름
• 0보다 크면 Local 시간이 빠름
The Berkeley Algorithms (ACTIVE - 계속알려줌)
(a) 타임디몬이 주기적으로 자기시간을 알려준다.
(b) 디몬이 어느정도 차이가 나는지 응답을 받는다.
(C) 다음시간 (예 3:05분) 에 3:05분이 되도록 계산하여 맞춘다.
○ Server 내 Time Daemon이 있어 Network 내 Node와 동기 수행
○ NTP와 달리 Active 방식
- Daemon은 자신의 시간을 Client에게 알림
- 차이가 나는 Client가 있으면 시간 조정 수행
○ 동작
1) Daemon 자신의 시간을 Client에게 알림
2) Client와 차이나는 시간 계산
3) 차이나는 시간에 흐른 시간만큼 보정 하여 시간 동기
Clock Synchronizationin Wireless Networks (무선망)
○ 무선망에서는 메시지전파, NIC에서의 소요시간, Application에서의 전달시간이 가변적이므로, 수신시간에 맞춰 시간을 동기화
○ 전달지연 (Propagation Delay)는 빛의 속도에 가까우므로 무시
참고사항 NIC: Network Interface Card (이더넷카드/무선랜카드/랜카드 등)
LOGICAL CLOCK
Lamport’s Logical Clocks
○ 전제: 송신시간 ＜ 수신시간
○ 관계: Happen Relation 표현
- 두 Event 사이에 대한 전/후 관계 표현
- Local Clock을 사용하되 Event의 전/후 시간만 맞춰줌
모든 로컬클록의 전체동기를 맞춰야하는경우는 오버헤드가 크기때문에 전후관계만 맞춰준다.
○ 구현
1) 각 Process는 자신의 Clock Counter를 유지한다.
2) Process가 메시지를 송신할 때 자신의 Clock Counter+1 값을 같이 전송한다.
3) 수신한 Process는 메시지의 Clock Counter 값과 자신의 Clock Counter 값을 비교한다.
•자신의 것이 크다면 그대로 유지
•수신한 Clock Counter의 값이 크다면 수신 값에 1을 더하여 자신의 Clock Counter를 바꾼다.
(1)
"happen-before"관계 →는 두 가지 상황에서 직접 관찰 할 수 있습니다. a와 b가 같은 프로세스의 이벤트이고 a가 b보다 먼저 발생하면 a → b가 참입니다. a가 한 프로세스에 의해 전송 된 이벤트이고 b가 다른 프로세스에 의해 수신 된 이벤트 인 경우 a → b
(2) 3개의 프로세스가 있고 서로 다른 컴퓨터 그리고 로컬클록이 다르게 작동하고 있다.
P1 은 6 단위로 증가하는 로컬클록에서 동작
P2 은 8 단위로 증가하는 로컬클록에서 동작
P3 은 10 단위로 증가하는 로컬클록에서 동작
m1 문제가 없음 이유는 6->16의 전후관계가 맞다.
m2 문제가 없음 이유는 24->40 전후관계가 맞다.
m3 문제 있음. P3의 송신은 60이나, P2의 수산입장에서는 64가 되며 m4도 마찬가지로 수신이 더 크므로 전후관계가 맞지않는다.
따라서 전후관계를 맞춰줘야할 필요가 있다.
(3) 프로세스가 메세지를 송신할때 자신의 Clock Counter에 +1 값을 같이 전송한다.
수신한 프로세스는 메시지의 Clock Counter 값과 자신의 값을 비교하고 자신의 것이 크다면 문제가 없으므로 그대로 유지하지만,
수신한 Clock 값이 크다면 수신값에다 +1을 더하여
자신의 Clock Counter를 바꾼다.
(4)&(5) 참고만하기
○ 예제. Totally Ordered Multicasting (램포트처럼 전/후)
- 데이터베이스를 중복으로 구성하고이를 여러 사용자가 사용하는 경우
- 중복된 데이터베이스간 거리는 아주 멀다고 가정
- 두 사용자가 동시에 업데이트를 수행한다고 가정했을 때 서로 가까운 위치의 데이터베이스를 먼저 업데이트함
- 먼 곳은 업데이트의 순서에 상관없이 나중에 업데이트되므로데이터베이스의일관성이깨짐
Update1이 먼저 그 다음 Update2 DB의 일관성이 깨질 수 있다.
Vector Clocks (인과관계)
○ 메시지의 전후관계 뿐만 아니라 인과관계도 고려
○ 표현: VCi=(Px, Py, Pz)
○ 동작
1) 어떤 Process가 다른 Process에게 메시지 를 보낼 경우 Vector 값 중 자신에게 해당 되는 부분을 1증가 시키고 메시지와 같이 전송
2) 수신한 Process는 자신의 Vector와 비교하 여 일관성에 문제가 없을 경우 Vector 업 데이트
3) 만약 수신한 메시지의 Vector 일관성이 없 다면 대기시키고, 일관성이 일치하는 다른 Vector를 가진 메시지를 Update 수행
VC= Vector Clock의 약자 이며 i는 프로세스의 이름(숫자)
P0에서 m이라는 메시지를 보내고있으며 P1의 m*는 m에 의해서 생성된 메시지 (인과관계가 존재)
모든 VC는 처음에 VC=(0,0,0)으로 시작하여 첫번째 자리의 0은 P0의 이벤트 발생수 두번째 0은 P1의 이벤트 발생수 세번째 0은 P2의 이벤트 발생수를 말한다.
VC0에서 (1,0,0) 인 경우 P0에서 발생되었기 때문에 첫번째 자리에 +1이 카운팅 된다. P0에서 m메시지를 보내는 이벤트를 수행하였다.
P1에서 수신했을때는 (1,0,0) 이지만 m*가 생성되었기 때문에 VC1(1,1,0)으로 이번에는 두번째가 카운트 된다.
하지만 무엇이 문제인가? P2가 문제가 되는 상황이다.
P2에서는 m1이 먼저 수신되는 것이 아니라 m*가 먼저 수신되기에 일관성이 없다.
하지만 VC2= (0,0,0) 상태가 되는 이유가 무엇일까? 원래는 P1에서 전달받았기에 (0,1,0)이어야 한다. 하지만 일관성이 없다고 판단하고
m*를 홀드시킨다. 홀드시킨 후 m이 오면 이후에 m*를 처리한다.
이후 VC2는 m을 받고 (1,0,0) 이 되고 m를 받았기에 m*를 처리한다. 따라서 VC2=(1,1,0)이 된다.
정확하게 P0 / P1 / P2 가 정확하게 (1,1,0) 으로 동기되게 된다.
Mutual Exclusion
Mutual Exclusion A Centralized Algorithm
○ Mutual Exclusion: 여러 Process가 공유 자원을 배타적으로 사용하는 것
예) 프린트의 경우: 한 사람이 쓸경우 다른 사람은 대기
○ Mutual Exclusion의 종류
1) Centralized - 코디네이터 / 큐 존재
2) Distributed - Peer 관계에서 자원공유
3) Token-Passing - 네트워크를 순회하는 토큰을 가진 피어가 자원사용
A Centralized Algorithm
- Coordinator가 존재
- Coordinator는 각 Process의 자원사용을 중재
- Queue를 사용하여 사용순서 결정
○ Centralized Algorithm 동작
1) Process는 Coordinator에게 자원사용 요청
2) Coordinator는 해당 자원이 비어있으면 사용을 허가하고 그렇지 않으면 대기 Queue에 삽입
3) 자원사용이 끝나면 대기 Queue의 다음 Process에게 자원사용 허가
○ 문제점: Coordinator가 Crash 되면 전체 시스템 Down
(a) 1번이 처음 코디네이터에게 쓰겠다고 요청한다. 이런 경우에 다른 대기자가 없기에 문제가 없다.
(b) 현재 1번이 사용중이기때문에 2번은 큐에 대기
(c) 1번이 끝나면 코디네이터에게 Release 하고 코디네이터는 2번에개 권한을 준다.
A Distributed Algorithm
○ Coordinator 없이 Peer-to-Peer 방식
○ 자원사용을 경쟁할 때 각 Process의 Timestamp 값으로 결정
○ 동작
1) 자원사용 전 모든 Peer에게 자신의 Timestamp 값을 알려줌
2) 경쟁자가 있을 경우 Timestamp가 낮은 Peer가 먼저 사용하고 사용이 끝나면 다른 Peer에게 통보
○ 문제점: 자원사용 중 Peer가 Crash 되면 전체 시스템 Down
(a) 자기의 타임스탬프(각자 로컬 클록에서 생성된 타임스탬프)를 다른 피어에게 알려준다.
(b) 2번피어가 타임스탬프가 12이고 0번피어의 경우에는 타임스태가 8이므로 0번에게 OK를 보내 양보한다. 1번의 경우 애초부터 사용할 마음이 없기에 타임스탬프가 없으므로 OK를 0번과 2번에 보냄
(c) 0번이 사용을 하고나면 다음 순번인 2번에게 OK신호를 보낸다.
A Token Ring Algorithm
○ Network를 순회하는 Token을 가진 Peer가 자원을 사용함
○ 자원사용이 종료되면 Token을 해제하고 다음 Peer에게 넘김
(a) 네트워크에서 순서가 지정되지 않은 프로세스 그룹.
(b) 소프트웨어로 만들어진 논리 링.
* 피어들간 토근을 계속 넘기며 토큰이 왔을 경우에 자원 사용 권한을 받는다.
※ Mutual Algorithm Summary
전체메시지수: 엔트리전 메시지횟수 뿐더러 모든 메시지의 합
엔트리전 메시지: 자신의 차례가 되기전까지의 메시지 수
문제: 알고리즘의 문제점
Centralized - 끝나고 1번 더 보냄 총 3번 / 자신이 쓰기 위해서 코디네이터에게 왔다 갔다 2번 / 코디네이터가 죽으면 문제
Distributed - n은 노드 수 2배를 주는 이유는 자기를 빼고 다 뿌려주기 때문이다. / 프로세스가 죽으면 문제
Token ring - 계속 토큰을 전달하기에 1부터 무한대 / 0 에서 n-1은 자기가 토큰을 가지고 있을 경우에 기다리지 않기때문에 0 이며, n-1은 한바퀴를 다 돌았을 경우 / 토큰과 프로세스가 죽으면 문제
Election Algorithms
○ Centralized 분산시스템 환경에서 Coordinator 역할을 수행할 Peer를 선정하는 방법
○ 종류
1) The Bully Algorithm
2) A Ring Algorithm
The Bully Algorithm
○ 각 Peer가 고유하게 갖는 Timestamp 또는 Priority를 사용
○ Coordinator는 가장 큰 Priority를 가짐
○ Coordinator Crash를 최초로 인지한 Peer가 알고리즘 실행
○ 동작
1) 어떤 Peer가 Coordinator의 Crash를 인지
2) 인지한 Peer는 자신의 Priority보다 높은 값을 갖는 Peer들에게 Alive 확인
3) 그 다음 순위의 Peer가 자신보다 높은 Priority 값을 갖는 Peer들에게 Alive 확인
4) 3)의 과정을 여러번 수행하여 Alive Peer 중 가장 높은 Priority를 갖는 Peer가 Coordinator가 됨
5) Coordinator가 된 Peer는 나머지 Peer들에게 자신이 새로운 Coordinator임을 알림
Bully Algorithms(1)
(a) 4번 피어가 7번의 크래시를 인지하고 자신보다 높은 6번과 5번에게 일렉션을 보냄
(b) 둘 다 응답함
(c) 5와 6은 7이 크래시된것을 모르고있는 상태이므로 5번과 6번은 자신보다 높은 피어들에게 일렉션을 보낸다.
5번보단 6번이 크므로 코디네이터가 되어야하고 6번보다 7번이 더 크므로 7이 코디네이터가 되어야 하지만 7번은 크래시 된 상태로 6번이 코디네이터가 된다.
Bully Algorithms(2)
(d) 피어 6은 5를 중지하도록 지시합니다.
(e) 피어 6이 승리하여 모든 피어에게 알려줍니다.
A Ring Algorithm
○ 각 Peer들은 Logical 한 Ring에 연결되어 있다고 가정
○ Ring을 따라 순회하며 Coordinator 선정
○ 동작
1) 어떤 Peer가 Coordinator의 Crash를 인지
2) 인지한 Peer부터 Ring 순회 순서를 따라Alive 탐지
3) Crash를 발견한 Peer 이전까지 순회한 후 그 중 가장 큰 Priority를 가진 Peer를 Coordinator로 선정
5번과 2번이 7번이 죽은것을 동시에 디텍션했다는 것을 가정
Election in Wireless Environments
○ Priority가 가장 높은 Peer를 가상의 트리구조로 탐색
○ 동작
1) 어떤 Peer가 Coordinator의 Crash를 인지
2) 인접 Peer로 Broadcasting
3) Broadcasting 메시지를 받은 Peer는 다음 인접 Peer로 Broadcasting하며 이때 전송 경로가 겹치는 경우 우선순위가 높은 Peer 만 Broadcasting
4) 3)의 과정을 수회 거쳐 Tree가 완성되면 Leaf부터 Root까지 Priority를 비교해 나가 며 탐색
5) 가장 큰 Priority를 가진 Peer가 Coordinator가 됨
코디네이터가 죽은것을 발견한 노드가 루트가 된다.
4번노드부터 트리를 구성하여 가장 높은 값인 8을 탐색한다.
가장 큰 값 8이 코디네이터가 된다.
여기에서 노드는 우선순위 또는 용량이 될 수 있다.
여기서 8이 코디네이터가 되는 과정은
(e)와 (f)그림을 보면된다.
전부다 탐색한 노드들은 다시 트리를 거꾸로 올라가며 교차점에서 비교를 하여 선정한다. (h,8) 이 가장 크므로 교차점을 통과하여 계속 올라가는 모습을 볼수있다.
Elections in Large-Scale Systems
○ 대규모 분산시스템의 경우 하나의 Coordinator로 전체를 관리하기 힘듬
○ Group 단위로 Superpeer를 선정하여 각 Group의 Coordinator 역할을 위임 - 관리자는 적정 Superpeer의 수를 결정
○ 동작: Repulsion Force(반발력)를 이용
1) A와 B의 진행방향 위에 있는 C가 있다고 가정
2) A와B의 합벡터(반발력)으로 C는 D로진행함
3) D가 Coordinator로 선정됨 (합벡터로 향하는 노드가 코디네이터)
반응형
'컴퓨터공학 > 분산시스템' 카테고리의 다른 글
| 분산시스템의 결함 허용 (Fault Tolerance) (1) | 2023.12.20 |
|---|---|
| 분산시스템의 일관성 및 복제(Consistency & Replication) (1) | 2023.12.20 |
| 분산시스템의 네이밍 (1) | 2023.12.20 |
| 분산시스템의 커뮤니케이션 (1) | 2023.12.20 |
| 분산시스템에서의 프로세스 (1) | 2023.12.20 |
