슭의 개발 블로그

Multithreaded programming에서 공유 자원에 접근할 때는 동시에 두 개 이상의 스레드가 자원을 변경시키지 않기 위해서 mutex 를 사용한다. Mutex를 사용하면 공유자원에 접근하는 스레드를 한 개로 제한하기 때문에 안전하지만, 어떤 경우는 비효율적이다. 예를 들어 여러 스레드가 공유 자원에 동시에 접근해야 하지만 그중 일부 스레드만 값을 변경하는 경우는 어떨까? 이런 경우 값을 읽기만 하는 스레드는 동시에 접근해도 상관없다. 하지만 어떤 스레드가 값을 변경하고 있으면, 다른 스레드는 공유 자원에 접근해서는 안 된다. 반대로 다른 스레드가 공유 자원에 접근하고 있는 중에는 값을 변경하는 스레드는 접근해서는 안 된다. 이때 사용하는 것이 shared-exclusive lock이라고도 하는 readers-writer lock 이다. Readers-writer lock은 여러 개의 reader와 한 개의 writer를 허용한다. 그래서 multiple-readers/single-writer lock(MRSW lock)이라고도 불린다. 즉, 이미 read lock이 잡혀있는 readers-writer lock에 read lock을 잡으면 바로 lock이 잡히고 다음 코드를 실행할 수 있지만, write lock을 잡으면, lock을 잡지 못하고 read lock이 풀릴 때까지 기다린다. 그렇다면 A thread 가 read lock을 잡고, B thread 가 write lock을 잡은 뒤 C thread 가 read lock을 잡으면 어떻게 될까? 단순하게 생각해보면 A thread 가 read lock을 잡고 있으니 B thread 의 write lock은 잡히지 못하고 기다리고, C thread 의 read lock은 잡힐 수 있기 때문에, A thread 와 C thread 의 코드가 실행될 것이다. 하지만 이런 구현의 경우 read lock이 빈번하게 잡히는 코드라면, write lock이 영원히 실행되지 못할 수도 있다. 이 ...

아무 글도 안 쓴지 벌써 삼 개월이 지났다. 아무래도 너무 오래 논거 같아서 뭐라도 써야 할 것 같다. 사실 쓰고 싶은 주제는 많다. 하지만 대부분 주제가 쓰는 데 시간이 걸릴 주제라서 귀찮고, 이번에는 간단하게 Rust 를 배우는데 읽기 좋은 자료들을 정리해보도록 하겠다. Rust는 배우기 어려운 언어로 소문나 있지만, 그런 만큼 Rust 개발 커뮤니티에서 공식적으로 제공하는 문서가 많이 있다. 그중에서 입문자가 읽기 가장 좋은 문서는 RBE라고 불리는 Rust by Example 다. RBE는 자세한 설명보다는 실제 코드를 어떻게 짜야 하는지를 보여준다. RBE를 읽었으면 Rust를 배우기 위해서 Rust Book이라고 불리는 Rust Programming Language 를 반드시 읽어야 한다. Rust Book은 Second edition 이후로 Live edition으로 관리되고 있는데, 기초적인 내용부터 Rust를 사용하는 데 꼭 필요한 내용을 담고 있다. 사실 일반적으로는 RBE보다 Rust Book을 먼저 읽는 것을 추천하는데 나는 Rust Book과 RBE 중 어느 쪽을 먼저 읽을지는 취향의 문제라고 생각한다. 그다음은 Rust Standard Library 다. Rust 표준 라이브러리를 설명한 문서인데, Rust를 no_std 옵션으로 사용할 것이 아니라면, 반드시 읽어야 하는 문서다. 하지만 라이브러리 매뉴얼이라는 특성상 처음부터 순서대로 읽을 일은 거의 없고 그때그때 필요한 것이 있으면 찾아보는 경우가 대부분이다. 하지만 한 번 처음부터 제대로 읽어보는 것을 추천한다. 특히 표준 라이브러리의 소스로 가는 링크를 제공하는데, 표준 라이브러리는 사실상 Rust를 가장 잘 쓰는 사람들이 짠 코드이기 때문에, 소스코드를 읽으며 배우는 점도 많다. Rust idiom을 배우기 위해서라도 한 번 읽어보는 것이 좋다. 여기까지 읽었으면 Rust에 대한 기본적인 지식은 생겼을 것이다. 여기까지만 해도 Rust로 프로그래밍하는데 별 문제...

