레이블이 garbage collection인 게시물을 표시합니다. 모든 게시물 표시
레이블이 garbage collection인 게시물을 표시합니다. 모든 게시물 표시

2019-04-14

Garbage collection과 memory leak

Garbage collection(a.k.a. GC)은 프로그램이 더 이상 접근할 수 없는 메모리를 자동으로 해제시켜 주는 기술을 의미한다. John McCarthy가 Lisp에 처음 구현한 이후 많은 언어가 사용하여 현대 프로그래머 중에 모르는 사람이 없다고 해도 좋을 정도로 널리 알려진 개념이다. 근데 이 GC에 대해서 사람들이 자주 착각하는 것이 있다. GC를 사용하는 이유가 memory leak을 잡아주기 위해서라고 생각하는 것이다. 만약 이렇게 생각했다면 GC에 대해 큰 착각을 하는 것이다.

GC는 memory leak을 막지 못한다. 사실 튜링 완전한 언어에서 memory leak을 막아주는 방법은 세상에 존재할 수 없다. 이것을 설명하기 위해서는 우선 memory leak이 무엇인지 알아야 한다. Wikipedia는 memory leak을 다음과 같이 설명한다.

a type of resource leak that occurs when a computer program incorrectly manages memory allocations in such a way that memory which is no longer needed is not released.

쉽게 설명해 memory leak이란, 사용하지 않을 메모리를 해제하지 않는 현상이다. 결국 memory leak을 잡기 위해서는 사용하지 않는 메모리를 찾아내는 것이 먼저다. 그리고 사용하지 않는 메모리를 완벽하게 찾아내는 건 불가능하다. 자세한 설명은 아래 코드를 통해서 하도록 하겠다.

위 코드에서 x는 언제 해제해야 할까? 보통은 use(x)가 끝난 뒤 해제해야 한다고 생각할 것이다. 하지만 some_function이 종료되지 않는 함수라면 어떨까? some_function이 내부에서 무한 루프를 돌고 절대 종료되지 않는 함수라면 use(x)는 호출될 일이 없다. 따라서 x는 앞으로 접근할 일이 없는 메모리고, some_function이 실행되고 있는 동안 x를 해제하지 않고 있는 것은 memory leak이다. 따라서 이 함수가 memory leak이 없다고 하려면 some_function이 실행되기 전에 이 함수가 종료되는 함수인지 아닌지 분석해서 x의 메모리 해제 시점을 결정해야 한다. 어떤 함수를 실행하기 전에 종료되는지 알 수 있다는 것은 정지 문제를 풀 수 있다는 것이므로 모순이다. 따라서 실행 전에 some_function이 종료되는지 알 방법은 없다. 즉, memory leak을 완벽히 잡는 방법은 존재할 수 없다.

그래서 GC를 비롯한 메모리 관리 기술들은 전부 앞으로 사용하지 않는 메모리를 전부 해제하는 것을 보장하지 않는다. 대신 앞으로 사용하지 않는 것이 확실한 메모리만 해제하는 방식으로 동작한다. 즉, memory leak을 모두 잡는 대신 해제해도 안전한 메모리만 해제하는 것이다. 이를 조금 더 formal 하게 표현하면, '이 메모리를 해제해도 안전한가?'라는 질문에 completeness는 포기하지만, soundness를 보장하는 알고리즘으로 해제할 메모리를 찾는다고 할 수 있다.

모든 memory leak을 잡지는 못하지만, 해제해도 안전한 메모리만을 해제하는 것. 이것이 GC의 역할이다. GC를 사용하면 사용해야 할 메모리를 해제하지 않는다. 즉, dangling pointer가 생기지 않는다는 것이고, 이에 따라서 double free나 use-after-free 같은 문제가 생기지 않는다. 즉, GC는 메모리 사용의 효율성이 아닌, 소프트웨어의 안정성을 올리는 도구라는 것이다.

GC를 썼더니 결과적으로 memory leak이 줄었다는 일은 있을 수 있다. 하지만 memory leak을 잡기 위해 GC가 있는 언어를 선택한다거나, GC가 있는 언어를 쓴다고 memory leak이 없을 것이라 생각하면 안 된다. 아쉽게도 memory leak은 사람이 소스를 분석해서 잡는 수밖에 없다. GC를 비롯한 메모리 관리 시스템은 전부 memory leak을 잡기 위한 기술이 아니라 해제해도 안전한 메모리만 해제하기 위한 기술로써 사용해야 한다.

2019-04-06

managed language와 unmanaged language?

