UNIX의 grep 명령어는 텍스트에서 특정 패턴을 찾는 도구입니다. 예를 들어, server.log 파일에 다음과 같은 내용이 있다고 가정해봅시다.

192.168.1.1 - - [21/Sep/2023:10:01:42] "GET /index.html HTTP/1.1"
192.168.1.2 - - [21/Sep/2023:10:01:50] "GET /about.html HTTP/1.1"
192.168.1.1 - - [21/Sep/2023:10:01:55] "POST /login HTTP/1.1"
192.168.1.3 - - [21/Sep/2023:10:02:01] "GET /contact.html HTTP/1.1"

이 로그 파일에서 특정 IP를 가진 로그만 뽑아내려면 다음과 같이 처리할 수 있습니다.

grep '192.168.1.1' server.log

grep 단독으로 사용해도 꽤 유용하지만, UNIX의 다른 도구인 awk나 파이프 연산자를 잘 조합하면 복잡한 케이스의 데이터도 추출할 수 있습니다. 192.168.1.1라는 특정 IP에서 어떤 HTTP 요청 유형(GET, POST 등)이 있었는지를 알고 싶다면 다음과 같이 작성할 수 있습니다.

grep '192.168.1.1' server.log | awk '{print $6}' | tr -d '"'

그렇다면 이런건 어떻게 만들 수 있을까요? 이번 글에서는 러스트를 이용해 CLI을 어떻게 개발하는지에 다루겠습니다.

명령어 구현하기

CLI는 크게 명령어 입력과, 결과 출력 두 단계로 나눌 수 있습니다. 이 일련의 과정을 처리하려면 입력으로 들어온 문자열을 파싱한 다음에 정해진 규칙에 따라 명령어 인자들을 인식하고, 해당하는 함수를 호출하면 됩니다.

여기서는 덧셈과 뺄셈을 수행하는 계산기를 CLI로 만들어보겠습니다. 아래는 대략적인 명령어 구조입니다. 추후 글이 진행되가면서 이 구조는 조금씩 바뀌기 때문에 그냥 그런가보다 하면서 넘어가면 됩니다.

binop <number1> --add | --sub  <number2>

곱셈과 나눗셈은 없는데, 이건 편의상 연산자 우선순위(Operator Precedence)를 배제하기 위해서입니다. 추가로 음수를 입력 값으로 받는 것도 제외하겠습니다. 이걸 처리하려면 좀 복잡한 파서를 추가해야 하는데 그러면 이 문사의 내용 범위 밖이기 때문입니다. 절대 귀찮아서가 아니에요.

입력

이제, 명령어 입력을 어떻게 받는지 알아보겠습니다. 단순히 문자열을 받고 분해한 다음 올바른 명령인지 검증하는 파서를 제작하면 됩니다. 이 방식은 러스트 책의 12장 I/O 프로젝트 문단에서 소개하는 내용입니다. 하지만 이 방법은 꽤 번거로운 작업이 많습니다. 하지만 clap을 이용하면 이 과정을 간단하게 넘어갈 수 있습니다. 명령어와 플래그, 입력값을 따로 인식할 필요 없이 그냥 “명령어가 어떻게 생겼고 이런 기능들이 있을거야”라고 정의만 해두면 파서 같은 부분은 라이브러리 단계에서 가져다 쓰면 됩니다.

전체 코드는 링크를 참고해주세요. 다만 제가 실수로 단계 별로 커밋하는걸 깜박해서 코드가 업데이트 되는 흐름은 날아갔습니다.

저는 입력을 받는 부분을 App과 Subcommand로 나눠서 코드를 작성합니다. 여기서는 앞에 BinOp을 붙여서 BinOpApp과 BinOpSubcommand로 구조체와 열거형을 정의하겠습니다.

// main.rs

use clap::{Parser, Subcommand};

#[derive(Parser, Debug)]
struct BinOpApp {
    #[clap(subcommand)]
    command: BinOpCommand,
}

#[derive(Subcommand, Debug)]
enum BinOpCommand {}

derive macro나 attribute를 사용할 수 없다는 오류가 발생하는 경우 높은 확률로 clap을 프로젝트에 추가할 때 feature를 지정하지 않아서 생기는 문제입니다. tokio 같이 derive macro를 이용하는 라이브러리를 사용할 때도 이런 경우가 종종 있기 때문에 cargo.toml 파일을 확인해보면 얼추 해결할 수 있습니다.

clap = { version = "4.4.5", features = ["derive"] }

옵션에 derive를 추가하면, derive macro 같은 요소들을 사용할 수 있습니다.

이름에서 알 수 있듯이 BinOpApp은 프로그램의 엔트리 포인트이고, 사용자가 입력하는 모든 명령어 인자들을 관리하는 역할을 합니다. 또한 BinOpApp은 필드로 BinOpCommand를 받는데 이건 실제 작업을 정의하는 열거형이고, 이 정보를 이용해 BinOpApp은 어떤 하위 커멘드(subcommand)가 실행되어야 할 지 결정합니다.

이제 덧셈과 뺄셈을 추가하면 됩니다. 이건 BinOpCommand에 추가하면 됩니다.

#[derive(Subcommand, Debug)]
enum BinOpCommand {
    #[clap(about = "add two numbers")]
    Add,
    #[clap(about = "subtract two numbers")]
    Sub,
}

clap의 parse() 메서드를 이용하면 명령어를 쉽게 파싱할 수 있습니다.

fn main() {
    let app = BinOpApp::parse();
    println!("{:?}", app);
}

코드를 실행해보면 명령어 목록을 보여주는 help가 출력됩니다.

Usage: binop <COMMAND>

Commands:
  add   Add two numbers
  sub   Subtract two numbers
  help  Print this message or the help of the given subcommand(s)

Options:
  -h, --help  Print help

매개 변수 받기

하지만 지금은 명령어의 종류만 추가했기 때문에 그 어떤 계산기스러운 동작을 하지 않습니다. 계산기스러운 동작을 하기 위해 이제 어떤 값을 계산할 것인지 정의하겠습니다.

값을 넣으려면 하위 커멘드에 플래그(flag) 타입을 지정하면 됩니다. 일단은 간단하게 i32 타입만 받도록 하겠습니다.

#[derive(Subcommand, Debug)]
enum BinOpCommand {
    #[clap(about = "add two numbers")]
    Add {
        #[clap(short='a', help = "The first number")]
        lhs: i32,
        #[clap(short='b', help = "The second number")]
        rhs: i32,
    },
    #[clap(about = "subtract two numbers")]
    Sub { ... },
}

lhs, rhs는 이항 연산에서 왼쪽 값과 오른쪽 값을 의미합니다. 또한 각 플래그마다 #[clap(..)] 매크로를 지정해 단축키(short)와 도움말을 추가했습니다. short는 기본값으로 필드 이름의 맨 앞글자를 사용합니다. 하지만 이 경우 중복되는 글자가 생길 수 있기 때문에 위의 코드 처럼 명시적으로 플래그를 지정할 수도 있습니다.

프로그램이 명령어와 각 플래그를 잘 받는지 확인하기 위해 메인 함수를 수정해보겠습니다.

fn main() {
    let app = BinOpApp::parse();
    match app.command {
        BinOpCommand::Add { lhs, rhs } => println!("{} + {}", lhs, rhs),
        BinOpCommand::Sub { lhs, rhs } => println!("{} - {}", lhs, rhs)
    };
}

패턴 매칭을 사용하면 인자로 받은 값을 쉽게 꺼낼 수 있습니다. 지금은 두 값을 인식하면 단순히 어떤 연산을 하겠다고 보여주는 정도이기 때문에 prinln!을 이용해 수식을 출력하도록 작성했습니다.

위에서 처럼 cargo run으로 이 프로그램을 실행시켜도 CLI는 동작하지만, 각 연산이 어떤 플래그를 가지고 있는지는 확인할 수 없습니다. 하지만 아래의 명령어를 실행하면 코드와 직접 상호작용할 수 있습니다.

cargo run -- binop -a 1 -b 2

터미널에 1 + 2라는 식이 출력되면 성공입니다.

플래그 타입 지정

이제 얼추 계산기스러운 동작을 하긴 하지만, 각 연산마다 플래그를 지정하는 것은 좀 많이 번거로운 것 같습니다. 플래그를 하나하나 입력하는 것 보다 아예 하나의 플래그에 여러 값을 받도록 하고 적당히 잘 가공해서 처리하면 어떨까요?

다시 하위 커멘드를 수정해보겠습니다. 이번에는 플래그를 하나만 받도록 수정하면 됩니다.

#[derive(Subcommand, Debug)]
enum BinOpCommand {
    #[clap(about = "Add two numbers")]
    Add {
        #[clap(short = 'n', help = "The numbers to add", )]
        numbers: Option<String>,
    },
    #[clap(about = "Subtract two numbers")]
    Sub {
        #[clap(short = 'n', help = "The numbers to subtract")]
        numbers: Option<String>,
    },
}

한번에 여러 값을 받으려면 Vec<T> 타입을 이용하는게 깔끔하겠지만, 아쉽게도 인식을 못해서 부득이하게 String 타입을 받도록 지정했습니다. GPT에게 방법이 있냐고 물어보면 매크로에 multiple(true)를 추가하면 된다고 하긴하는데 이건 아예 존재하지도 않습니다. 그래서 저는 입력으로 들어온 문자열을 띄어쓰기 단위로 분리한 다음에 i32 타입으로 파싱하는 식으로 처리하기로 했습니다. 문자열이 길어지면 엄청 느려지겠지만, 솔직히 누가 그 정도로 길게 문자열을 넣을까요?

[2023-09-28 수정 내역] 위에서 Vec<T>를 인식하지 못한다 했는데, 이후에 따로 찾아보니 #[arg(num_args(0..))]를 원하는 플래그 위에 추가하면 쉽게 처리할 수 있었습니다. 출처

#[derive(Subcommand, Debug)]
enum Command {
 #[clap(about = "...")]
 Foo {
      #[clap(...)]
   #[arg(num_args(0..)]
      foo_flag: "벡터와 같은 여러 값을 받는 타입"
}

또한 String 타입을 Option으로 묶었는데, 기본 값을 설정하고 플래그를 이용해 값을 지정하지 않으면 기본 값인 0을 출력하도록 할 것입니다. 그럼 수정된 메인 함수는 아래와 같아집니다.

fn main() {
    let app = BinOpApp::parse();
    match app.command {
        BinOpCommand::Add { numbers } => {
            let numbers = numbers.unwrap_or(String::from("0"));
            let num_vec = numbers
                .split_ascii_whitespace()
                .collect::<Vec<&str>>()
                .into_iter()
                .map(|n| n.parse::<i32>().unwrap());

            println!("{}", num_vec.sum::<i32>());
        }
        BinOpCommand::Sub { numbers } => {
            let numbers = numbers.unwrap_or(String::from("0"));
            let num_vec = numbers
                .split_ascii_whitespace()
                .collect::<Vec<&str>>()
                .into_iter()
                .map(|n| n.parse::<i32>().unwrap())
                .collect::<Vec<i32>>();

            let mut sub = num_vec[0];
            for n in num_vec[1..].iter() {
                sub -= n;
            }

            println!("{}", sub);
        }
    }
}

저는 코드의 깊이(depth)가 깊은걸 지향하기 때문에 함수형 프로그래밍 기법을 사용했는데, for 문을 이용해서 합과 차를 구해도 별 문제는 없습니다. 문자열을 i32 벡터로 만드는 부분은 코드가 중복되기 때문에 따로 함수로 빼면 좋을 것 같네요. 리팩토링을 적용한 수정된 코드는 다음과 같습니다.

fn main() {
      let app = BinOpApp::parse();
      match app.command {
          BinOpCommand::Add { numbers } => {
              let numbers = numbers.unwrap_or(String::from("0"));
              let sum = string_to_numbers(numbers).into_iter().sum::<i32>();

              println!("{}", sum);
          }
          BinOpCommand::Sub { numbers } => {
              let numbers = numbers.unwrap_or(String::from("0"));
              let num_vec = string_to_numbers(numbers);

              let mut sub = num_vec[0];
              for n in num_vec[1..].iter() {
                  sub -= n;
              }

              println!("{}", sub);
          }
      }
}

fn string_to_numbers(numbers: String) -> Vec<i32> {
    numbers
        .split_ascii_whitespace()
        .collect::<Vec<&str>>()
        .into_iter()
        .map(|n| n.parse::<i32>().unwrap())
        .collect::<Vec<i32>>()
}

타입별 특성

플래그의 타입은 i32, f32, u64와 같은 숫자 리터럴과 String과 같은 문자열 그리고 Vec<T>와 같은 벡터 타입들을 사용할 수 있다는건 이미 코드에서 확인했습니다. 그렇다면 불리언과 같은 bool을 사용하면 어떻게 될까요?

연산자 내부에 결과를 출력하는 옵션을 추가해보겠습니다. 플래그는 불리언 타입의 -p로 설정하겠습니다. 여기서 p는 print의 약자입니다.

#[derive(Subcommand, Debug)]
enum BinOpCommand {
    #[clap(about = "Add two numbers")]
    Add {
        #[clap(short = 'n', help = "The numbers to add", )]
        numbers: Option<String>,
        #[clap(short = 'p', help = "Print the result")]
        print: bool,
    },
    // ...
}

fn main() {
      let app = BinOpApp::parse();
      match app.command {
          BinOpCommand::Add { numbers, print } => {
              let numbers = numbers.unwrap_or(String::from("0"));
              let sum = string_to_numbers(numbers).into_iter().sum::<i32>();

              if print {
                  println!("{}", sum);
              }
          }
          // ...
      }
}

이렇게 하면 계산 결과를 출력할지를 결정할 수 있습니다. 명령어는 binop add -n "1 2 3" -p를 사용하면 됩니다. 플래그를 사용하면 true, 없으면 false로 알아서 정해지기 때문에 따로 값을 넣을 필요가 없습니다.

원시 타입 이외에서 열거형이나 PathBuf 같은 타입들도 사용할 수 있습니다.

테스트를 통한 번거로움 줄이기

지금까지는 cargo run을 이용해 동작을 검증했습니다. 빌드 후 실행을 하더라도 다시 명령어를 입력하는 것은 번거롭습니다. 하지만 테스트 코드를 사용한다면 번거로운 과정을 없앨 수 있습니다. 물론 테스트를 작성하는 것도 꽤나 번거롭지만, 적어도 다시 처음부터 명령어를 입력하는 것 보단 훨씬 정신건강에 좋지 않을까 싶네요. 애써 터미널에 엄청 긴 명령어를 입력했는데 오타 때문에 실행이 안되는 상황을 생각해보면 바로 느껴질겁니다. 참고로 맥에서는 option 키를 누른 상태로 커서를 움직여 원하는 위치에 클릭하면 한번에 되지만 그래도 번거롭습니다.

현재 메인 함수는 값을 따로 반환하지 않고 출력만 하기 때문에 assert_eq!를 이용해서 값을 직접 비교할 수는 없습니다. 직접적인 비교는 불가능하지만 (따로 함수로 빼면 되긴합니다.), 문자열을 원하는 형태로 받았는지 그리고 string_to_numbers 함수가 문자열을 Vec<i32> 타입으로 잘 변환하는지만 확인한다면 전체 동작을 간접적으로 비교할 수는 있습니다.

#[cfg(test)]
mod binop_test {
    use super::*;

    #[test]
    fn test_add() {
        let app = BinOpApp::parse_from(&["binop", "add", "-n", "1 2 3 4 5"]);
        assert_eq!(app.command, BinOpCommand::Add { numbers: Some(String::from("1 2 3 4 5")) });
    }

    #[test]
    fn test_sub() {
        let app = BinOpApp::parse_from(&["binop", "sub", "-n", "1 2 3 4 5"]);
        assert_eq!(app.command, BinOpCommand::Sub { numbers: Some(String::from("1 2 3 4 5")) });
    }