3줄 요약 Chromium OS에서 PlayStore 실행시키는 거 보고 반함 집에서 놀던 노트북에 설치함 포맷 거의 2주 정도 삽질을 했다. 시작은 우연히 보게 된 위의 영상 때문이었다. Chrome OS의 고질적인 문제인 쓸만한 앱이 없다는 문제를 해결하기 위해 ChromeOS에서 안드로이드 앱을 실행할 수 있게 했다는 것이다. 안 그래도 개발용 데스크톱을 새로 장만하면서, 전에 사용하던 리눅스 노트북의 용도가 단순 인터넷 서핑 정도가 됐기 때문에 망설임 없이 노트북을 포맷하고 Chrome OS의 오픈소스 버전인 Chromium OS를 설치했다. Chromium OS를 설치하면서 기대했던 것은 대략 다음과 같다. Play Store를 이용해서 노트북으로 안드로이드 게임 플레이하기 어차피 인터넷밖에 안 할 거 크롬 이외의 UI 부하를 줄여서 조금이라도 저전력으로 만들기 필요하면 개발자 모드로 터미널 사용하기 설치하는 게 쉽지는 않았다. Chromium OS는 공식적으로 바이너리 배포를 하지 않는다. Chromium OS를 사용하는 공식적인 방법은 ChromeOS가 설치된 크롬북을 구매하는 것뿐이다. 그 외의 개인적으로 사용하고 싶은 사람들은 Chromium OS를 소스에서 빌드해서 설치해야 한다. 그래서 소스를 클론 받았는데, 소스만 22GB다. 구글 프로젝트 대부분이 그렇듯이, 내부적으로 의존하고 있는 라이브러리의 소스까지 전부 포함하고 있기 때문인듯하다. 어쨌든 소스 받는 데만 하루가 걸렸다. 그리고 빌드를 시작했는데 빌드 중 중간결과물만 100GB가 넘는 크기가 나왔다. 그래도 어찌어찌 빌드하여 설치했는데, 실행이 안 된다. 찾아보니 기본적으로는 지원되는 하드웨어가 적고, 다양한 하드웨어를 지원하기 위해는 빌드 시 설정을 바꿔야 한다고 한다. 그래서 이것저것 뒤져가면서 빌드를 다시 해봤는데 여전히 실행이 안 된다. 그래서 포기하려던 찰나에 비공식적으로 Chromium OS 이미지를 배포하는 사람 이 있다는 것을 발견하고...

Rust 는 RAII idiom 을 사용하는 언어로, 객체가 소멸하는 시점에 따라 코드의 의미가 달라진다. 예를 들어 아래 코드를 보자. 이 코드는 Service 의 객체를 생성하고 종료하기를 기다리는 코드다. 이 코드는 문법적으로는 아무 문제가 없다. 하지만 종료할 때까지 Service 가 어떤 동작을 수행하기를 원했다면 이는 틀린 코드다. Service 객체는 아무 변수에도 bind 되지 않았기 때문에 이 객체는 두 번째 줄에 있는 문장이 끝나면 소멸한다. Service 객체가 wait_for_exit 이 수행될 때까지 살아있기를 원한다면, 아래와 같이 변경해야 한다. 위의 코드에서 Service 의 객체는 변수 service 에 bind 된다. 따라서 두 번째 라인이 끝나도 소멸하지 않고 wait_for_exit 이 종료되는 것을 기다리고, run 함수가 종료되면서 stack이 unwind 될 때 소멸한다. 하지만 위의 코드를 컴파일하면 server 가 unused variable이라는 경고가 보일 것이다. Rust 컴파일러는 선언된 변수가 사용되지 않으면 경고를 내기 때문이다. 그렇다면 사용하지 않는 변수의 소유권만 가지고 있고 싶을 때는 어떻게 해야 할까? 이 경우 _(underscore)로 시작하는 변수 이름을 사용하면 된다. Rust 컴파일러는 _로 시작하는 변수를 특별 취급하기 때문에, _로 시작하는 변수는 사용하지 않아도 컴파일러 경고가 나지 않는다. 그렇다면 사용하지 않는 변수에 아무런 이름을 주지 않으면 어떻게 될까? 어차피 사용하는 것이 목적이 아니고, 객체를 bind만 해서 가지고 있는 것이 목적이라면 아래 코드처럼 아무 이름 없이 _ 를 변수로 사용해도 되지 않을까? 아쉽게도 위 코드는 예상대로 동작하지 않는다. 이는 _ 가 객체의 소유권을 가지지 않기 때문이다. 이를 Rust의 용어로는 _ 는 value를 bind 하지 않는다고 말한다. 즉, 위의 코드는 Service 객체를 생성하고 소멸시킨 뒤 wait...