얼마 전 우연히 이런 글을 보게 됐다. 프로그래밍 언어를 managed language와 unmanaged language로 구분한 것인데 그 기준을 garbage collection(a.k.a. GC)을 하는가 아닌가로 잡았다. 난생처음 들어보는 기준이었다. 인생이 힘들어서 노느라 바쁜 사이 뭔가 새로운 논문이 나왔나 하고 찾아봤다.

역시나 이런 경우 대부분 그렇듯이 다른 나라에서는 안 쓰이고 다른 나라에서는 안 쓰이고 우리나라에서 작성된 블로그만 보였다. 그 블로그들이 공통으로 언급하는 것으로 보아 어떤 사람이 유튜브에서 처음 사용한 것 같다. 사실 다른 나라에서는 안 쓰이는 기준이라는 건 별로 중요하지 않다. 그보다 중요한 건 이 managed language라는 것이 잘못 붙여진 이름이라는 것이다.

일단 managed/unmanaged라는 용어 자체가 없는 것은 아니다. 이건 MS 진영에서 만든 용어다. MS는 managed language 대신 managed code라는 단어를 주로 쓰기는 했지만 말이다. MS에서 만든 managed code는 Common Language Runtime(a.k.a. CLR)에서 실행되는 코드를 의미한다. 반대로 CLR에 의존하지 않는 코드를 unmanaged code라고 부른다.

물론 CLR이 제공하는 기능에 GC가 포함되기 때문에 managed code는 GC을 사용한다. 하지만 GC에 초점을 맞추면 안 된다. 여기서 중요한 것은 virtual machine 위에서 코드가 실행된다는 것이다. virtual machine 위에서 돌기 때문에 컴퓨터 아키텍쳐에 따라 새로 컴파일할 필요 없다거나, 다른 머신에서도 같은 동작을 기대할 수 있다는 등 CLR의 장점에 주목해야 한다.

한때는 managed code를 생성할 것을 목표로 설계된 C#, Visual Basic 같은 언어를 managed language라고 부르기도 했지만, 요새는 잘 안 보인다. 안 쓰이게 된 이유는 모르겠다. 그저 C++을 이용해 CLR을 쓸 수 있게 해주는 C++/CLI 같은 프로젝트가 나오면서 구분할 필요가 없어진 것이 이유가 아닐까 추측할 뿐이다. 그렇다면 MS의 managed code는 둘째치고 GC를 사용하는가 아닌가를 기준으로 managed language라는 새로운 기준을 만들면 안 되는 것일까?

결론부터 말하면 오해를 줄 수 있기 때문에 안 된다. GC를 쓰는가 아닌가를 기준으로 언어를 나눌 수는 있다. 이건 의미 있는 기준이다. 하지만 그 기준으로 붙여진 이름이 managed language이면 안 된다. 이 이름은 메모리를 자동으로 관리하는 방법이 GC뿐이라는 오해를 주게 된다.

10년 전에는 GC를 사용하는 언어를 기준으로 managed/unmanaged를 나눠도 이상하지 않았을 것이다. 당시에는 메모리를 자동으로 관리하는 방법이 GC를 쓰는 것밖에 없었기 때문이다. 하지만 2002년 David Walker 교수가 정리한 linear type system이나 affine type system에 대한 개념을 기반으로 리소스를 안전하게 사용하는 방법에 대한 많은 연구가 있었고, 현대 프로그래밍 언어들은 이에 관한 개념을 적극적으로 반영하고 있다. 심지어 C++마저도 말이다. 특히 저 글에서 unmanaged로 구분하고 있는 Rust 같은 경우가 affine type system을 적극적으로 사용하여 메모리를 관리하는 대표적인 언어다. 즉, 이제는 GC가 메모리를 자동으로 관리하는 유일한 방법이 아니다.

분류는 새로운 개념을 쉽게 배우게 해주는 좋은 도구다. 분류라는 것은 추상적이고 많은 개체의 속성을 분명하고 외우기 쉽게 해준다. 하지만 이것은 어디까지나 기준이 명확하고 용어가 올바를 때의 얘기다. 잘못된 기준으로 분류하거나 잘못 도니 이름을 사용하게 되면 오히려 배움에 방해가 될 뿐이다.

2018-04-29

Ethereum의 state trie pruning

Ethereum은 현재 상태를 prefix tree의 일종인 modified merkle patricia trie(a.k.a. MPT)로 저장한다. MPT는 state root의 hash를 계산하기 위해 state trie 전체를 볼 필요가 없이, 수정된 branch의 hash만 다시 계산하면 되기 때문에 빠르게 root hash를 찾을 수 있다.

MPT를 이용하면 새로 추가되는 노드의 수도 최소화할 수 있다. 예를 들어 위의 그림에서 block N과 block N + 1의 차이는 A의 오른쪽 자식의 값이 10에서 20으로 변경된 것뿐이다. 이 경우 10에서 20으로 변경된 노드의 부모 외의 다른 노드는 전부 기존의 노드를 재활용할 수 있다. 따라서 푸른색으로 그려진 3개의 노드만 새로 추가하면 된다.

