주제 : Clock Sync
1. 분산시스템에서 동기화
여러 컴퓨터가 한 리소스를 동시에 액세스하려는 경우,
이들을 Ordering을 해야 한다. 뭘 기준으로?
하나의 프린터를 여러 컴퓨터에서 동시요청이 왔을 때, 프린터는 하나 하나 순서대로 출력을 한다. 내부에서 어떠한 Serialization을 한다는 소리다.
그렇지 않으면 하나의 종이에 모든 요청이 겹쳐서 표현하겠지.
컴퓨터마다의 시간은 다 다르다
2. Clock Sync
ex. Make compiler
하나의 컴퓨터안에서 Make를 사용할 경우,
원본 소스 파일의 시간이 2150,
컴파일한 파일 시간이 2149라면,
컴파일 후에 뭔가를 수정했다고 눈치를 채고 작업을 할 수 있다.
그런데 만약 여러 컴퓨터에서
1. source file 10
2. compiled file 9
이렇게 나눠져 있는데, 서로의 컴퓨터 시간이 달라서 넘어가면 어떻게 하는가?
결론 : 여러 컴퓨터의 시간을 어떻게 맞출 것인가?
3. Physical clocks
-
Computer timer
쿼츠 크리스탈로 만들어서, 전기를 넣으면 안에서 진동을 한다.
몇 번 진동하면 인터럽트 줘서 시간을 추가한다.
그런데 이 광물은 컴퓨터 마다 진동수가 다 다를 수 있다. -
Standard time measurement
Solar time
- 해가 머리위에 있을 때를 기준으로
- 편차가 있음
Atomic time
- 원자의 주기는 매우 정확
- solar time이랑 비교하면 조금 차이가 있다.
- UTC는 원자시계로 계싼
4. Clock sync algorithm
UTC에 물어보면 되는데, 네트워크 딜레이는 어떻게 하나? 매번 다를텐데?
time skew : 시간 변화량 (더 빨리가냐 느리게 가냐)
C(t) - 1 : 0이면 딱 맞는거고, 0보다 크면 내가 더 빠른거고. (Skew)
C(t) - t : UTC 시간 대비 내 시계 차이 (Offset)
Maximum drift rate
- UTC에 비해 기울기가 얼마나 가파른가
Network Time Protocol (NTP)
나보다 정확한 시계있는 컴퓨터한테 물어서, 딜레이 보정해서 계산
가정 : 보내고 받는 딜레이는 동일하다고 생각
A와 B를 직접 비교할 수 없다. 시계가 다르니까. 그러나 지들끼리는 계산할 수 있으므로
(T4-T1) - (T3-T2) / 2 를 하면 하나의 딜레이를 나온다.
B가 준 시간에 그 딜레이를 더해서 시간을 계산하면 된다!
Q. 시간을 과거로 되돌리는게 위화감이 드는데?
A. 그럴경우 일정시간 느리게 흘러가게 해서 맞춘다.
Q. 정확도 높은 서버인지 어떻게 판단?
A. 티어를 나눠서 어떤 레벨인지 서로 공유 후 판단.
Berkeley algorithm
Opposite approach to NTP
시간 정확한 애가 다른 애들한테 물어보고 알려주기
정확한 시계의 애가 다 물어보고, 그 차이를 평균내서, 모든 컴퓨터가 맞추는 것이다.
UTC 무시하고 지들끼리만 사용하고 싶을 경우 사용!
5. Logical Clocks
근데 생각을 해보니까, 굳이 현재 리얼 타임을 신경쓰는게 중요한게 아니라,
진짜 중요한건 이벤트 간 "순서"를 따지기 위함임을 눈치챈다.
Lamport logical clocks
두 전제
- Happens-before relation
- A -> B (모두가 동의하는 이벤트의 순서)
-메시지를 보내고 받는 이벤트는 순서가 분명하다! (줘야 받지)
이 두가지를 가지고 순서를 매긴다.
각 프로세스마다 Logical clock이 다르다. P1은 6씩 늘어나고, P2는 8씩 늘어나고 상관없다. 기조는 각 프로세스마다 독립된 시간이니까.
문제는 서로 프로세스간 메시지를 받을 때는 고려를 해야 한다.
m1을 보면, 메시지를 주는 6보다 받는 애가 커야 한다. 우연찮게 그렇다. 넘어가.
아래에서 60에서 보냈는데 받는애가 56이다. 이러면 안된다. 이럴 때 수정을 한다. 60보다 크게.
그럼 P1의 12와, P2 24는 관계가 있을까?
모른다. 이럴 경우 Concurrent하다고 한다.
구현할 때는 1씩 증가해서 만든다.
서로 다른 지역 은행 예제
현재 잔액 1000
- SF에서 +1000
- NY에서 이자 1% 지급
이 동시에 발생했을 때 각각 DB가 있을텐데 어떤 순서로 처리해야 하나?
알고리즘
- 모든 메시지엔 타임스탬프가 담김
- 업데이트 메시지는 멀티캐스트된다.
메시지를 받으면
- 타임스탬프에 따라 오더링 (Sort)
- 로컬 큐에 넣기
- ACK 멀티캐스트 (실행 전에 모든 노드의 동의 받아야 실행가능)
미들웨어에서 이 과정이 진행, 실행은 앱에 메시지 보내야 실행.
언제 ACK을 보낼거냐 3단계
- 내가 아무것도 안하고 있음 Go 아니면
- 업데이트 나도 하려고 했는데, PID가 니가 더 낮으면 니꺼 Go
- 아니면 내꺼 먼저 처리하고 동의해줄게
PID를 둬서 메시지는 (time,PID) 페어로 구성된다.
포인트는 PID로 정렬, 그리고 모든 노드의 ACK을 받아야만 실행할 수 있다.
Vector clock
램포트 시계의 문제 : Concurrent한 이벤트들이 있을 경우 처리가 안됨 => Causality 처리 못함.
VC(a)
프로세스 만큼 벡터 클락 엔트리가 있음.
Pi에서 index i : 내 로지컬 클락
P0의 벡터 클락에서 인덱스 2가 3이라면, P2에서 이벤트 3개 발생했다는 뜻.
7. Mutual Exclusion
공유 리소스를 동시에 접근하려고 할때 어떻게 처리할 것인가?
Token-based
서로 토큰을 돌려가며 주고 받고 자기가 토큰 있으면 접근 가능
Permission based
Locking 매커니즘과 비슷
- Central : 대장
- Decentral : 민주적으로 모든 노드에게 물어봄
- Distributed : 쓰려고 하는 놈들끼리만 서로 합의