    #[test]
    fn test_string_to_numbers() {
        let numbers = String::from("1 2 3 4 5");
        let num_vec = string_to_numbers(numbers);

        assert_eq!(num_vec, vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_sum_parsed_numbers() {
        let numbers = String::from("1 2 3 4 5");
        let num_vec = string_to_numbers(numbers);

        let sum = num_vec.into_iter().sum::<i32>();

        assert_eq!(sum, 15);
    }
}

참고로 BinOpCommand와 app.command를 비교하려면 BinOpCommand의 매크로에 PartialEq를 추가해야 합니다.

더 복잡한 연산 처리하기

일반적인 계산기는 동일한 연산자를 여러번 사용할 수 있습니다. 하지만 CLI에서는 특성상 -a "10 10" -s "1 1" -a "10" 처럼 한 명령어에 동일한 플래그를 여러번 사용하는건 불가능합니다. 이 문제를 해결하기 위해 복잡한 식은 아예 수식 문자열을 받아서 처리하는 방법을 사용하기로 했습니다.

수식에 “-1 + 2” 처럼 음수가 포함되는 경우와 “1 +” 처럼 불완전한 경우(특히 연산자의 수가 숫자 보다 많을 때)를 고려해야겠지만, 음수는 구현의 편의를 위해 이미 이전에 생략하기로 했었죠, 그래서 후자의 경우만 예외 처리하도록 하겠습니다. 또한 이곳저곳 불완전한 부분이 더 있는데, 어려운건 아니니까 직접 수정해보는 것을 추천합니다.

#[derive(Subcommand, Debug, PartialEq)]
enum BinOpCommand {
        // ...
    Expr {
        #[clap(short = 'e', help = "The expression to evaluate")]
        expr: Option<String>,
    },
}

fn main() {
    let app = BinOpApp::parse();
    match app.command {
      // ...
      BinOpCommand::Expr { expr } => {
          let expr = expr.unwrap_or(String::from("0"));
          let mut result = 0;
          let mut temp_number = String::new();
          let mut op = '+';

          let mut num_count = 0;
          let mut op_count = 0;

          for c in expr.chars() {
              if c.is_digit(10) {
                  temp_number.push(c);
                  num_count += 1;
              } else if c == '+' || c == '-' {
                  if !temp_number.is_empty() {
                      let number = temp_number.parse::<i32>().unwrap();
                      match op {
                          '+' => result += number,
                          '-' => result -= number,
                          _ => panic!("Unknown operator"),
                      }
                      op_count += 1;
                      temp_number = String::new();
                  }

                  op = c;
              }
          }

                    // 연산자의 수가 숫자 보다 많으면 패닉
          if op_count != num_count - 1 {
              panic!("Invalid expression: number of operators is more than number of numbers");
          }

          let number = temp_number.parse::<i32>().unwrap();
          match op {
              '+' => result += number,
              '-' => result -= number,
              _ => panic!("Unknown operator"),
          }

          println!("{}", result);
      }
}

수식 파싱과 계산은 그냥 각 칸 마다 숫자와 연산자가 번갈아 써진 테이프를 한칸씩 이동해나가면서 계산하는 방식이라고 보면 됩니다.

메인 함수 줄이기

물론 여기까지 작성해도 충분히 (완전히는 아니지만) 계산기의 기능을 하지만, 메인 함수의 크기가 매우 크고 단일 책임 원칙을 위반한다는 문제가 있습니다. 지금 코드의 크기는 매우 작아서 이 부분은 생략해도 되지만, 명령어의 수가 커지면 그만큼 코드도 복잡하고 읽기가 싫어지기 때문에 저는 리팩토링을 추천합니다.

제가 CLI 코드를 작성할 때 각 로직을 처리하는 핸들러 함수를 만드는 스타일을 선호합니다. 핸들러 함수를 이용하면 메인 함수에서는 플래그에 맞는 함수만 호출하면 되기 때문에 메인 함수의 크기가 작아지고, 테스트 작성이 편해지고 그리고 뭐가 어떻게 돌아가는지 쉽게 볼 수 있다는 장점이 있습니다.

이 핸들러 함수는 기존의 패턴 매칭 되는 부분에서 실행되는 로직을 따로 함수로 뺀 것이기 때문에 아래와 같이 코드를 수정할 수 있습니다.

fn main() {
    let app = BinOpApp::parse();
    match app.command {
        BinOpCommand::Add { numbers } => add_handler(numbers),
        BinOpCommand::Sub { numbers } => sub_handler(numbers),
        BinOpCommand::Expr { expr } => expr_handler(expr),
    }
}

마무리

이것으로 clap 라이브러리를 이용해서 간단히 CLI 도구를 만드는 방법에 대해 알아보았습니다. 이런저런 설명이 많긴했는데, 빠진 내용도 많아서 차라리 를 읽는게 더 많은 도움이 될 것 같습니다.

하지만 간단히 만드는 정도로는 제 경험상 이 정도 내용만 알아도 얼추 쓸만한 프로그램을 만들 수 있다고 저는 생각합니다. 암튼 이것으로 대략적인 CLI 구현 방법을 마치겠습니다.

저번에 ZIO 정기 모임에 참석했었습니다. 이번 모임에서는 DB에 데이터를 넣고 가져오는 방법에 대해 다뤄봤고, 실습으로 각자 어떤 서비스를 만들어보는 시간을 가졌었습니다. 저는 자전거 대여 시스템을 만들어보았습니다. 물론 당일에 완성은 못했고 이후에 따로 마무리지었습니다.

먼저 데이터베이스(DB)는 도커와 PostgreSQL을 이용했고, 당연하게도 언어는 스칼라, 라이브러리는 ZIO를 이용했습니다. 추가로 쿼리를 다뤄야 하기 때문에 doobie라는 라이브러리도 사용했죠.

이번 포스팅에서 도커를 이용해 데이터베이스를 만들고 데이터를 추가하는 방법을 전부 다루면 좋겠지만, 데이터베이스 생성은 생략하겠습니다. 하지만 방법을 간단한 명령어를 사용하는 것이기 때문에 참고자료에 관련 링크를 남겨놓겠습니다. 또한 전체 코드는 ZIO 모임 레포에서 확인할 수 있습니다

구조

서비스를 구현하기 위해 생각한 구조는 다음과 같습니다. 먼저 진입점인 App에서 (정확히는 BicycleRentalApp에서) ID와 비밀번호, 그리고 정류소 위치와 같은 정보들을 읽어들입니다.

그다음 대여와 반납과 같은 비즈니스 로직은 BicycleRentalService에서 추상화하고, 이 레이어에서 필요한 메서드들은 User, Station, RentalRecord 클래스에서 호출합니다. 마지막으로 각 클래스는 기본적인 쿼리를 보내고 데이터를 가져오는 메서드들과 DB에 저장된 테이블의 구조를 담도록 했습니다.

데이터 생성 및 조작 그리고 연결

먼저 User, Station, RentalRecord의 각 클래스들은 DB의 테이블과 동일한 필드들을 가지고 있습니다. 먼저 도커에 저장된 데이터베이스들을 보겠습니다.

• users : 유저 관련 데이터를 담는 역할을 합니다. 코드에서는 user이지만, 이 단어는 도커에서 예약어로 지정되어 있기 때문에 단수형으로 테이블을 생성하는 것은 불가능했습니다.

CREATE TABLE users (
    id text NOT NULL,
    password text,
    balance integer,
    PRIMARY KEY (id)
);

• station : 대여소의 정보를 저장합니다.

CREATE TABLE station (
    stationId integer NOT NULL,
    availableBikes integer,
    PRIMARY KEY (stationId)
);

• rental_record : 대여 기록을 저장하는 테이블입니다.

CREATE TABLE rental_record (
    userId text NOT NULL,
    stationId integer,
    endStation integer,
    rentalTime integer,
    cost integer,
    FOREIGN KEY (userId) REFERENCES users(id),
    FOREIGN KEY (stationId) REFERENCES station(stationId),
    FOREIGN KEY (endStation) REFERENCES station(stationId)
);

이제 각 데이터 테이블을 다루기 위해 클래스를 생성하겠습니다. case class를 이용하면 됩니다.

case class User(id: String, password: String, balance: Int);
case class Station(stationId: Int, availableBikes: Int);
case class rentalRecord(userId: Int, startStationId: Int, endStation: Option[Int], rentTime: Int, cost: Int);

이제 BicycleRentalApp을 데이터베이스에 연결하면 됩니다. 도커에서 PostgreSQL 컨테이너의 포트는 기본적으로 5432이기 때문에 이 포트 번호로 설정하겠습니다. 그럼 전체 코드는 다음과 같습니다.

// BicycleRentalApp.scala

object BicycleRentalApp extends ZIODefaultApp {

    // 이후에 로그인과 자전거 대여 서비스의 코드들이 들어갑니다. 
    private val prog = ???

    override def run = prog.provide(
        con >>> ConnectionSource.fromConnection >>> Database.fromConnectionSource
    )

    // 도커 컨테이너에 연결하기 위한 세팅입니다.
    val postgres = locally {
        val path = "localhost:5432"
        val name = ???
        val user = ???
        val password = ???

        s"jdbc:postgresql://$path/$name?user=$user&password=$password"
    }

    private val conn = ZLayer(
        ZIO.attempt(
            java.sql.DriverManager.getConnection(
                postgres
            )
        )
    )
}

사용자 데이터 다루기

이제 데이터베이스에 테이블도 추가했고 데이터를 다뤄볼 준비도 끝냈습니다. 쿼리를 날려보며 이것저것 추가하면 되는데, 먼저 유저 데이터를 추가해보겠습니다. 파일은 User.scala입니다.

package com.bicycle_db

import io.github.gaelrenoux.tranzactio.doobie.{Database, tzio}
import doobie._
import doobie.implicits._
import bicycle_db.UsersTableRow
import zio.ZIO

case class User(...)

class UserServices(db: database) {
    def insertUserTableRow(row: User): ZIO[Database, Throwable, Int] = {
        val insertQuery = tzio {
                    (fr"insert into users (id, password, balance) values (" 
                    ++ fr"${row.userId}," 
                    ++ fr"${row.password}," 
                    ++ fr"${row.balance})").update.run
        }

            db.transactionOrWiden(insertUserTableQuery).mapError(e => new Exception(e.getMessage))
        }
    }
}

UserService.insertUserTableRow는 User 클래스에 DB에서 가져온 정보를 담는 메서드입니다. SQL 쿼리는 변수에 직접 바인딩하는 방식을 써도 되지만, SQL injection을 방지하기 위해 Doobie의 Statement Fragments 방식을 이용했습니다. 뭐 정확히는 저렇게 사용하는게 아니지만 연습삼아 해봤습니다.

이제 이 함수는 BicycleRentalApp에서 아래와 같이 데이터를 추가할 수 있습니다. 이렇게 추가한 데이터를 가지고 대여, 반납 시스템을 검증해보겠습니다.

object BicycleRentalApp extends ZIOAppDefault {

    val prog = for {
        userData <- userService.insertUserTableRow(Users("foobar", "password1", 1000))
        _ <- Console.printLine(userData)
    } yield()

    override def run = prog.provide(
    conn >>> ConnectionSource.fromConnection >>> Database.fromConnectionSource
  )

    // ...
}

run 함수에서 >>> 연산자는 함수 체이닝의 역할을 합니다. 예를 들어, 여기서는 conn을 Connection.fromConnection으로 전달하고, 그 결과를 다시 Database.fromConnectionSource로 전달하는 식으로 동작합니다.

Station과 RentalRecord도 동일한 방법을 이용해 데이터를추가할 수 있습니다. 즉, 요렇게 나머지 함수들도 구현하면 데이터를 추가할 수 있습니다.

_ <- userService.insertUserTableRow(Users("foobar", "password1", 1000))
_ <- stationService.insertStationTableRow(Station(123, 10)) // start station
_ <- rentalRecordService.insertStationTableRow(Station(456, 10)) // end station

비즈니스 로직 추상화하기

이제 데이터베이스에 간단한 데이터를 넣어봤으니, 대여와 반납과 같은 비즈니스 로직을 구현해보겠습니다. 추가로 로그인시 등록된 회원인지 판별하는 기능도 넣어보겠습니다. 코드 위치는 BicycleRentalService.scala입니다.

package com.bicycle_db

import io.github.gaelrenoux.tranzactio.ConnectionSource
import io.github.gaelrenoux.tranzactio.doobie.{Database, tzio}
import zio._
import doobie._
import doobie.implicits._
import cats.implicits._

class BicycleRentalService(db: Database) {

    case class DatabaseError(message: String) extends Exception(message)

    def fromSqlException: PartialFunction[Throwable, DatabaseError] = {
        case e: java.sql.SQLException => DatabaseError(e.getMessage)
    }

    def rentBike(userId: String, stationId: Int, rentalTime: Int): ZIO[Any, Throwable, Int] = {
        val rentalRecord = RentalRecord(userId, stationId, None, rentalTime, 1000)
        val rentBicycleQuery = tzio {
            (fr"UPDATE users SET balance = balance -" ++ fr"${rentalRecord.cost}" ++ fr"WHERE id =" ++ fr"$userId").update.run *>
            (fr"INSERT INTO rentalRecord (userId, stationId, rentalTime, cost) VALUES (" ++ fr"$userId," ++ fr"$stationId," ++ fr"${rentalRecord.rentalTime}," ++ fr"${rentalRecord.cost}").update.run *>
            (fr"UPDATE station SET availableBicycles = availableBikes - 1 WHERE stationId =" ++ fr"$stationId").update.run
        }

        db.transactionOrWiden(rentBicycleQuery).mapError(fromSqlException)
    }

    def returnBike(userId: String, returnStationId: Int): ZIO[Any, Throwable, Int] = {
        val returnBikeQuery = tzio {
            (fr"UPDATE rentalRecord SET endStation =" ++ fr"$returnStationId" ++ fr"WHERE userId =" ++ fr"$userId" ++ fr"AND endStation IS NULL").update.run *>
            (fr"UPDATE station SET availableBikes = availableBikes + 1 WHERE stationId =" ++ fr"$returnStationId").update.run
        }

        db.transactionOrWiden(returnBikeQuery).mapError(fromSqlException)
    }

    def checkBikeAvailability(stationId: String): ZIO[Any, Throwable, Boolean] = {
        val checkBikeAvailabilityQuery = tzio {
            (fr"SELECT EXISTS (SELECT * FROM station WHERE stationId =" ++ fr"$stationId" ++ fr"AND availableBikes > 0)").query[Boolean].unique
        }

        db.transactionOrWiden(checkBikeAvailabilityQuery).mapError(fromSqlException)
    }

    def calculateRentalCost(rentalTime: Int): Int = {
        rentalTime * 1000
    }

    //// Login System ////

    def verifyUser(userId: String, password: String): ZIO[Any, Throwable, Boolean] = {
        val verifyUserQuery = tzio {
            (fr"SELECT EXISTS (SELECT * FROM users WHERE id =" ++ fr"$userId" ++ fr"AND password =" ++ fr"$password)").query[Boolean].unique
        }

        db.transactionOrWiden(verifyUserQuery).mapError(fromSqlException)
    }
}

순서대로 대여, 반납, 대여 가능 여부 판단, 요금 계산 그리고 로그인 시스템의 코드입니다.

• rentBike - 자전거를 대여합니다. 먼저 사용할 시간 만큼 요금을 가져간 뒤, 대여 기록에 데이터들을 저장합니다. 그리고 대여한 정류소의 자전거 수를 1만큼 뺍니다.
• returnBike - 자전거를 반납합니다. 해당 유저가 빌려간 기록에 반납 위치를 저장하고, 반납 장소의 자전거 댓수를 증가합니다.
• checkBikeAvailability - 대여 가능한 자전거 수를 확인해 대여 가능 여부를 확인합니다.
• calculateRentalCost - 요금을 계산합니다. 편의상 시간 * 1000(원)으로 설정했습니다.
• verifyUser - 로그인시 해당 유저가 있는지 검사합니다. 단순히 users 테이블에서 id와 password 필드가 있는지 확인합니다.

추가로 에러타입을 좀 더 구체적인 타입으로 대체하기 위해 에러 유형을 정의한 뒤, ZIO의 mapError를 사용해 변환했습니다. 여기서는 doobie의 SqlState를 사용했고 fromSqlException이 이 역할을 합니다.

각 쿼리를 *>를 이용해서 체이닝 했는데, 이 메서드는 두 개의 표현식을 순차적으로 실행한 뒤, 첫 번째 표현식의 결과를 무시하고 두 번째 표현식의 결과를 반환합니다. 가제한 설명은 이후에 위에서 설명한 >>> 연산자와 함께 다루겠습니다.

REPL

유저의 입력을 받고 로그인-대여-반납을 처리하는 코드입니다. 각 클래스를 new로 인스턴스를 생성하고 각 서버스를 추가하면 됩니다.

object BicycleRentalApp extends ZIOAppDefault {

    val prog = for {
        _ <- ZIO.unit
        database <- ZIO.service[Database]

        // create services instances
        userService = new UserServices(database)
        stationService = new StationServices(database)
        rentalRecordService = new RentalRecordServices(database)
        rentalService = new BicycleRentalService(database)

        // login system
        _ <- Console.printLine("Enter your user id: ")
        userId <- Console.readLine
        _ <- Console.printLine("Enter your password: ")
        password <- Console.readLine

        // check if the user is verified or not. if not, fail the program
        isVerified <- rentalService.verifyUser(userId, password)
        _ <- if (isVerified) 
                Console.printLine("Log in") 
            else 
                ZIO.fail("Can't find user")

        // rent a bicycle
        _ <- Console.printLine("Enter the station id: ")
        stationId <- Console.readLine
        isAvailable <- rentalService.checkBikeAvailability(stationId)
        // if `isAvailable`, then get `rentTime` and proceed to rent a bicycle
        // else, fail the program
        _ <- if (isAvailable) {
                for {
                    _ <- Console.printLine("Enter the rental time: ")
                    rentalTime <- Console.readLine
                    rentalCost = rentalService.calculateRentalCost(rentalTime.toInt)
                    _ <- rentalService.rentBike(userId, stationId.toInt, rentalTime.toInt)
                    _ <- Console.printLine(s"Your rental cost is $rentalCost")
                } yield ()
            } else {
                ZIO.fail("No available bikes")
            }

        // return a bicycle
        _ <- Console.printLine("Enter the station id: ")
        returnStationId <- Console.readLine
        _ <- rentalService.returnBike(userId, returnStationId.toInt)
        _ <- Console.printLine("Bike has returned. Thank you for using our service!")
    } yield ()

        // ...
}

>>>, *> 연산자

위에서 사용한 연산자를 더 깊게 다뤄보겠습니다. >>> 연산자는 함수의 체이닝을, *>는 두 개의 표현식을 순차적으로 실행한 뒤 첫 번째 표현식의 결과를 무시하고, 두 번째 표현식의 결과를 반환하는 역할을 한다는 것을 이미 알아보았습니다.

각 연산자의 구현은 다음과 같이 되어있습니다.

// ZLayer.scala 

/**
 * Feeds the output services of this layer into the input of the specified
 * layer, resulting in a new layer with the inputs of this layer as well as
 * any leftover inputs, and the outputs of the specified layer.
 */
def >>>[E1 >: E, ROut2](that: => ZLayer[ROut, E1, ROut2])(implicit
  trace: Trace
): ZLayer[RIn, E1, ROut2] =
  ZLayer.suspend(ZLayer.To(self, that))

이 연산자 구현에서 ZLayer는 첫 번째 레이어 self를 실행한 뒤 나온 결과를 사용해 두 번째 레이어인 that을 생성합니다. ZLayer는 모나드의 개념을 활용하여 레이어를 조합하고 조작하는데 사용되며, 이런 방식으로 두 개의 레이어를 순차적으로 조합하고 새로운 레이어를 반환합니다. 모나드는 값을 감싸는 컨테이너로, 값을 추출하거나 다른 모나드로 변환하는 연산을 수행할 수 있습니다.

이 동작은 flatMap과 유사하다고 볼 수 있습니다. flatMap은 모나드 안의 값을 다른 모나드로 변환하는데 사용하는 함수입니다. 예를 들어, 스칼라의 Option에서 flatMap으로 >>>과 비슷한 동작을 하는 코드를 작성할 수 있습니다.

val option1: Option[Int] = Some(10)
val res: Option[String] = option1.flatMap(num => Some(s"Number is: $num"))

println(res) // Some(Number is: 10)

option1은 Some(10)으로 값이 존재하는 Option이고, flatMap 함수를 이용하여 option1의 값을 추출한 후 첫 번째 함수의 실행 결과를 res에 담아 반환합니다.

*> 메서드 역시 flatMap의 동작과 유사합니다. 아래와 같이 구현되어있습니다.

// Apply.scala

final def *>[A, B](fa: F[A])(fb: F[B]): F[B] =
    productR(fa)(fb)

*> 연산자는 모나드 F를 사용하여 두 개의 표현식 fa와 fb를 순차적으로 실행한 후, 첫 번째 표현식 fa의 결과를 무시하고 두 번째 표현식 fb의 결과를 반환하는 연산자입니다. productR이 두 모나드 값을 받아서 두 번째 값을 반환하는 역할을 합니다.

*> 역시 flatMap과 유사하다고 볼 수 있습니다. 순차적인 실행을 수행하고, 첫 번째 모나드의 결과를 사용하지 않는다는 점에서 그렇습니다. 이 메서드를 flatMap을 사용해 구현할 때 Option 모나드를 이용하는 경우, 첫 번째 Option을 실행한 후 결과를 무시하고, 두 번째 Option을 반환하도록 만들면 됩니다.

val fa: Option[Int] = Some(10)
val fb: Option[String] = Some("foo")

val res: Option[String] = fa.flatMap(_ => fb)

println(res) // Some(foo)

fa와 fb는 각각 Some(10)과 Some(”foo”)로 값이 존재합니다. flatMap 함수를 이용하여 fa의 실행 결과를 무시하고, fb를 반환하여 res에 Some("foo")가 할당되고, 이는 *>과 유사한 동작을 수행합니다.

참고 자료

1. 도커를 이용한 PostgreSQL 데이터베이스 생성

패턴 매칭은 항목 재작성 규칙(term rewriting rule)과 기술적으로는 다르지만 어느 부분에서는 비슷하다고 볼 수 있습니다. 이 재작성 규칙은 왼쪽 항과 오른쪽 항으로 구성되며, 왼쪽은 대체될 패턴을 나타내고 오른쪽은 그 패턴이 대체될 결과를 나타냅니다.

x + 0 -> x
x * 1 -> x

예를 들어, 위 규칙은 덧셈과 곱셈에서 항등원(Identity element)을 제거하는 역할을 합니다. 왼쪽에 있는 수식이 대체된 결과는 오른쪽의 x를 나타낸다고 볼 수 있고 이것이 재작성 규칙의 작동 방식입니다.

하지만 패턴 매칭은 주어진 데이터의 구조와 값이 특정 패턴과 일치하는지 확인하고 그에 따라 코드를 실행하는 더 단순화된 문제를 처리합니다. 패턴 매칭은 주어진 데이터의 구조와 값이 특정 패턴과 일치하는지만 단순히 확인하고 그에 따라 코드를 실행합니다[1]. 또한 텍스트 우선 체계(textual priority scheme)를 이용해 매칭된 규칙이 항상 고유하도록 합니다. 이는 패턴 매칭 규칙이 코드에서 나타나는 순서에 따라 적용되는 방식을 의미합니다.

head :: [a] -> a
head (x:_) = x
head [] = error "Empty list"

이 코드는 (x:_)와 [] 두 가지 패턴이 있습니다. (x:_) 패턴은 하나 이상의 요소를 가진 리스트에 매칭되며, 두 번째 패턴 []는 빈 리스트에 매칭됩니다.

패턴은 코드에 나타나는 순서대로 평가되기 때문에 첫 번째 패턴이 먼저 평가됩니다. 매칭에 실패하면 두 번째 패턴이 평가됩니다. 이러한 방식이 텍스트 우선 체계를 나타냅니다.

패턴 매칭을 수행하면서 컴파일러는 패턴 매칭을 매칭 오토마타(matching automata)라는 테스트로 변환합니다. 이 매칭 오토마타에는 주로 결정 트리(decision tree)와 백트래킹 오토마타(backtracking automata)와 같은 방식이 있습니다.

결정 트리

먼저 결정 트리에 대해 알아보겠습니다. 결정트리는 트리 기반 모델이며 각 노드에서 특정 조건을 테스트 하고 결과에 따라 다른 분기로 이동하는 구조를 가지고 패턴의 순서에 따라 트리를 구성합니다.

    [Root]
    /    \
[Node1] [Node2]
 /  \     /  \
[A] [B] [C] [D]

Root는 최상위 노드를, Node1과 Node2는 Root의 자식 노드를 나타내며 A, B, C, D는 각각 Node1과 Node2의 자식 노드를 나타냅니다. 각 노드에서 특정 조건을 테스트하고, 그 결과에 따라 다음 노드로 이동합니다.

Python을 이용해 결정 트리의 코드를 간단히 작성한다면 아래와 같습니다.

def match_pattern_decision_tree(pattern, data):
    if len(pattern) != len(data):
        return False

    for p, d in zip(pattern, data):
        if p != d and p != '_':
            return False

    return True

print(match_pattern_decision_tree(['A', 'B', '_'], ['A', 'B', 'C']))  # True
print(match_pattern_decision_tree(['A', 'B', '_'], ['A', 'B', 'D']))  # True
print(match_pattern_decision_tree(['A', 'B', 'C'], ['A', 'B', 'D']))  # False

패턴과 데이터를 zip()으로 묶은 후, 서로 맞는지 확인하는 간단한 동작을 합니다. 여기서 _ 는 와일드카드(wildcard)이며 모든 값에 일치하는 패턴입니다.

트리 구조 기반 알고리즘은 트리의 높이를 최소화 하는 것이 중요합니다. 높이는 트리의 루트 노드에서 임의의 리프(leaf) 노드 까지의 최대 경로의 길이와 같고, 일반적으로 시간 복잡도는 $O(h)$라 할 수 있습니다. 즉, 복잡한 패턴을 처리할 수록 트리의 높이와 복잡도는 커집니다. 또한 복잡해지는 만큼 필요한 노드의 수도 동일하게 증가하기 때문에 공간복잡도는 $O(n)$ 정도입니다. 따라서 결정트리는 복잡한 패턴을 처리할 때 시간과 비용을 많이 소모하게 됩니다.

Backtracking automata

백트래킹 오토마타는 정규표현식 매칭에서 주로 쓰이는 알고리즘입니다. 정확히는 비결정적 유한 오토마타(Non-deterministic Finite Automaton, NFA)라고 표현하는게 맞겠지만, 편의상 여기서는 백트래킹 오토마타라는 표현으로 퉁치겠습니다.

NFA 방식은 주어진 상태와 입력에 대해 여러 가지 가능한 상태 전이를 허용하기 때문에 패턴 매칭이 다양한 패턴을 동시에 고려할 수 있게 합니다. 예를 들어, 패턴이 "_", "B", "C"으로 주어진 경우 “_” 패턴에는 여러가지 경우에 대응할 수 있기 때문에 여러가지 매칭이 가능합니다. 이러한 특성 덕분에 패턴 매칭이 다양한 패턴을 고려할 수 있게됩니다.

  [S1] ---A--->  [S2] ---B---> [S3]
  ^  \                          /
   \--C------------------------/

S1, S2, S3는 각각 오토마타의 상태를 나타냅니다. 각 화살표는 상태 전이를 나타내며, 화살표 위의 문자는 해당 전이를 유도하는 입력을 나타냅니다.

매칭이 실패하면 이전 상태로 돌아가서 다른 경로를 탐색하는데 여기서 S3 부근이 매칭에 실패해 S1로 돌아간 후 다시 경로 C를 통해 S3로 이동하는 것을 볼 수 있습니다.

가능한 모든 경로를 탐색해야하기 때문에 불필요한 노드를 방문할 수 있고, 최악의 경우 $O(2^n)$이라는 시간복잡도를 가집니다. 하지만 다양한 상태와 상태 전이를 이용해 패턴을 찾아내기 때문에 결정 트리 방식 보다 복잡한 패턴에서는 더 유연하게 동작합니다. 또한 이 복잡도는 휴리스틱이나 memoziation과 같은 방식으로 충분히 개선할 수 있다고 봅니다.

Python으로 간단히 구현하면 다음과 같습니다.

def match_pattern_backtracking(pattern, data, index=0):
    if index == len(pattern):
        return True

    if index < len(data) and (pattern[index] == data[index] or pattern[index] == '_'):
        return match_pattern_backtracking(pattern, data, index + 1)

    return False

print(match_pattern_backtracking(['A', 'B', '_'], ['A', 'B', 'C']))  # True
print(match_pattern_backtracking(['_', 'B', '_'], ['A', 'B', 'D']))  # True
print(match_pattern_backtracking(['_', 'B', 'C'], ['A', 'B', 'D']))  # False

결정 트리와 코드는 비슷하지만, 재귀 호출을 통해 백트랙킹을 수행한다는 점에서 차이를 보입니다. 매개변수 index는 현재 어디까지 확인했는지 나타내는 역할을 합니다.

각주

[1] 패턴 매칭은 데이터 구조나 표현 식의 가장 바깥쪽 부분(예를 들어, 트리 구조에서 루트 부분)에서만 이뤄집니다. 즉, 데이터 구조와 표현식 내부에서는 매칭이 이뤄지지 않는다는 것을 의미합니다. 예를 들어 다음과 같은 코드가 있습니다.

case list of
  (x:_) -> print x          -- 첫 번째 요소를 출력
  [] -> print "Empty list"  -- 리스트가 비어있을 경우 출력

이 코드는 리스트의 상위 레벨인 첫 번째 요소에서만 패턴 매칭을 수행합니다. 리스트의 세부사항 $n$번째 요소나 중첩된 리스트의 경우는 이 코드만으로 처리되지 않습니다.

반면에 항목 재작성 규칙은 임의의 컨텍스트 $C[\space . \space]$ 에 대해 규칙 $(lhs, rhs)$을 적용해 $C[lhs] \rightarrow C[rhs]$과 같은 규칙을 적용합니다. 위에서 설명했듯, 왼쪽 항을 오른쪽의 항으로 바꾸는 것입니다.

이 임의의 컨텍스트에서는 데이터 구조의 어느 부분에서든지 이 규칙을 적용할 수 있습니다.

add([]) -> 0
add([hd | tl]) -> hd + add(tl)

예를 들어, 이 규칙은 재귀적으로 동작하면서 리스트의 모든 요소를 더합니다. 여기서 컨텍스트는 다음과 같습니다

1. 빈 리스트에 적용되는 컨텍스트. 빈 리스트를 0으로 재작성
2. 리스트의 첫번째 요소(hd)와 나머지 요소(tl)에 적용되는 컨텍스트. 리스트의 첫 번째 요소와 나머지 요소의 합을 계산하여 재작성

이와 같이, 재작성 규칙은 임의의 컨텍스트 내에서는 어느 부분이든 적용될 수 있으며, 이를 통해 데이터 구조의 내부적인 세부 사항까지 처리할 수 있습니다.

참고 자료

1. https://en.wikipedia.org/wiki/Rewriting
2. https://stackoverflow.com/a/7883554
3. Compiling Pattern Matching to Good Decision Trees (Luc Maranget)
4. 형식언어와 오토마타 (Peter Linz, 역: 김응모, 홍릉출판사, p.58)
5. https://cstheory.stackexchange.com/a/6266

어쩌다 이름도 긴 오픈소스 컨트리뷰터 아카데미(OSSCA)에 참여하게 되었는데 (참여 이유도 이름이 맘에 들어서 그냥 등록했었다. 타입 세이프 하다는데 이걸 어떻게 참음?), 참여하게 된 프로젝트는 ZIO를 가지고 뭔가하는 그런 프로젝트이다.

미리 밝히자면 스칼라는 이름만 들어봤고 ZIO는 더더욱 처음 들어봤다. 그래서 여기서 뭘 하고 이걸로는 또 뭘 하는건지 알려면 발대식에 참가했어야 했지만, 시원하게 첫날부터 지각을 한 덕분에 프로젝트에 대한 얘기는 못 나눴다(그래도 굿즈는 챙겼다. 파이콘을 제외하고 최근에 참여한 개발 관련 행사 중 가장 일상생활에서 쓰기 좋은 굿즈였다). 그래도 다음 날에 디스코드로 다음에 뭘 할건지에 대한 자료는 받아서 벼락치기로 스칼라 코드와 ZIO를 만져보게 되었고, 이건 그 벼락치기의 기록이다.

#2

아무튼 첨부된 레포에는 간단한 프로젝트들이 있었다. 다음주 까지 코드를 읽고 서로 어땠는지 얘기를 나눈다거나 미완성된 기능을 추가(*옵션임) 해봐도 된다는 말과 함께였다. 그나마 익숙한건 HTTP 서버여서 이 코드 부터 읽기로 했다. 이전에 엘릭서나 OCaml을 만져봤기 때문에 읽는거 자체는 무난했다.

#3

HTTP 서버의 코드는 스칼라를 몰라도 HTTP를 만져봤음 “대충 이렇게 저렇게 되겠구나”라는 생각이 들 정도로 직관적이였다. 요청을 처리하는 app과 각 경로로 들어오는 요청을 처리하고 응답을 하는 구조였다.

object Main extends ZIOAppDefault {

  val app =
    Http.collectZIO[Request] {
      case Method.GET -> Root / "text" =>
        for {
          _ <- zio.Console.printLine("/text endpoint!")
          res <- ZIO.succeed(Response.text("Hello World!"))
        } yield res
      case Method.GET -> Root / "apple" =>
        for {
          _ <- zio.Console.printLine("/apple endpoint!")
          res <- ZIO.succeed(Response.text("APPLE!"))
        } yield res
      case Method.GET -> Root =>
        for {
          _ <- zio.Console.printLine("root endpoint!")
          url = URL.decode("http://localhost:13333/apple").toOption.get
          res <- ZClient.request(Request.get(url))
        } yield res
    }

  override val run =
    Server
      .serve(app.withDefaultErrorResponse)
      .provideLayer(Server.defaultWithPort(13333) ++ Client.default)
}

그래서 이 HTTP 서버에 미완성된 부분을 추가하기로 했는데, 나중에 알았지만 미완성된 부분은 이게 아니라 파일 전송 프로젝트 폴더였다. 하지만 이 코드도 충분히 개선할 부분은 있으니까 상관 없지 않을까 싶다.

#404

수정을 하겠다고는 했는데, 이건 꽤나 막연한 일이다. 그래서 어떤걸 추가하면 좋을까 하면서 이것저것 만져보다 404 페이지가 따로 없다는걸 알았다. 그래서 잘못된 경로를 요청했을때 404 페이지로 보내는걸 추가하기로 했다.

404 페이지 추가는 간단하다. app에서 각 요청과 링크를 패턴 매칭으로 처리했기 때문에, 저 링크들 이외의 링크는 전부 404로 보내면 그만이라 다음과 같은 와일드카드를 추가했다.

val app =
    Http.collectZIO[Request] {
      // 생략
      case _ =>
        for {
          current <- getCurrentTime
          _ <- zio.Console.printLine(s"not found! [${req.method}] [$current]")
          res <- ZIO.succeed(Response.text("404 page not found!"))
    } yield res

그럼 이렇게 예쁘게 404 페이지가 나온다.

#5

이렇게 기능 하나를 추가했다. 하지만 페이지에 접속할 때 마다 터미널에 단순히 문자열만 출력되니까 뭔가 느낌이 안 살았다. 그 영화 같은거 보면 알록달록한 문자들이 촤라락 하면서 나오는 그런게 있어야 뭔가 하는 맛이 나듯이 터미널에 로그를 보강하기로 했다.

메시지에 색을 입히려면 ANSI 같은걸 쓰면 되는데, 이건 귀찮아서 요청 시간과 HTTP 메서드의 종류만 출력하도록 만들었다.

대충 메시지 [시간] [HTTP 메서드]

그러면 각 요청에 대한 메서드 종류와 시간을 로깅(logging)해야 하는데, 찾아보니까 ZIO에는 zio-logging이라는 라이브러리가 있어서 이걸 사용하기로 했다.

먼저 build.sbt에 종속성을 추가했고 시간과 날짜는 깔끔하게 자바의 API를 사용했다.

lazy val `http-server` = project
  .settings(sharedSettings)
  .settings(
    libraryDependencies ++= Seq(
      "dev.zio" %% "zio-http" % "3.0.0-RC2",
      "dev.zio" %% "zio-logging" % "2.1.13",   // +
    )
  )

이제 로그 메시지를 출력하도록 수정했다

import zio._
import zio.logging._
import zio.http.{Http, Request, Response, Status, _}
import java.time.ZonedDateTime
import java.time.format.DateTimeFormatter

object Main extends ZIOAppDefault {

  val app =
    Http.collectZIO[Request] {
      case req @ Method.GET -> Root =>
        for {
          current <- ZIO.effectTotal(ZonedDateTime.now().format(DateTimeFormatter.ISO_INSTANT))
          _ <- log.info(s"Time: $current - Method: ${req.method} - /")
          res <- ZIO.succeed(Response.text("Available endpoints: /text, /apple"))
        } yield res

      /*
          나머지도 비슷
      */

      case _ =>
        for {
          current <- ZIO.effectTotal(ZonedDateTime.now().format(DateTimeFormatter.ISO_INSTANT))
          _ <- log.info(s"Time: $current - Unknown method and endpoint")
          res <- ZIO.succeed(Response.text("404 page not found!"))
        } yield res
    }

  override val run =
    Server
      .serve(app.withDefaultErrorResponse)
      .provideCustomLayer(Server.defaultWithPort(13333) ++ Client.default)
}

여기서 req는 현재 요청에 대한 정보를 포함하는 Request 객체이다. 여기에 패턴 매칭 문법을 사용하면 HTTP 메소드와 URI를 분해하고, 이 정보를 사용하여 적절하게 응답을 처리할 수 있다.

예를 들어, 다음과 같은 요청은

case req @ Method.GET -> Root / "apple" => 

HTTP 메소드가 GET이고 URI가 /apple인 요청에 해당하는 경우를 나타낸다.

req @는 해당 요청 전체를 req 변수에 할당한다. 이러면 메소드나 경로 외에도 요청의 다른 부분 (예: 헤더, 쿼리 매개변수 등)에 접근할 수 있고, 이걸 이용해 다른 기능들을 추가하기도 수월해진다.

이걸로도 뭔가 있어보이는 로그 메시지를 출력하지만, 자세히 보면 current가 중복된다. 그래서 저 부분을 함수로 추출했다.

object Main extends ZIOAppDefault {

    def getCurrentTime: ZIO[Any, Nothing, String] =
    ZIO.succeed(LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")))

  val app =
    Http.collectZIO[Request] {
      case req @ Method.GET -> Root =>
        for {
          current <- getCurrentTime
          _ <- log.info(s"Time: $current - Method: ${req.method} - /")
          res <- ZIO.succeed(Response.text("Available endpoints: /text, /apple"))
        } yield res

      // ...
    }
}

이제 로그 메시지는 아래와 같이 나온다.

root endpoint! [GET] [2023-07-10 19:31:16]
/text endpoint! [GET] [2023-07-10 19:31:19]
/apple endpoint! [GET] [2023-07-10 19:31:22]

#6

어느 링크에 접속할 수 있는지 메인 페이지에 보여주면 좋을 것 같다는 생각이 들었다. 그리고 메인 페이지는 HTML을 이용해서 각 페이지로 접속할 수 있는 링크를 두면 이것저것 테스트 하기 좋겠다는 느낌도 들었다.

스칼라 코드에 HTML을 넣으려면 기존의

res <- ZIO.succeed(Response.text("text"))

에서 Response.text를 Response.html로 변경하면 된다. 그래서 맨 첫 페이지, 그러니까 로컬호스트에 접속하면 가장 먼저 보이는 페이지를 보여주는 부분을 수정했다.

object Main extends ZIOAppDefault {

  val app =
    Http.collectZIO[Request] {
      case req @ Method.GET -> Root =>
        for {
          current <- getCurrentTime
          htmlForm =
            """
            <html>
            <head>
              <title>Front Page</title>
            </head>
            <body>
              <h1>Available links</h1>
              <ul>
                <li><a href="/text">/text</a></li>
                <li><a href="/apple">/apple</a></li>
                <li><a href="/form">/form</a></li>
              </ul>
            </body>
            """
          _ <- zio.Console.printLine(s"root endpoint! [${req.method}] [$current]")
          res <- ZIO.succeed(Response.html(htmlForm))
        } yield res

            // ...
        }
}

HTML은 그냥 접속 가능한 페이지를 리스트로 보여주는 간단한 동작을 한다.

#7

뭐 이정도만 해도 충분하지만 딱 하나 아쉬웠던건 HTTP 메서드가 GET만 보이지, POST가 없었다는 것이다. 종 다양성이 보장되어야 생태계가 건강하듯이, 로그 메시지도 이것저것 보여야 질리지 않는 법이다.

그래서 어떤 메시지를 보내면 해당 메시지를 받았다고 처리하는 기능을 추가했다. 하지만 구현을 간단하게 하기 위해 /form을 통해 메시지를 전송하면, /submit 페이지에서 받았다는 응답을 보내는 식으로 동작하게 했다. 이 두 요소는 패턴 매칭 문에 추가하면 된다.

object Main extends ZIOAppDefault {
    val app =
    Http.collectZIO[Request] {
      case req @ Method.POST -> Root / "submit" =>
        for {
          current <- getCurrentTime
          _ <- zio.Console.printLine(s"root endpoint! [${req.method}] [$current]")
          res <- ZIO.succeed(Response.text("Received POST request!"))
        } yield res
      case req @ Method.GET -> Root / "form" =>
        for {
          current <- getCurrentTime
          htmlForm =
            """
            |<form action="/submit" method="post">
            |  <label for="message">Message:</label><br>
            |  <input type="text" id="message" name="message"><br>
            |  <input type="submit" value="Submit">
            |</form>
            """.stripMargin
            res <- ZIO.succeed(Response.html(htmlForm))
        } yield res
    }
}

/form 페이지는 다음과 같이 랜더링 되고,

메시지를 작성한뒤 전송하면 /submit 페이지로 이동해 메시지를 받았다는 페이지를 보여준다.

그러면 로그 창엔 이렇게 표시된다.

root endpoint! [GET] [2023-07-10 19:38:52]
root endpoint! [POST] [2023-07-10 19:45:51]

#8

아무튼 요렇게 스칼라로 HTTP 서버 코드를 개선시켜봤다. 기왕 하는거 파일 전송 코드를 건들였음 더 좋았겠지만, 벼락치기로 달리고 있기 때문에 그런 고차원적인 프로토콜은 건들 수가 없었다. 하지만 수정을 하면서 스칼라와 ZIO에 대충 익숙해지긴 한거 같다. 그래서 결론은 “패턴 매칭은 최고다”이다.

전체 코드

import zio._
import zio.http.{Http, Request, Response, Status, _}
import zio.logging._
import java.time.LocalDateTime
import java.time.format.DateTimeFormatter

object Main extends ZIOAppDefault {

  def getCurrentTime: ZIO[Any, Nothing, String] =
    ZIO.succeed(LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")))

  val app =
    Http.collectZIO[Request] {
      case req @ Method.GET -> Root =>
        for {
          current <- getCurrentTime
          htmlForm =
            """
            <html>
            <head>
              <title>Front Page</title>
            </head>
            <body>
              <h1>Available links</h1>
              <ul>
                <li><a href="/text">/text</a></li>
                <li><a href="/apple">/apple</a></li>
                <li><a href="/form">/form</a></li>
              </ul>
            </body>
            """
          _ <- zio.Console.printLine(s"root endpoint! [${req.method}] [$current]")
          res <- ZIO.succeed(Response.html(htmlForm))
        } yield res
      case req @ Method.GET -> Root / "text" =>
        for {
          current <- getCurrentTime
          _ <- zio.Console.printLine(s"/text endpoint! [${req.method}] [$current]")
          res <- ZIO.succeed(Response.text("Hello World!"))
        } yield res
      case req @ Method.GET -> Root / "apple" =>
        for {
          current <- getCurrentTime
          _ <- zio.Console.printLine(s"/apple endpoint! [${req.method}] [$current]")
          res <- ZIO.succeed(Response.text("APPLE!"))
        } yield res
      case req @ Method.GET -> Root =>
        for {
          current <- getCurrentTime
          _ <- zio.Console.printLine(s"root endpoint! [${req.method}] [$current]")
          url = URL.decode("http://localhost:13333/apple").toOption.get
          res <- ZClient.request(Request.get(url))
        } yield res
      case req @ Method.POST -> Root / "submit" =>
        for {
          current <- getCurrentTime
          _ <- zio.Console.printLine(s"root endpoint! [${req.method}] [$current]")
          res <- ZIO.succeed(Response.text("Received POST request!"))
        } yield res
      case req @ Method.GET -> Root / "form" =>
        for {
          current <- getCurrentTime
          htmlForm =
            """
            |<form action="/submit" method="post">
            |  <label for="message">Message:</label><br>
            |  <input type="text" id="message" name="message"><br>
            |  <input type="submit" value="Submit">
            |</form>
            """.stripMargin
            res <- ZIO.succeed(Response.html(htmlForm))
        } yield res
      case req @ _ =>
        for {
          current <- getCurrentTime
          _ <- zio.Console.printLine(s"not found! [${req.method}] [$current]")
          res <- ZIO.succeed(Response.text("404 page not found!"))
        } yield res
    }

  override val run =
    Server
      .serve(app.withDefaultErrorResponse)
      .provideLayer(Server.defaultWithPort(13333) ++ Client.default)
}

구현에 앞서 러스트에서 이 검사기의 역할과 이게 어떤 식으로 동작하는지 알아보겠습니다. 러스트에서 검사기는 메모리 안정성을 확보하는데 중요한 역할을 합니다. 이때 변수의 빌림 규칙(borrowing rule)을 강제로 적용하는데, 러스트에서의 규칙은 다음과 같습니다.

1. 동시에 가변, 불변 참조를 가질 수 없음: 한 스코프 내부에서 어떤 변수가 가변 참조 되고 있는 동안에는 그 변수에 대한 불변 참조를 만들 수 없고, 반대의 경우도 마찬가지입니다.
2. 한 번에 하나의 가변 참조만 존재할 수 있음: 어떤 변수에 대한 가변 참조가 존재하는 동안에는 그 변수를 동시에 다른 곳에서 참조하거나 수정하는 것을 방지하는 역할을 합니다.
3. 불변 참조는 동시에 여러 개 존재할 수 있음: 가변 참조와 다르게 불변 참조는 해당 변수를 읽는 작업에서 사용합니다. 읽는 작업은 수정과 다르게 데이터의 변형이 일어나지 않기 때문에 한 스코프 내에서 여러 개의 불변 참조를 생성해도 문제가 없습니다. 어찌보면 RwLock과 비슷한 동작을 한다고 생각하면 됩니다.

이 검사기는 컴파일 시간에 프로그램을 분석해 이 규칙들을 지키는지 검사하는 역할을 합니다. 러스트의 검사기는 소유권 시스템과 라이프타임 개념을 사용해 빌림 규칙을 적용합니다.

참고로 소유권 시스템은 변수가 오직 하나의 소유자(owner)를 가지며, 소유자가 스코프를 벗어나면 변수가 메모리에서 해제되는 것을 보장하고, 라이프타임은 변수의 참조가 유효한 범위를 지정해 변수를 추적합니다.

논리 명제 표현식과 추론 규칙

들어가기에 앞서 코드를 읽기 쉽게 축약할 수 있는 논리 명제 표현식을 소개하겠습니다. 이 논리 표현식을 이용하면 복잡한 복합 명제를 단순하게 표현할 수 있습니다.

기본 연산자는 다음과 같습니다.

1. 부정($\neg$): 명제 P의 부정은 "$P$가 아님"을 의미
2. 논리곱($\land$, and): 두 명제 $P$와 $Q$의 논리곱은 "$P$와 $Q$ 모두 참"
3. 논리합($\lor$, or): 두 명제 $P$와 $Q$의 논리합은 "P 또는 $Q$ 중 적어도 하나는 참”
4. 조건부($\rightarrow$): 두 명제 $P$와 $Q$에 대한 $P \rightarrow Q$는 "$P$가 참이면 $Q$도 참"
5. 동치($\leftrightarrow$): 두 명제 $P$와 $Q$에 대한 $P \leftrightarrow Q$는 "$P$와 $Q$는 모두 참이거나, 모두 거짓"

추론 규칙은 아래의 표기법을 이용해 표기할 수 있습니다.

$$ \frac{전제}{결론} $$

이 표기법은 주어진 전제에서 어떤 결과가 나오는지를 나타냅니다.

표기법에서 가로선 위의 내용은 "전제"를, 가로선 아래의 내용은 "결론"을 의미합니다. 즉, "전제가 참이면 결론도 참이다"라는 추론 규칙을 표현합니다.

예를 들어, modus ponens(전건 긍정, MP)을 이 표기법을 이용해 표현하면 다음과 같습니다.

$$ \frac{P \space \space P \rightarrow Q}{Q} $$

이 추론 규칙은 "$P$가 참이고 $P$가 참일때 $Q$도 참이면, $Q$는 참이다"라는 논리적 추론을 나타냅니다.

이 명제 표현식과 추론 규칙을 적절히 사용한다면 복잡한 규칙도 간결하게 표현할 수 있습니다. 그래서 이후에 코드 설명에서 좀 길다 싶으면 이 표기법들을 이용할 것입니다.

Borrow System

이제 대여 검사기를 구현해보겠습니다. 러스트에는 이런 방식으로 구문을 분석하고 상태를 지정합니다.

단계를 나눈다면 코드 파싱(parsing)과 검사 단계로 나눌 수 있는데 파싱은 말 그대로 코드를 읽고 AST(추상 구문 트리)를 생성하는 단계입니다.

이후 검사기는 생성된 AST를 순회하면서 모든 변수와 그 참조 관계에 어떤 상태를 지정합니다. 이 상태는 참조 관계와 여부를 나타내며 각각 불변/가변 대여, 다중 대여, 대여 없음 4가지 경우로 나뉩니다. 이후 부여된 각 상태에 맞게 변수와 참조를 처리하면 끝입니다. 간단하죠?

하지만 여기서 작성한 검사기는 여러가지 복잡한 사정으로 인해 가변 참조는 다루지 않습니다. 그래서 나오는 모든 참조는 모두 불변 참조입니다. 더 간단하죠?

인스턴스 생성과 Borrow State

이제 검사기 구현을 해보겠습니다. 시작이 반이니 검사기 인스턴스와 BorrowState를 먼저 정의해야 합니다.

검사기의 구조는 변수의 borrow 정보를 저장할 공간과 스코프 정보만 저장하면 되기 때문에 저는 HashMap을 사용했습니다. 이렇게 하면 borrows는 스코프 단위로 각 변수와 표현식의 대여 관계를 저장하는 컨테이너의 역할을 합니다.

pub struct BorrowChecker<'a> {
    borrows: Vec<HashMap<&'a str, BorrowState>>,
}

해시 맵의 키와 값은 각각 변수 이름과 borrow 정보를 나타냅니다. 다음으로, 상태를 나타내는 BorrowState를 정의해보겠습니다.

#[derive(Debug, PartialEq)]
pub enum BorrowState {
    Uninitialized,
    Initialized,
    Borrowed,
    ImmutBorrowed,
}

위 그림과 다르게 4가지 상태로 정의했습니다. Uninitialized와 Initialized는 각각 변수가 현재 인식되었는지를 확인하는 플래그입니다. 그리고 Borrowed와 ImmutBorrowed는 borrow의 상태와 유형을 나타냅니다. 예를 들어, Borrowed 표시가 없으면 이는 참조되지 않은 일반 변수를 의미하며, ImmutBorrowed는 불변 참조를 나타내는 플래그입니다.

이제 기본 설정은 끝났으니 검사기의 인스턴스를 생성해보겠습니다. 이 인스턴스는 BorrowChecker::new 함수를 통해 생성됩니다.

impl BorrowChecker {
    pub fn new() -> Self {
            BorrowChecker {
            borrows: vec![HashMap::new()],
      }
     }
}

Checking Statement

검사기는 생성된 AST를 순회하면서 변수의 borrow 유형을 검사하고 상태를 부여하고 각 상태에 맞는 메소드를 호출하는 방식으로 작동합니다.

상태를 할당하기 전에 먼저 참조(reference)와 관련된 AST를 보기전에 미리 짚고 넘어가야 되는 사항이 있습니다. Expression::Reference를 정의할 때 String이 아니라 Box<Expression>을 사용했어야 했다는 점입니다. 작성 당시 제작 목표는 최소한의 동작만을 하도록 하는 것이였고, 참조는 변수 이름만 처리하도록 하는게 목표였습니다. 그래서 이후 참조된 함수를 호출(ex. let a = &foo(a, &b))하는 것은 불가능하다는 점을 미리 알립니다.

// ast.rs

#[derive(Debug, PartialEq)]
pub enum Statement {
    VariableDecl {
        name: String,
        value: Option<Expression>,
        is_borrowed: bool,
    },

        // ...
}

#[derive(Debug, PartialEq)]
pub enum Expression {
    // ...
    Reference(String),
}

이후 생성된 AST는 BorrowChecker::check_statement와 BorrowChecker::check_variable_decl을 통해 처리됩니다. BorrowChecker::check_statement는 주어진 구문이 Statement::VariableDecl인지 확인하고, check_variable_decl 함수를 호출합니다. 이런 방식으로 Statement::VariableDecl을 처리할 수 있습니다.

type BorrowResult = Result<(), BorrowError>;

impl BorrowChecker {
    fn check_statement(&mut self, stmt: &'a Statement) -> BorrowResult {
        match stmt {
            Statement::VariableDecl { ... } => self.check_variable_decl(name, value, *is_borrowed),
            _ => unimplemented!("나머지는 이후에 다룸."),
        }
     }

    fn check_variable_decl(
        &mut self,
        name: &'a str,
        value: &'a Option<Expression>,
        is_borrowed: bool,
    ) -> BorrowResult {
        match (is_borrowed, value) {
            // 1
            (true, Some(Expression::Reference(ref ident))) => {
                if let Some(state) = self.get_borrow(ident) {
                    match state {
                        BorrowState::Borrowed | BorrowState::Uninitialized => /* 에러 */
                        _ => {}
                    }
                    self.insert_borrow(name, BorrowState::ImmutBorrowed);

                    return Ok(());
                }

                Err(BorrowError::VariableNotDefined(ident.into()))
            }
            // 2
            (false, Some(expr)) => {
                self.check_expression(expr)?;
                self.insert_borrow(name, BorrowState::Initialized);

                Ok(())
            }
            // 3, 4
           (true, _) | (false, None) => /* 에러 처리 */
        }
    }
}

BorrowChecker::check_variable_decl 함수는 변수의 정보를 토대로 BorrowState를 결정합니다. 변수의 대여 여부와 값에 따라 패턴 매칭을 수행하고, 그 결과에 따라 상태를 지정합니다. 이 과정은 변수의 대여 상태를 추적하고 대여 규칙을 잘 지키고 있는지 확인하는 단계입니다.

패턴 매칭 부분에서 각각 어떤 역할을 하는지 간단히 살펴보겠습니다. 번호는 코드에 주석으로 매긴 조건 번호입니다.

1. 변수가 참조되었고, 값이 참조되는 경우입니다. 이 경우 이미 대여된 변수에 대한 참조를 생성하려는지 확인합니다.
2. 변수가 참조되지 않았지만, 값이 있는 경우를 나타냅니다. 일반 변수 선언을 나타내기 때문에 대여 상태를 Initialize로 설정합니다.
3. 변수가 참조되었지만, 값은 참조되지 않은 케이스를 나타냅니다. 존재하지 않는 변수를 대여하려는 상황을 나타내기 때문에 에러를 반환합니다.
4. 변수가 대여되지 않았고, 값도 없는 케이스입니다. 초기값 없이 변수를 선언하려는 시도를 나타내기 때문에 에러를 반환합니다.

명제를 추출하면 위 케이스들을 간결하게 표현할 수 있습니다. 해당 함수의 명제는 다음과 같습니다.

• $P$: stmt가 Statement::VariableDecl인 경우
• $Q$: is_borrowed가 true인 경우
• $R$: 어떤 변수 선언에서 value가 참조인 경우
• $S$: 선언된 변수의 상태가 BorrowState::Borrowed 또는 BorrowState::Uninitialized인 경우
• $T$: ident에 해당하는 state가 존재함.
• $U$: 변수의 값이 존재함.
• $V$: 변수가 대여되지 않음
• $E$: 에러

먼저, BorrowChecker::check_statement를 위 명제들로 표현해보겠습니다.

$$ P \rightarrow CheckVariableDecl $$

이 표현식은 단순히 검사하고 있는 구문의 AST에 Statement::VariableDecl이 포함되어 있다면 특정 함수를 호출하라는 조건을 나타냅니다.

또한 패턴 매칭의 각 케이스는 아래와 같이 표현할 수 있습니다. 이 케이스들을 모두 check_variable_decl 함수 내부에서 동작하기 때문에 $P$가 항상 참인 경우에만 성립합니다. 그래서 표기의 단순화를 위해 $P$는 생략했습니다.

1. $Q \land R \land T \land \lnot S \rightarrow$ $ImmutBorrow$
2. $\lnot Q \land (\lnot R \land U )\rightarrow Initialized$
3. $Q \land \lnot R \rightarrow E$
4. $\neg U \land V \rightarrow E$

지금까지의 내용을 요약하면 다음과 같습니다

• BorrowChecker는 AST를 순회하면서 변수의 대여 유형을 확인하고 상태를 부여하는 함
• 검사기는 check_statement와 check_variable_decl 함수를 통해 변수의 대여 유형과 상태를 부여함
• check_statement는 Statement::VariableDecl인 구문을 확인
• check_Variable_decl 함수는 변수의 정보를 기반으로 BorrowState를 결정

스코프 관리

그럼 대여의 범위는 어떻게 관리해야 할까요? 개발자가 직접 처리하는 방법도 있지만, RAII(Resouce Acquisition is Initialization)와 같이 스코프를 벗어나면 자동으로 해제하도록 하는게 더 편리하고 안전할 것 같아서, 여기서는 이 방법을 사용하겠습니다. 물론 러스트도 이 방법을 사용하기도 해서 그렇습니다.

RAII는 스코프의 진입 시점에 리소스를 할당하고, 스코프를 벗어나는 시점에서 자동으로 해제하는 방식입니다. 이를 구현하는BorrowChecker::allocate_scope 함수를 살펴보겠습니다.

BorrowChecker::allocate_scope 함수는 제네릭 함수로 FnOnce를 이용하여 각 값 마다 필요한 처리를 하고 개별 스코프에 처리된 값들을 할당합니다.

impl BorrowChecker {
    fn allocate_scope<F, T>(&mut self, action: F) -> T
    where
        F: FnOnce(&mut Self) -> T,
    {
        // 스코프 할당
        self.borrows.push(HashMap::new());

        // 각 스코프에서 구문에 맞는 처리를 함
        let result = action(self);

        // 스코프 해제
        self.borrows.pop();

        result
    }
}

이 함수는 새로운 스코프를 할당하고(push), 스코프 범위를 벗어나면 대여한 변수들을 해제(pop)합니다. 즉, RAII의 개념을 구현하고, 스코프의 범위에 따라 자동으로 할당과 해제를 관리합니다,

이 함수와 함께 사용하는 함수로는 check_function_def나 check 등, 어떤 스코프 범위를 지정해야 하는 구문을 처리하는 함수들이 있습니다(여기서 다루진않지만 if-else와 같은 조건문도 해당함). 이 함수들은 allocate_scope 함수를 통해 스코프를 관리합니다.

impl BorrowChecker {
    fn check_statement(&mut self, stmt: &'a Statement) -> BorrowResult {
      match stmt {
          Statement::FunctionDef { name, args, body } => {
              self.allocate_scope(|s| s.check_function_def(name, args, body))
          }
          Statement::Scope(stmts) => self.allocate_scope(|s| s.check(stmts)),
          _ => unimplemented!("지금은 일단 생략")
      }
     }
}

이러한 방식은 stack discipline 방식을 반영합니다. 스택에는 각 구문(ex. 함수)에 대한 프레임이 있으며, 함수 호출과 반환, 블록 진입과 탈출 등 프로그램의 실행 흐름에 따라 메모리를 자동으로 관리합니다. 후입선출(LIFO) 구조를 가지고 있기 때문에 가장 마지막에 추가된 항목이 가장 먼저 제거되는 특성이 있습니다.

스택의 특성 덕분에 RAII를 사용할 수 있고, 이 RAII 덕분에 명시적으로 메모리를 관리할 필요 없이 자동으로 스코프를 관리할 수 있습니다.

변수 선언과 처리

BorrowChecker에서 변수를 관리하는 함수는 BorrowChecker::check_variable_decl와 BorrowChecker::check_borrowed_variable입니다. 여기서는 대여된 변수를 처리하는 것만 보겠습니다.

이전에 변수는 다음 AST를 통해 생성된다는걸 확인했었습니다.

#[derive(Debug, PartialEq)]
pub enum Statement {
    VariableDecl {
        name: String,
        value: Option<Expression>,
        is_borrowed: bool,
    },
    // ...
}

이후, 생성된 AST는 BorrowChecker::check_borrowed_variable로 전달됩니다. 이때 BorrowChecker::check 함수를 통해서 전달됩니다.

impl BorrowChecker {
    fn check_borrowed_variable(
        &mut self,
        name: &'a str,
        value: &'a Option<Expression>,
    ) -> BorrowResult {
        if let Some(Expression::Ident(ref ident)) = value {
            if let Some(state) = self.get_borrow(ident) {
                if state == &BorrowState::Borrowed {
                    return Err(/* 변수가 이미 대여된 상태라 다시 대여할 수 없음 */);
                }

                self.insert_borrow(name, BorrowState::ImmutBorrowed);
                return Ok(());
            }

            return Err(/* 변수 선언 안됨 */);
        }

        Err(BorrowError::InvalidBorrow(name.into()))
    }
}

이 함수는 검사해야할 변수식이 대여 규칙을 만족하고 있는지 검사합니다. 변수가 대여 상태(BorrowState::Borrowed)가 아닌 경우 self.insert_borrow 함수를 통해 변수와 상태를 등록하지만, 대여 상태인 변수가 들어오면 에러를 반환합니다.

표기를 단순화하기 위해 코드의 상황과 조건을 나누어 논리적 명제로 표현해보겠습니다. 주요 단계를 명제로 표현하면 다음과 같습니다.

• $P$: 값이 ident로 선언되어 있음
• $Q$: ident에 해당하는 state가 존재함
• $R$: state가 BorrowState::Borrowed임
• $S$: 통과
• $E$: 에러 반환. (에러 메시지는 여러 종류이지만 편의상 $E$로 통일)

이 명제들을 이용해 BorrowChecker::check_borrowed_variable를 표현하면 다음과 같고, 대여 규칙을 만족하는 경우는 한 가지입니다.

$$ \frac{P \space \space \space Q \space \space \space \neg R}{S} $$

값이 선언되어 있고 상태가 있지만, 값이 이미 대여된 상태가 아닌 경우에만 유효합니다. 그 외 다른 조건들은 모든 대여 규칙을 만족하지 않습니다.

$$ \frac{P \space \space \space Q \space \space \space R}{E} \space \space \space \frac{P \space \space \neg Q}{E} \space \space \space \frac{\neg P}{E} $$

함수 선언과 호출 처리

함수와 관련된 기능은 두 가지가 있습니다. 첫 번째는 함수를 선언하는 것이고, 두 번째는 함수를 호출하는 것입니다. 또한, 함수는 개별적인 스코프를 가지고 있습니다.

함수의 범위를 검사하는 것은 상대적으로 쉽습니다. BorrowChecker::check 함수는 AST를 재귀적으로 순회하면서 각 구문에 맞는 함수를 호출하고 있습니다. 따라서 함수 구문 처리 함수를 작성하고, 이를 check 함수에 추가하면 됩니다. 함수 구문 처리 함수는 함수 선언을 처리하는 메서드와 함수 호출을 처리하는 메서드로 구성됩니다.

먼저, 함수와 관련된 AST를 살펴보겠습니다.

#[derive(Debug, PartialEq)]
pub enum Statement {
    FunctionDef {
        name: String,
        // boolean은 함수가 대여됐는지 표시합니다.
        args: Option<Vec<(String, bool)>>,
        body: Vec<Statement>,
    },
    Return(Option<Expression>),
    Expr(Expression),
}

#[derive(Debug, PartialEq)]
pub enum Expression {
    // ...
    FunctionCall {
        name: Box<Expression>,
        args: Vec<Expression>,
    },
}

이 AST는 함수의 구문 구조를 나타냅니다. FunctionDef는 함수 정의를 나타냅니다. 특히 args의 튜플은 각 매개변수의 이름과 참조 여부를 나타냅니다. 예를들어, function foo(a, &b)가 있다면 [("a", false), ("b", true)]의 형태로 표시됩니다. Statement의 나머지 요소들인 Return은 함수의 반환값을 나타내고, Expr은 단일 표현식을 나타냅니다.

Expression은 표현식을 나타내고, FunctionCall은 함수 호출을 표현합니다. 호출할 함수의 이름과 전달할 인자 목록을 가지고 있습니다.

정의된 함수에 스코프를 할당하는 것과 함수 호출을 처리하는 것도 여타 구문 처리와 마찬가지로 BorrowChecker::check_statement를 통해 이루어집니다. 또한 함수는 내부에 여러 구문과 스코프를 가지고 있고, 또 어떤 함수는 반환 값을 가지고 있기 때문에 나머지 요소들도 추가해줘야 합니다.

impl BorrowChecker {
    fn check_statement(&mut self, stmt: &'a Statement) -> BorrowResult {
        match stmt {
            Statement::VariableDecl { ...} => self.check_variable_decl(...),
            Statement::FunctionDef { name, args, body } => {
                self.allocate_scope(|s| s.check_function_def(name, args, body))
            }
            Statement::FunctionCall { name, args } => self.check_function_call(name, args),
            Statement::Scope(stmts) => self.allocate_scope(...),
            Statement::Return(expr) => self.check_return(expr),
            Statement::Expr(expr) => self.check_expression(expr),
        }
    }
}

Statement::FunctionDef와 다르게 Statement::FunctionCall과 Statement::Return 그리고 Statement::Expr은 따로 스코프를 할당할 필요가 없기 때문에 그냥 호출을 하면 됩니다. 또한 단순히 AST에 해당 토큰이 있는지 확인을 하는 역할이 전부이기 때문에, 여기서는 Statement::FunctionDef만 다루도록 하겠습니다.

이 함수와 관련된 코드는 다음과 같습니다.

impl BorrowChecker {
    fn check_function_def(
        &mut self,
        _name: &'a str,
        args: &'a Option<Vec<(String, bool)>>,
        body: &'a [Statement],
    ) -> BorrowResult {
        self.borrows.push(HashMap::new());

        // 함수의 매개 변수 처리
        if let Some(args) = args {
            for (arg, is_borrowed) in args {
                self.insert_borrow(arg, BorrowState::Initialized);

                if *is_borrowed {
                    self.borrow_imm(arg)?;
                }
            }
        }

        // 함수 내부 구문 확인
        let result = self.check(body);

        // borrow 해제
        self.borrows.pop();

        result
    }

        fn borrow_imm(&mut self, name: &'a str) -> BorrowResult {
        let state = self.get_borrow(name);
        if state.is_none() || state == Some(&BorrowState::Initialized) {
            self.insert_borrow(name, BorrowState::ImmutBorrowed);
            return Ok(());
        }

        Err(BorrowError::CannotBorrowImmutable(name.into()))
    }
}

먼저 BorrowChecker::check_function_def 부터 보겠습니다. 이 함수는 정의된 함수를 확인하는 역할을 합니다. 먼저 새로운 스코프를 생성하고, 주어진 매개변수들을 스코프에 등록합니다. 등록된 매개변수는 borrowed된 상태인 경우 immutably borrowed로 설정합니다. 이후 함수의 본문(body)를 분석하고, 해당 범위에서의 빌림을 해제(pop)합니다.

BorrowChecker::borrow_imm 함수는 주어진 이름의 변수를 불변하게 빌리는 작업을 합니다. 해당 변수가 아직 정의되지 않았거나 이미 초기화된 상태라면, 변수의 상태를 불변 대여로 변경하는 역할을 합니다. 러스트의 빌림 규칙을 적용하는 메서드라고 볼 수 있습니다.

요약하면 다음과 같습니다.

• check_function_def() 함수는 함수의 매개변수를 처리할 때, 매개변수가 변경 가능 여부를 확인
• 변경 가능한 매개변수는 BorrowState::ImmutBorrowed 상태로 대여 됨
• borrow_imm() 함수는 변수를 변경 불가능한 상태로 대여할 때, 해당 변수가 이전에 변경 가능한 상태로 대여되었는지 확인

결론

이렇게 빌림 규칙을 적용하는 코드를 작성해봤습니다. 물론 설계상의 오류도 있고 의도적으로 생략된 기능들도 있어서 완전히 러스트의 그것과 똑같이 동작한다고 할 순 없습니다. 하지만 코드 분석 시 어떻게 동작하고, 어떤 식으로 작동하는지 참고하는 용으로는 나쁘지 않은 것 같습니다. 당연히 개인적인 생각입니다.

만약 러스트 처럼 라이프타임(lifetime)을 추가한다면 대여 규칙을 적용한 것처럼 똑같이 라이프타임 규칙을 추가하면 됩니다. 라이프타임도 별반 다를 것 없이, 값을 넣기 위한 메모리를 할당 받고 있는 동안만 유효하고, 변수가 정의된 스코프 범위 내에서만 유효하다는 점에서 여기서 작성한 규칙과 딱히 다른 점이 없어 규현 자체는 무난할 것 같습니다. 나중에 시간이 되는대로 라이프타임 구현도 다루겠습니다.

참고 문서

1. https://rustc-dev-guide.rust-lang.org/borrow_check.html
2. http://www.aistudy.co.kr/logic/inference_rule.htm
3. https://www.cs.cmu.edu/~410-s14/lectures/L02_Stack.pdf
4. https://rust-lang.github.io/rfcs/2094-nll.html
5. https://blog.devgenius.io/rust-lifetimes-simplified-part-1-the-borrow-checker-b851b570d043
6. https://arxiv.org/abs/2205.05181

어디서 부터 꼬인건지는 다행히 금방 찾아냈다. 코드 맨 밑 바닥을 지탱하고 있는 타입을 선언할 때 “설마 여기까지 기능을 확장하겠어?”라는 안일한 생각으로부터 발생한 문제였다. 이렇게 git blame을 돌릴 필요도 없이 순식간에 원인을 찾아냈고, 내가 입력해야 할 명령어는 git blame —myself였다는걸 깨닫는데는 오랜 시간이 걸리지 않았다.

처음 작성할 때 모든 확장 가능성을 열어두고 작성했으면 진작에 수정하고도 남았을 것이다. 하지만 깨닫게 된 시점에선 이런 생각은 아무런 의미가 없다. 문제는 해결되지 않았고, 수정할 파일은 여전히 산더미 처럼 쌓여있다.

잘못 설계된(작성된) 코드는 바이러스와 같다. 작성 시점에서는 잠복기를 가져 아무 문제 없이 잘 돌아가지만, 결국 어느 시점에는 문제가 터지고 그 문제는 손 쓸 새도 없이 씨뻘건 에러 표시와 함께 모든 파일로 번져나간다.

뭐시기 주도 개발이 성행하는 요즘, 그 어떤 방법론을 사용하더라도 애초에 적용대상이 잘못 설계된 코드라면 맥을 못 추릴게 분명하다.

이제 해결책은 두 가지다. 전부 수정하거나, 포기하거나. 나는 후자를 택했다. 지금 재작성하는게 장기적으로도 좋은 선택임이 분명하다. 하지만 시간이 부족하기에 좋은 선택인걸 알고도 선택하지, 아니 선택할 수 없었다.

현재 내 코드는 데스 스파이럴에 빠진 개미와 같다. 하지만 결국 전부 수정이라는 좋은 방안 대신 “버그가 아니라 기능"이라는 택도 없을 이 세단어로 소용돌이를 가리는 재귀적-지록위마(指鹿僞馬)를 택하기로 결정했다. 하지만 언젠간 이것도 터질 때가 올 것이다.

이전 포스팅에서 우리는 기초적인 동시성과 액터 모델에 대해 알아보았습니다. 하지만, 작성한 액터 모델에는 오버플로우를 발생시킬 가능성이 있었습니다. 바로 2개 이상의 액터가 서로를 구독하면 무한히 메시지가 돌면서 값이 계속 업데이트 되는 것이였죠. 이번 포스팅에서는 그래프 탐색 알고리즘을 이용해 문제가 되는 부분을 미리 찾아내는 작업을 해보겠습니다.

그래프

액터를 노드로 구독 관계를 간선으로 표현하면 $G = (V, E)$ 꼴의 그래프로 표현할 수 있습니다. 구독 관계는 방향성이 있기 때문에 유향 그래프(directed graph)로 볼 수 있습니다. 유향 그래프에서 사이클이 있는지 검사하는 것은 주어진 그래프가 유향 비순환 그래프(DAG, Directed Acyclic Graph)인지 판별하는 것입니다.

어떤 노드 $v$에서 출발해 간선을 따라 다시 노드 $v$로 돌아온다면 순환한다고 합니다. 이때 그래프에 순환하는 구조가 없다면(즉, 사이클이 없다면) 유향 비순환 그래프, 즉 DAG(directed acyclic graph)라고 합니다.

이 DAG를 검사하는 알고리즘은 여러가지가 있지만, 여기서는 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 방식을 사용할 것입니다.

깊이 우선 탐색(DFS)

깊이 우선 탐색은 이름 처럼 깊이(depth)를 우선으로 하는 탐색 알고리즘입니다. 즉, 그래프의 어떤 노드에서 출발해 한 경로를 따라 가능한 깊은 곳 까지 내려면서 그래프를 탐색합니다. 탐색 중 더 이상 방문할 노드가 없다면 왔던 길을 되돌아가는(backtrace) 방식을 사용합니다.

1. 시작 노드를 스택에 추가
2. 현재 스택의 맨 위에 있는 노드를 확인
    |방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리 
    | 방문하지 않은 인접 노드가 없다면 스택에서 해당 노드를 꺼냄
3. 2번 과정을 스택이 빌 때까지 반복

너비 우선 탐색(BFS)

너비 우선 탐색은 너비(breadth)를 우선으로 하는 탐색 알고리즘입니다. DFS가 한 노드에서 출발해 가장 깊은 곳 까지 내려가는 방식을 사용했다면, BFS는 특정 노드에서 시작해 인접한 노드들을 모두 탐색하고, 방문했던 노드에서 인접한 노드들을 또 탐색하는 방식으로 동작합니다.

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼내고 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 넣고 방문 처리
3. 2번 과정을 큐가 빌 때까지 반복

위상정렬

위상 정렬을 방향성이 있는 그래프 구조에서 사용하는 알고리즘으로, 그래프의 노드들 선형으로 정렬하는 역할을 합니다. 이때 나열되는 순서는 간선들의 방향을 따라야 합니다. 예를 들어, 노드 A에서 노드 B로 향하는 간선이 있다면 A는 B 보다 앞서야 합니다. 이렇게 위상 정렬은 노드들의 선후관계를 유지하며 모든 노드를 나열할 수 있게 해줍니다.

1. BFS를 사용, 그래프의 모든 노드를 방문
2. 각 노드에 대해 BFS를 수행 
    | 더 이상 방문할 수 있는 인접 노드가 없다면, 해당 노드를 리스트의 앞쪽에 추가
3. 완료

참고로 위 세 알고리즘 모두 시간 복잡도는 $O(V+E)$를 가집니다. $V$는 그래프 내의 노드의 수를, $E$는 간선의 수를 의미합니다. 또한 공간 복잡도는 $O(V)$입니다.

구현

이제 각 알고리즘을 구현하면서 어느 알고리즘이 더 효율적인지 벤치마크를 돌려보면서 비교해보겠습니다. 벤치마크는 러스트의 criterion을 사용했습니다.

DFS, BFS 그리고 위상 정렬 순으로 본 뒤, 벤치마크 순서대로 보겠습니다. 먼저 DFS의 구현입니다.

impl ActorPool {
    pub fn detect_cycle_dfs(&self, actor_id: usize) -> Result<bool, ActorError> {
        let actor = self.get_actor_info(actor_id)?;

        let mut visited = HashSet::new();
        let mut stack = Vec::new();

        visited.insert(actor_id);
        stack.push(actor);

        while let Some(curr_actor) = stack.pop() {
            let subs = curr_actor.get_subscribers();

            for sub in subs {
                if visited.contains(&sub) {
                    return Ok(true);
                }

                let sub_actor = self.get_actor_info(sub)?;
                stack.push(sub_actor);
                visited.insert(sub);
            }
        }

        Ok(false)
    }
}

이 코드에서 시작 노드는 actor입니다. 이 노드에서 출발해 방문한 모든 노드는 visited에 저장됩니다. 탐색 중에 노드의 하위 노드(구독자)가 이미 visited에 있다면, 그래프에 사이클이 존재한다는 것이므로true를 반환해 사이클을 판별할 수 있습니다.

BFS의 구현도 보겠습니다.

impl ActorPool {
    pub fn detect_cycle_bfs(&self, actor_id: usize) -> Result<bool, ActorError> {
        let actor = self.get_actor_info(actor_id)?;

        let mut visited = HashSet::new();
        let mut q = VecDeque::new();

        visited.insert(actor_id);
        q.push_back(actor);

        while let Some(curr_actor) = q.pop_front() {
            let subs = curr_actor.get_subscribers();

            for sub in subs {
                if visited.contains(&sub) {
                    return Ok(true);
                }

                let sub_actor = self.get_actor_info(sub)?;
                q.push_back(sub_actor);
                visited.insert(sub);
            }
        }

        Ok(false)
    }
}

DFS와 비슷하지만, 스택 대신 큐를 사용하는데 collections::VecDeque를 사용했습니다. VecDeque는 양쪽 끝에서의 삽입과 삭제가 효율적으로 이루어지는 동적 배열로 구성된 큐입니다. 사이클을 판별하는 방법은 DFS와 같습니다.

마지막으로 위상정렬의 구현을 보겠습니다. 이때 그래프 탐색에는 BFS 방식을 사용했습니다.

impl ActorPool {
    pub fn detect_cycle_topological_sort(&self, actor_id: usize) -> Result<bool, ActorError> {
        // map to store the in-degree of each actor
        let mut in_degree: HashMap<usize, i32> = HashMap::new();

        let init_actor = self.get_actor_info(actor_id)?;
        let init_subs = init_actor.get_subscribers();

        in_degree.insert(actor_id, 0);

        for sub in init_subs {
            in_degree.insert(sub, 0);
        }

        // calculate the in-degree of each node in the subset
        for (_, actor) in self.actor_list.lock().unwrap().iter() {
            let subs = actor.get_subscribers();

            for sub in subs {
                if let Some(degree) = in_degree.get_mut(&sub) {
                    *degree += 1;
                }

                in_degree.insert(sub, 1);
            }
        }

        // queue to store nodes with in-degree of 0
        let mut q: VecDeque<usize> = VecDeque::new();

        // add nodes with in-degree of 0 to the queue
        for (id, degree) in in_degree.iter() {
            if *degree == 0 {
                q.push_back(*id);
            }
        }

        while let Some(curr_id) = q.pop_front() {
            // get current actor and its subscribers
            let curr_actor = self.get_actor_info(curr_id)?;
            let curr_subs = curr_actor.get_subscribers();

            for sub in curr_subs {
                if let Some(degree) = in_degree.get_mut(&sub) {
                    *degree -= 1;

                    // if in-degree becomes 0, add the subscriber to the queue
                    if *degree == 0 {
                        q.push_back(sub);
                    }
                }
            }
        }

        Ok(in_degree.values().any(|&degree| degree != 0))
    }
}

위상정렬을 이용해서 사이클을 판별하는 방법의 기본 전제는 “사이클이 없는 그래프에서만 정렬이 가능”하다 입니다. 따라서 위상 정렬을 적용할 수 없는 노드가 있다면 사이클이 있다고 판별할 수 있습니다. 이 함수의 구조는 다음과 같습니다.

1. 방문 차수(In-degree, 이하 차수) 계산: 방문 차수는 다른 노드에서 들어오는 간선의 수를 의미하며, 이 차수를 계산합니다. 그래프에 사이클이 없다면, 반드시 하나 이상의 노드는 방문 차수가 0이 되어야 합니다.
2. 큐 초기화: 계산된 차수를 바탕으로, 큐에 차수가 0인 노드를 추가합니다.
3. 정렬 적용: 큐에서 노드를 하나씩 꺼낸 뒤, 그 노드가 가리키는 노드(subscriber)의 차수를 1씩 감소시킵니다. 이후 차수가 0이 된 노드를 큐에 추가합니다. 이 과정을 큐가 빌 때까지 반복합니다.
4. 사이클 유무 판단: 모든 노드를 처리한 후에도 in-degree가 0이 아닌 노드가 있다면 그래프에는 사이클이 존재한다는 의미입니다. 따라서 마지막에 in-degree가 있는지 확인하고, 만약 있다면 true를 반환합니다.

위 세 알고리즘은 특정 액터에 하위 액터(구독자)를 추가할 때 사이클이 생기는지 검사하는 목적이라 전체 액터 그래프를 검사하지 않습니다. 만약 그래프 전체에서 사이클을 판별할 때는 특정 액터의 ID를 받는 대신 그래프를 받는 식으로 수정해야 합니다.

아무튼, 이렇게 세 가지 알고리즘을 구현해 봤습니다. 이제 벤치마크를 돌려보면서 어느 알고리즘이 효율적인지, 그리고 그게 왜 다른 알고리즘 보다 효율적인지 알아보겠습니다.

벤치마크

벤치마크는 criterion을 이용했습니다.

// rustor/benches/benchmark.rs

use criterion::{criterion_group, criterion_main, Criterion, BenchmarkId, black_box};
use rustor::model::actor::ActorPool;

fn create_large_graph(n: usize) -> ActorPool {
    let total_actors = n;

    let pool = ActorPool::new();
    let mut actor_ids: Vec<usize> = Vec::new();

    for _ in 0..total_actors {
        let actor_id = pool.create_actor();
        actor_ids.push(actor_id);
    }

    for i in 1..total_actors {
        pool.subscribe(actor_ids[i], vec![actor_ids[i - 1]])
            .unwrap();
    }

    // create cycle by making the last actor subscribe to the first actor
    pool.subscribe(actor_ids[0], vec![actor_ids[total_actors - 1]])
        .unwrap();

    pool
}

fn benchmark(c: &mut Criterion) {
    let pool = create_large_graph(1500);

    c.bench_function("dfs_cycle_detection", |f| {
        f.iter(|| pool.detect_cycle_dfs(0).unwrap())
    });

    c.bench_function("bfs_cycle_detection", |f| {
        f.iter(|| pool.detect_cycle_bfs(0).unwrap())
    });

    c.bench_function("topological_sort_cycle_detection", |f| {
        f.iter(|| pool.detect_cycle_topological_sort(0).unwrap())
    });
}

criterion_group!(benches, benchmark);
criterion_main!(benches);

create_large_graph는 거대한 원형구조의 액터 그래프를 생성합니다. 이제 cargo bench 명령으로 벤치마크를 실행하면 됩니다.

벤치마크의 결과는 결론부터 말하자면, 위상정렬이 압도적으로 빨랐고 그 다음으로 BFS, DFS 순이였습니다. 그럼 이제 왜 이런 결과가 나왔는지 각 알고리즘의 특성을 비교해보면서 분석해보겠습니다. 결과 그래프는 모두 Mean 그래프를 이용했습니다.

DFS vs. BFS

위상정렬의 결과를 보기 전에, 먼저 DFS와 BFS의 결과를 비교해보고 왜 이런 속도 차이가 나타났는지 비교해보겠습니다.

	DFS	BFS
그래프
평균 시간	~300 µs	~296 µs

DFS, BFS 모두 시간 복잡도와 공간 복잡도는 $O(V+E)$, $O(V)$를 가지지만, 그래프를 보면 BFS가 DFS 보다 근소한 차이로 빨랐습니다. 이 차이는 두 알고리즘의 특성에서 기인합니다. DFS는 특정 노드의 자식 노드들을 모두 방문한 다음에 다른 노드로 넘어가기 때문에, DFS는 사이클을 방문하더라도 그 사이클의 모든 노드를 방문해야합니다. 반면에, BFS는 특정 노드와 같은 레벨의 노드를 우선적으로 탐색하기 때문에 특정 레벨에서 사이클을 탐지하면 탐색을 중료할 수 있습니다.

예를 들어 아래와 같은 그래프가 있다고 가정해보겠습니다. 화살표는 노드의 구독 관계를 나타냅니다.

그림에서 보이듯, 사이클은 노드 B와 노드 C 사이에 있습니다. 만약 사이클이 없는 경우 DFS, BFS 모두 A, B, C, D, E 노드를 방문합니다.

하지만, 사이클이 있는 경우 BFS와 DFS는 방문하는 노드의 수에서 차이가 나타납니다. DFS 방식은 탐색 중 사이클을 찾아도 그 사이클의 하위 노드를 전부 방문해야 하지만, BFS의 경우 사이클을 발견하자마자 탐색을 종료합니다. 즉, 위 그래프에서 BFS가 방문하는 노드는 A, B, C 세개이기 때문에 성능상 차이가 발생합니다.

위 벤치마크에서는 단순히 거대한 원형 구조의 그래프를 탐색하기 때문에 약간의 차이가 나는 걸로 결과가 나왔지만, 좀 더 복잡한 관계의 그래프에서는 확연한 차이가 나타날 것으로 예상합니다.

BFS vs. 위상 정렬

이제 BFS와 위상정렬을 비교해보겠습니다. 위상정렬의 벤치마크 결과는 다음과 같습니다. BFS의 평균 실행 시간인 295.75 µs에 비교하면 위상정렬의 144.42 µs는 2배 이상 빠릅니다. 위상정렬을 구현할 때 BFS 방식을 이용해 노드를 탐색했는데 왜 이런 결과가 나왔을까요?

	BFS	위상 정렬
그래프
평균 시간	~296 µs	~144 µs

위상정렬과 BFS 모두 시간 복잡도는 $O(V+E)$를 가지고, 공간 복잡도 역시 둘 다 큐를 사용하기 때문에 $O(V)$의 복잡도를 가집니다. 하지만, 위상정렬은 BFS와 달리 차수를 계산하면서 노드를 방문하기 때문에 그래프의 구조를 좀 더 효과적으로 분석할 수 있고, 이로인해 실행 시간의 차이가 발생합니다.

그렇다면 왜 차수가 이런 차이를 만들어냈을까요? 왜냐하면 진입 차수는 특정 노드의 의존성(dependency)를 파악하는데 도움이 되기 때문입니다. 다시 위에 있는 그래프 그림을 볼까요? 각 노드의 진입 차수는 A는 0, 나머지 B, C, D, E는 전부 1입니다. 이 그래프에서 위상 정렬이 진행되는 과정과 사이클을 찾는 과정은 아래와 같습니다.

먼저 진입 차수가 0인 노드를 찾습니다. 이 경우 노드 A입니다. 따라서 노드 A를 먼저 방문하고 이 노드를 지나는 간선을 전부 제거합니다. 그럼 그래프는 아래와 같이 변합니다. (편의상 노드 A는 생략)

이제 이 그래프에서 진입 차수가 0인 노드를 찾아야 하는데, 노드 B, C, D는 전부 차수가 1이므로 차수가 0인 노드를 찾을 수 없고 더 이상의 진행을 할 수 없습니다. 위상 정렬은 주어진 그래프가 DAG인 경우만 가능하는 점에서 보면, 탐색하는 그래프 내에 적어도 한개 이상의 사이클이 있다는 것이 확인됩니다. 즉, 노드 A만 방문했지만 그래프 어딘가에 사이클이 있다는 것이 판단 가능하죠. 물론 이 예시는 상당히 간소화 된 그래프이기 때문에 좀 극단적이긴 합니다.

하지만, BFS 방식은 노드 A에서 출발해 직접 연결된 노드를 우선적으로 탐색합니다. 그리고 방문한 노드는 방문 리스트에 추가합니다. 아무튼 그 다음에 노드 B를 방문하고, 노드 B와 연결된 노드 C를 방문합니다. 이제 노드 C에 연결된 노드 B를 방문하는데, 이 경우 노드 B는 이미 방문 리스트에 있으므로 사이클이 있음을 탐지하게 됩니다. 하지만, 이 경우 적어도 노드 A, B, C는 방문해야 하기 때문에 위상 정렬 보다는 시간이 더 걸리게 됩니다.

마무리

이것으로 액터 시스템 내부에 구독 관계를 추가할 때 미리 사이클이 있는지 판별하는 알고리즘을 작성해봤습니다. BFS, DFS 그리고 위상 정렬을 비교해보면서 왜 이런 결과가 나오게 됐는지 분석도 해봤습니다. 물론 벤치마크에서 사용한 그래프는 간략한 구조를 가졌기 때문에 실제 액터 모델에서 돌리면 또 다른 결과가 나올 것입니다. 하지만, 대부분의 경우 위상 정렬이 BFS, DFS 보다 효율적일 것이라고 생각합니다. 왜냐하면, 그래프 전체를 스캔하는 것이 아닌 특정 액터(노드)에서 시작하는 구독 관계에서 사이클이 있는지 판단하는 것이기 때문에 여기서 사용한 예시와 크게 다르지 않을 것이기 때문입니다.

참고문서

1. <Introduction to Algorithms (3rd edition)> (cormen et al., MIT press, pp.594-615)

분산 시스템에서 ID는 데이터의 중복이나 키 생성 등 다양한 용도로 사용할 수 있기 떄문에 고유한 ID를 생성하는 것은 중요합니다.

이번 글에서는 고유 ID 생성의 장단점을 포함해 트위터의 Snowflake 알고리즘을 구현해보겠습니다. 또한 이 글의 내용 대부분은 <대규모 시스템 설계 기초, 알렉스 쉬>를 참고했습니다.

추가로, 이 글은 이전에 작성한 글을 재작성했습니다.

고유 ID의 특성

고유 ID의 특성을 장점과 단점 두 가지 측면에서 비교해보겠습니다.

장점

1. 중복 방지: 분산 환경에서 여러 서버가 동시에 작업하는 경우 서로 다른 서버에서 생성된 ID가 겹칠 수 있습니다. 하지만 ID 생성기를 사용하면 이러한 중복을 방지할 수 있습니다.
2. 독립성 보장: ID 생성기를 사용하면 분산 환경에서 서버가 타임스탬프 또는 기타 방법을 사용하여 독립적으로 ID를 생성할 수 있습니다.
3. 분산 DB 키 생성: ID 생성기를 사용하여 분산 환경에서 데이터베이스의 키를 생성할 수 있습니다. 이렇게 하면 각 서버에서 데이터를 생성하고 동기화할 필요가 없어져 데이터베이스 성능이 향상됩니다.
4. 고성능: ID 생성기는 속도에 최적화된 알고리즘을 사용하여 분산 환경에서 ID를 빠르게 생성할 수 있습니다.
5. 추적성: ID 생성기는 앞서 언급한 값을 사용하여 ID를 생성합니다. 이를 통해 ID의 생성 시간, 생성자 등의 정보를 추적할 수 있습니다.

따라서 분산 시스템에서 ID 생성기를 사용하면 중복 방지, 독립성 보장, DB 키 생성 분산, 고성능, 추적성 등의 이점을 얻을 수 있습니다.

단점

반면 장점이 있다면 단점도 있습니다.

1. 의존성 문제: 아이디 생성기를 활용하게 되면, 시스템의 아이디 생성 과정이 이 생성기에 종속적이게 됩니다. 따라서 만약 생성기에 문제가 생긴다면, 시스템 일부가 제대로 작동하지 않을 위험이 있습니다.

2. 시스템 복잡성 증가: ID 생성기는 보통 다른 시스템들과 함께 운영되는데, 이로 인해 전체 시스템의 복잡도가 높아질 수 있습니다. 이는 유지보수와 문제 해결을 더 어렵게 만들 수 있습니다.

3. 대역폭 및 지연 시간 문제: ID 생성기가 분산 환경에서 동작하기 때문에, 각 서버가 생성기에 접속하는 과정에서 대역폭과 지연 시간이 생깁니다. 이런 현상은 전반적인 성능 저하를 초래할 수 있습니다.

4. 예측할 수 없는 ID 값: 아이디 생성기가 임의의 값을 사용하여 아이디를 생성하는 경우 예측할 수 없는 아이디 값이 생성될 수 있으며, 이로 인해 아이디 값을 추적하거나 유지하기가 어려운 경우가 발생할 수 있습니다.

5. 보안: ID 생성기는 데이터의 식별자를 생성하는 데 사용되므로 보안 문제가 발생할 수 있습니다. ID 값이 예측 가능한 경우 보안 위험이 발생할 수 있습니다. 예를 들어 공격자가 시스템에 악의적으로 액세스하여 데이터를 변경하거나 삭제할 수 있습니다.

ID 생성기를 사용하면 몇 가지 단점도 있지만 대부분 충분히 처리할 수 있습니다. 따라서 ID 생성 시스템을 도입 여부를 결정할 때는 시스템의 대규모 운영, 보안, 성능 등 다양한 요소를 고려하는 것이 중요합니다.

구현

고유 ID 생성기를 만드는 방법은 다양합니다. UUID, 티켓 서버 그리고 트위터의 Snowflake 알고리즘이 있는데요, 여기서는 Snowflake를 직접 구현해보겠습니다.

Snowflake

Snowflake 알고리즘은 트위터에서 게시글(트윗)이나 다른 데이터 객체의 고유 ID를 생성하는데 사용합니다. 이 알고리즘은 타임스탬프, machine identifier, 시퀀스 번호로 구성되있습니다. 이때 시퀀스 번호는 고유하고 정렬가능한(sortable) 64비트 정수입니다.

비록 최근에 트위터의 시스템이 이상해져서 이 글을 쓰는게 맞나 싶긴한데, 그래도 ID 생성 시스템에 맛이 간건 아니라서 그대로 진행해도 될 것 같네요.

명세

Snowflake는 타임스탬프, machine identifier, 시퀀스 번호로 구성되있습니다. 각 요소의 특성은 다음과 같습니다.

1. 타임스탬프: ID의 유일성을 보장합니다. 타임스탬프는 밀리초 단위로 측정되며 현재 UNIX 시간을 기준으로 합니다. 다만, 저번 나이스(NEIS) 유출 사태에서 원인이 타임스탬프만 그대로 사용한 것이 원인이라는 의견들이 있어, 단순히 이것만 가져다 쓰는건 무리가 있습니다. 그렇기 때문에 다른 정보들도 포함해야 안정성을 높일 수 있습니다.

2. Worker ID(인스턴스): 이 ID는 서버 ID와 machine ID로 구성되어 있습니다(각각 5비트). ID를 생성하도록 할당된 각 작업자(worker)에게는 고유한 ID가 할당됩니다. 작업자 ID는 서로 다른 작업자가 생성한 ID가 겹치지 않도록 보장합니다.

3. 시퀀스 번호: 동일한 작업자가 동일한 밀리초 내에 생성한 ID를 구분하는 데 사용됩니다. 이 시퀀스는 새 ID가 생성될 때마다 증가합니다.

<대규모 시스템 설계 기초> 책에서는 알고리즘을 구현할 때 제약 사항을 아래와 같이 설정했기 때문에 이번 구현에서는 이 사항들을 따를 것입니다.

1. 64비트 정수로 ID를 생성
2. 밀리초당 최대 4096개의 고유 ID를 생성
3. ID가 고유하고 시간별로 정렬 가능한지 확인

그럼 이제 코드로 구현해보겠습니다.

Snowflake 구현

스노우플레이크의 사양을 참조하여 러스트로 실시간으로 ID를 생성하는 자체 알고리즘을 만들어 보겠습니다. 전체 코드는 링크에서 확인할 수 있습니다.

먼저, 기본 뼈대를 잡아야합니다.

const MAX_IDS_PER_MILLISECOND: usize = 4096;

#[derive(Debug, Clone, Copy)]
pub struct IdGenerator {
    epoch: SystemTime,
    timestamp: i64,
    machine_id: i32,
    server_id: i32,
    index: usize,
}

epoch는 UNIX 시간을 가져오고, 이후에 타임스탬프로 처리됩니다. machine)id와 server_id 필드는 worker ID의 역할을 합니다. 마지막으로 index는 시퀀스 번호입니다.

이제 생성기의 코드입니다. 다만, 여기서 get_epoch()나 get_timestamp()의 설명은 생략하겠습니다.

impl IdGenerator {
    pub fn new(machine_id: i32, server_id: i32) -> Self {
        let epoch = get_epoch();

        Self::with_epochs(machine_id, server_id, epoch)
    }

    fn with_epochs(
            machine_id: i32, 
            server_id: i32, 
            epoch: SystemTime
        ) -> Self {
        let timestamp = get_timestamp(epoch);

        Self {
            epoch,
            timestamp,
            machine_id,
            server_id,
            index: 0,
        }
    }

    /// 단일 ID를 실시간으로 생성
    pub fn generate_id(&mut self) -> i64 {
        // 1밀리초 마다 4096개의 ID를 생성해야 하기 때문에
        // 시간을 4096으로 나눠야 합니다.
        self.index = (self.index + 1) % MAX_IDS_PER_MILLISECOND

        let mut now = get_timestamp(self.epoch);
        // 시간이 마지만 시간과 다르면 인덱스를 재설정합니다.
        // 아니면, 그냥 인덱스를 증가하면 됩니다.
        match now.cmp(&self.timestamp) {
            Ordering::Equal => {
                if self.index == 0 {
                    now = bind_time(now, self.epoch);
                    self.timestamp = now;
                }
            }
            _ => {
                self.timestamp = now;
                self.index = 0;
            }
        }
        // `self.timestamp`는 64비트이고, 22비트를 왼쪽으로 이동하여 42비트로 만듭니다.
        // `self.machine_id`는 17비트를 왼쪽 시프트하여 12비트로 만듭니다.
        // `self.server_id`는 12비트를 왼쪽 시프트하여 12비트로 만듭니다.
        // `self.index`는 보완(complement) 비트입니다.
        self.timestamp << 22
          | (self.machine_id as i64) << 17
          | (self.server_id as i64) << 12
          | self.index as i64
    }
}

이 코드를 검증하기 위해 테스트를 작성했습니다.

#[cfg(test)]
mod tests {
    use super::*;
  use std::time::Instant;

  const MAX_CAPACITY: usize = 10_000;

    #[test]
  fn test_id_generator() {
      let mut id_gen = IdGenerator::new(1, 2);
      let mut ids: Vec<i64> = Vec::with_capacity(MAX_CAPACITY);

      for _ in 0..99 {
          for _ in 0..MAX_CAPACITY {
              ids.push(id_gen.generate_id_by_time());
          }

          ids.sort();
          ids.dedup();

          assert_eq!(ids.len(), MAX_CAPACITY);

          println!("{}", ids[9999]);

          ids.clear();
      }
   }
}

결과는 실행할 때마다 다르지만 아래와 같은 형태를 띕니다.

// ...
7034777258942410107
7034777258954990731
7034777258963381147

test tests::test_id_generator ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.24s

마무리

이것으로 고유 ID 생성의 특징과 장단점, Snowflake 알고리즘의 구조와 코드 구현에 대해 알아보았습니다.

참고 자료

1. <가상 면접 사례로 배우는 대규모 시스템 설계 기초>, 알렉스 쉬, 옮긴이: 이병준, 인사이트

소개

액터 모델 구현 두번째 시간입니다. 이전 포스팅에서 동시성 제어와 각각의 특징들을 살펴보았습니다. 이번 포스팅에서는 액터 모델의 특징을 알아보고 러스트로 직접 구현해보는 시간을 가지도록 하겠습니다. 전체 코드는 링크를 참고해주세요.

액터 모델

액터 모델은 동시성 프로그래밍 모델 중 하나 입니다. 이 모델은 시스템을 독립적인 액터들의 집합으로 보며, 각 액터는 비동기로 메시지를 주고받으며 상호작용합니다. 액터 모델은 다음 세가지 요소로 구성됩니다.

• 액터(Actor) : 시스템의 기본 단위로, 메시지를 주고받으며 상호작용할 수 있는 독립적인 계산 엔티티입니다. 각 액터는 자신만의 상태를 가지고 있지만, 상태를 외부에서 직접 변경하는 것은 불가능합니다. 상태 변경은 오직 액터가 받은 메시지에 의해서만 가능합니다.
• 메시지(Message) : 액터들 간의 상호작용은 메시지를 통해서만 이루어집니다. 메시지는 비동기적으로 전달됩니다. 어떤 액터 A가 다른 액터 B(수신 액터)로 메시지를 전송하면, 수신 액터 B는 그 메시지를 처리하기 위해 적절한 연산을 수행합니다. 메시지 전달은 액터 간에 직접적인 데이터 공유가 없기 때문에 경쟁 조건(race condition)과 같은 동시성 문제를 피할 수 있습니다.
• 메일 박스(Mailbox) : 각 액터는 전달받은 메시지를 보관하는 메일박스를 가지고 있습니다. 메시지는 전달받은 순서대로 메일박스에 저장되며, 액터에서 처리할 준비가 됐을 때 순차적으로 처리됩니다.이러한 기능 덕분에 시스템의 병렬성이나 효율성을 높일 수 있습니다.

액터 모델은 이메일 시스템에 비유할 수 있습니다. 각 사용자(액터)는 자신의 이메일 계정(상태)과 메일 박스를 가지고 있고, 메일을 통해 서로 메시지를 주고 받습니다. 메일을 받은 사람은 자신이 편할 때 처리할 수 있지만(비동기) 보낸 사람은 알 수 없습니다(물론 메일을 읽은 시간을 표시하는 기능 가진 서비스도 있습니다). 이렇게 각 액터는 독립적으로 동작하며, 서로의 정보에 직접 접근하지 않고 메시지를 통해 상호작용합니다.

Actor Configuration

액터 모델에서 계산은 각 액터의 상태와 값(환경)을 변경하면서 실행됩니다. 따라서 특정 단계에서의 모델 상태를 파악하는 것이 중요한데, 이 상태를 표기하는 것이 바로 액터 컨피규레이션(actor configuration)입니다. 계산을 실행할 때는 액터 컨피규레이션을 조작하면서 동작합니다.

액터 컨피규레이션의 정의는 다음과 같습니다. $\alpha$는 액터 이름에서 식으로의 사상(projection)이며, $E$는 환경입니다. 예를 들어 함수에서 데이터 $x$가 액터 $\alpha$로 송신되면 환경 $E$는 다음과 같이 전이(transfer)됩니다.

$$ E \rightarrow E \cup { \langle \alpha \Leftarrow x \rangle} $$

여기서 $\langle \alpha \Leftarrow x \rangle$은 $\alpha$에 데이터 $x$를 보내는 것을 의미합니다. 이 메시지를 통해 기존 환경 $E$에 변화된 것을 추가해($\cup$으로 표현 됨) 새로운 환경으로 전이됩니다.

특정 단계에서의 액터 모델의 상태는 다음과 같이 쓸 수 있습니다.

$$ \alpha \space | \space E $$

이 경우 다음 조건이 성립합니다.

$$ \forall a \in dom(\alpha) : \space fv(\alpha(a)) \subseteq dom(\alpha) \ \forall \langle a \Leftarrow v \rangle : \space {a} \cup fv(v) \subseteq dom(\alpha) $$

첫번째 조건은 식 안의 자유변수가 유효한 액터명인 것을 나타내며, 두번째 조건은 송신 중 메시지의 수신지가 유효한 액터명인지 나타냅니다.

이 조건들이 성립하지 않는다면, 자유변수가 존재하지 않는 액터를 가르키고 있거나 존재하지 않는 액터에 데이터를 송신하고 있다는 것을 나타냅니다. 자유 변수는 $\lambda$ 추상과 letrec을 통해 판단되지만, 이 글에서는 생략하겠습니다.

다음으로 액터 $\alpha$가 $n$개 존재한다면 아래의 식으로 표기할 수 있습니다.

$$ \alpha = [A_0]{v_0}, \space [A_1]{v_1}, \space ..., \space [A_{n-1}]{v{n-1}} $$

이때 $A_i \space \vert \space i \in {0, \space ..., \space n - 1}$는 각 액터의 식, $v_i \space \vert \space i \in {0, \space …, \space n-1}$는 액터명입니다.

또한, 환경 $E$는 송신 중 데이터의 다중 집합이며, $m$개의 데이터를 송신 중일 때 $E$는 다음과 같이 표현됩니다.

$$ E = {\langle d_0 \Leftarrow e_0 \rangle, \space \langle d_1 \Leftarrow e_1 \rangle, \space ..., \space \langle d_{m-1} \Leftarrow e_{m-1} \rangle } $$

여기서 $\langle dst \Leftarrow data \rangle$은 데이터의 송신을 나타내며, $d_i \space \vert \space i \in {0, …, m-1}$은 수신 액터를, $e_i \space \vert \space i \in {0, …, m-1}$은 송신 데이터를 의미합니다. 또한, 송신을 $Send(data, actor)$ 함수로 수신은 $Recv(message)$로 표기한다면, 각 함수의 정의는 다음과 같습니다.

$$ Send(data, actor) \rightarrow null \newline Recv(\lambda y.M) \rightarrow (\lambda y.M) x $$

Send 함수는 송신할 데이터와 타겟 액터를 매개변수로 받습니다. null을 반환하는 것은 액터 모델은 비동기 처리의 특성과 Fire-and-forget 패턴 때문입니다.

Fire-and-forget 패턴 fire-and-forget 패턴은 발신자가 메시지를 수신자에게 보내고 메시지가 전달되었는지 확인하지 않는 패턴입니다. 수신자는 메시지에 대한 응답을 보낼 수 있지만, 발신자는 응답을 굳이 기다리지 않기 때문에 주로 응답이 필요하지 않거나 높은 처리량이 필요한 분야에서 사용됩니다.

액터 모델 구현

이제 액터 모델을 직접 구현해보겠습니다. 먼저 액터의 생성과 메시지 전파를 다루고, 추가 요소인 구독자(subscriber) 기능도 구현하겠습니다.

기본 설정

액터를 생성하고 메시를 전파하기에 앞서 먼저 액터의 구조체를 정의하겠습니다. Actor 구조체에는 액터를 식별할 ID와 초기 상태, 값 그리고 구독자와 메일 박스가 있습니다. condvar 필드는 조건 변수이며, 다른 스레드가 무언가를 변경하고 마무리할 때까지 스레드를 대기 상태로 만드는데 사용됩니다. 이 필드는 이후 메시지 전달에서 자세히 설명하겠습니다.

struct Actor {
    id: usize,
    state: RwLock<ActorState>,
    value: RwLock<i32>,
    subs: RwLock<HashMap<usize, Arc<Actor>>>,
    mailbox: Mutex<VecDeque<Message>>,
    condvar: Condvar,
}

그 다음 액터의 상태를 정의하는 ActorState 입니다. ActorState::Active는 말 그대로 현재 활성화 되어 있다는 것을 의미합니다. 액터의 상태는 직접적으로 변경할 수 없고, 메시지를 통해 변경해야 합니다. 예를 들어 상태를 변경하라는 메시지가 전달되거나, 액터가 특정 기준을 넘으면 상태를 전환하는 식을 고려해볼 수 있습니다.

#[derive(Debug, PartialEq, Copy, Clone)]
enum ActorState {
    Active,
    Inactive,
}

ID는 액터를 식별하는 수단이기 때문에 AtomicUsize를 이용해 고유 ID를 생성할 것입니다. Actor::new()로 액터 구조체의 값을 초기화 할 때 같이 ID를 생성하면 됩니다. 이때 .fetch_add(1, Odering::SeqCst)로 액터가 생성될 때 마다 ID가 1씩 증가하도록 했습니다.

값을 초기화 할 때 state, value, subs는 다른 스레드에서도 읽어야 하기 때문에 RwLock을 사용했고, 메일박스의 경우 해당 액터에서만 접근하도록 해야 하기 때문에 Mutex를 사용해서 초기화 했습니다.

메일박스는 VecDeque::with_capacvity()를 이용해 미리 보관할 메시지의 용량을 지정했고, 메시지를 받을 때마다 메모리를 재할당 하는 것을 피했습니다.

use std::sync::atomic::{AtomicUsize, Ordering};

// 액터의 고유 ID 생성
static ACTOR_ID: AtomicUsize = AtomicUsize::new(0);
static MAILBOX_CAPACITY: usize = 10;

impl Actor {
    fn new() -> Arc<Self> {
        const INC: usize = 1;
        let id = ACTOR_ID.fetch_add(INC, Ordering::SeqCst);

        let actor = Actor {
            id,
            state: RwLock::new(ActorState::Active),
            value: RwLock::new(INITIAL_VALUE),
            subs: RwLock::new(HashMap::new()),
            mailbox: Mutex::new(VecDeque::with_capacity(MAILBOX_CAPACITY)),
            condvar: Condvar::new(),
        };

        Arc::new(actor)
    }
}

이제 생성된 액터의 정보를 조작하는 메서드들을 정의하겠습니다. 이 메서드들은 이후 메시지 처리에서 쓰일 것입니다.

impl Actor {
        fn get_id(&self) -> usize {
        self.id
    }

    fn get_state(&self) -> Result<ActorState, ActorError> {
        let value = self.state.read().unwrap();
        Ok(value.to_owned())
    }

    fn get_value(&self) -> Result<i32, ActorError> {
        let value = self.value.read().unwrap();
        Ok(value.to_owned())
    }

    fn set_value(&self, value: i32) -> Result<(), ActorError> {
        let mut value_lock = self.value.write().unwrap();
        *value_lock = value;

        Ok(())
    }
}

이렇게 Actor에 메서드를 계속 추가하는 것도 나쁘진 않지만, 책임의 분산을 위해 액터를 조작하는 인터페이스를 추가했습니다.

ActorPool은 생성된 액터들의 정보를 저장하는 역할을 하고, 메시지 전송이나 액터의 정보를 가져오는 창구 역할을 합니다.

#[derive(Debug)]
struct ActorPool {
    actor_list: Mutex<HashMap<usize, Arc<Actor>>>,
}

해시맵 구조를 가지고 액터의 ID를 키(key)로 생성된 액터들의 정보(Actor 구조체)를 값(value)로 가집니다.

ActorPool의 구현을 정의하겠습니다. ActorPool::new로 필드를 초기화 했습니다.

impl ActorPool {
    fn new() -> Self {
        ActorPool {
            actor_list: Mutex::new(HashMap::new()),
        }
    }
}

이제 기본 설정은 끝냈으니 본격적으로 액터를 구현해볼 차례입니다.

액터 생성

액터를 생성하는 것은 단순합니다. 그냥 액터를 생성하고, 고유한 ID와 기본 값들이 잘 설정되있는지 확인하면 됩니다. 간단히 도표로 표현하면 다음과 같습니다.

먼저 사용자는 CLI와 같은 도구를 사용하여 액터의 생성을 요청합니다. 그 후, 이 요청은 ActorPool 인터페이스로 전달되고 적절하게 처리되어 액터가 생성됩니다. 생성된 액터는 다시 ActorPool을 통해 사용자에게 자신의 정보인 struct Actor를 제공합니다.

액터의 생성과 정보 출력을 위한 API는 각각 ActorPool::create_actor와 ActorPool::get_actor_info(id)입니다.

ActorPool::create_actor는 Actor::new를 사용하여 새로운 액터를 생성한 후, 해당 액터를 ActorPool.actor_list 필드에 저장합니다.

ActorPool::get_actor_info(id) 메서드는 특정 id를 가진 액터를 ActorPool::actor_list 필드에서 검색한 다음, 해당 액터의 정보를 사용자에게 제공하는 역할을 합니다. 이 정보에는 Actor 구조체에 정의된 내용이 모두 포함됩니다.

impl ActorPool {
    fn create_actor(&self) -> usize {
        let actor = Actor::new();     // 새로운 액터 객체 생성
        let id = actor.get_id();

        let mut actor_list = self.actor_list.lock().unwrap();
        actor_list.insert(id, actor); // 생성한 액터를 `actor_list`에 저장

        id
    }

    fn get_actor_info(&self, actor_id: usize) -> Result<Arc<Arctor>, ActorError> {
        // `actor_list`의 정보를 가져오기 위해 lock을 획득합니다.
        let actor_list = self.actor_list.lock().unwrap();
        let actor = actor_list
                .get(&actor_id)
                .ok_or(ActorError::TargetActorNotFound(actor_id.to_string()))?;

        Ok(actor.to_owned())
    }
}

actor_list는 여러 스레드에서 동시에 접근해야 하는 필드이므로, 안전한 처리를 위해 lock()을 사용하여 락을 획득해야 합니다. 이를 통해 여러 스레드가 actor_list 필드에 안전하게 접근할 수 있습니다. 예를 들어, ActorPool::create_actor에서는 필드에 생성된 액터를 추가하기 위해 접근해야 하며, ActorPool::get_actor_info에서는 필드의 정보를 가져와야 하기 때문에 lock을 획득이 필요합니다.

메시지 처리

이제 생성된 액터에 메시지를 보낼 차례입니다. 액터는 상태와 값 뿐만 아니라 받은 메시지를 저장하는 메일 박스도 갖고 있습니다. 메시지는 메일 박스에 순차적으로 쌓이며 적절한 시점에 처리됩니다. 액터는 메시지를 처리하면서 자신의 값과 상태를 업데이트하는 방식으로 동작합니다.

각 액터는 구독자(subscriber)를 가지고 있으며, 액터가 받은 메시지는 반드시 구독자에게도 보내야 합니다. 즉, 액터는 메시지를 처리하는 동안 자신을 구독하고 있는 액터에도 메시지를 전달하는 역할을 수행해야 합니다. 이렇게 함으로써 액터는 자신과 구독자 간에 통신과 상호작용이 이루어집니다.

전체적인 메시지 처리는 다음 흐름으로 나눌 수 있습니다.

1. 메시지 생성 및 전송 (Send)
   1. ActorPool::create_actor
   2. ActorPoo::message_loop
2. 구독 처리 (Subscribe)
   1. Actor::add_subscriber
   2. Actor::remove_subscriber
   3. ActorPool::subscribe
3. 메시지 전파 (Propagate)
   1. Actor::send_message
   2. Actor::propagate_message
4. 처리 (Handle)
   1. Actor::exexute_message
   2. Actor::handle_message

메시지 생성 및 전송 메시지 처리는 액터 생성 부분에서 작성한 ActorPool::create_actor 메서드에서 처리합니다. 이 메서드는 액터를 생성하는 역할을 하지만, 메시지 처리를 위해 별도의 스레드를 생성하고 각 액터의 메일박스로 부터 메시지를 처리하는 역할 또한 수행합니다. 이때 생성한 스레드 내부에서 ActorPool::execute_message를 호출합니다.

impl ActorPool {
    fn create_actor(&self) -> usize {
        let actor = Actor::new();
        let id = actor.get_id();
        let actor_clone = Arc::clone(&actor);  // +
                                               // +
        std::thread::spawn(move || {           // +
            actor_clone.execute_messages();    // +
        });                                    // +

        let mut actor_list = self.actor_list.lock().unwrap();
        actor_list.insert(id, actor);

        id
    }

    fn message_loop(&self, actor_id: usize, message: Message) -> Result<(), ActorError> {
        let actor = self.get_actor_info(actor_id)?;
        actor.send_message(message)
    }
}

Arc::clone을 이용해 액터의 복제본을 만들었습니다. 이렇게 한 이유는 다른 스레드에서도 Actor 인스턴스를 안전하게 공유하기 위해서입니다.

그 다음, std::thread::spawn을 사용하여 새 스레드를 생성했습니다. 이 스레드는 Actor의 메시지 처리(Actor::execute_message)하는 역할을 담당합니다. 즉, Actor가 생성되는 즉시 독립적인 스레드에서 실행되며, 자신의 메일박스에서 메시지를 읽고 처리합니다.

독립적인 스레드에서 각 Actor가 실행되면, Actor 간에 상호 작용이 발생할 때 서로를 차단(blocking)하지 않습니다. 예를 들어, 하나의 액터가 긴 작업을 수행하는 동안에도 다른 액터들은 계속해서 메시지를 처리할 수 있습니다.

업데이트된 Actor::create_actor() 함수를 이용하면 동적으로 액터를 생성하고 메시지를 처리할 수 있습니다. 액터 컨피규레이션 표기법을 사용하면 이 함수의 전이를 다음과 같이 작성할 수 있습니다.

$$ [new(M)]a \space || \space E \rightarrow [a']_a, \space [recv(M)]{a'} \space || \space E $$

Actor::create_actor 함수는 $a’$이라는 액터를 생성하고 반환합니다. 단, 실행 시점의 액터 컨피규레이션이 $\alpha \space | \space E$이면, $a’ \notin dom(\alpha)$이 됩니다. 즉, 위 식을 $\alpha \space | \space E \overset{\text{[new:a, a']}}{\longrightarrow} \space \alpha' \space | \space E$로 간략히 표현했을때, 이것은 $a’ \notin dom(\alpha)$이고 $a’ \in dom(\alpha')$가 되어 새로운 액터 $a’$가 액터 컨피규레이션에 추가됐음을 나타냅니다.

생성된 액터는 $M$을 이용해 즉시 메시지를 처리할 수 있는 상태가 됩니다. ActorPool::execute_message가 인수 $M$의 역할을 한다고 보면 됩니다.

간단히 말해, 이제 Actor::create_actor는 새로운 액터를 생성하고, 동시에 즉시 메시지를 처리할 수 있게 합니다.

ActorPool::message_loop는 특정 액터에게 메시지를 전송하는 역할을 합니다. 이 함수는 사용자에게 메시지와 어느 액터에 메시지를 전송할지 ID를 받고, 해당 액터의 Actor::send_message를 호출하면서 메시지를 전송합니다.

구독 처리

구현할 액터는 메시지를 처리할 때 자신을 구독하고 있는 다른 액터에게도 동일한 메시지를 전송해야 합니다. 이를 위해 액터의 subs 필드에 구독자를 업데이트하는 함수를 작성하겠습니다.

구독자에 가중치를 추가하여 메시지 전송에 우선순위를 두고 싶다면 BTreeMap이나 우선순위 큐를 사용하여 가중치가 높은 순서대로 정렬한 다음 차례로 처리할 수 있습니다. 하지만, 다행히 여기서 구현할 액터는 이런 시스템이 없기 때문에 단순히 HashMap을 사용해도 충분합니다.

메시지 업데이트는 간단합니다. 구독 리스트의 락을 획득하고 액터를 해시맵에 추가(삭제)한 다음, 락을 반환하면 됩니다. 이때 subs 필드는 RwLock으로 래핑되어 있으므로 쓰기 락(.write)을 사용하여 수정 권한을 얻어야 합니다.

구독자 추가, 삭제는 각각 Actor::add_subscriber, Actor::remove_subscriber에 대응됩니다.

impl Actor {
        fn add_subscriber(&self, actor: Arc<Actor>) -> Result<Option<Arc<Actor>>, ActorError> {
          let mut subs = self.subs.write().unwrap();

          if subs.contains_key(&actor.get_id()) {
              return Err(ActorError::ActorAlreadyExists(actor.get_id().to_string()));
          }

          Ok(subs.insert(actor.get_id(), actor))
      }

      fn remove_subscriber(&self, actor_id: usize) -> Result<(), ActorError> {
          let mut subs = self.subs.write().unwrap();

          if subs.contains_key(&actor_id) {
              subs.remove(&actor_id);
          }

          Err(ActorError::TargetActorNotFound(actor_id.to_string()))
      }
}

구독자 리스트에 넣으려는 액터가 이미 있다면 따로 에러 처리를 했습니다. 반대로 삭제하려는 액터가 없을 때도 에러를 반환하도록 했습니다.

메시지 전파

메시지를 받은 액터는 자신의 값을 업데이트하고, 다른 액터들에게도 메시지를 전송해야 합니다. 메시지를 전송하는 방법은 두 가지가 있습니다. 첫 번째 방법은 특정 조건을 만족하면 메시지를 전송하는 방법이고, 두 번째 방법은 자신과 연결된 액터들에게 동일한 메시지를 전달하는 방법입니다. 이번 구현에서는 두 번째 방법을 사용할 것입니다.

메시지는 Message 타입의 열거형으로 정의되어 있으며, 각각 증가(increment)와 감소(decrement)를 포함합니다. 메시지 타입은 패턴 매칭으로 종류를 파악하고, 메시지에 맞는 함수를 호출합니다. 호출되는 함수는 각각 Actor::increment, Actor::decrement에 대응합니다.

Actor::update_value는 코드 중복을 줄이기 위한 함수입니다. 이 함수는 FnOnce로 메시지에 대응하는 함수를 호출하고, 액터의 값을 업데이트합니다.

#[derive(Debug, Clone)]
enum Message {
    Increment(i32),
    Decrement(i32),
}

impl Actor {
    fn update_value<F>(&self, modifier: F) -> Result<(), ActorError>
    where
    // `FnOnce` 트레이트는 클로저를 한 번 호출 할 수 있는 타입으로 제한하는 역할을 합니다.
    // 특히, 이 트레이트는 클로저가 소유권을 소비(consume)하는 형태의 호출을 수행할 수 있도록 합니다.
        F: FnOnce(i32) -> Result<i32, ActorError>,
    {
        let mut value = self.get_value()?;
        value = modifier(value)?;

        self.set_value(value)
    }

    fn increment(&self, n: i32) -> Result<(), ActorError> {
        self.update_value(|value| Ok(value + n))
    }

    fn decrement(&self, n: i32) -> Result<(), ActorError> {
        self.update_value(|value| Ok(value - n))
    }
}

이제 메시지를 전달하고, 자신의 구독자에게 전파하는 함수들을 작성해보겠습니다. 각각 Actor::send_message, Actor::propagate_message입니다.

impl Actor {
    fn send_message(&self, message: Message) -> Result<(), ActorError> {
        // 메일박스의 용량이 꽉 찼는지 확인
        let mut mailbox = self.mailbox.lock().unwrap();
        if mailbox.len() >= mailbox.capacity() {
            return Err(ActorError::MailboxOverflow(self.id.to_string()));
        }

        // 액터가 비활성화(`ActorState::Inactive`) 상태면 메시지를 그냥 보관함.
        if self.state.read().unwrap().to_owned() == ActorState::Inactive {
            self.mailbox.lock().unwrap().push_back(message.clone());
        }

        // 메일박스에 보관된 메시지 처리
        mailbox.push_back(message.clone());

        // 자신을 구독하고 있는 액터에도 메시지 전파
        self.propagate_message(message)?;

        // 조건 변수를 이용해 메일박스에 메시지가 추가되면 
        // 스레드를 깨워 `execute_message`가 실행되도록 처리
        self.condvar.notify_all();

        Ok(())
    }

    fn propagate_message(&self, message: Message) -> Result<(), ActorError> {
        // 현재 액터의 구독 리스트를 가져옴
        let subs = self.subs.read().unwrap();

        // 구독 리스트에 있는 각 액터에 메시지를 전달
        for (_, actor) in subs.iter() {
            actor.send_message(message.clone())?;
        }

        Ok(())
    }
}

마지막으로 메시지 처리입니다. 메시지 처리는 Actor::execute_message와 Actor::handle_message 메서드를 통해 처리됩니다.

Actor::execute_messages 메서드는 루프를 돌면서 메일박스의 보관된 메시지를 읽고 처리하는 함수입니다. 이때도 조건 변수를 사용해 메일박스에 메시지가 없으면 스레드를 대기 상태로 두고, 메시지가 있는 경우에만 처리하도록 처리했습니다.

impl Actor {
    fn execute_messages(&self) {
        loop {
            let mut mailbox = self.mailbox.lock().unwrap();

            // 메일박스에 메시지가 들어올 때까지 대기 상태 유지
            if mailbox.is_empty() {
                mailbox = self.condvar.wait(mailbox).unwrap();
            }

            // 메시지가 들어오면 가장 먼저 들어온 메시지 소비(consume)
            while let Some(msg) = mailbox.pop_front() {
                self.handle_message(msg).unwrap();
            }
        }
    }
}

Actor::execute_messages에서 메시지를 읽을 때 메시지의 종류를 매핑하는 함수는 Actor::handle_messages입니다. 단순하게 패턴 매칭으로 처리하고, 각 메시지에 해당하는 핸들러 함수를 호출합니다. 각각 이전에 작성한 Actor::increment와 Actor::decrement입니다.

메시지를 송수신 하는 것을 액터 컨피규레이션으로 표현하면 다음과 같이 표현할 수 있습니다. 여기서는 액터 A가 액터 B로 메시지를 보내는 상황을 가정했습니다.

$$ [Send(x, b)]_a, \space [Recv(\lambda y.M)]_b \space | \space {\space} \rightarrow [null]_a, \space [Recv(\lambda y.M)]_b \space | \space {\langle b \Leftarrow x \rangle} \newline \rightarrow [null]_a, \space [(\lambda y.M x)]_b \space | \space {\space} $$

impl Actor {
        fn handle_message(&self, message: Message) -> Result<(), ActorError> {
        // 패턴 매칭을 통해 각 메시지에 해당하는 함수 호출
        let result = match message {
            Message::Increment(n) => self.increment(n),
            Message::Decrement(n) => self.decrement(n),
        };

        // 조건 변수를 이용해 메시지가 처리되었음을 
        // `execute_messages` 스레드에 알림
        self.condvar.notify_all();

        result
    }
}

이제 액터끼리 메시지를 주고받을 수 있습니다. 그러나 액터가 서로 구독하고 있다면 서로 무한히 메시지를 전달할 가능성이 있으며, 이는 잠재적으로 오버플로우를 발생시킬 수 있습니다. 이 문제를 해결하려면 액터가 일정 값에 도달하면 값을 리셋하거나, 메시지 처리를 중단하거나, 메시지에 ID를 추가하여 메시지당 처리 횟수를 한 번만 하도록 할 수 있습니다.

그러나 저는 액터를 구독 리스트에 추가할 때 미리 서로 구독하고 있는지 확인하는 알고리즘을 추가하기로 했습니다. 각 액터를 노드로, 구독하고 있는 것을 간선으로 둔다면 유향 그래프 구조가 만들어집니다. 그런 다음 이 그래프에 대해 사이클을 판별하는 알고리즘을 작성하고, 구독 추가 로직에 추가하기만 하면 됩니다. 그러나 여기서 사이클 감지 알고리즘을 설명하면 내용이 길어지기 때문에 이 내용은 다음 편으로 미루겠습니다.

정리

이것으로 액터 모델의 구현의 특징과 동시성, 액터 컨피규레이션 표기법 그리고 구현하는 방법을 알아봤습니다.

먼저 액터 모델의 특징에 대해 알아보았습니다. 액터 모델은 동시성 처리를 위한 모델이며, 각각 독립적으로 동작하는 개체들로 구성되며, 서로 메시지를 주고받으며 상호작용합니다.

액터 모델을 동시성 처리에 사용하면 확장성과 비동기 처리에 큰 이점을 얻을 수 있습니다. 왜냐하면 액터 모델은 수평적으로 확장이 가능하며, 여러 인스턴스를 생성할 수 있기 때문에 처리량을 선형적으로 늘릴 수 있기 때문입니다.

또한 기본적으로 비동기 메시지 전달을 기반으로 동작하기 때문에 블로킹 되지 않고 작업을 수행할 수 있다는 특징도 있었습니다.

이 정도 구현만 해도 액터는 충분히 돌아가지만, 다음 글에서는 값의 오버플로우를 방지할 순환 참조(구독) 탐지 알고리즘을 작성하겠습니다.

같이 보기

1. 동시성 프로그래밍 (다카노 유키, 옮긴이: 김모세, 2022, 한빛미디어, p.313-340)

액터 모델(Actor model)은 동시성 프로그래밍의 복잡성을 관리하기 위한 도구 중 하나입니다. 이번 시리즈에서는 액터 모델의 기본 개념과 구현 그리고 동시성 제어 각각 두 가지 내용을 다룰 것입니다. 본격적인 구현에 앞서 먼저 러스트의 대표적인 동시성 제어 타입에 대해 알아보겠습니다.

동시성 제어

액터 모델을 구현하기 전에 먼저 러스트의 동시성 제어에 대해 알아보겠습니다. 동시성 제어는 여러 프로세스 또는 스레드가 동시에 공유 자원에 접근할 때 발생할 수 있는 문제를 방지하고, 공유 자원에 대한 일관성과 무결성을 유지하는 메커니즘입니다. 병렬 프로그래밍의 중요한 요소이며, 프로그램의 실행 순서에 따라 결과가 달라질 수 있는 비결정성을 관리하는게 중요합니다.

여러 스레드가 데이터에 접근할 때 발생하는 문제 중 대표적인 것은 경쟁 상태와 데드락입니다.

경쟁 상태(race condition)는 여러 프로세스가 동시에 공유하는 자원(데이터)에 접근할 때 일어날 때 발생하는 문제입니다. 예를 들어, 두 개의 스레드 A, B가 있다고 가정해보겠습니다. 만약 A가 데이터를 읽고 업데이트하는 도중에 B가 그 데이터를 변경하면, A가 하고 있던 작업은 중지되거나 예상치 못한 결과를 일으킬 수 있습니다. 참고로 경합 상태를 일으키는 부분을 크리티컬 섹션(critical section, 위험 영역)이라고 부릅니다. 이 영역을 보호하기 위해 이후에 설명할 동기 처리를 이용합니다.

또한 데드락은 여러 프로세스나 스레드가 서로가 가진 자원을 점유하고 있는 상태에서, 서로가 점유한 자원을 기다리며 무한히 대기하는 상황을 말합니다. 이때 프로그램은 더 이상 진행할 수 없게 되며, 데드락 상태에 있는 프로세스나 스레드는 해결되기 전까지 계속 대기하게 됩니다.

이러한 문제를 미연에 방지하기 위해서 동시성 매커니즘을 사용하는데, 러스트에는 Mutex, Arc, Condvar, RwLock 등의 도구가 있습니다. 이 도구들은 스레드 간의 실행 순서를 조정하고, 데이터의 접근을 제어하는 등의 역할을 하여 동시성 문제를 관리합니다.

Mutex와 RwLock

뮤텍스(Mutex)는 상호 배제(Mutual Exclusion)의 줄임말로, 가장 자주 사용하는 동기화 기법입니다. 동시에 데이터에 접근하려는 다른 스레드를 일시적으로 차단하여 특정 스레드가 일부 데이터에 독점적으로 접근할 수 있도록 하는 역할을 합니다. 다른 표현으로는 크리티컬 섹션을 실행할 수 있는 프로세스의 수를 최대 1개로 제한하는 동기 처리입니다.

예를 들어, 크리티컬 섹션을 처리하는 플래그를 생각할 수 있습니다. 해당 플래그가 참이면 작업을 실행하고, 그렇지 않으면 실행하지 않는 동작을 생각해볼 수 있습니다. 이 구역에 대한 접근 권한을 제어하는 것을 잠금(locking)이라고 부르며, 이는 잠금(lock)과 해제(unlock)의 두 가지 형태로 이루어집니다.

1. 락(Lock): 데이터에 대한 독점적인 접근을 획득하기 위해 사용됩니다. 락을 획득한 스레드는 데이터를 읽거나 수정할 수 있습니다. 락을 얻지 못한 상태에서 데이터에 접근하는 것은 불가능 하고, 락을 획득할 때 까지 스레드는 대기해야 합니다.
2. 언락(unlock): 락을 반환하여 다른 스레드가 접근할 수 있도록 합니다. 데이터 접근이나 수정이 완료된 이후에는 락을 반환하여 다른 스레드가 데이터에 접근 할 수 있도록 해야 합니다.

뮤텍스를 사용해 스레드가 락을 획득하고 반환하는 예시 코드입니다.

use std::sync::Mutex;
use std::thread;

fn main() {
    let data = Mutex::new(0);

    let thread1 = thread::spwan(move || {
        let mut guard = data.lock().unwrap(); // lock 획득

        // lock을 획득한 스레드는 데이터 수정 가능
        *guard += 1;
        println!("thread 1 value: {}". *guard);

        /* 스코프 범위를 벗어나면 자동으로 unlock */
    });

    let thread2 = thread::spwan(move || {
        let mut guard = data.lock().unwrap();

        *guard += 10;
        println!("thread 1 value: {}". *guard);

        drop(guard); // 명시적인 unlock도 가능합니다
    });

    // `join()`을 호출해 스레드의 작업이 완료될때 까지 대기
    thread1.join().unwrap();
    thread2.join().unwrap();    
}

러스트에서는 뮤텍스로 보호되는 변수는 데이터를 보존하기 위해 락 없이는 접근할 수 없도록 되어 있습니다. 또한, 보호 대상 데이터가 스코프를 벗어나면 락이 자동으로 해제됩니다. lock 함수는 LockResult<MutexGuard<'_, T>>라는 타입을 반환하는데, LockResult는 다음과 같이 정의됩니다.

type LockResult<Guard> = Result<Guard, poisonError<Guard>>;

lock 함수를 사용하여 락을 획득하는 경우, MutexGuard라는 타입으로 보호 대상 데이터를 감싸서 반환하며, 이 MutexGuard 변수의 스코프를 벗어나면 락이 자동으로 해제됩니다. 그래서 명시적으로 해제를 하지 않아도 됩니다. 또한, 어떤 스레드가 락 획득 중에 패닉에 빠진다면 해당 뮤텍스는 poisoned 상태에 있는 것으로 간주되고 락 획득에 실합니다.

RwLock은 읽기-쓰기 잠금(read-write lock)의 약자입니다. RwLock은 동시에 여러 개의 읽기 작업은 허용하지만, 쓰기 작업은 한 번에 하나의 스레드만 수행할 수 있도록 하는 동기화 기법입니다. 왜냐하면 쓰기 작업과 다르게 읽는 작업은 데이터를 수정할 필요가 없기 때문입니다.

RefCell 처럼 RwLock은 내부에서 참조 카운팅을 통해 공유 borrow와 독점 borrow의 수를 추적합니다. 하지만, RwLock은 충돌 borrow가 발생해도 패닉을 일으키는 대신, 현재 스레드를 block 상태로 변경하고, 문제가 되는 borrow가 사라질 때 까지 대기합니다.

뮤텍스 처럼 RwLock의 내용을 borrow하는 것을 locking이라고 합니다. 하지만 RwLock의 경우, 읽기 작업과 쓰기 작업 간의 동시성을 관리하기 위해 두 가지 종류의 락을 사용합니다.

1. 읽기 락(Read Lock): 읽기 락은 데이터를 공유하는 경우에 사용합니다. 여러 스레드가 동시에 읽기 락을 얻을 수 있으며, 쓰기 작업과 상호 배제되지 않으므로 여러 스레드가 동시에 읽기 작업을 할 수 있습니다.
2. 쓰기 락(Write Lock): 쓰기 락은 데이터 수정 시 사용됩니다. 쓰기 락은 읽기 락과 상호 배제되며, 한 번에 하나의 스레드만 쓰기 락을 얻을 수 있습니다. 쓰기 락을 얻은 스레드는 데이터를 수정하고, 다른 스레드들은 읽기 락이나 쓰기 락을 얻을 때까지 대기해야 합니다.

다음은 RwLock을 사용하는 예입니다.

use std::sync::RwLock;
use std::thread;
use std::time::Duration;

fn main() {
    let data = RwLock::new(0); // RwLock으로 보호되는 데이터

    // 읽기 작업을 수행하는 스레드
    for _ in 0..5 {
        let data = data.clone(); // RwLock을 클론하여 여러 스레드가 동시에 읽을 수 있도록 함

        thread::spawn(move || {
            // 읽기 락을 얻음
            let guard = data.read().unwrap();
            println!("read: {}", *guard);
        });
    }

    // 쓰기 작업을 수행하는 스레드
    for _ in 0..3 {
        let data = data.clone(); // RwLock을 클론하여 여러 스레드가 동시에 쓸 수 있도록 함

        thread::spawn(move || {
            // 쓰기 락을 얻음
            let mut guard = data.write().unwrap();
            *guard += 1; // 데이터 수정
            println!("write: {}", *guard);
        });
    }

    thread::sleep(Duration::from_secs(2)); // 스레드들이 작업을 완료할 때까지 대기
}

RwLock을 이용해 여러 스레드가 동시에 데이터에 접근하는 예제입니다. 읽기 작업을 수행하는 스레드는 read() 메서드를 호출하여 읽기 락을 얻고, 쓰기 작업을 수행하는 스레드는 write() 메서드를 호출하여 쓰기 락을 얻습니다.

read()를 호출하면 보호 대상 데이터를 RwLockreadGuard 타입으로 감싼 불변 참조를 얻을 수 있고, 읽는 것만 가능합니다. 또한 뮤텍스와 같이 해당 참조의 스코프를 벗어나면 자동으로 락이 해제됩니다.

write()의 경우에도 마찬가지입니다. 이 함수를 호출하면 보호 대상 데이터를 RwLockWriteGuard 타입으로 감싼 가변 참조를 얻을 수 있습니다.

Arc(Atomic Reference Counting)

Arc는 여러 스레드에서 공유할 수 있는 객체에 대한 참조를 나타내고, 하나의 데이터에 대한 여러 소유권을 안전하게 관리하는 동시성 타입입니다.

데이터에 대한 참조 횟수를 추적하며, 스레드가 Arc를 통해 데이터에 접근하면 참조 카운터가 증가하고 참조가 끝나면 감소합니다. 이후에 참조 카운터가 0이 되면, 데이터는 해제됩니다. 따라서 여러 스레드가 동시에 데이터에 접근해도 참조 카운터를 조작하면서 데이터에 대한 소유권 충돌을 피할 수 있습니다.

Rc 역시 참조 횟수를 추적하지만, Arc와 비교하면 공유의 측면에서 차이가 있습니다. Arc는 Rc와 달리 참조 카운팅을 원자적 연산을 사용하여 관리하므로 여러 스레드 간에 안전하게 공유할 수 있습니다. 이를 통해 여러 스레드가 동시에 Arc를 통해 데이터에 접근하고 참조 카운터를 조작할 수 있습니다. 반면에 Rc는 단일 스레드에서만 사용하기에 적합하며, 스레드 간에 공유할 때는 안전하지 않습니다.

또한, Arc는 참조 카운팅을 관리하기 위해 원자적 연산을 사용하는데 이 경우 일반적인 메모리 액세스보다 더 많은 비용이 발생할 수 있습니다.

Arc는 Send와 Sync 트레이트를 구현한 타입에 대해서만 Send와 Sync를 자동으로 구현합니다. 하지만 Arc<T>에 스레드 안전하지 않은 타입 T를 넣는 것은 불가능합니다. 이는 Arc가 참조 카운팅을 관리하는 데 있어서 안전하지만, 내부 데이터에 대해서는 스레드 안전성을 추가하지 않기 때문입니다. 따라서 스레드 안전하지 않은 타입을 Arc<T> 안에 넣어 스레드 안전하게 만들 수 없습니다. 이런 경우에는 Arc<T>와 함께 std::sync 타입인 Mutex<T>를 사용하여 스레드 안전성을 보장할 수 있습니다.

다음은 Arc를 사용해 여러 스레드가 공유 데이터에 접근하는 코드입니다.

use std::sync::Arc;
use std::thread;
use std::time::Duration;

fn main() {
    let data = Arc::new(0);

    for _ in 0..5 {
        let cloned = Arc::clone(data); // `Arc`를 clone하여 스레드마다 공유

        thread::spwan(move || {
            println!(
                "thread: {}, value: {}", 
                thread::current().id(), 
                *data,
            );
        });        
    }

    // 스레드들이 실행을 완료할 때까지 대기
    thread::sleep(Duration::from_secs(1));
}

위 예시에서는 Arc를 사용하여 여러 스레드에서 데이터에 접근하고 출력합니다. Arc::new()를 사용하여 데이터를 Arc로 감싸고, 스레드마다 Arc를 클론하여 공유합니다. 각 스레드는 공유된 Arc를 통해 데이터에 접근할 수 있습니다. Arc는 참조 카운팅을 관리하므로 여러 스레드가 동시에 데이터에 접근해도 안전하게 참조 카운터를 조작하여 데이터에 대한 소유권 충돌을 방지합니다.

요약하자면, Arc는 여러 스레드 간에 공유할 수 있는 참조 타입으로, 참조 카운팅을 원자적 연산으로 관리하여 스레드 안전하게 공유할 수 있습니다. 그러나 Rc와 비교하면 약간의 오버헤드가 발생할 수 있습니다. Arc는 Send와 Sync를 구현한 타입에 대해서만 자동으로 구현되며, 스레드 안전하지 않은 타입을 Arc<T> 안에 넣을 수는 없습니다. 이런 경우에는 Arc<T>와 함께 Mutex<T> 등의 std::sync 타입을 사용하여 스레드 안전성을 보장할 수 있습니다.

Condvar(Condition Variables)

Condvar는 스레드 간의 조건부 동기화를 위한 메커니즘입니다. Condvar는 특정 조건이 만족될 때 까지 스레드를 대기 상태로 만듭니다.

주로 뮤텍스와 함께 사용되며, 뮤텍스로 보호되는 데이터의 상태에 따라 스레드 동작을 조절합니다. 다음은 Condvar를 활용한 예제입니다.

use std::sync::{Arc, Mutex, Condvar};
use std::thread;

fn main() {
    let data = Arc::new(Mutex::new(false)); // 뮤텍스로 보호되는 데이터
    let condvar = Arc::new(Condvar::new()); // 조건 변수

    // 스레드 1
    let data_clone = Arc::clone(&data);
    let condvar_clone = Arc::clone(&condvar);
    let thread1 = thread::spawn(move || {
        let mut guard = data_clone.lock().unwrap(); // 뮤텍스 락 획득

        // 특정 조건이 충족되지 않으면 대기
        while !*guard {
            guard = condvar_clone.wait(guard).unwrap();
        }

        // 조건이 충족되면 작업 수행
        println!("threa 1: Pass");
    });

    // 스레드 2
    let data_clone = Arc::clone(&data);
    let condvar_clone = Arc::clone(&condvar);
    let thread2 = thread::spawn(move || {
        let mut guard = data_clone.lock().unwrap(); // 뮤텍스 락 획득

        // 특정 작업 수행 후 조건 충족
        *guard = true;

        // 대기 중인 스레드를 깨움
        condvar_clone.notify_one();

        // 뮤텍스 락은 여전히 보유한 상태로 블록을 벗어남
        println!("thread 2: Pass");
    });

    thread1.join().unwrap();
    thread2.join().unwrap();
}

Condvar에는 스레드 간의 조건부 동기화를 위해 사용되는 메서드들이 있습니다. wait(), notify_one() 그리고 notify_all() 들인데요, 이 메서드들은 주로 공유 데이터의 특정 상태가 변경되기를 기다리는 작업에서 주로 사용됩니다. 대기 중인 스레드는 조건이 충족되기 전까지 작업을 중지하고, 조건이 충족되면 알림을 받아 작업을 재개합니다.

1. wait() : 특정 조건이 충족될 때까지 스레드를 대기 상태로 만듭니다. 뮤텍스의 락을 획득한 상태에서 wait()을 호출하면 해당 스레드는 뮤텍스를 언락하고 대기 상태로 전환됩니다. 대기 중인 스레드는 다른 스레드에 의해 깨어날 때까지 대기하다가, 깨어나면 다시 뮤텍스의 락을 획득하고 작업을 재개합니다.
2. notify_one(): 대기 중인 메서드 하나를 깨우고, 해당 스레드가 뮤텍스의 락을 획득하게 해주는 역할을 합니다. 여러 스레드가 대기 중이더라도, notify_one()은 호출 될 때마다 대기 중인 스레드 중 하나만 깨웁니다. 다만, 어떤 스레드가 활성화 될지는 모릅니다.
3. notify_all(): 대기 중인 모든 스레드를 깨웁니다. 대기 중인 스레드가 없는 경우 아무 것도 하지 않습니다.

정리

1. Mutex는 상호 배제를 구현하기 위한 타입으로, 데이터에 동시에 접근하는 것을 제어합니다. Mutex는 lock()과 unlock()을 통해 데이터의 독점적인 접근을 관리합니다.
2. RwLock은 읽기와 쓰기 작업 간의 동시성을 관리하는 타입입니다. 여러 스레드가 동시에 읽기 작업을 수행할 수 있지만, 쓰기 작업은 한 번에 하나의 스레드만 수행할 수 있도록 제한합니다.
3. Arc는 여러 스레드 간에 안전하게 공유할 수 있는 참조 카운팅 타입입니다. Arc는 여러 소유권을 안전하게 관리하고, 데이터에 대한 참조 횟수를 추적하여 스레드 간의 안전한 공유를 가능하게 합니다.
4. Condvar는 스레드 간의 조건부 동기화를 위한 메커니즘입니다. Condvar는 특정 조건이 충족될 때까지 스레드를 대기 상태로 만들고, 조건이 충족되면 스레드를 깨워 작업을 진행할 수 있도록 합니다.

참고 자료

1. Atomics and Locks (Mara Bos, 2023, O'Reilly, p.15-24)
2. 동시성 프로그래밍 (다카노 유키, 역: 김모세, 2022, 한빛미디어, p.83-116)
3. https://doc.rust-lang.org/std/sync/struct.Arc.html

러스트의 소유권(ownership)은 변수가 가리키는 값을 한번에 하나만 소유할 수 있도록 하여 메모리 안정성을 보장하는 시스템입니다. 이번 글에서는 이 소유권의 개념을 직접 만들고 있는 언어에 어떻게 적용하고 있는지 풀어보겠습니다.

빌림 (Borrowing)

소유권 그래프를 구현하기에 앞서 빌림과 소유권에 대해 알아보겠습니다. 먼저 러스트의 빌림 규칙은 소유권(ownership)과 참조(reference) 그리고 빌림(borrowing)을 기반으로 작동합니다.

• 소유권: 이후에 설명하겠지만, 러스트에서 값은 항상 한 번에 하나의 소유자(owner)를 가질 수 있습니다. 소유자는 값에 대한 제어권을 가지고, 해당 값이 스코프를 벗어나면, drop을 통해 자동으로 메모리에서 해제됩니다.
• 참조: 또한 빌림을 이용해 값에 대한 참조자(reference)를 생성할 수 있습니다. 참조자는 값을 소유하지 않고도 값을 읽거나 변경할 수 있습니다. 참조자는 불변 참조자(immutable reference)와 가변 참조자(mutable reference)로 나뉘며, 불변 참조자는 여러 개의 동시 참조를 허용하지만 가변 참조자는 오직 하나의 동시 참조만 허용합니다.
• 빌림: 소유자가 값을 임시로 다른 코드 블럭에 대여할 수 있습니다. 이러면 소유권을 넘기지 않고도 값을 사용할 수 있습니다. 빌림은 동시에 여러 개의 불변 빌림(immutable borrowing)이 가능하지만, 가변 빌림(mutable borrowing)은 하나의 빌림만 허용합니다.

소유권 (Ownership)

소유권에 대해 간단히 알아보겠습니다. 러스트의 소유권은 객체(값)의 소유권을 추적하고 객체가 더 이상 필요하지 않을 때 해제하는 식으로 동작합니다. 이때 각각의 객체에 대한 소유권은 오직 하나의 소유자만 가질 수 있고, 소유권을 가진 객체가 소멸하면 자동으로 메모리를 해제합니다. 이로써 가비지 컬렉터 없이 메모리 안정성을 보장합니다.

소유권을 다른 변수에 할당하려면 값을 이동(move)해야 하는데, 값을 이동하면 소유권이 새로운 변수로 이동합니다. 하지만 이존 변수의 소유권은 무효화됩니다. 또한 복사(copy)는 데이터를 복사해서 새로운 소유자를 생성합니다. 소유권을 가진 변수를 다른 변수에 할당하면 해당 데이터의 복사본이 새로운 메모리 공간에 할당됩니다. 이 복사된 데이터는 원본 데이터와는 독립적으로 존재하며, 각 변수는 서로 다른 소유권을 가집니다.

하지만 복사의 비용은 비싸기 때문에 참조(reference)를 하는 방법도 있습니다. 참조자를 사용하면 객체에 대한 접근을 공유할 수 있는데, 참조자는 객체를 소유하지 않고 단순히 참조만을 제공합니다. 이를 통해 여러 개의 참조자가 동시에 데이터에 접근할 수 있게됩니다.

소유권 그래프 (Ownership Graph)

유향 그래프 구조를 간단히 묘사한 그림. 3번, 4번 노드는 서로 연결되어 있고, 3번 노드는 2번을 그리고 1번 노드는 2번, 3번 노드를 향하고 있다.

그렇다면 이 소유권을 추적하기 위해선 어떻게 해야할까요? 정적 분석(Static Analysis)이나 참조 계수(Reference counting)를 이용할 수 있고, 아니면 Garbage Colletion과 같은 방법도 있습니다. 하지만 여기서는 소유권 그래프를 구현한 뒤, 소유권을 추적해보겠습니다. 그래프를 이용하면 컴파일 시간에 소유권 규칙을 검사할 수 있고, 코드의 소유권 이동과 참조자의 범위를 깔끔하게 처리할 수 있습니다. 또한, 추가 오버헤드가 발생하지 않아 리소스나 시간을 효율적으로 유지할 수 있게 도와줍니다.

그래프는 소유권과 빌림(borrowing)의 관계를 보여줍니다. 그래프의 노드(node)는 변수 또는 객체를 나타내며, 간선(edge)은 소유권의 이동이나 참조 관계를 의미합니다. 그래프는 변수의 선언이나 할당이 이뤄질때 생성되고, 변수의 소유권은 노드 간의 연결로 나타냅니다.

예를 들어, 변수의 소유권을 다른 변수로 넘겨주면, 그래프에는 소유권 이동을 표시하는 간선이 추가됩니다. 이때 소유권 이동은 이전 변수의 무효화와 새로운 변수의 소유권 취득을 의미합니다.

참조자의 생성과 사용은 그래프에서 참조 관계를 나타냅니다. 참조자는 소유권을 가지지 않고 객체에 대한 접근을 제공하기 때문에 그래프에는 참조자를 의미하는 간선이 형성됩니다. 추가로 이 참조자는 소유권의 범위 내에서만 유효합니다.

컴파일러는 소유권 그래프를 정적으로 검사하고 규칙을 잘 지키고 있는지 확인합니다. 러스트를 예로 들면, 불변 참조자와 가변 참조자 간의 충돌이나 그외 다른 문제들도 컴파일 시간에 분석해 문제를 미연에 방지합니다.

더 깊고 자세한 내용은 딴 블로그나 공식문서를 확인하는게 더 이로울 것 같으니 넘어가겠습니다. 또한 여기서 구현할 코드는 위에서 말한 복잡한 내용들을 전부 쳐낸 열화-열화판으로 구현할 것입니다.

소유권 그래프 구현

소유권 그래프를 구현하기 전에 어떻게 구현하고 또 어떤 데이터 구조를 사용해야 할까요? 먼저 소유권 그래프의 작동 방식을 보겠습니다.

작동 방식

각 단계를 단순하게 표현하면 다음과 같습니다.

1. AST(추상 구문 트리)를 순회하면서 각각의 스코프 노드를 만날 때마다 새로운 스코프를 생성합니다.
2. 각 스코프는 변수의 소유권을 추적하기 위한 변수 테이블(인접성 목록)을 유지합니다.
3. 변수가 생성될 때, 현재 스코프에 소유권 정보를 등록합니다.
4. 빌림이 발생할 때, 변수가 다른 스코프에 이미 빌려져 있는지 확인합니다..
5. 빌림이 발생하면 해당 노드의 연결 목록에 변수의 차용 정보를 추가합니다.
6. 범위가 끝나면 연결 목록에서 변수의 빌림 정보를 제거합니다.
7. 중첩된 범위에서 빌림이 발생하는 경우, 각각의 범위에서 빌림을 해결하고 소유권 정보를 업데이트합니다.
8. AST 순회가 완료된 후, 모든 빌림 규칙을 확인하여 빌림이 올바른지 확인합니다.

이제 각 단계에 해당하는 코드를 보면서 어떤 걸 고려하고 또 어떻게 작동하는지 알아보겠습니다. 다만 중첩 스코프의 경우는 아직 완전히 구현되지 않아 추정되는 동작만을 서술했다는 점은 양해부탁드립니다. 또한 아래의 코드 스니펫(snippet)은 별다른 설명이 없다면 build_ownership_graph 메서드 내에 있는 부분입니다.

AST 순회 및 새 스코프 생성

현재 언어 구현하고 있는 언어에는 AST를 아래와 같이 정의합니다. 자세한 설명이나 다른 부분은 생략했지만 이 링크에서 전체 코드를 확인할 수 있습니다.

// borrows/ast.rs

#[derive(Debug, PartialEq)]
pub enum Statement {
    FunctionDef {
        name: String,
        args: Option<Vec<(String, bool)>>,
        body: Vec<Statement>,
    },
    VariableDecl {
        name: String,
        value: Option<Expression>,
        is_borrowed: bool,
    },
    Scope(Vec<Statement>),
    Return(Option<Expression>),
    Expr(Expression),
}

// ...

아래의 코드는 AST는 순회하면서 Statement::Scope(_) 노드를 만날 때마다 새로운 스코프를 생성하는 부분입니다.

// borrow/ownership.rs

Statement::Scope(scope) =>  {
    let prev_owner = current_owner.clone();
    let mut declared_in_scope = vec![];
    for inner_stmt in scope {
        // ...
    }
    // ...
}

prev_owner는 이전 소유자를 저장하고, current_owner는 현재 소유자를 저장합니다. 또한 declared_in_scope 변수는 현재 스코프에서 저장된 변수들을 저장하는 역할을 합니다.

각 스코프의 변수 테이블

소유권 그래프의 구현에는 인접 리스트(Adjacency List), 인접 행렬(Adjacency Matrix) 아니면 둘 다 결합한 인접 리스트 배열(Adjacency List Array)과 같은 여러가지 데이터 구조들을 사용할 수 있습니다. 아래의 표는 이 세가지 데이터 구조를 비교한 표입니다. 여기서 $V$는 정점의 수를, $E$는 간선의 개수의 의미합니다.

인접 리스트는 각 노드마다 인접한 노드들의 연결 리스트를 가지고 있으므로 저장 공간이 노드 수와 간선 수에 비례합니다. 노드 추가와 삭제가 용이하며, 노드 탐색에는 $O(V+E)$의 시간 복잡도를 가지는 것을 볼 수 있습니다. 또한 표에는 안 나와있지만 추가 정보를 저장하기에도 용이한 구조입니다.

하지만 밀집 그래프에서는 비효율적인데, 현재 만들고 있는 언어는 테스트 용으로 쓰기 좋게 최소한의 구조와 기능만을 가지도록 만들고 있어서 밀집된 경우는 굳이 고려하지 않아도 됩니다. 그래서 그래프 구현에는 인접 리스트 방식을 사용할 것입니다.

이제 그래프의 구조와 관계를 어떻게 표현했는지 알아보겠습니다. 먼저, 노드의 연결 정보는 연결 리스트를 통해 저장합니다. 각 노드는 인접한 노드들을 연결 리스트로 저장하며, 이를 통해 그래프의 구조를 나타냅니다.

처음 구현을 시도했을 때 사용했던 자료구조는 해시 맵(HashMap)이였습니다. 하지만 아래의 결과에서 보이듯 생각과 다르게 동작했다는 문제점이 발생했습니다.

// borrow/ownership.rs [예전 구현]

#[derive(Debug, PartialEq, Eq, Clone)]
struct OwnershipGraph {
    graph: HashMap<String, Vec<String>>,    // 해시 맵을 이용해 그래프 구조 생성
}

impl OwnershipGraph {
    pub fn new() -> Self {
        graph: HashMap::new(),
    }
}

예를 들어 다음과 같은 AST가 입력으로 들어갔다고 가정하면,

// let a = 42;
// let b = &a;
// let c = &a;
// let d = &b;

**[AST]**
Statement::VariableDecl {
    name: "a".into(),
    is_borrowed: false,
    value: Some(Expression::Number(42)),
},
Statement::VariableDecl {
    name: "b".into(),
    is_borrowed: true,
    value: Some(Expression::Reference("a")),
},
Statement::VariableDecl {
    name: "c".into(),
    is_borrowed: true,
    value: Some(Expression::Reference("a")),
},
Statement::VariableDecl {
    name: "d".into(),
    is_borrowed: true,
    value: Some(Expression::Reference("b")),
}

다음과 같은 결과가 나와야 합니다.

OwnershipGraph { graph: {"a": ["b", "c"], "b": ["d"], "global_var": ["a"]} }

하지만 아래와 같은 결과가 출력되었죠.

OwnershipGraph { graph: {"a": ["c", "d"], "b": [""], "global_var": ["a"]} }

처음에는 원인을 알 수 없었지만, 이후 분석해보니, 해시 맵 특성상 순서가 뒤죽박죽 저장되어서 소유권의 관계를 정확하게 추적하지 못해서 발생한 문제였었습니다. 그래서 순서를 유지하면서 그래프 관계를 만들 수 있는 자료구조로 변경해야 될 필요가 생겼습니다.

그래서 해시 맵 대신 B-트리 맵(BTreeMap)으로 코드를 수정했습니다. 해시 맵에 비해 상대적으로 연산은 좀 걸리지만[BTM], 키(각 변수 노드)를 기준으로 정렬된 상태를 유지하기 때문에 소유권의 전파와 전이를 파악하는데 적합했습니다.

그렇다면 정렬된 순서를 왜 유지해야 할까요? 바로 이 순서를 유지해야 소유권 관계의 시간적 흐름을 명징하게 처리할 수 있기 때문입니다.

예를 들어, 소유권 이전과 이후를 비교하거나, 특정 시간 범위 내에서 소유권 관계를 탐색해야한다고 가정해봅시다. 만약 이때 해시 맵을 사용한다면 큰 어려움이 발생합니다.

해시 맵이 어떤 식으로 동작하는지 묘사한 그림. 각 키에 해당하는 값들이 해시 함수를 통과해 특정 값을 가지는지 묘사되어 있다.

왜냐하면 해시 맵은 해시 함수를 이용하여 키를 해시 값으로 변환한 후 데이터에 접근하기 때문에 키-값(key-value)이 정렬되는 순서를 예측할 수 없기 때문이죠. 또한 연속된 범위(특정 시간) 내에서 소유권 관계를 탐색하려면 일련의 키-값 순서대로 탐색을 하는 것이 아닌 해시 맵을 순회하면서 범위를 검사해야 하는 것도 덤입니다.

B트리가 어떤 식으로 동작하는지 묘사되있는 그림이다. $k_1$를 루트로 하여 순서대로 정렬된 구조를 가진다.

반면, B 트리 맵은 키를 기준으로 정렬된 상태를 유지하는 자료구조입니다. 각 노드를 키로 하고 인접 리스트를 값으로 저장하면, B트리는 키의 정렬된 순서를 유지하면서 소유권 관계를 저장합니다.그렇기 때문에 소유권의 이전과 이후, 또는 특정 시간 범위 내에서 소유권 관계를 탐색할 때 용이합니다.

B트리 맵으로 표현한 그래프 구조는 아래와 같습니다.

// borrow/ownership.rs

#[derive(Debug, PartialEq, Eq, Clone)]
struct OwnershipGraph {
    graph: BTreeMap<String, Vec<String>>,
}

각 키(String)는 그래프의 노드를, 해당 키에 연결된 값(Vec<String>)은 해당 노드에 인접한 노드들을 표현한 인접 리스트입니다. 그래프의 구조는 소유권 그래프 문단을 확인해주세요.

이 그래프는 OwnershipGraph::new 메서드를 통해 생성됩니다.

impl OwnershipGraph {
    pub fn new() -> Self {
        graph: BTreeMap::new(),
    }
}

이제 테스트를 실행시켜보면 의도한 그래프의 형태를 가지게 되었다는 것을 확인할 수 있습니다.

소유권 등록

// borrow/ownership.rs

const GLOBAL: &str = "global_var";  // <- 전역(global) 스코프를 나타냅니다

//...
    Statement::VariableDecl { name, is_borrowed, value } => {
      if *is_borrowed {
          if let Some(Expression::Reference(ref_var)) = value {
              current_owner = ref_var.clone();
              graph.add_borrower(&current_owner, name); // <- 소유권 등록
          }
      } else {                                      // -+ 변수에 할당된 값이 어떤 변수를
          current_owner = GLOBAL.to_string();       //  | 참조한 경우가 아니면, 해당 스코프의
      }                                             // -+ 전역 변수로 처리.
      graph.add_owner(&current_owner, name);
    }
// ...

변수가 선언되면 그 변수의 소유권을 현재 스코프에 등록합니다. OwnershipGraph::add_owner 메서드를 사용하여 현재 소유자(current_owner)를 변수의 소유자 목록에 추가합니다.

else 구문 내부에서는 스코프 내의 변수의 값이 참조된게 아니면 그 스코프 내에서의 전역 변수로 처리하도록 합니다.

impl OwnershipGraph {
    fn add_owner(&mut self, owner: &str, variable: &str) {
            let entry = self.graph.entry(owner.to_string()).or_insert_with(Vec::new);
          if !entry.contains(&variable.to_string()) {
        entry.push(variable.to_string());
    }
}

위에서 보이듯 이 메서드는 그래프에 새로운 노드(owner)를 추가합니다. 새로운 변수가 선언될 때 노드가 추가됩니다.

빌림 검사

// borrow/ownership.rs

// ...
if *is_borrowed {
    if let Some(Expression::Reference(ref_var)) = value {
        current_owner = ref_var.clone();   // <- 1
        // ...
    }
}

이 코드는 변수가 참조되는 경우를 처리합니다. is_borrowed가 참인 경우, 즉 변수가 별려지는 경우에 이 코드 블록이 실행됩니다.

value가 Expression::Reference 타입인 경우는 차용되는 변수가 참조(Reference) 되고 있음을 나타냅니다. ref_var는 참조되는 변수의 이름을 가리킵니다.

(1)에서 차용되는 변수(ref_var)를 현재 소유자(current_owner)로 설정합니다. 이는 차용되는 변수가 다른 스코프에 이미 소유되어 있는지 확인하는 과정입니다. 만약 ref_var가 이미 다른 스코프에 소유되어 있다면, 그 스코프가 현재 소유자가 됩니다.

이 과정을 통해, 변수가 빌려지는 경우 해당 변수가 이미 다른 스코프에 소유되어 있는지 확인하고, 그 스코프를 현재 소유자로 설정하여 빌림을 관리합니다. 이는 러스트의 소유권 및 빌림 규칙을 모방한 것으로, 한 번에 하나의 소유자만을 가질 수 있고, 불변 참조는 여러 개 있을 수 있지만 가변 참조는 한 번에 하나만 있어야 한다는 규칙을 지키도록 합니다.

대여 리스트 업데이트

// borrow/ownership.rs

if *is_borrowed {
    if let Some(Expression::Reference(ref_var)) = value {
        current_owner = ref_var.clone();
        graph.add_borrower(&current_owner, name); // <-
    }
}

변수가 참조되는 경우, 그 빌림을 노드의 대여 목록에 추가합니다. OwnershipGraph::add_borrower 메서드를 사용하여 현재 소유자(current_owner)를 변수의 대여 목록에 추가합니다.

impl OwnershipGraph {
    pub fn add_borrower(&mut self, owner: &str, borrower: &str) {
    if let Some(borrowers) = self.graph.get_mut(owner) {
        if !borrowers.contains(&borrower.to_string()) {
            borrowers.push(borrower.to_string());
        }
    }
    }
}

OwnershipGraph::add_borrower는 그래프의 노드 사이에 간선을 추가합니다. 변수가 다른 변수로부터 참조되면 간선이 추가됩니다.

빌림 제거

// borrow/ownership.rs

for var in declared_in_scope {
    graph.remove_owner(&prev_owner, &var);
    current_owner = prev_owner.clone();
}

차용 범위가 끝나면, 그 범위에서 선언된 모든 변수의 빌림을 연결 목록에서 제거합니다. OwnershipGraph:remove_owner 메서드를 사용하여 이전 소유자(prev_owner)를 변수의 소유자 목록에서 제거합니다.

impl OwnershipGraph {
    pub fn remove_owner(&mut self, owner: &str, variable: &str) {
    if let Some(owners) = self.graph.get_mut(owner) {
        owners.retain(|x| x != variable);
    }
  }
}

이 메서드는 그래프에서 노드(owner)를 제거합니다. 변수가 범위를 벗어날 때 노드가 제거됩니다.

소유권 정보 업데이트

⚠️ 이 부분은 아직 스코프가 완전히 구현되지 않아 예상되는 대략적인 동작만을 설명합니다. 하지만 추후 업데이트 될 예정입니다. [2023-06-12 기준]

// borrow/ownership.rs

Statement::Scope(scope) =>  {
    let prev_owner = current_owner.clone();
    let mut declared_in_scope = vec![];          // <- 1
    for inner_stmt in scope {
        if let Statement::VariableDecl { name, value, is_borrowed } = inner_stmt {
            declared_in_scope.push(name.clone());
            // ...
            graph.add_owner(&prev_owner, name);  // <- 2
            current_owner = name.clone();        // <- 3
        }
    }
    // ...
}

중첩된 범위에서 빌림이 발생하는 경우, 각 범위에서 빌림을 적절히 해결하고 소유권 정보를 업데이트합니다. 이 코드는 중첩된 범위에서 변수를 선언하고(1), 그 변수의 소유권을 이전 소유자(prev_owner)에 등록하며(2), 변수를 현재 소유자(current_owner)로 설정(3)하는 과정을 보여줍니다.

최종 빌림 규칙 검사

// borrow/ownership.rs

for (variable, owners) in &graph.graph {
    if owners.len() > 1 {            // <- 1
        for owner in owners {        // <- 2
            if owner == variable {   // <- 3
                return Err(OwnerGraphError::MultipleOwners(variable.clone()));
            }
        }
    }
}

이 코드는 AST 순회가 끝난 후 모든 빌림 규칙을 확인하여 빌림이 올바른지 확인하는 부분입니다.

(1)에서는 한 변수가 여러 소유자를 가지고 있는지 확인합니다. 소유권 규칙에서 변수는 한 번에 하나의 소유자만을 가질 수 있기 때문입니다.

(2)에서는 소유자 목록의 각 소유자에 대해 검사를 적용합니다.

(3)에서는 소유자가 변수 자신을 소유하고 있는지 확인합니다. 이는 변수가 자기 자신을 소유하고 있는지 확인하는 것으로, 이 경우에도 빌림 규칙을 위반한 것입니다. 즉, AST 순회를 마친 뒤, 빌림 규칙을 적용하여 올바르게 빌렸는지 검증하는 단계입니다. 만약 한 변수가 여러 소유자를 가지고 있거나, 자기 자신을 소유하는 경우에는 MultipleOwners 에러를 반환합니다.

전체 코드

전체 구현 코드는 다음 링크를 참고해주세요. 소유권 그래프 뿐만 아니라 현재 구현된 AST나 파서와 같은 부분들도 볼 수 있습니다. [구현]

마무리

이것으로 소유권 그래프의 구현과 설명을 마치겠습니다. 먼저 러스트의 빌림 규칙과 소유권에 대해 간단히 알아보았고, 그래프를 구현하는 과정에서 고려해야 할 사항과 데이터 구조, 그리고 정렬된 상태로 유지해야 하는 이유 등을 살펴보았습니다. 아직 완벽하게 동작하는 코드는 아니지만(작성 시점 기준으로), 이런 대략적인 흐름을 파악하고 구현하는 데 참고가 되었으면 좋겠습니다.

각주

[deg] 그래프 이론에서 $deg(v)$는 정점(vertex)의 차수(degree)를 의미합니다. 즉, 정점 $v$에 접하는 간선(edge)의 수를 나타냅니다. $O(deg(v))$는 일반적으로 정점 v의 차수에 따라 달라지는 일부 알고리즘 또는 연산에 대한 시간 복잡성의 상한을 나타내며, 이는 시간 복잡성이 최대 $deg(v)$의 일정한 배수에 비례한다는 의미입니다. 인접 리스트의 노드 삭제의 복잡도는 $O(V+E)$로 표기할 수 있지만, 소유권 그래프에서 노드 삭제는 해당 노드와 연결된 모든 소유권 관계를 수정해야 하기 때문에 연결된 간선의 차수에 따라 소요 시간이 달라집니다. 따라서 이 표에서는 삭제에 걸리는 복잡도를 $O(deg(v))$로 표현했습니다. 이는 인접 리스트 배열의 노드 삭제에도 해당됩니다.

[BTM] BTreeMap에서 노드 삭제, 삽입, 검색의 복잡도는 $O(logn)$입니다. HashMap의 $O(1)$에 비하면 느리지만, 딱히 신경 쓸 필요는 없습니다.