그렇다면 더는 접근할 필요가 없는 노드들은 어떻게 되는가? 위의 예제에서 붉은색으로 표시된 3개의 노드는 block N + 1에서는 필요 없는 노드다. 그렇다면 이 3개의 노드는 3개의 푸른색 노드가 추가되고 나면 바로 지워도 될까? 그랬으면 문제가 쉬웠겠지만 아쉽게도 그렇지 않다. Ethereum은 block의 finality를 보장하지 않는다. 다른 말로 언제든지 block N + 1이 block N으로 retract 될 수 있다는 것이다. 게다가 Web3 API를 통해서 과거의 state에 접근하는 것도 가능하기 때문에 현재 상태에서 안 쓰이는 노드를 바로 지울 수는 없다.

그렇다고 영원히 남겨둘 수는 없다. 현재 ethereum에서 최신 state의 크기는 약 25GB 정도지만, 과거 state를 전부 저장하면 300GB를 넘어간다. 게다가 이 크기는 점점 커질 것이기 때문에 이를 전부 저장하는 것은 현실적이지 않다. Ethereum은 접근할 수 있는 과거 state를 127개로 제한하여 그보다 오래된 state에만 포함된 노드는 지워도 되도록 하였다. 하지만 지워도 된다는 것과 지울 수 있다는 것은 별개의 문제다. DB에 저장돼있는 노드 중 최근 127개의 노드에서 접근할 수 없는 노드를 찾아 지우는 것은 쉬운 문제가 아니다.

이 문제는 computer science에서 오랫동안 풀어 온 automatic memory management 문제와 비슷하다. 실제로 Vitalik Buterin이 쓴 state tree pruningreference counting을 언급하고 있다. 하지만 ethereum의 state trie pruning은 일반적인 memory management와 다른 점이 하나 있다.

일반적인 automatic memory management는 volatile 한 자원을 다룬다. 따라서 프로그램이 비정상 종료되는 상황을 고려하지 않아도 된다. 프로그램이 종료되면 관리해야 할 자원이 남아 있지 않기 때문이다. 하지만 state trie의 노드는 DB에 저장되는 persistence 메모리다. 프로그램의 비정상 종료로 인해 state trie가 비정상적인 상태가 되면 복구할 방법이 없다. Vitalik이 제시한 state tree pruning이 메인 넷에 들어가지 못한 것도 이런 이유에서다.

Reference counting이 아닌 다른 방법으로 state trie pruning을 구현할 수도 있다. 예를 들어 trace를 이용하는 방법도 tracing garbage collection도 automatic memory management에서 흔히 사용되는 기법이다. 하지만 trace에 필요한 추가적인 메모리나, stop-the-world에 의해 생기는 성능 문제 등이 먼저 해결돼야 한다.

이러한 문제들로 현재 go-ethereum에서는 매우 한정적으로 state trie pruning을 한다. State trie에 대해 cache를 사용하는데, 이 cache에만 저장된 노드에 대해서는 pruning을 하고 DB에 저장된 노드는 pruning을 하지 않는 방식이다. Caching 된 노드는 서버가 정상적으로 종료되거나, 생성된 지 128 block이 지났거나, 캐시 크기를 넘겼거나, 마지막으로 cache된 노드가 DB에 저장된 지 5분이 지나면 DB에 저장한다. 즉, 위의 조건을 만족하기 전에 cache에서 삭제된 노드는 DB에 저장하지 않는다.

하지만 생성된 지 5분이 지나지 않아서 삭제되는 노드는 그리 많지 않다. 따라서 대부분의 삭제됐어야 할 노드는 여전히 DB에 남아 있다. 이에 대해 ethereum에서는 state pruning을 구현하는 것을 계속 시도하고 있다. 하지만, state trie pruning이 실제로 구현되기 전에는 fast sync를 사용하여 다음과 같은 방법을 사용하기를 권장한다.

  1. 새 클라이언트를 띄운다.
  2. 기존 클라이언트에서 새 클라이언트로 fast sync를 받는다.
  3. 기존 클라이언트를 지운다.

위의 과정을 거치면 새 노드에서는 fast sync로 동기화된 상태까지의 garbage node 없이 유효한 노드만 관리할 수 있다. 언뜻 보기에는 주먹구구식 방식으로 보이지만, 위험 부담이 있는 garbage collection을 구현하는 것보다 안전하고 현실적인 해결책이다. Ethereum에 garbage collection이 구현되기 전까지는 계속 위와 같은 방식을 이용해야 할 것으로 보인다.