글

들어가며

프로그래밍에서 작업 흐름이 여럿인 경우를 제법 만날 수 있습니다. 목적부터 작업 흐름이 여럿일 수 있고(여러 사용자가 있는 구조), 더 빠른 처리를 위해 여럿을 사용할 수도 있고(병렬 프로그래밍), 관리를 위해 개념적으로 쪼개어 작업할 수 도 있습니다.

하지만 여러 작업 흐름을 고려하고 프로그래밍을 하면 작업 흐름끼리 충돌해서 프로그램이 죽어버리거나, 데이터가 오염되는 문제가 생길 수가 있습니다. 데이터베이스에서 간헐적으로 발생하는 데드락이나, 구글 독스 등 클라우드 프로그램을 이용할 때 글자가 갑자기 사라지는 것이 그 예시입니다.

이 글에서는 소프트웨어에서 여러 작업 흐름을 어떻게 제어하는지 개념적으로 간단히 알아보겠습니다.

하나로 전부 처리하기

튜닝의 끝은 수정이라는 말처럼 프로그래밍 관점에서 놀랍고 높은 수준이고 멋있는 기술을 사용하는 것은 아니지만 제일 좋은 방법입니다. 일단 생각할 게 없기 때문에 구현이 아주 쉽습니다. 그리고 누가 작업할지 따질 필요도 없기 때문에 아주 효율적입니다.

규칙을 두고 나누기

작업자 전부의 Ground Rule을 정하고 나누는 방법입니다. 규칙만 잘 정한다면 신경써야할 부분이 적고, 성능 손실도 적게 병렬 처리가 가능합니다.

네트워크

초창기 전송 프로토콜인 ALOHA에서는 충돌이 일어나지 않도록 기도하면서 데이터를 보내고 수신 장치에서 ACK응답을 보내길 기다렸습니다. 일정 시간이 지나도 ACK가 오지 않는다면 실패로 처리하고 다시 보내고, 프레임이 단 1비트라도 충돌한다면 전체를 그냥 버렸습니다. 이걸 성공하거나 지정된 최대 전송 횟수가 될 때까지 계속 반복했습니다. 당연히 효율은 약 18.4% 정도로 좋지 못했죠.

이런 문제를 해결하기 위해 slot이라는 개념이 도입되었습니다, slot은 시간을 여러 칸으로 나눠서 slot이 시작되는 시점에만 데이터를 전송하는 겁니다. slot이 도입됨으로써 두 장치에서 보낸 데이터가 머리와 꼬리에서 충돌하는 일을 막을 수 있습니다. 그러니까, 고작 몇 비트 충돌로 전체를 다시 전송해야 하는 일은 없어진 것이죠. 효율은 약 36.8%로 올랐습니다.

순수 ALOHA

순수 ALOHA

Slotted ALOHA

Slot이 적용된 ALOHA

현대의 네트워크는 Slotted ALOHA보다 발전해서 다양한 규칙이 추가되었습니다. 시간 단위로 쪼개 쓰기, 주파수 대역대를 나누어 쓰기, 주파수를 코드로 쪼개서 쓰기 등등

Rust의 소유권

프로그래밍 언어에서 규칙을 두고 자원을 나누는 예로 Rust의 소유권과 라이프타임 개념을 들 수 있습니다. Rust에서 어떤 변수는 하나의 작업 흐름만 수정할 수 있습니다. 소유권을 옮기거나 복사하지 않는다면 변수 수정이 불가능합니다. 소유권에 대한 규칙은 무척 복잡하므로 이 글에서 전부 다루기 어렵습니다. 간단하게만 살펴보겠습니다.

fn take_mut(d: &mut i32) {
	*d += 1;
}

fn just_read(d: &i32) {
	println!(d);
}

fn main() {
	let mut x = 1;
	let mrx = &mut x;  // x의 소유권을 가져옵니다.
										 // x의 소유권이 이동했으므로, 이 지점에서 x는 사용할 수 없습니다.

	// just_read(&x);  // 소유권은 mrx에 있으므로 불가능합니다.
	take_mut(mrx);  // take_mut 안으로 소유권이 옮겨졌다가 돌아옵니다.
	take_mut(mrx);  // take_mut 안으로 소유권이 옮겨졌다가 돌아옵니다.
									// mrx가 더 이상 쓰이지 않으니 mrx의 소유권은 끝났습니다.
	// 여기서부터는 정상적으로 x를 쓸 수 있습니다.
  
  println!("{}", x);
}

