용도
분산 시스템에서 특정 1개 프로세스를 coordinator로 지정하는 알고리즘.
여기서 coordinator는 leader라고도 불리며 클라우드 컴퓨팅에서 분산 시스템의 각 노드들에게 작업을 나눠 할당 해준다던지, 각각의 노드들 작업을 완료하고 결과를 돌려주면 취합하는 것과 같은 중앙 집중형 작업을 하는 노드다.
원리
각 프로세스들에게 고유한 아이디를 부여하고, 가장 큰 아이디를 가진 프로세스가 항상 coordinator 역할을 하도록 한다.
장점
- 여러 개의 분산된 (서버)프로세스 중 coordinator 역할을 할 프로세스를 동적으로 선정 할 수 있다.
- Coordinator (서버)프로세스 장애시 설정의 변경, 시스템 재시작 필요 없이 다른 프로세스가 해당 역할을 넘겨 받을 수 있다.
단점
- 동적인 시스템 확장이 힘들다. 그룹내 모든 프로세스들은 다른 프로세스들의 정보를 미리 알고 있어야 하므로 신규 노드 추가를 위해서는 설정 파일을 변경하고 재시작 해야만 한다.
제약 사항
- 각 프로세스들은 고유한 아이디(라던지 순차적으로 구분 할 수 있는 무엇인가)를 가지고 있어야 한다.
- 모든 프로세스들은 몇 개의 다른 프로세스가 있는지 알아야 한다.
- 하지만 다른 프로세스가 현재 구동 중인지 아닌지는 알 필요 없다.
구동 방식
- (a.1). 그룹 내의 프로세스 중 하나가 coordinator가 다운 되었다는 것을 인지.
위 그림에서는 4번 프로세스가 7번 프로세스가 다운 된 것을 발견 했다. - (a.2). coordinator의 다운을 감지한 프로세스는 자기보다 높은 아이디를 가지고 있는 프로세스들에게 ELECTION 메시지를 전송한다.
- (a.3). 아무런 프로세스도 응답을 하지 않으면 그 자신이 coordinator가 된다. 아무런 프로세스도 응답을 하지 않는다는 것은 ELECTION메시지를 보낸 목적지 프로세스가 다운 되어있거나, 지정된 시간내에 응답을 주지 않았을 때를 의미한다.
- (b) - (d). ELECTION 메시지를 받은 프로세스들은 sender에게 OK 메시지를 전송하고, sender의 역할을 이어 받는다.
위 그림의 (b) 과정 에서는 5번과 6번 프로세스가 4번에게 OK 메시지를 응답하고
(c). 5번 프로세스는 6번과 7번에게 ELECTION 메시지를 보낸다.
(d). 6번 프로세스 역시 5번 프로세스에게 OK 메시지를 보내고 7번 프로세스에게 ELECTION 메시지를 보낸다. - (e). 과정에서 가장 마지막 까지 election에 참가한 6번 프로세스는 7번 프로세스가 죽어 있으므로(또는 시간 내 응답이 없으므로) 자신이 새로운 coordinator가 되어 다른 모든 프로세스들에게 자신이 새로운 coordinator가 되었음을 알린다.
- 만일 이전에 죽었던 프로세스가 다시 살아 나는 경우(7번 프로세스가 재부팅 되는 경우), 해당 프로세스는 위의 과정을 거쳐 다시 coordinator가 된다.