지난번 글 에서 설명했듯이 이더리움 은 Modified Merkle Patricia Trie 를 4가지 용도로 사용한다. 이 중 State Trie와 Storage Trie는 변경되는 데이터를 효율적으로 저장하고 검증하기 위해서 사용된다. 하지만 Transaction Trie와 Receipts Trie는 변경되는 데이터가 대상이 아니다. 이 두 trie는 하나의 블록에서 사용된 트랜잭션과 그에 의해 생성된 receipt의 검증을 위해서만 사용되는 휘발성 데이터다. 이더리움이 두 가지 목적을 위해 같은 데이터 구조를 사용하는 이유는 같은 구현을 공유하기 위해서였다. 하지만 목적이 다르기 때문에 Transaction Trie나 Receipts Trie를 생성하는데 최적화된 코드는 State Trie나 Storage Trie를 생성하는데 필요한 코드와 다르다. 실제로 Parity 는 각각의 용도로 다른 코드를 사용한다. 그렇다면 Transaction Trie나 Receipts Trie를 위해 애초에 같은 Trie를 사용할 이유가 없지 않았을까? 현재 코드박스에서 개발하고 있는 코드체인의 transactions_root와 invoices_root는 이런 고민이 반영됐다. 그래서 UTXO를 저장하는 Merkle Patricia Trie 와는 다른 구현을 사용하기로 결정했다. 그렇다면 transactions_root와 invoices_root에 필요한 특성은 무엇이 있을까? 최소한의 필요조건은 데이터를 검증할 수 있어야 한다는 것이다. 이 검증은 단순히 데이터셋을 검증할 뿐 아니라 데이터의 순서도 일치하는지 확인해야 한다. 여기까지가 이더리움을 비롯한 일반적인 블록체인에서 필요한 특성이다. 코드체인에서는 여기에 몇 가지 요구사항이 더 들어갔다. 우선 구현이 간단해야 한다. 간단해야 한다는 것은 코드가 단순하다는 것뿐 아니라 메모리 사용량이 적고, 실행하는데 시간이 적게 걸려야 한다는 것을 의미한다. 이는 코드체인이 라이트 클라이언트를 고려하고 있기 때문이다...

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 지난주 에 이어 이번 주는 P2P를 주제로 발표 했다. 이번에도 발표자료를 만들면서 참고한 자료를 공유하도록 하겠다. Chord: a scalable peer-to-peer lookup protocol for internet applications Tapestry: A Resilient Global-scale Overlay for Service Deployment Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems A Scalable Content-Addressable Network P2P 네트워크 중에서도 네트워크 토폴로지가 특정한 규칙에 의해서 구성되는 네트워크를 structured 네트워크라고 말한다. Structured network는 unstructured network에 비해 특정 노드에 부하가 걸리거나 의존하는 것을 방지하면서 잘 분산된 네트워크를 구성할 수 있다. 위의 4 논문은 각기 Chord , Tapestry , Pastry , Content Addressable Network (a.k.a. CAN)라는 대표적인 structured 네트워크 오버레이를 제시하는 논문이다. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric Kademlia는 위의 네 논문을 개선하는 네트워크 오버레이를 제시한다. BitTorrent , eDonkey , 이더리움 등 많은 P2P 시스템이 kademl...

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 회사에서 이런 거 하느라 바빠서 한동안 다른 글은 읽을 시간이 없네요. 발표는 몇 주 동안 계속할 거라서 당분간은 발표자료 만들면서 참고했던 자료들을 공유할 것 같습니다. Impossibility of distributed consensus with one faulty process 분산 환경에서 합의 알고리즘을 말할 때 빼놓을 수 없는 논문이다. 합의 알고리즘에 필요한 기본적인 속성은 크게 safety와 liveness가 있다. Safety는 잘못된 합의가 이루어지지 않는다 는 것이고, liveness는 언젠가는 합의가 반드시 이루어진다 는 것이다. 위 논문은 비동기 네트워크에서 하나의 fail-stop failure 노드만 있어도 이 합의가 이루어질 수 없다는 것을 보였다. 이를 FLP impossibility라고 부른다. Consensus in the presence of partial synchrony 첫 번째 논문이 비동기 네트워크에서 safety와 liveness를 보장하는 합의 알고리즘이 불가능하다는 FLP impossibility를 보였다. 그래서 이 논문은 partial synchronous model을 만들어 특정한 가정 아래서 safety와 liveness를 같이 보장하는 합의 알고리즘을 만들 수 있게 해줬다. Partial synchronous model은 메시지가 언젠가는 도착하는 것을 보장하지만 그 도착하는 시간이 언제인지 알 수 없는 모델이다. The Byzantine generals problem Byzantine failure라는 용어의 어원이 된 논문이다. 이...