관리를 위임하기

관리를 위임하는 방법은 자원을 사용할 수 있는 권한을 관리하는 구성요소를 하나 정해두고 이 구성요소가 모든 자원의 사용을 통제하는 것입니다. 규칙을 두고 나누는 방식과 다르게, 분배 역할만 전담하는 요소가 추가되어 추가적인 비용이 들어가지만 좀 더 유연하게 대응할 수 있다는 장점이 있습니다. 운영체제가 정확하게 이 역할을 수행합니다.

운영체제

운영체제는 프로세스/쓰레드가 사용할 수 있는 모든 자원을 관리합니다. 스케줄러를 통해 프로세스/쓰레드의 컴퓨팅 자원 사용을 통제하고, 시스템 콜을 통하지 않으면 프로세스/스케줄러는 파일 읽기/쓰기, 소켓 열기/쓰기/읽기/닫기 전부 불가능합니다. 자원 별로 구체적으로 어떻게 관리하는지는 조금씩 다르지만(CPU 자원은 스케줄링, 메모리는 가상 메모리 시스템 등) 시스템 콜을 경유한다는 점은 동일합니다.

합의하기

합의하기는 자원을 쓰고 싶은 모든 작업자들이 적당한 방식으로 누가 쓸지 합의하는 방식입니다. 관리를 위임하는 방법은 관리자가 단일 장애점이 되어 관리자가 정상 작동하지 않는다면 시스템 전체가 정상 작동할 수 없습니다. 합의하는 방식은 작업자 하나가 고장나도 시스템 전체에는 지장이 없다는 장점이 있습니다. 그 대신에, 합의하는 데에는 대체로 상당한 시간이 소모됩니다. 그래서 순수하게 합의만 이용하는 것이 아니라, 합의해서 관리자나 규칙을 정하는 방법으로 동작하게 됩니다.

Raft 분산 합의 알고리즘

Raft 알고리즘은 분산 시스템에서 리더를 선출하는 알고리즘입니다. 즉, 모든 작업을 합의하는 것은 아니고 관리를 위임할 노드를 하나 뽑는 알고리즘입니다. 이렇게 한 이유는 당연히 매 작업마다 합의하게 되면 자원 소모가 상당하기 때문입니다.

Raft 알고리즘에서는 다음 세 가지 역할이 정해져 있습니다. 첫째는 Leader로 모든 작업 명령을 전파하고 모든 노드가 동일하게 작업을 수행하게 만듭니다. 주기적으로 자신의 상태를 다른 Follower에게 전파합니다. 둘째는 Follower로 리더로부터 받은 명령을 처리합니다. 마지막은 Candidate로 리더가 어떤 이유로든 부재할 경우, Follower가 새 리더를 정하기 위해 전환된 것입니다.

기본적으로 Leader는 모든 작업 명령을 가지고 모든 팔로워가 동일한 명령을 수행하도록 합니다. Follwer 과반이 정상적으로 작업을 수행했다면, 수행이 완료되지 않은 나머지 Follower도 정상 수행하도록 강제합니다. 중간에 Follwer가 고장났더라도 Leader가 가진 작업 명령을 그대로 복제해 수행하게 됩니다.

Raft 알고리즘

Raft 알고리즘 구성

맺음말

지금까지 소프트웨어가 여러 작업 흐름을 통제하는 방법을 알아보았습니다. 들어가는 글에서 언급했듯이 이 글은 개념적으로 어떤 방법을 쓰는지에 초점을 두었습니다. 더 자세한 정보를 원하신다면 따로 검색하시거나 아래 참조글을 확인하시면 되겠습니다.

참조

  1. Data communication & Networking, Behrouz A. Forouzan
  2. https://kjhoon0330.tistory.com/entry/운영체제OS-CPU-스케줄링
  3. 모두의 코드
    1. https://modoocode.com/338
  4. https://seongjin.me/raft-consensus-algorithm/