8년차가 이미 아는 기초(정렬·기본 자료구조·BFS/DFS·기본 DP)는 제외하고, 프로토콜·시스템·AI 엔지니어링의 고급 주제 100개를 하루 1개씩. *(2026-07-30 Jay 지시로 신설 — 구 "매일의 알고리즘(CLRS)" 트랙 종료·흡수.)*
운영: 매일 리포트 2 Basic Knowledge 안에서 1개. 완료-게이트(체크해야 다음 Day, 미체크면 반복).
분량: 개념 1개 + 코드/수식 10~25줄 + 연습 1개 + 실무·Verex 연결 1줄. "존재를 알고 필요할 때 꺼내 쓰는" 수준이 멈춤선.
분할상환분석은 연산 하나하나의 최악 비용이 아니라 n번 연산의 총비용을 보는 분석이다. 포텐셜 함수법은 자료구조의 상태를 실수 하나 Φ로 요약하고, 각 연산의 분할상환 비용을 실제 비용에 포텐셜 변화량을 더한 값으로 정의한다.
How it works이 정의 덕분에 n번 연산의 총 분할상환 비용을 더하면 중간 항이 전부 telescoping으로 소거되어, Φ가 0 이상이고 초기값이 0이면 분할상환 비용의 합이 실제 비용의 합의 상한이 된다. 동적 배열이 가득 찰 때마다 2배로 늘리는 doubling 전략에 Φ = 2·num − size를 잡으면, 복사가 일어나는 비싼 삽입도 매번 상수 시간 3으로 상각된다.
Why"평균적으로 O(1)"이라는 말이 운이 아니라 수학적으로 보장된다는 걸 증명해야, 시스템이 가끔 비싼 연산을 감당할 수 있는지 설계 단계에서 판단할 수 있기 때문이다.
Red-Black 트리·B+Tree·Skip List는 전부 정렬된 키를 O(log n)에 다루는 사전 자료구조지만, 실제로 갈리는 축은 복잡도가 아니라 디스크·동시성이다. 균형 트리에서 정말 비싼 연산은 탐색이 아니라 회전이고, 회전은 여러 노드를 원자적으로 바꿔야 해서 락 범위가 조상 쪽으로 넓어진다.
How it worksSkip List는 균형을 구조적으로 유지하는 대신 삽입할 때 동전을 던져 레벨을 정해 확률로 사는데, 회전이 아예 없으므로 삽입이 지역적이라 CAS만으로 락프리 구현이 가능하다. B+Tree는 노드 하나에 페이지 크기만큼 많은 키를 담아 디스크 지역성을 얻는 대신 회전 없이 노드 분할·병합으로 균형을 유지한다.
Why락을 어디에 얼마나 잡는가와 한 노드에 키를 몇 개 담는가가 그 자료구조가 동시 쓰기가 많은 시스템에서 쓸 수 있는지 없는지를 가르기 때문이다.
영속(persistent) 자료구조는 갱신 연산이 기존 버전을 파괴하지 않고 새 버전을 만들며, 이전 버전도 계속 조회 가능한 자료구조다. 핵심 기법은 구조 공유로, 변경된 경로 위의 노드만 새로 복사하고 나머지 서브트리는 이전 버전과 포인터를 그대로 공유한다.
How it works균형 트리나 트라이 기반 구조에서는 루트부터 변경 지점까지의 경로 길이가 O(log n)이므로 갱신 한 번의 시간과 추가 메모리도 O(log n)에 머문다. 과거 버전을 읽기만 가능한 부분 영속성과 과거 버전에서 다시 갱신까지 가능한 완전 영속성을 구분하며, 함수형 언어의 불변 리스트나 HAMT(hash array mapped trie)가 대표 사례다.
Why롤백, 스냅샷 격리, undo, 낙관적 동시성처럼 여러 버전을 동시에 살아 있게 해야 하는 시스템에서 매 갱신마다 전체 복사를 하면 O(n) 비용이 나기 때문이다.
함수형 업데이트는 기존 자료구조를 변형하지 않고 변경분만 반영한 새 버전을 만들어 반환하는 방식이다. 이를 값싸게 하는 핵심 기법이 path copying으로, 루트에서 수정 지점까지의 경로에 있는 노드만 복사하고 나머지 서브트리는 이전 버전과 포인터로 공유한다(structural sharing).
How it works균형 트리나 HAMT 같은 트라이 계열에서는 경로 길이가 O(log n)이므로 한 번의 업데이트 비용도 O(log n) 노드 복사로 억제된다. 대신 진짜 비용은 점근 복잡도가 아니라 상수항에 숨어 있다.
Why불변 상태를 쓰는 프론트엔드·상태머신 코드에서 "복사는 O(log n)이니 공짜"라고 믿다가 GC 스파이크와 캐시 미스로 처리량이 무너지는 일이 흔하다. 반대로 diff를 참조 비교로 처리할 수 있다는 점은 리렌더·변경 전파 최적화의 근거가 된다.
트라이는 키를 문자 단위로 쪼개 경로로 표현하는 자료구조이고, 패트리샤 트라이는 자식이 하나뿐인 연속 구간을 하나의 간선으로 압축(path compression)해 깊이를 줄인 변형이다. 이더리움의 Merkle Patricia Trie(MPT)는 여기에 머클 해시를 얹어, 각 노드가 자식들의 해시를 담고 부모는 그 해시들을 다시 해시하는 방식으로 상태 전체를 하나의 루트 해시로 커밋한다.
How it worksMPT의 분기 노드는 니블(4비트) 단위라 자식이 최대 16개이므로, 한 노드의 증명에는 형제 해시들이 모두 들어가고 증명 크기는 대략 (경로 깊이 × 분기 폭)에 비례해 커진다. Verkle 트라이는 해시 대신 벡터 커밋먼트(다항식 커밋먼트 계열)를 써서 한 노드의 자식 전체를 상수 크기 커밋먼트 하나로 묶고, 열람 증명도 상수 크기에 가깝게 만든다.
Why상태 증명 크기는 라이트 클라이언트와 stateless 검증의 대역폭을 직접 결정하고, 갱신 비용은 풀노드의 블록 처리 시간을 결정한다. 어느 쪽을 깎을지 모르면 스토리지 계층 설계나 증명 기반 기능의 실현 가능성을 판단할 수 없다.
확률적 자료구조는 정확한 답 대신 제한된 오차를 허용하는 대가로 메모리를 크게 줄이는 구조다. Bloom filter는 비트 배열과 k개의 해시 함수를 써서 원소 포함 여부를 판정하며, 거짓 양성은 있지만 거짓 음성은 없고 원소 삭제도 되지 않는다.
How it worksCuckoo filter는 원소 대신 짧은 지문(fingerprint)을 두 후보 버킷 중 하나에 넣는 방식이라 삭제를 지원한다. Count-Min sketch는 여러 해시 행의 카운터 배열로 빈도를 추정하며, 충돌 때문에 과대추정은 하지만 과소추정은 하지 않는다.
Why로그·멤풀·캐시처럼 원소가 수억 개인 곳에서 정확한 집합이나 카운터를 그대로 들고 있으면 메모리가 먼저 터진다.
스트리밍 알고리즘은 데이터를 한 번(또는 몇 번) 순차적으로만 훑으면서, 입력 크기보다 훨씬 작은 공간으로 근사 답을 내는 알고리즘이다. 정확한 답을 내려면 서로 다른 원소 수에 비례하는 메모리가 필요하다는 하한이 있기 때문에, 대신 오차와 실패확률을 파라미터로 받아 확률적 보장을 주는 스케치 자료구조를 쓴다.
How it worksheavy hitters(빈도 상위 원소 찾기)는 Misra-Gries처럼 카운터를 고정 개수만 유지하며 일괄 감소시키는 방식이나, Count-Min Sketch처럼 여러 해시 함수로 2차원 카운터 배열에 더하고 최솟값을 추정치로 쓰는 방식으로 푼다. 근사 분위수는 t-digest, KLL 같은 구조가 표본을 계층적으로 압축해 원하는 분위수를 오차 범위 안에서 답한다.
Why로그·메트릭·주문 흐름처럼 전량 저장이 불가능한 데이터에서 상위 사용자, p99 지연 같은 값을 실시간으로 알아야 할 때 정확 집계는 메모리에서 먼저 무너진다.
순서 통계란 배열을 정렬했을 때 k번째로 작은 원소를 뜻하며, 전체 정렬 없이 그 원소만 찾는 문제를 선택 문제라 한다. Quickselect는 퀵정렬의 분할을 재사용하되 피벗이 속한 한쪽 구간만 재귀하므로 기대 시간이 선형이지만, 피벗이 계속 치우치면 최악에는 제곱 시간이 된다.
How it works중위수의 중위수는 원소를 5개씩 묶어 각 그룹의 중위수를 구하고 그 중위수들의 중위수를 피벗으로 삼아, 매 단계에서 일정 비율 이상의 원소가 확실히 제거되도록 보장한다. 이 보장 덕분에 재귀식이 선형으로 풀려 최악에도 선형 시간이 되지만 상수 계수가 커서 실무에서는 느리다.
Whyp99 지연을 계산하거나 상위 N개를 뽑는 작업에서 전체 정렬을 돌리면 불필요한 로그 배수를 지불하게 되고, 순진한 Quickselect는 적대적 입력에서 최악 케이스로 끌려갈 수 있다.
서픽스 배열은 문자열의 모든 접미사를 사전순으로 정렬한 뒤 그 시작 위치만 배열로 보관하는 인덱스이다. 정렬돼 있으므로 임의의 패턴 검색을 이분 탐색으로 처리할 수 있고, 인접한 접미사의 공통 접두사 길이를 담은 LCP 배열을 함께 두면 반복 부분문자열, 서로 다른 부분문자열 개수 같은 질의도 선형에 가깝게 풀린다.
How it works서픽스 오토마톤(DAWG)은 같은 정보를 상태 기계로 표현한 것으로, 문자열의 모든 부분문자열을 인식하는 최소 결정적 오토마톤이며 상태 수가 입력 길이에 선형으로 유지된다. 오토마톤은 온라인으로 한 글자씩 추가하며 만들 수 있어 스트리밍에 유리하고, 서픽스 배열은 메모리가 조밀해 대용량 정적 텍스트에 유리하다.
Why로그·트레이스처럼 텍스트는 고정돼 있는데 검색은 수없이 반복되는 상황에서, grep식 선형 스캔은 데이터가 커지는 순간 그대로 비용이 된다.
세그먼트 트리는 배열 구간에 대해 결합법칙이 성립하는 연산(합, 최솟값, gcd 등)을 O(log n)에 질의·갱신하는 이진 트리 구조다. Lazy propagation은 구간 전체를 갱신할 때 각 노드에 "아직 자식에게 내려보내지 않은 연산"을 보류값으로 저장하고, 그 자식을 실제로 방문하는 시점에 밀어내려 구간 갱신도 O(log n)에 처리한다.
How it works이 기법이 성립하려면 보류 연산끼리 합성 가능해야 하고, 구간 크기에 따라 노드 값에 어떻게 반영되는지가 정의되어야 한다(예: 구간 덧셈이면 합에 delta 곱하기 구간 길이를 더한다). 영속(persistent) 세그먼트 트리는 갱신 시 루트에서 잎까지의 경로에 있는 O(log n)개 노드만 새로 만들고 나머지 서브트리는 이전 버전과 공유하는 path copying 기법으로, 모든 과거 버전을 O(log n) 추가 공간에 보존한다.
Why롤백이나 시점 스냅샷이 필요한 상태 집계, 그리고 구간 갱신이 대량으로 들어오는 워크로드에서 naive 구현은 갱신당 O(n)으로 무너진다.
위상정렬은 방향 비순환 그래프(DAG)의 정점을 모든 간선 u→v에 대해 u가 v보다 앞서도록 나열하는 것이다. Kahn 알고리즘은 진입차수 0인 정점을 큐에 넣고 꺼낼 때마다 인접 정점의 진입차수를 줄이는 방식으로 O(V+E)에 이를 계산하며, 큐가 비었는데 남은 정점이 있으면 사이클이 존재한다는 뜻이다.
How it works스케줄링 관점에서는 위상정렬의 각 단계, 즉 동시에 진입차수가 0이 되는 정점 집합을 하나의 병렬 레이어로 묶을 수 있고, 이때 레이어 수는 DAG의 최장 경로 길이와 같다. 따라서 프로세서가 무한히 많아도 실행 시간의 하한은 최장 경로(critical path)이며, 이것이 병렬 스케줄의 근본 한계다.
Why블록 내 트랜잭션을 병렬로 돌리려는 모든 설계는 결국 '충돌 그래프의 최장 경로'라는 한계에 부딪히므로, 병렬화로 얻을 수 있는 최대 이득을 미리 추정하려면 이 계산이 필요하다.
유량 네트워크는 각 간선에 용량이 있는 방향 그래프이고, 소스에서 싱크로 보낼 수 있는 최대 유량을 구하는 문제가 최대 유량 문제다. 최대 유량-최소 컷 정리는 소스와 싱크를 분리하는 컷 중 용량 합이 최소인 값이 최대 유량과 정확히 같다고 말하며, 이는 선형계획법 쌍대성의 조합론적 사례다.
How it works알고리즘은 잔여 그래프(residual graph)에서 증가 경로를 찾아 유량을 밀어 넣는 방식이 기본이고, 경로 선택 전략에 따라 Edmonds-Karp(최단 증가 경로)나 Dinic(레벨 그래프 + 블로킹 유량)으로 나뉜다. 이분 매칭은 모든 용량을 1로 둔 유량 문제로 환원되며, 이때 최대 매칭 크기가 최소 정점 덮개 크기와 같다는 König 정리가 최소 컷 정리의 특수형으로 따라 나온다.
Why스케줄링, 주문 배정, 노드-샤드 할당처럼 "누구에게 무엇을 얼마나" 문제가 나오면 대부분 유량 또는 매칭으로 환원되며, 잘못 모델링하면 지수 시간 탐색을 짜게 된다.
선형계획(LP)은 선형 부등식 제약 아래에서 선형 목적함수를 최대화하거나 최소화하는 문제이며, 실행가능 영역은 볼록 다면체이고 최적해가 존재하면 그 꼭짓점에서 달성된다. 모든 LP에는 짝이 되는 쌍대(dual) 문제가 있고, 약쌍대성은 임의의 쌍대 실행가능해가 원문제 최적값의 한계를 준다는 것, 강쌍대성은 양쪽이 모두 실행가능하면 두 최적값이 일치한다는 것이다.
How it works쌍대 변수는 각 제약의 잠재가격(shadow price), 즉 그 제약을 한 단위 완화했을 때 목적값이 얼마나 개선되는지를 뜻한다. 상보여유 조건은 여유가 남는 제약의 잠재가격은 0이고, 양의 가격이 붙은 제약은 반드시 타이트하다는 관계를 말한다.
Why경매나 블록스페이스 배분처럼 희소 자원을 나누는 문제에서, 배분의 최적성 증명과 참가자에게 물릴 가격이 같은 쌍대 구조에서 나온다는 사실을 알아야 논쟁을 수치로 끝낼 수 있다.
많은 조합 최적화 문제는 변수에 0 또는 1만 허용하는 정수계획(IP)으로 정확히 표현되지만 IP 자체는 NP-hard다. LP 완화는 이 정수 제약을 0 이상 1 이하의 실수 구간으로 느슨하게 풀어 다항 시간에 최적해를 구하는 기법이며, 완화한 최적값은 원 문제 최적값의 한계(하한 또는 상한)를 준다.
How it works랜덤 라운딩은 이렇게 얻은 분수해 x_i를 "i를 선택할 확률"로 해석해 독립적으로 동전을 던져 정수해로 되돌린다. 기댓값 계산과 집중 부등식으로 결과가 LP 최적값의 일정 배 안에 들어옴을 보이면 근사비가 증명된다.
Why실무의 스케줄링·배치·매칭 문제는 대부분 NP-hard라 최적해를 고집하면 풀리지 않고, 성능 보장이 있는 근사해를 언제 받아들일지 판단하는 근거가 필요하다. 또 LP 완화값은 휴리스틱 해가 최적에서 얼마나 떨어졌는지 재는 무료 기준선이 된다.
온라인 알고리즘은 입력 전체를 미리 보지 못하고 요청이 도착할 때마다 되돌릴 수 없는 결정을 내려야 하는 알고리즘이다. 성능은 절대 비용이 아니라 경쟁비로 재는데, 임의의 입력열에 대해 (온라인 알고리즘의 비용) / (모든 입력을 아는 오프라인 최적의 비용)의 최악값으로 정의된다.
How it works캐시 교체(페이징)에서는 크기 k인 캐시에 대해 LRU와 FIFO가 k-경쟁적이고, 결정론적 알고리즘의 경쟁비 하한도 k라서 LRU는 이 부류에서 최적이다. 무작위화를 허용하면 마킹 알고리즘처럼 기댓값 기준 경쟁비를 로그 규모로 낮출 수 있는데, 이는 적대적 입력이 알고리즘의 다음 수를 예측하지 못하게 만들기 때문이다.
Why캐시, 커넥션 풀, 실시간 입찰, 주문 매칭처럼 '미래를 모른 채 지금 결정해야 하는' 코드는 어디에나 있는데, 평균 케이스 직관만으로는 적대적 트래픽에서 무너진다. 경쟁비는 그 최악을 정량화해 주는 유일한 언어다.
환원은 문제 A의 인스턴스를 다항 시간에 문제 B의 인스턴스로 바꾸는 변환이며, A가 B로 환원되면 B가 A보다 쉽지 않다는 뜻이다. NP-완전은 NP에 속하면서 NP의 모든 문제가 그 문제로 환원되는 문제이고, NP-난해는 NP 소속 여부와 무관하게 그만큼 어려운 문제를 가리킨다.
How it works새로운 문제가 어렵다는 것을 보이는 표준 방법은 이미 알려진 NP-완전 문제를 그 문제로 환원하는 것이다. P와 NP가 다르다면 NP-완전 문제에 다항 시간 정확 알고리즘은 존재하지 않는다.
Why어려움의 근거를 모르면 본질적으로 불가능한 최적화를 계속 튜닝하며 시간을 태우거나, 반대로 쉽게 풀리는 특수 구조를 못 알아보고 성급히 포기한다.
work-span 모델은 병렬 계산을 DAG로 보고 두 값으로 요약한다. work T1은 전체 연산량(프로세서 1개로 걸리는 시간), span T∞는 의존성 사슬의 임계 경로 길이(프로세서가 무한히 많아도 못 줄이는 시간)이며, 병렬성은 T1/T∞로 정의된다.
How it works좋은 스케줄러(예: work-stealing)는 Tp가 대략 T1/p + T∞ 수준임을 보장하므로, 병렬성이 p보다 충분히 커야 선형 스케일에 가까워진다. Amdahl의 법칙은 문제 크기를 고정한 채 직렬 비율 s가 있으면 속도향상이 1/s로 상한이 걸린다고 말한다.
Why코어를 늘렸는데 성능이 안 오를 때, 원인이 직렬 구간인지 임계 경로인지 스케줄링 오버헤드인지 구분하지 못하면 엉뚱한 곳을 튜닝하게 된다.
조합적 대상의 열거란 부분집합, 조합, 순열 같은 구조를 중복 없이 빠짐없이 하나씩 생성하는 기법이다. 그레이 코드는 연속한 두 코드가 정확히 한 비트만 다르도록 부분집합을 나열하는 순서이며, 반사 이진 그레이 코드는 인덱스 i에 대해 i와 i를 오른쪽으로 한 칸 시프트한 값의 XOR로 간단히 얻는다.
How it works순열은 사전순으로 다음 순열을 만드는 방법이나, 매 단계 인접 두 원소만 교환하며 모든 순열을 생성하는 방식으로 열거할 수 있다. 이런 최소 변화 열거의 핵심 이점은 이전 상태에서 한 번의 작은 갱신으로 다음 상태의 평가값을 증분 계산할 수 있다는 것이다.
Why테스트 벡터 생성, 퍼징 시드 설계, 작은 상태 공간의 완전 탐색에서 중복이나 누락 없이 전수를 도는 것이 곧 검증의 신뢰도이고, 최소 변화 순서를 쓰면 상태 되감기 비용이 사라진다.
알고리즘 선택은 점근 복잡도만으로 결정되지 않고, 입력 규모, 데이터 분포, 접근 패턴, 메모리 계층, 갱신 빈도, 최악 대 평균 요구사항이라는 축들의 조합으로 결정된다. 예를 들어 n이 작으면 상수가 작은 O(n^2)가 O(n log n)을 이기고, 데이터가 거의 정렬돼 있으면 적응적 정렬이 유리하며, 캐시 지역성이 좋은 배열 기반 구조가 포인터 추적 구조보다 실측에서 앞서는 일이 흔하다.
How it works읽기 위주면 정적 인덱스, 쓰기 위주면 로그 구조나 상환 분석이 좋은 구조를 고른다. 지연시간 꼬리(p99)가 중요하면 평균이 좋아도 최악이 나쁜 상환 알고리즘은 피해야 한다.
Why실무 성능 사고의 상당수는 잘못된 알고리즘이 아니라 제약을 잘못 짚은 선택에서 나오고, 그 비용은 코드가 굳은 뒤에 드러난다.
IR은 소스 언어와 타깃 기계 사이에 두는 중간 표현으로, 최적화와 코드 생성 로직을 언어 수 곱하기 타깃 수가 아니라 언어 수 더하기 타깃 수로 줄이기 위한 계층이다. SSA는 모든 변수가 정확히 한 번만 정의되도록 이름을 재부여한 IR 형식이며, 제어 흐름이 합류하는 지점에서는 어느 선행 블록에서 왔는지에 따라 값을 고르는 phi 함수를 둔다.
How it works각 사용 지점이 유일한 정의를 가리키므로 def-use 관계가 표현 자체에 명시되고, 상수 전파·죽은 코드 제거·공통 부분식 제거 같은 최적화가 별도 자료 흐름 분석 없이도 단순해진다. phi를 어디에 넣을지는 지배 관계에서 나오는 dominance frontier로 계산하며, 레지스터 할당 직전에 phi를 복사 명령으로 풀어내는 out-of-SSA 단계를 거친다.
WhyLLVM, Go 컴파일러, 대부분의 JIT, 그리고 Solidity의 Yul 기반 IR 파이프라인까지 현대 최적화가 전부 SSA 위에서 돌아가므로, 어떤 코드가 왜 최적화되고 왜 안 되는지 읽으려면 SSA 사고가 필요하다.
데이터플로 분석은 프로그램의 제어흐름 그래프 위에서 각 지점에 성립하는 사실(fact)을 방정식으로 세우고, 격자(lattice) 위에서 고정점에 도달할 때까지 반복 계산하는 정적 분석 기법이다. 상수 전파는 각 변수에 '아직 모름 / 상수 c / 상수 아님'이라는 격자 값을 붙여 전방향으로 전파하고, 분기 합류점에서는 두 값의 meet를 취해 서로 다른 상수가 만나면 '상수 아님'으로 떨어뜨린다.
How it works죽은 코드 제거는 반대로 후방향 liveness 분석을 써서, 어떤 변수의 정의가 이후 어디서도 쓰이지 않고 부수효과도 없으면 그 정의를 삭제한다. 격자의 높이가 유한하고 전이 함수가 단조(monotone)이면 반복이 반드시 종료한다는 것이 이 방식의 정당성 근거다.
Why옵티마이저가 왜 어떤 코드는 지우고 어떤 코드는 남기는지, 특히 부수효과가 있는 연산 앞에서 최적화가 멈추는 이유를 이해해야 생성된 바이트코드나 기계어를 읽고 성능·가스 차이를 설명할 수 있다.
레지스터 할당은 무한한 가상 레지스터를 갖는 중간 표현을 실제 물리 레지스터 개수 k개에 사상하는 단계다. 동시에 살아 있는(live) 값들을 정점으로, 생존 구간이 겹치는 쌍을 간선으로 하는 간섭 그래프(interference graph)를 만들면 문제는 그래프 k-컬러링이 되고, 일반 그래프의 k-컬러링은 NP-완전이므로 Chaitin류의 휴리스틱(차수 < k인 정점을 스택에 밀어내고 되돌리며 색칠)을 쓴다.
How it works색칠에 실패한 값은 메모리로 내보내는 스필(spill)을 하며, 스필 비용은 보통 접근 횟수를 반복문 중첩 깊이로 가중한 값을 차수로 나눈 형태의 휴리스틱으로 추정한다. SSA 형태에서는 간섭 그래프가 chordal이라 최적 색칠이 다항 시간에 가능해, 현대 컴파일러는 SSA 기반 할당이나 JIT용 linear scan을 쓰기도 한다.
Why핫 루프에서 성능이 안 나오는 원인이 알고리즘이 아니라 레지스터 압박에 의한 스필/리로드인 경우가 흔하고, 이를 알아야 인라이닝이나 변수 생존 구간을 줄이는 식의 소스 수준 대응을 할 수 있다.
인라이닝은 함수 호출을 피호출 함수의 본문으로 치환하는 변환으로, 호출 오버헤드 제거 자체보다 호출 경계를 없애 상수 전파·죽은 코드 제거 같은 후속 최적화를 열어 주는 효과가 더 크다. 대신 코드 크기가 늘어 명령어 캐시 압박이 생기므로 컴파일러는 함수 크기와 호출 빈도 휴리스틱으로 인라인 여부를 결정한다.
How it works루프 변환에는 unrolling, 루프 불변식 끌어올리기(LICM), 루프 교환, 융합과 분할, 타일링이 있고 공통 목적은 데이터 의존성을 깨지 않으면서 지역성과 명령어 수준 병렬성을 높이는 것이다. 자동 벡터화는 반복 간 의존이 없는 루프를 SIMD 명령으로 묶는 변환인데, 포인터 앨리어싱 가능성, 불규칙한 제어 흐름, 부동소수점 결합법칙을 바꿔서는 안 된다는 제약 때문에 자주 실패한다.
Why핫 루프가 기대만큼 안 빨라지는 원인은 대개 알고리즘이 아니라 벡터화가 걸리지 않았거나 인라인이 막혀 후속 최적화가 전부 무산된 것이기 때문이다.
현대 VM은 모든 코드를 처음부터 최적화하지 않고 계층화(tiered) 전략을 쓴다. 처음에는 인터프리터나 빠르게 뱉는 베이스라인 컴파일러로 실행하면서 호출 횟수·루프 반복 수·타입 프로파일을 수집하고, 임계치를 넘은 hot 코드만 최적화 컴파일러로 다시 컴파일한다.
How it works최적화 단계는 프로파일을 근거로 "이 인자는 항상 정수다", "이 호출 대상은 항상 같은 함수다" 같은 가정을 세워 인라인·특수화하고, 그 가정을 검사하는 guard를 코드에 심는다. guard가 깨지면 역최적화(deopt)가 일어나 최적화 프레임의 상태를 인터프리터 프레임으로 되돌리고 느린 경로에서 실행을 이어간다.
Why워밍업을 무시한 마이크로벤치마크는 실제보다 훨씬 느리거나 빠른 값을 내놓아 잘못된 최적화 결정을 유도한다. 또 한 곳에서 다형적으로 쓰이는 객체 모양 하나 때문에 hot loop가 deopt에 빠져 처리량이 몇 배 떨어지는 일이 실제로 자주 생긴다.
스택 머신은 피연산자를 명시하지 않고 암묵적으로 스택 상단에서 꺼내 쓰는 구조라 명령어 인코딩이 짧고 컴파일러 백엔드가 단순하지만, 같은 계산을 하는 데 필요한 명령어 수가 많고 DUP·SWAP 같은 스택 정리 연산이 추가된다. 레지스터 머신은 피연산자를 이름으로 지정하므로 명령어 수가 적고 값의 재사용이 명시적이라 레지스터 할당·JIT 같은 최적화에 유리한 대신, 인코딩이 길고 명령어 집합이 복잡해진다.
How it worksEVM은 256비트 워드를 다루는 스택 머신이고 스택 깊이가 1024로 제한되며, 성능보다 명세의 단순함과 모든 노드에서의 결정론적 재현을 우선한 설계다. WebAssembly도 명세상으로는 스택 기반 검증 모델을 쓰지만, 함수 지역 변수와 구조화된 제어 흐름(블록·루프·분기 라벨)을 제공해 네이티브 레지스터 코드로 AOT/JIT 컴파일하기 쉽게 되어 있다.
WhyEVM 바이트코드를 읽거나 가스를 다투다 보면 스택 조작 오버헤드가 비용에 그대로 잡히고, 대안 VM 논의를 따라가려면 두 모델의 트레이드오프가 전제 지식이 된다. 컴파일러 출력이 왜 그렇게 생겼는지도 여기서 설명된다.
가스는 연산·상태 저장·대역폭 소비를 하나의 회계 단위로 정량화해 요금을 매기는 장치다. 각 opcode의 가스 값은 실제 자원 소비에 비례해야 하며, 저평가된 연산이 하나라도 있으면 그것이 곧 DoS 벡터가 된다(과거 이더리움에서 상태 접근·스토리지 비용이 여러 차례 재조정된 이유다).
How it works상태를 늘리는 쓰기는 비싸게, 상태를 지우는 연산은 환급을 주는 식으로 상태 증가에 대한 유인을 설계한다. EIP-2929처럼 같은 슬롯·주소의 첫 접근(cold)과 재접근(warm)을 다르게 과금하는 것은 캐시 지역성까지 요금 모델에 반영한 예다.
Why비용 모델이 실제 자원 소비와 어긋나면 공격자가 헐값에 노드를 마비시킬 수 있고, 반대로 과다 책정하면 정직한 사용자가 밀려난다.
EVM 인터프리터는 바이트코드를 프로그램 카운터로 한 옵코드씩 읽어 스택 머신으로 실행하는 루프다. JUMP와 JUMPI의 목적지는 반드시 JUMPDEST 옵코드여야 하고, PUSH 명령의 즉시 데이터(immediate data) 안에 우연히 같은 바이트값이 들어 있는 위치는 유효한 목적지가 아니다.
How it works그래서 구현체는 코드를 한 번 선형 스캔하며 PUSH의 데이터 길이만큼 건너뛰는 방식으로 유효 JUMPDEST 비트맵을 만들어 두고, 점프마다 O(1)로 검사한다. 메모리는 0에서 시작해 32바이트 워드 단위로만 확장되며, 확장 비용은 워드 수에 대해 선형 항과 2차 항의 합이라 크게 쓸수록 한계비용이 가파르게 오른다.
Why메모리 비용의 2차 항 때문에 큰 calldata 복사나 대형 배열 처리가 예상보다 훨씬 비싸지고, JUMPDEST 규칙을 모르면 어셈블리나 코드 검사 로직에서 잘못된 가정을 하게 된다.
WebAssembly는 스택 기반 가상 머신의 명령 집합으로, 제어 흐름이 임의 점프가 아니라 블록·루프·분기라는 구조적 형태로만 표현되어 검증기가 정적으로 타입과 흐름을 확인할 수 있다. 메모리는 선형 메모리라 불리는 하나의 연속된 바이트 배열이고 모든 접근이 경계 검사를 거치므로, 모듈은 자기 메모리 밖을 절대 읽거나 쓸 수 없다.
How it works호출 스택과 함수 주소는 엔진이 관리하며 간접 호출은 타입이 검사된 테이블 인덱스로만 가능해서, 전통적인 스택 스매싱이나 임의 코드 주소로의 점프가 원천적으로 막힌다. 모듈은 명시적으로 import한 호스트 함수 외에는 파일, 네트워크, 시계 등 바깥세상에 닿을 수 없으므로 샌드박싱 경계는 곧 import 목록이 된다.
Why신뢰할 수 없는 코드를 안전하게 실행해야 하는 플러그인 시스템, 엣지 런타임, 대체 스마트 컨트랙트 VM이 모두 이 모델 위에 서 있어서, 경계가 어디까지인지 정확히 알아야 위협 모델을 제대로 그릴 수 있다.
현대 GC는 "멈추고 전부 훑기"를 피하기 위해 작업을 잘게 쪼개거나(증분) 애플리케이션 스레드와 겹쳐서(병행) 수행한다. 병행 마킹은 마킹 중에 객체 그래프가 변하는 문제를 낳으므로, 쓰기 배리어로 변경을 기록해 삼색 불변식(검은 객체가 흰 객체를 직접 가리키지 않는다)을 유지한다.
How it works리전 기반 GC는 힙을 균일한 크기의 리전으로 나누고 회수 효율이 높은 리전만 골라 처리해, 전체 힙 크기와 정지 시간의 결합을 끊는다. ZGC는 컬러드 포인터와 로드 배리어를 써서 재배치(compaction)까지 병행으로 수행하고, Go의 GC는 비이동·비세대형 병행 마크스윕이며 GOGC 목표에 맞춰 마킹 속도를 조절하는 페이싱을 쓴다.
Why지연시간이 중요한 서버에서 GC는 코드가 아무리 빨라도 p99를 혼자 망칠 수 있는 요인이고, 튜닝 손잡이의 의미를 모르면 힙만 키우는 대증요법에 갇힌다.
Rust의 소유권은 모든 값에 유일한 소유자를 두고 소유자가 스코프를 벗어날 때 자원을 해제해, GC 없이 컴파일 타임에 메모리 안전을 보장하는 규칙이다. 차용 검사기는 여기에 aliasing과 mutation을 동시에 허용하지 않는 규칙을 더해, 같은 시점에 다수의 불변 참조 또는 단 하나의 가변 참조만 존재하도록 강제한다.
How it worksNLL(Non-Lexical Lifetimes)은 차용의 유효 구간을 렉시컬 스코프 끝까지가 아니라 제어 흐름 그래프상 그 참조가 마지막으로 쓰이는 지점까지로 계산해, 안전한데도 거부되던 코드를 통과시킨다. 그럼에도 검사기가 증명하지 못하는 구조(자기 참조, 순환 그래프, 공유 가변 상태)가 남고, 이때는 참조 대신 인덱스를 쓰는 arena 방식, Rc와 RefCell로 검사를 런타임으로 옮기는 방식, 필드별 분리 차용, 마지막 수단으로 unsafe를 안전한 API 뒤에 캡슐화하는 방식을 쓴다.
WhyRust로 노드, 인덱서, ZK 도구를 만들면 시간의 상당 부분이 로직이 아니라 차용 검사기와의 싸움에 들어가고, 우회 패턴을 알면 설계 단계에서 그 싸움 자체를 피할 수 있다.
범용 메모리 할당자는 임의 크기 요청을 빠르게 처리하면서 단편화를 억제해야 하는데, 이를 위해 크기를 몇십 개의 size class로 반올림해 같은 클래스끼리 모아 관리하는 segregated free list 구조를 쓴다. jemalloc은 스레드마다 arena를 배정하고 tcache라는 스레드 로컬 캐시를 두어 대부분의 할당·해제가 락 없이 끝나게 하며, 메모리는 큰 단위(chunk 또는 extent)로 OS에서 받아 잘라 쓴다.
How it worksmimalloc은 스레드마다 heap을, 페이지마다 free list를 두고 로컬 해제와 원격(다른 스레드에서의) 해제를 분리된 리스트로 처리해 원자 연산을 줄이는 free list sharding 아이디어를 쓴다. 두 설계가 공유하는 핵심은 스레드 로컬 캐싱으로 경합을 없애고, size class로 외부 단편화를 내부 단편화로 바꿔 관리 가능하게 만들고, 해제된 메모리를 OS에 돌려주는 시점(purge/decay)을 정책으로 다루는 것이다.
Why멀티스레드 서버에서 처리량이 코어 수에 비례해 늘지 않을 때 원인이 할당자 경합인 경우가 흔하고, RSS가 실제 사용량보다 훨씬 크게 유지되는 현상도 할당자의 단편화·반환 정책으로 설명된다.
ABI는 컴파일된 코드끼리 지켜야 하는 이진 수준 계약으로 호출 규약(인자 전달 레지스터, 스택 정렬, 반환값 위치), 구조체 레이아웃과 패딩, 이름 맹글링 등을 규정한다. FFI는 서로 다른 언어가 이 ABI를 매개로 호출하는 방식이며, 보통 C ABI를 공통분모로 삼기 때문에 구조체에 명시적 C 레이아웃 지정이 필요하다.
How it works안전성 문제는 세 축에서 생긴다. 첫째, 패닉이나 예외가 FFI 경계를 넘어 되감기(unwind)하면 상대 언어의 런타임이 이를 처리할 수 없어 정의되지 않은 동작이 되므로 경계에서 잡아 에러 코드로 변환해야 한다.
Why암호 라이브러리나 DB 엔진을 네이티브로 붙일 때 대부분의 크래시는 로직이 아니라 이 경계 규약(패닉 누출, GC 이동, 해제 책임 불명확)에서 나온다.
결정론적 실행은 같은 입력과 같은 초기 상태에서 언제나 같은 출력과 같은 상태 전이를 얻는 성질이다. 이를 깨뜨리는 대표 요인은 부동소수점(연산 순서, 확장 정밀도, FMA, 라이브러리 구현 차이), 현재 시각과 타임아웃, 난수, 스레드 스케줄링, 해시맵 순회 순서, 그리고 파일·네트워크 같은 외부 입출력이다.
How it works봉인하는 방법은 이 비결정성 원천을 전부 주입 가능한 입력으로 바꾸는 것으로, 부동소수점 대신 정수·고정소수점 산술을 쓰고, 시각과 난수 시드는 인자로 받아 기록하며, 순회 순서는 명시적 정렬로 고정한다. 이렇게 하면 리플레이 검증, 재현 가능한 테스트, 상태 머신 복제가 모두 성립한다.
Why재현되지 않는 간헐 버그의 상당수가 시각·난수·순회 순서 같은 숨은 비결정성에서 오고, 리플레이 디버깅과 복제 실행은 결정론 위에서만 가능하기 때문이다.
형식 검증은 테스트처럼 몇 개 입력을 시험하는 대신, 명시한 성질이 정의된 입력 공간 전체에서 성립하는지를 논리적으로 판정한다. 바닥에는 명제 논리의 충족 가능성을 푸는 SAT 솔버(CDCL 기반)와 불리언 함수를 변수 순서에 대해 정규형으로 표현하는 BDD가 있고, 그 위에 비트벡터·배열·산술 같은 이론을 얹어 판정하는 SMT 솔버가 있다.
How it works심볼릭 실행은 프로그램을 구체적 값 대신 심볼로 실행하며 분기마다 경로 조건을 모으고, 그 조건과 성질의 부정을 SMT에 던져 반례를 찾는다. 실무 도구는 성격이 다른데, Foundry의 invariant 테스트는 상태를 가진 랜덤 퍼징이라 반례를 찾으면 확실하지만 못 찾았다고 증명이 되진 않고, Halmos 같은 심볼릭 실행 도구는 루프 전개 깊이 등으로 제한된 범위 안에서 증명을 준다.
Why스마트 컨트랙트는 배포 후 수정이 어렵고 실패 비용이 자금 손실이라, 단위 테스트가 커버하지 못하는 상태 공간을 성질 단위로 막아야 한다. 동시에 도구가 주는 보장의 범위를 오해하면 "검증했다"는 잘못된 안심을 사게 된다.
실행 계층은 소스 코드가 실제 하드웨어 동작이 되기까지의 단계 사슬로 볼 수 있다. 앞단은 렉싱·파싱으로 AST를 만들고 의미 분석으로 타입과 이름을 확정하는 프론트엔드이고, 가운데는 SSA 같은 중간 표현 위에서 상수 전파·인라이닝·죽은 코드 제거 등을 수행하는 최적화 단계다.
How it works뒷단은 명령어 선택·레지스터 할당·코드 생성으로 타깃 명령어(네이티브 기계어 또는 VM 바이트코드)를 뽑고, 그 결과를 인터프리터나 JIT가 실행하며 런타임이 메모리·GC·예외를 관리한다. 이더리움에 대응시키면 Solidity가 Yul 같은 IR을 거쳐 EVM 바이트코드가 되고, 클라이언트의 EVM 인터프리터가 이를 실행하면서 각 opcode마다 가스를 차감하는 구조다.
Why성능이나 동작 이상을 만났을 때 소스, 컴파일러 최적화, VM 실행, 런타임 중 어디를 봐야 하는지 즉시 좁히지 못하면 디버깅이 추측으로 흐른다. 계층 지도는 그 좁히기의 기준선이다.
CPU와 컴파일러는 단일 스레드 의미가 보존되는 한 메모리 접근을 자유롭게 재배열하므로, 다른 스레드에 무엇이 어떤 순서로 보이는지는 메모리 모델이 규정한다. relaxed 원자 연산은 연산 자체의 원자성만 보장하고 주변 접근과의 순서는 보장하지 않는다.
How it worksrelease 저장과 그 값을 읽은 acquire 로드가 짝을 이루면 release 이전의 모든 쓰기가 acquire 이후 코드에 보이는 happens-before 관계가 성립한다. seq_cst는 여기에 더해 모든 seq_cst 연산에 대한 단일 전역 순서를 보장하며 가장 비싸다.
Why순서 지정을 잘못해도 x86에서는 대개 통과하고 ARM처럼 약한 메모리 모델이나 고부하에서만 드러나서, 재현이 극도로 어려운 버그가 된다.
논블로킹 알고리즘은 진행 보장의 강도로 나뉜다. lock-free는 어떤 스레드가 멈춰도 시스템 전체로는 누군가 반드시 전진함을 보장하고, wait-free는 모든 스레드가 유한한 단계 안에 자기 연산을 끝냄을 보장하며, obstruction-free는 경합이 사라지면 끝남만 보장한다.
How it works대부분 CAS 같은 원자적 read-modify-write 위에 만들어지는데, 여기서 ABA 문제가 생긴다. 어떤 위치의 값이 A에서 B로 바뀌었다가 다시 A가 되면 CAS는 '변한 적 없다'고 착각해 성공하지만 실제 자료구조 상태는 달라져 있을 수 있다.
Why락프리 큐나 맵을 직접 쓰거나 만들 때 ABA와 메모리 회수를 빠뜨리면 재현이 극히 어려운 use-after-free와 데이터 손상이 프로덕션에서만 터진다.
RCU는 읽기가 압도적으로 많은 자료구조에서 읽기 측이 락이나 원자적 쓰기 없이 데이터를 참조하도록 만드는 동기화 기법이다. 갱신자는 기존 노드를 제자리에서 고치는 대신 복사본을 만들어 수정한 뒤 포인터를 한 번의 원자적 발행으로 교체하므로, 독자는 항상 낡은 버전이거나 새 버전이거나 둘 중 하나의 일관된 상태만 본다.
How it works발행 시점에는 새 노드의 초기화가 포인터 교체보다 먼저 보이도록 메모리 순서 보장이 필요하다. 낡은 버전을 즉시 해제하면 아직 그것을 읽고 있는 독자가 깨지므로, 모든 기존 독자가 임계 구역을 빠져나갔음이 보장되는 시점인 유예 기간이 지난 뒤에 회수한다.
Why읽기 대 쓰기 비율이 크게 치우친 라우팅 테이블, 설정 스냅샷, 심볼 테이블에서 뮤텍스나 RW락은 캐시 라인 경합만으로 확장성을 무너뜨리고, RCU 계열 기법이 그 병목을 없앤다.
CPU는 메모리를 캐시라인 단위(보통 64바이트)로 주고받으므로, 논리적으로 무관한 두 변수라도 같은 라인에 있으면 서로 다른 코어의 쓰기가 그 라인의 소유권을 계속 뺏고 뺏기는 상태가 된다. 이것이 false sharing이며, 락도 없고 데이터 경쟁도 없는데 처리량만 급락하는 형태로 나타난다.
How it works해결책은 코어별로 갱신되는 카운터나 상태를 캐시라인 경계에 정렬하고 패딩으로 분리하는 것이다. NUMA 시스템에서는 한 걸음 더 나아가, 메모리가 어느 소켓에 붙어 있느냐에 따라 접근 지연과 대역폭이 달라지므로 스레드와 그 스레드가 만지는 데이터를 같은 노드에 두는 지역성이 중요해진다.
Why코어를 늘렸는데 처리량이 오히려 떨어지는 전형적 원인이고, 프로파일러의 함수별 시간만 봐서는 원인이 보이지 않는다.
현대 CPU는 파이프라인을 비우지 않으려고 분기의 방향과 목적지를 예측하며, 예측이 틀리면 잘못 진행한 명령을 버리고 다시 채우는 데 상당한 사이클을 낭비한다. 하드웨어 프리페처는 순차 접근이나 일정한 stride 패턴을 감지해 캐시 라인을 미리 가져오므로, 예측 가능한 접근은 포인터를 따라가는 접근보다 훨씬 빠르다.
How it works데이터 지향 설계는 이 하드웨어 특성에 맞춰 자료 배치를 바꾸는 방법론으로, 객체 배열(AoS) 대신 필드별 배열(SoA)을 쓰거나 함께 접근되는 필드를 모아 가져온 캐시 라인에서 실제로 쓰는 바이트 비율을 높인다. 분기 자체를 없애는 기법(조건부 이동, 분기 없는 계산, 입력 정렬)도 같은 맥락에 있다.
Why복잡도가 동일한데 실측이 몇 배 차이 나는 경우 원인은 대개 캐시 미스와 분기 오예측이며, 이걸 모르면 핫 루프 최적화의 방향을 처음부터 잘못 잡는다.
전통적인 소켓 I/O는 시스템 콜마다 유저-커널 경계를 넘고 커널 버퍼와 유저 버퍼 사이에서 데이터를 복사하므로, 작은 요청이 매우 많은 워크로드에서는 이 오버헤드가 전체 비용을 지배한다. zero-copy는 그 복사를 제거하거나 줄이는 기법으로, 파일 전송의 sendfile이나 splice처럼 데이터가 유저 공간을 거치지 않게 하는 방식이 대표적이다.
How it worksio_uring은 커널과 유저 공간이 공유하는 두 개의 링 버퍼(제출 큐와 완료 큐)를 두어 요청을 큐에 써 넣고 완료를 큐에서 읽는 비동기 인터페이스이며, 여러 요청을 한 번의 시스템 콜로 제출하거나 폴링 모드에서는 시스템 콜 없이도 진행시킬 수 있다. 커널 바이패스는 한 걸음 더 나아가 NIC 큐를 유저 공간 드라이버에 직접 매핑해 커널 네트워크 스택 자체를 건너뛰는 접근으로, 지연은 크게 줄지만 커널이 제공하던 프로토콜 처리와 보호를 애플리케이션이 떠안게 된다.
Why지연이 마이크로초 단위로 중요한 매칭 엔진이나 초고빈도 RPC 게이트웨이에서는 애플리케이션 로직이 아니라 시스템 콜·복사 비용이 병목이 되므로, 어디까지가 커널 비용인지 구분할 줄 알아야 한다.
세 모델은 동시성을 어떤 단위로 쪼개고 상태를 어떻게 공유하느냐가 다르다. 이벤트 루프는 단일 스레드가 준비된 I/O 이벤트를 논블로킹으로 순회하며 콜백/태스크를 실행하므로 컨텍스트 스위치와 락이 거의 없지만, 하나의 CPU 바운드 작업이 루프를 막으면 전체가 멈춘다.
How it works스레드 모델은 OS가 선점 스케줄링을 해주어 블로킹 코드를 그대로 쓸 수 있고 멀티코어를 자연히 활용하지만, 공유 메모리를 락으로 지켜야 해서 경합·데드락·false sharing 같은 비용이 생긴다. 액터 모델은 상태를 액터 내부에 가두고 오직 비동기 메시지로만 통신하게 해 공유 메모리 자체를 없애며, 대신 메시지 복사 비용과 메일박스 backpressure, 순서 보장 범위가 설계 이슈가 된다.
Why동시성 버그와 지연 스파이크의 상당수는 선택한 모델의 전제(루프를 막지 마라, 공유 상태를 락으로 지켜라, 메일박스가 무한하지 않다)를 깨는 데서 나온다.
큐 이론은 도착 과정과 서비스 과정을 확률적으로 모델링해 대기 길이와 지연을 예측하는 도구다. Little's law는 안정 상태에서 L = λW, 즉 시스템 안의 평균 항목 수가 평균 도착률과 평균 체류시간의 곱과 같다는 관계이며 분포에 대한 가정 없이 성립한다는 점이 강력하다.
How it works이용률 ρ가 1에 가까워지면 대기시간은 대략 1/(1-ρ)에 비례해 급격히 커지므로, 시스템은 이용률 100%가 아니라 여유를 남긴 지점에서 운영해야 한다. 백프레셔는 소비자가 감당하지 못하는 유입을 생산자 쪽으로 되밀어 큐가 무한히 자라는 것을 막는 기법으로, 유계 큐, 블로킹, 크레딧 기반 흐름 제어, 부하 차단으로 구현한다.
Why부하가 몰릴 때 서비스가 무너지는 경로는 대부분 큐가 무한히 커지며 지연이 타임아웃을 넘고 재시도가 폭증하는 형태이고, 이 지점은 용량 계산으로 미리 막을 수 있기 때문이다.
테일 레이턴시는 평균이 아니라 p99·p999처럼 분포 꼬리에 있는 응답 시간을 말한다. 한 요청이 여러 백엔드로 fan-out되면 전체 응답은 가장 느린 하나에 묶이므로, 개별 서버의 드문 지연이 상위 레벨에서는 흔한 지연으로 증폭된다.
How it workshedged request는 첫 요청이 예컨대 p95를 넘겨도 응답이 없을 때 다른 복제본에 같은 요청을 하나 더 보내고 먼저 오는 응답을 쓰는 기법으로, 추가 부하는 몇 퍼센트인데 꼬리는 크게 줄어든다. load shedding은 반대 방향으로, 용량을 넘는 요청을 큐에 쌓지 않고 입구에서 빨리 거절해 이미 받아들인 요청의 지연 목표를 지키는 전략이다.
Why평균 응답 시간만 보는 대시보드는 사용자 체감 실패를 통째로 놓치고, 과부하 때 무한정 큐잉하는 서비스는 재시도까지 겹쳐 붕괴한다. 꼬리 관리와 부하 차단은 가용성 설계의 기본기다.
프로파일링은 크게 코드에 훅을 심는 계측(instrumentation)과 주기적으로 실행 상태를 표본화하는 샘플링으로 나뉘고, perf는 커널의 perf_events를 통해 타이머나 PMU 이벤트 오버플로 시점에 인터럽트를 걸어 콜스택을 수집하는 샘플링 도구다. 플레임그래프는 수집된 스택들을 동일 접두사끼리 접어(fold) 그린 그림으로, y축은 스택 깊이이고 x축 너비는 그 스택이 표본에서 차지한 비율일 뿐 시간 축이 아니다.
How it works따라서 넓은 프레임은 '오래 걸린 구간'이 아니라 '표본에서 자주 잡힌, 즉 CPU를 많이 점유한 코드'로 읽어야 한다. PMU는 CPU 내장 하드웨어 카운터로 cycles, instructions, cache-misses, branch-misses 같은 이벤트를 세며, 이로부터 IPC를 계산해 병목이 명령어 공급 쪽인지 메모리 접근 쪽인지 분기 예측 실패 쪽인지 구분할 수 있다.
Why추측으로 최적화하면 대개 엉뚱한 곳을 고치게 되고, 특히 CPU 바운드와 메모리 바운드는 해법이 완전히 다르다. 카운터와 플레임그래프는 그 구분을 데이터로 강제한다.
벤치마크는 하나의 수치를 재는 일이 아니라 측정값의 분포를 추정하는 실험이다. JIT 컴파일, 캐시, 분기 예측기, 커넥션 풀 때문에 초기 실행은 정상 상태와 다르므로 워밍업 구간을 측정에서 제외해야 한다.
How it works사용자 체감은 평균보다 중앙값과 꼬리 분위수(p95, p99)에 가깝고, 반복 실행 간 분산을 함께 보고해야 두 버전의 비교가 성립한다. 회귀 감지는 기준선 대비 차이가 노이즈 범위를 넘는지의 판단이므로, 공유 CI처럼 흔들리는 환경에서는 임계값을 넉넉히 잡거나 같은 실행 안에서의 상대 비교를 쓴다.
Why워밍업과 분산을 무시한 벤치마크는 실제 성능 회귀를 통과시키고 무해한 변경을 회귀로 오탐해서, 결국 아무도 결과를 믿지 않게 된다.
eBPF는 커널 안에서 안전하게 실행되는 샌드박스 VM이다. 사용자가 작성한 작은 프로그램을 커널에 로드하면 verifier가 종료성과 메모리 접근 안전성을 정적으로 검증하고, 통과한 프로그램만 JIT 컴파일되어 kprobe, uprobe, tracepoint, perf 이벤트, 네트워크 훅 등에 붙어 실행된다.
How it works프로그램과 유저스페이스는 map이라는 공유 자료구조(해시맵, 배열, 링버퍼 등)로 데이터를 주고받는다. 커널 모듈을 새로 짜거나 애플리케이션을 재시작·재컴파일하지 않고도 실행 중인 시스템의 내부 이벤트를 관측할 수 있다는 것이 핵심 이점이다.
Why프로덕션에서 재현되지 않는 지연 스파이크나 특정 syscall 병목을 코드 수정·재배포 없이, 그리고 애플리케이션 로그에 없는 계층까지 내려가 볼 수 있는 거의 유일한 수단이다.
분산 트레이싱은 하나의 요청이 여러 서비스를 지나가는 경로를 트레이스라는 단위로 묶고, 각 작업 구간을 부모-자식 관계를 가진 스팬으로 기록하는 관측 기법이다. 서로 다른 프로세스에서 같은 트레이스로 묶이려면 트레이스 식별자와 부모 스팬 식별자를 요청 헤더에 실어 전파해야 하며, 이 전파 규약이 표준화되어 있어야 이종 시스템이 이어진다.
How it works모든 요청을 저장하면 비용이 감당되지 않으므로 샘플링이 필요한데, 헤드 기반 샘플링은 트레이스 시작 시점에 확률적으로 결정을 내리고 그 결정을 하위로 전파해 트레이스가 조각나지 않게 한다. 테일 기반 샘플링은 트레이스가 끝난 뒤 전체를 보고 판단하므로 에러나 느린 요청을 선별해 남길 수 있지만, 완성될 때까지 버퍼링해야 해서 메모리와 구조적 복잡도를 요구한다.
Why장애는 대개 평균이 아니라 꼬리에서 발생하는데, 순수 확률 샘플링만 쓰면 정작 필요한 느린 요청과 실패 요청의 트레이스가 남지 않아 사후 분석이 불가능해진다.
SLO는 사용자 관점의 서비스 수준 지표(SLI)에 대해 정한 목표치이고, 에러 예산은 그 목표가 허용하는 실패의 총량이다. 1%가 한 기간 동안 쓸 수 있는 예산이며, 이 예산은 배포 속도와 안정성 사이의 명시적 교환 수단이 된다.
How it works예산이 남으면 더 공격적으로 배포하고, 소진되면 기능 출시를 멈추고 신뢰성 작업에 투입하는 식의 정책으로 운영한다. 용량 계획은 여기에 부하 예측을 결합해, 목표 지연시간을 유지한 채 소화 가능한 최대 부하와 필요한 여유분을 정하는 작업이다.
Why"얼마나 안정적이어야 하는가"를 숫자로 합의해 두지 않으면 장애 대응과 기능 개발의 우선순위 다툼이 매번 감정 싸움이 된다.
카오스 엔지니어링은 운영과 유사한 환경에 통제된 장애를 의도적으로 주입해, 시스템이 정상 동작을 유지한다는 가설을 실험으로 검증하는 방법론이다. 절차는 관측 가능한 지표로 정상 상태(steady state)를 정의하고, 특정 장애 하에서도 그 지표가 유지된다는 가설을 세우고, 실제 장애(인스턴스 종료, 지연 추가, 패킷 손실, 의존 서비스 오류 응답)를 주입한 뒤 가설이 깨지는지 관찰하는 순서다.
How it works핵심 원칙은 폭발 반경을 작게 시작해 점진적으로 넓히고, 실험을 즉시 중단할 abort 조건을 미리 정해두는 것이다. 목적은 장애를 만드는 것이 아니라 이미 잠재해 있던 결함(타임아웃 미설정, 재시도 폭주, 순환 의존, 잘못된 폴백)을 통제된 시간에 드러내는 데 있다.
Why분산 시스템의 실제 장애는 개별 컴포넌트보다 그 사이의 타임아웃·재시도·폴백 조합에서 나오고, 이런 상호작용은 단위 테스트로 절대 잡히지 않는다.
성능 예산 문서는 시스템이 지켜야 할 성능 목표를 숫자와 조건으로 명시해 설계·리뷰·배포 판단의 기준으로 삼는 문서다. 최소한 대상 워크로드(요청 종류와 비율), 부하 수준(초당 요청 수, 동시성), 지표와 목표치(평균이 아니라 p95·p99 같은 꼬리 지연, 처리량, 자원 사용량), 측정 방법과 환경이 들어가야 재현 가능한 기준이 된다.
How it works예산은 전체 목표를 구간별로 쪼개 배분할 때 실효성이 커지는데, 예를 들어 종단 지연 목표를 네트워크·큐 대기·핸들러·DB 호출로 나누어 각 구간의 상한을 정하면 어느 구간이 예산을 초과했는지 바로 드러난다. 목표치는 근거 있게 정해야 하며, 사용자 체감이나 상류 시스템의 타임아웃처럼 외부 제약에서 역산하는 것이 임의로 정한 숫자보다 방어 가능하다.
Why성능은 목표가 문서화되어 있지 않으면 '느리다/빠르다'는 주관적 논쟁이 되고, 회귀가 누적된 뒤에야 발견되어 원인 추적이 어려워진다.
일관성 모델은 동시 접근이 있을 때 시스템이 어떤 실행 순서까지 허용하는지를 정하는 계약이다. 선형화 가능성(linearizability)은 단일 객체에 대한 개별 연산이, 각자의 호출과 응답 사이 어느 시점에 원자적으로 일어난 것처럼 보이고 그 순서가 실시간 순서를 존중할 것을 요구한다.
How it works직렬성(serializability)은 다중 객체 트랜잭션에 대한 성질로, 동시 실행 결과가 어떤 순차 실행과 같기만 하면 되고 실시간 순서는 요구하지 않는다. 인과 일관성(causal)은 인과적으로 선행하는 쓰기들만 순서를 보장하고 동시(concurrent) 쓰기는 노드마다 다른 순서로 봐도 되며, 최종 일관성(eventual)은 새 갱신이 멈추면 언젠가 복제본이 수렴한다는 것만 약속한다.
Why"읽었는데 방금 쓴 값이 없다" 류의 버그는 대개 시스템이 약속한 모델을 실제보다 강하게 가정한 결과이고, 반대로 필요 이상으로 강한 모델을 고르면 지연과 비용을 그냥 낭비한다.
분산 환경에서는 완전히 동기화된 전역 물리 시계를 가정할 수 없으므로 사건의 순서를 인과관계로 정의한다. Lamport 논리 시계는 각 노드가 카운터를 유지해 로컬 이벤트마다 증가시키고 메시지 수신 시 max(내 값, 받은 값)+1로 갱신하며, a가 b의 원인이면 C(a) < C(b)를 보장하지만 역은 성립하지 않아 동시성을 구분하지 못한다.
How it works벡터 시계는 노드 수만큼의 카운터 배열을 들고 다녀 두 사건이 인과적으로 앞뒤인지 아니면 동시(concurrent)인지를 정확히 판별하지만, 메타데이터 크기가 노드 수에 비례해 확장성이 떨어진다. 하이브리드 논리 시계(HLC)는 물리 시각과 논리 카운터를 한 값으로 결합해, 인과성을 어기지 않으면서도 물리 시각에 가깝게 유지되는 단조 증가 타임스탬프를 만든다.
Why여러 노드의 로그를 물리 시각으로 정렬하면 원인과 결과가 뒤집혀 보이고, 동시 갱신 충돌을 탐지할지 말지도 결국 어떤 시계를 쓰느냐에서 갈리기 때문이다.
Raft의 기본 골격은 리더 선출과 로그 복제지만, 실운영에서 어려운 부분은 그 바깥의 세 가지다. 멤버십 변경은 옛 구성과 새 구성이 동시에 서로 다른 과반을 만들어 두 리더가 생기는 상황을 막아야 하므로, 두 구성의 과반을 동시에 요구하는 joint consensus를 거치거나 한 번에 한 노드만 더하고 빼는 방식으로 제한한다.
How it works로그 압축은 로그가 무한히 자라는 것을 막기 위해 상태 머신을 스냅샷으로 저장하고 그 이전 로그를 버리는 것이며, 뒤처진 팔로워에게는 로그 대신 스냅샷을 통째로 전송하는 별도 RPC가 필요하다. 읽기 보장은 리더가 자신이 아직 리더인지 모른 채 옛 상태를 반환할 수 있다는 문제에서 온다.
Why논문 수준의 Raft만 구현하고 운영에 들어가면 노드 교체 중 스플릿 브레인, 무한히 커지는 로그, 리더 교체 직후의 stale read가 차례로 터진다. 이 세 가지가 실제 장애의 대부분이다.
기본 Paxos는 하나의 값을 합의하는 데 prepare와 accept 두 단계를 거치며, 각 단계마다 과반 정족수의 응답이 필요하다. Multi-Paxos는 연속된 여러 인스턴스를 합의할 때 안정적인 리더가 prepare 단계를 인스턴스마다 반복하지 않고 한 번에 미리 확보해 두어, 정상 상태에서는 accept 한 라운드만으로 값을 확정한다.
How it works전통적으로는 모든 정족수가 서로 교차해야 한다고 여겨졌지만, Flexible Paxos는 안전성에 실제로 필요한 조건이 1단계 정족수와 2단계 정족수가 교차하는 것뿐임을 보였다. 즉 |Q1| + |Q2| > N만 만족하면 되고, Q1끼리 또는 Q2끼리는 교차하지 않아도 된다.
Why합의 시스템의 지연과 장애 내성은 대부분 정족수 크기 선택에서 결정되는데, '무조건 과반'이라는 통념만 갖고 있으면 그 조정 여지를 놓친다. 리더 기반 프로토콜의 정상 경로가 왜 1 RTT인지도 여기서 나온다.
부분 동기 환경에서 f개의 비잔틴 노드를 견디려면 전체 노드 수가 3f+1 이상이어야 하고, 정족수를 2f+1로 잡으면 임의의 두 정족수가 최소 f+1개 노드에서 겹친다. 그 교집합에는 정직한 노드가 반드시 하나 이상 포함되므로, 서로 상충하는 두 값이 동시에 확정될 수 없다는 안전성이 나온다.
How it worksPBFT는 pre-prepare, prepare, commit 3단계로 합의를 이루지만 뷰 체인지 비용이 노드 수에 대해 크게 증가한다. HotStuff는 투표를 임계 서명으로 집계하고 리더를 통해 중계해 통신량을 선형으로 줄이고, 연속된 체인 규칙으로 뷰 체인지를 단순화했다.
Why지분증명 체인, 롤업 시퀀서, 사이드 인프라가 모두 이 계열이라 완결성이 어떤 가정 위에서 보장되는지, 리더가 죽었을 때 진행성이 어떻게 회복되는지를 알아야 장애를 해석할 수 있다.
DAG 기반 합의는 '데이터를 퍼뜨리는 일'과 '순서를 정하는 일'을 분리한다. Narwhal은 멤풀 계층으로, 각 검증자가 트랜잭션 배치를 만들고 다른 검증자들의 서명(가용성 증명)을 모아 이전 라운드 배치들을 참조하는 정점을 만들며, 그 결과 모든 검증자가 거의 같은 DAG를 갖게 된다.
How it works이 DAG는 이미 데이터가 전파·저장되었음을 보장하므로, 합의 계층은 실제 트랜잭션이 아니라 DAG의 메타데이터만 다루면 된다. Bullshark 같은 순서화 프로토콜은 추가 메시지를 거의 주고받지 않고, 각 검증자가 자기 로컬 DAG를 정해진 규칙으로 해석해 결정적으로 같은 전체 순서를 뽑아낸다.
Why리더 하나가 모든 트랜잭션을 브로드캐스트하는 고전 BFT는 리더의 대역폭이 곧 시스템 처리량 상한이 되는데, 이 분리 구조가 그 병목을 어떻게 푸는지가 최신 고성능 체인 설계의 핵심 아이디어다.
나카모토 합의는 작업증명으로 블록을 생성하고 가장 누적 작업량이 큰 체인을 정본으로 삼는 규칙이며, 여기서 최종성은 절대적이지 않고 확률적이다. 어떤 블록 위에 정직한 블록이 더 쌓일수록 공격자가 그 블록을 되돌리기 위해 따라잡아야 할 격차가 커지므로, 되돌림 확률은 확인 수가 늘어남에 따라 지수적으로 감소한다.
How it works이 보장은 공격자의 해시파워가 정직한 쪽보다 작다는 가정과 네트워크 전파가 충분히 빠르다는 가정 위에서만 성립한다. selfish mining은 채굴한 블록을 즉시 공개하지 않고 비밀 체인을 유지하다가 정직한 블록이 나오면 전략적으로 공개해, 정직한 채굴자들의 작업을 무효화시키는 전략이다.
Why몇 확인을 기다려야 하는가는 안전 파라미터를 돈으로 환산하는 결정이며, 인센티브 공격이 존재한다는 사실은 다수 정직 가정만으로 시스템을 정당화할 수 없음을 뜻한다.
이더리움의 합의는 두 요소로 나뉘는데, LMD-GHOST는 어느 체인을 따를지 고르는 포크 선택 규칙이고 Casper FFG는 그 위에서 최종성을 부여하는 규칙이다. LMD-GHOST는 각 검증자의 가장 최근 투표만 세어 가중치가 가장 큰 서브트리를 따라 내려가며 헤드를 정한다.
How it worksCasper FFG는 에포크 경계의 체크포인트를 대상으로 투표하며, 스테이크의 3분의 2 이상이 어떤 링크를 지지하면 그 체크포인트가 justified 되고, 연속된 justification이 성립하면 finalized 된다. 재조직은 아직 finalize되지 않은 구간에서만 자연스럽게 일어나며, 네트워크 지연·검증자 이탈·투표 타이밍 때문에 다수 가중치가 늦게 드러날 때 발생한다.
Why"몇 블록 기다려야 안전한가"라는 질문의 답이 여기서 나오고, 확정 전 데이터를 확정된 것처럼 다루면 reorg 때 상태가 어긋난다.
이더리움의 파이널리티는 현재 여러 슬롯에 걸친 에폭 단위 투표 누적으로 확정되므로, 블록이 포함된 뒤 최종 확정까지 수 분 수준의 시간이 걸린다. 싱글슬롯 파이널리티(SSF)는 한 슬롯 안에서 전체 검증자 집합의 투표를 모아 그 슬롯의 블록을 즉시 확정하려는 연구 방향이다.
How it works병목은 합의 규칙 자체보다 시스템 공학 쪽에 있는데, 검증자 수가 매우 많을 때 슬롯 시간 안에 모든 서명을 수집·집계·검증하고 전파해야 하기 때문이다. BLS 서명은 다수를 하나로 집계할 수 있지만, 집계 트리를 통과하는 네트워크 전파와 누가 참여했는지를 나타내는 비트필드 처리 비용이 그대로 남는다.
Why파이널리티 지연은 브리지 확정, 거래소 입금 인정, 온체인 정산의 안전 기준을 직접 결정하는 값이라 서비스 설계에 그대로 반영된다.
Reed-Solomon 부호는 k개의 데이터 심볼을 다항식의 계수(또는 평가값)로 보고 서로 다른 n개의 점에서 평가해 n개의 심볼을 만드는 소거부호로, 차수 k-1 다항식은 서로 다른 k개의 점으로 유일하게 복원되므로 임의의 k개 조각만 있으면 원본을 되살릴 수 있다. 데이터 가용성 문제는 블록 생산자가 데이터를 실제로 공개했는지를 전체를 내려받지 않고 확인해야 한다는 데서 생기며, 소거부호로 확장해 두면 '데이터를 감추려면 최소한 상당 비율의 조각을 감춰야 한다'는 성질이 만들어진다.
How it works데이터 가용성 샘플링(DAS)은 이 성질을 이용해 각 라이트 노드가 무작위 위치의 조각 몇 개를 요청하고 모두 받으면 통과시키는 방식이며, 숨겨진 조각의 비율이 일정 이상이므로 샘플 수를 늘리면 감지 실패 확률이 지수적으로 줄어든다. 여기에 각 조각이 약속된 데이터와 일치하는지 검증하는 수단(예: KZG 같은 다항식 약속 또는 사기 증명)이 함께 필요하며, 그렇지 않으면 생산자가 잘못 부호화한 조각을 낼 수 있다.
Why롤업의 안전성은 결국 '데이터가 공개되었는가'에 달려 있고, 라이트 클라이언트가 풀 노드 없이도 이를 확률적으로 검증할 수 있게 해 주는 것이 DAS이므로 L2 위 서비스의 신뢰 가정을 이해하려면 필수다.
라이트 클라이언트는 전체 블록과 상태를 보관·실행하지 않고, 블록 헤더 체인만 따라가면서 특정 사실을 Merkle 증명으로 검증하는 노드다. 헤더의 상태 루트를 신뢰의 앵커로 삼아, 어떤 계정 잔액이나 스토리지 값이 그 루트에 포함된다는 포함 증명을 받아 로컬에서 해시로 재계산해 확인한다.
How it works여기서 헤더 자체의 정당성은 합의 계층에서 얻어야 하며, PoS 체인에서는 검증자 서명 집합에 대한 경량 증명을 통해 헤더를 따라간다. 상태 없는(stateless) 검증은 여기서 한 걸음 더 나아가, 블록 실행에 필요한 상태 조각과 그 증명을 witness로 블록과 함께 받아 상태 DB 없이도 블록을 재실행·검증하는 방식이다.
Why모바일·브라우저·크로스체인 브리지처럼 풀노드를 돌릴 수 없는 환경에서 신뢰 가정을 최소화하려면 라이트 클라이언트 검증이 유일한 현실적 수단이다.
크로스체인 시스템은 상대 체인에서 일어난 사실을 무엇을 근거로 믿는지에 따라 분류된다. 외부 검증형 브릿지는 멀티시그나 별도 검증자 집합의 증언에 의존하므로 신뢰 근거가 그 집합의 정직성과 키 관리에 있고, 그래서 대형 탈취 사고의 단골 표적이 되어 왔다.
How it works라이트클라이언트 방식은 상대 체인의 합의 규칙을 직접 검증해 상대 체인의 합의 안전성 외에 추가 신뢰를 요구하지 않지만, 구현 복잡도와 온체인 검증 비용이 크고 이를 줄이기 위해 ZK 증명을 쓰는 방향이 활발하다. 인텐트·솔버 기반은 사용자가 원하는 결과만 선언하고 솔버가 자기 자금으로 먼저 채워 준 뒤 나중에 정산에서 회수하는 구조라, 신뢰 가정이 메시지 전달의 진위에서 솔버의 담보와 정산·분쟁 절차로 옮겨간다.
Why체인 간 자산이나 데이터를 붙일 때 실제 위험은 코드 버그보다 이 다리가 결국 누구를 믿는 구조인가에서 나오고, 그 신뢰 가정이 서비스 전체의 최악 손실 범위를 정하기 때문이다.
대부분의 롤업은 트랜잭션 순서를 정하는 시퀀서를 단일 주체가 운영한다. 이 구조는 빠른 확정감과 낮은 지연을 주지만, 그 주체가 특정 사용자의 트랜잭션을 배제하거나 멈추면 사용자가 체인을 쓸 수 없다는 검열·가용성 위험을 남긴다.
How it worksforce inclusion은 이 위험의 하한을 정하는 장치로, 사용자가 시퀀서를 거치지 않고 L1의 inbox 컨트랙트에 트랜잭션을 직접 제출하면 일정 지연 창이 지난 뒤에는 롤업이 그것을 반드시 포함해야 유효한 상태 전이로 인정되게 만든다. 덕분에 시퀀서가 검열해도 사용자는 최소한 출금 같은 탈출 경로를 확보한다.
WhyL2에 올린 서비스의 최악 시나리오는 시퀀서가 멈추거나 우리 트랜잭션만 배제하는 경우인데, force inclusion 경로의 존재 여부와 지연 창 길이가 그때 자금이 묶이는 시간을 결정한다. 이는 배포 체인을 고르는 실질적 기준이다.
사기 증명(fraud proof) 방식은 제출된 상태 전이를 일단 유효하다고 가정하고, 챌린지 기간 안에 누군가 잘못을 지적하면 온체인 검증으로 되돌리는 구조다. 이 방식의 안전성은 암호학이 아니라 게임이론 가정에 의존하는데, 정직한 챌린저가 최소 한 명 존재하고(1-of-N) 그가 챌린지 기간 내에 검열당하지 않고 L1에 트랜잭션을 넣을 수 있어야 한다.
How it works여기서 verifier's dilemma가 생기는데, 검증에는 항상 비용이 들지만 보상은 사기가 실제로 일어났을 때만 발생하므로 합리적 참여자는 검증을 게을리할 유인을 갖고, 이를 본드와 슬래싱으로 보정한다. 유효성 증명(validity proof) 방식은 상태 전이가 규칙을 따랐음을 암호학적 증명으로 보여 주므로 정직한 감시자 가정도 챌린지 기간도 필요 없다.
WhyL2 위에서 자산을 다루면 출금 지연 기간, 챌린저 존재 가정, 검열 저항 같은 조건이 곧 사용자 자금의 안전 조건이 된다. 이를 모르면 브리지나 정산 설계에서 실제 신뢰 가정을 잘못 잡는다.
MEV는 블록 안에서 트랜잭션의 포함 여부·순서·검열을 조정해 뽑아낼 수 있는 초과 가치를 말한다. Proposer-Builder Separation은 블록을 조립하는 빌더와 블록을 제안하는 검증자를 분리해, 제안자가 블록 내용을 보지 않은 채 헤더에 서명하고 가장 높은 입찰가의 블록을 받도록 하는 구조다(이더리움에서는 릴레이를 거치는 오프체인 형태로 널리 쓰인다).
How it works빌더는 서처들이 보낸 번들을 모아 블록 가치를 최대화하고 그 상당 부분을 입찰가로 제안자에게 지급하는 경매가 형성된다. 타이밍 게임은 제안자가 슬롯 안에서 제안을 최대한 늦춰 MEV를 더 모으려는 행위로, 블록 전파 여유를 깎아 네트워크 안정성을 해치는 유인 문제다.
WhyDEX와 예측시장의 사용자 주문은 샌드위치·백런의 표적이고 정산 트랜잭션도 포함 시점이 조작될 수 있어, 프로토콜 설계 단계에서 방어를 넣지 않으면 나중에 막을 수 없다.
분산 시스템에서 메시지 전달은 실질적으로 at-most-once 아니면 at-least-once이며, 순수한 exactly-once 전달은 불가능하다. 대신 현실적인 목표는 '재시도는 얼마든지 일어나되 효과는 한 번'인 exactly-once 처리이고, 이는 수신 측이 멱등해야 달성된다.
How it works멱등성은 보통 요청마다 고유한 멱등 키를 붙이고, 처리 결과를 그 키로 저장해 두었다가 같은 키가 다시 오면 새로 처리하지 않고 저장된 결과를 돌려주는 식으로 구현한다. 아웃박스 패턴은 '상태 변경'과 '메시지 발행'이 서로 다른 시스템이라 원자적으로 묶이지 않는 문제(이중 쓰기)를 해결한다.
Why결제·정산처럼 중복 실행이 곧 금전 손실인 흐름에서, 재시도와 장애 복구가 있는 한 멱등 키와 아웃박스 없이는 언젠가 반드시 중복이나 유실이 발생한다.
분산 시스템 설계에서 어떤 알고리즘이 무엇을 보장하는지는 항상 가정의 함수이므로, 설계 문서의 첫 줄은 장애 모델과 신뢰 가정이어야 한다. 장애 모델은 노드가 멈추고 끝나는 crash-stop, 멈췄다 복구되는 crash-recovery, 메시지를 흘리는 omission, 임의로 거짓말하는 Byzantine 등으로 구분되며 뒤로 갈수록 필요한 정족수와 비용이 커진다.
How it works타이밍 모델은 동기, 부분 동기, 비동기로 나뉘고, 완전 비동기에서는 하나의 크래시만 있어도 결정론적 합의가 불가능하다는 것이 알려져 있다. 신뢰 가정에는 정직한 노드 비율, 인증된 채널과 서명의 존재, 시계 오차 한계, 그리고 어떤 주체를 신뢰할 수 있다고 보는지가 들어간다.
Why실제 장애는 대부분 코드 버그가 아니라 문서화되지 않은 가정이 조용히 깨질 때 발생하고, 가정이 적혀 있지 않으면 리뷰에서 그 위반을 지적할 방법 자체가 없다.
MVCC는 갱신 시 기존 행을 덮어쓰지 않고 새 버전을 만들어, 각 트랜잭션이 자신의 스냅샷에 보이는 버전만 읽게 하는 기법이다. 덕분에 읽기가 쓰기를 막지 않고 쓰기도 읽기를 막지 않으며, 어떤 버전이 보이는지는 트랜잭션 ID와 가시성 규칙으로 판정한다.
How it works스냅샷 격리는 이 위에서 더티 리드·논리피터블 리드·로스트 업데이트를 막지만 직렬화 가능성을 보장하지는 않는다. 대표적 이상현상이 write skew로, 두 트랜잭션이 같은 집합을 읽고 각자 겹치지 않는 서로 다른 행을 갱신해, 개별적으로는 제약을 지키지만 합쳐 놓으면 불변식이 깨지는 경우이다.
Why격리 수준 이름만 믿고 애플리케이션 불변식을 DB에 맡기면, 부하가 올라가 동시 실행이 겹치는 순간에만 조용히 깨지는 버그가 생긴다.
WAL은 데이터 페이지를 수정하기 전에 변경 내역을 로그 파일에 먼저 순차 기록해 내구성과 크래시 복구를 보장하는 기법이며, 무작위 쓰기를 순차 쓰기로 바꾸는 부수 효과도 크다. 커밋이 진짜 내구적이 되려면 로그 레코드가 저장장치에 도달해야 하고, 이를 위해 fsync 또는 fdatasync로 OS 페이지 캐시와 장치 캐시를 강제로 비워야 하는데 이 호출이 커밋 지연의 지배적 비용이다.
How it works그룹 커밋은 짧은 시간 창 안에 도착한 여러 트랜잭션의 로그를 모아 한 번의 fsync로 함께 내구화해, fsync 횟수를 트랜잭션 수가 아니라 시간 단위에 비례하게 만든다. 그 결과 개별 트랜잭션의 지연은 조금 늘지만 전체 처리량은 크게 오르며, 이는 지연과 처리량을 맞바꾸는 전형적인 배칭이다.
WhyDB가 갑자기 느려질 때 원인이 쿼리 플랜이 아니라 커밋당 fsync인 경우가 많고, 반대로 빨라 보이는 설정이 사실은 내구성을 포기한 것일 수도 있다.
LSM 트리는 쓰기를 메모리의 memtable에 모았다가 정렬된 불변 파일(SSTable)로 flush하고, 레벨별로 쌓인 파일들을 컴팩션으로 병합해 정리하는 구조로, 랜덤 쓰기를 순차 쓰기로 바꾸어 쓰기 처리량을 얻는다. 대가로 세 가지 증폭이 생긴다.
How it works쓰기 증폭은 하나의 논리적 쓰기가 컴팩션을 거치며 여러 번 디스크에 다시 쓰이는 배수이고, 읽기 증폭은 하나의 조회가 여러 레벨·파일을 확인해야 하는 비용이며, 공간 증폭은 아직 정리되지 않은 옛 버전과 삭제 마커 때문에 실제 데이터보다 저장 공간이 커지는 비율이다. 레벨드 컴팩션은 레벨마다 키 범위가 겹치지 않게 유지해 읽기·공간 증폭을 낮추는 대신 쓰기 증폭이 크고, 티어드(사이즈 계층) 컴팩션은 반대로 쓰기 증폭이 작지만 겹치는 파일이 많아 읽기·공간 증폭이 커진다.
Why체인 노드의 상태 DB나 인덱서 백엔드가 대개 LSM 기반이라, 디스크 쓰기량이 폭증하거나 컴팩션이 밀려 읽기 지연이 튀는 장애를 만나면 이 세 증폭의 관점 없이는 원인을 못 잡는다.
B+트리는 정렬된 키를 페이지 단위 노드에 유지하며 갱신을 제자리(in-place)로 수행하므로 읽기 증폭이 작고 범위 스캔이 자연스럽지만, 랜덤 쓰기가 랜덤 페이지 쓰기로 이어져 쓰기 증폭과 페이지 분할 비용이 크다. LSM 트리는 쓰기를 메모리 테이블에 모아 순차적으로 SSTable로 flush하고 백그라운드 compaction으로 정리하므로 쓰기 처리량이 높은 대신, 하나의 키가 여러 레벨에 흩어져 읽기 증폭이 생기고(블룸 필터로 완화) compaction이 지연 스파이크와 공간 증폭을 만든다.
How it works이더리움의 상태는 Merkle Patricia 트리를 키-값 저장소 위에 얹는 구조라, 블록마다 루트까지의 경로 노드가 통째로 새로 쓰이는 무작위·쓰기 편중 패턴이 나온다. 그래서 Geth 계열은 LSM 기반 저장소(LevelDB, 이후 Pebble)를 써 왔고, Erigon은 평탄한 키 배치와 B+트리 기반 MDBX로 상태를 재구성해 읽기 증폭과 디스크 사용량을 줄이는 방향을 택했다.
Why노드 동기화가 느리거나 디스크가 폭증하는 문제는 대개 애플리케이션 로직이 아니라 스토리지 엔진의 증폭 특성과 접근 패턴의 불일치에서 온다.
이더리움 상태는 논리적으로 Merkle Patricia Trie지만, 이 구조를 그대로 키-값 DB에 담으면 계정 하나를 읽는 데 루트부터 리프까지 여러 번의 랜덤 조회가 필요하고 노드가 해시로 키잉되어 저장 지역성이 없다. 그래서 실행 클라이언트들은 계정과 스토리지 슬롯을 평평한 키로 직접 저장하는 flat/snapshot 레이아웃을 따로 두어 읽기를 한 번의 조회로 만들고, 트리는 루트 계산과 증명 생성 용도로 유지한다.
How it works트리 노드 저장 방식은 노드 내용의 해시를 키로 쓰는 hash 기반과 트리 안에서의 경로를 키로 쓰는 path 기반으로 나뉘며, path 기반은 같은 경로의 이전 버전을 덮어써서 디스크 증가를 억제하는 대신 과거 상태 조회를 위해 별도의 되돌리기 저널이 필요하다. 결국 설계는 읽기 속도, 디스크 증가량, 과거 상태 보존, 증명 생성 능력 사이의 트레이드오프다.
Why노드 동기화 속도, 디스크 사용량, 아카이브 노드 운영 비용이 전부 이 레이아웃 선택에서 결정되고, 인프라 비용 논의가 실은 이 얘기이기 때문이다.
노드는 블록·영수증 같은 히스토리와 각 시점의 상태 트라이를 모두 저장할 수 있지만, 전체를 영구 보관하면 디스크가 감당되지 않는다. 프루닝은 최신 상태를 유지하는 데 필요 없는 과거 상태 트라이 노드를 지우는 것으로, 이 노드는 현재 잔고·스토리지 조회는 되지만 오래된 블록 시점의 상태 조회는 못 한다.
How it works아카이브 노드는 모든 과거 상태를 보존해 임의 블록 시점의 조회와 재실행이 가능한 대신 저장 비용이 훨씬 크다. 동기화 방식도 갈리는데, 모든 블록을 재실행하는 full sync와 달리 snap sync는 상태를 트라이 노드 단위가 아니라 평면 키-값 구간 단위로 내려받고 각 구간을 상태 루트에 대한 range proof로 검증한 뒤, 동기화 중 변한 부분을 healing 단계에서 메운다.
Why"과거 블록 시점의 잔고나 포지션을 조회하라"는 요구가 뒤늦게 들어오면 아카이브 노드나 별도 인덱서가 없어 대응이 불가능해진다. 노드 운영 비용과 조회 가능 범위는 처음부터 같이 결정해야 한다.
인덱싱 파이프라인은 체인의 블록·로그·트레이스를 읽어 쿼리 가능한 형태로 변환해 저장하는 시스템이고, 재생 가능성은 원본 데이터로부터 언제든 처음부터 다시 돌려도 동일한 결과에 도달하는 성질을 뜻한다. 이를 얻으려면 변환 로직이 결정론적 순수 함수여야 하며, 현재 시각·난수·외부 API 응답처럼 재실행 시 달라지는 입력이 변환 안에 들어가면 안 된다.
How it works진행 상태는 (블록 번호, 로그 인덱스) 같은 커서로 표현하고 쓰기는 멱등해야, 중단 후 재시작이 중복이나 누락 없이 이어진다. 체인은 재구성(reorg)이 일어나므로 확정되지 않은 구간의 결과는 블록 해시를 함께 저장해 되돌리거나 재처리할 수 있어야 하고, 확정 이후 구간만 불변으로 취급한다.
Why인덱서는 버그 수정이나 스키마 변경이 잦은데, 재생이 불가능하면 과거 데이터를 손으로 패치하는 지옥에 들어간다. reorg 처리를 빠뜨리면 조용히 틀린 데이터가 남는다.
로우 스토어가 레코드를 통째로 붙여 저장하는 반면 컬럼 스토어는 같은 컬럼의 값을 연속 배치해, 질의에 필요한 컬럼만 읽어 I/O를 크게 줄인다. 같은 타입에 값 분포도 비슷한 데이터가 모이므로 RLE, 딕셔너리, 델타, 비트팩킹 같은 압축이 훨씬 잘 듣고 압축된 상태로 연산하는 것도 가능해진다.
How it works실행 엔진도 튜플 하나씩 넘기는 volcano 모델 대신 수천 개 값 묶음(벡터) 단위로 처리해 함수 호출 오버헤드를 줄이고 캐시 지역성과 SIMD를 살린다. 대신 단건 조회나 잦은 갱신에는 불리하므로 OLTP 경로는 여전히 로우 스토어가 맞다.
Why분석 질의를 운영 DB에 그대로 던지면 수십 배 느리고 비싸며, 워크로드 성격과 저장 방식을 맞추지 못하면 인덱스 튜닝으로는 회복되지 않는다.
스트리밍 처리에서는 이벤트가 실제 발생한 시각(event time)과 시스템이 처리한 시각(processing time)이 다르고, 네트워크 지연이나 재시도 때문에 순서도 뒤섞인다. 워터마크는 '이 타임스탬프보다 이른 이벤트는 사실상 모두 도착했다'는 시스템의 추정치로, 이벤트 시간 윈도우를 언제 닫고 결과를 낼지 결정하는 신호다.
How it works워터마크는 추정이므로 늦게 온 데이터(late data)가 있을 수 있고, 허용 지연 시간을 두어 결과를 갱신하거나 별도 경로로 빼내는 정책이 필요하다. 여기서 완결성과 지연 사이의 트레이드오프가 생긴다.
Why집계 값이 '왜 조금씩 틀리냐'는 문제의 대부분은 버그가 아니라 이벤트 시간과 워터마크 정책을 명시하지 않은 데서 나온다.
벡터 검색은 임베딩 공간에서 질의 벡터와 가까운 항목을 찾는 문제이며, 고차원에서는 정확한 최근접 탐색이 사실상 전수 비교로 퇴화하므로 근사 최근접 탐색을 쓴다. ANN 인덱스의 품질은 정확도인 recall과 지연·메모리 사이의 트레이드오프 곡선으로 평가하며, 어떤 인덱스도 이 곡선을 벗어나 공짜로 좋아지지 않는다.
How it worksHNSW는 계층적 근접 이웃 그래프를 만들어 위층의 성긴 연결로 멀리 점프하고 아래층에서 정밀 탐색하는 그리디 탐색을 수행하며, 탐색 폭 파라미터로 recall과 속도를 조절한다. IVF-PQ는 먼저 벡터 공간을 클러스터로 나눠 질의와 가까운 몇 개 리스트만 조사하고, 벡터를 부분 공간별 코드북 인덱스로 압축해 메모리를 크게 줄이면서 근사 거리로 비교한다.
WhyRAG나 유사 항목 추천의 체감 품질은 대개 생성 모델이 아니라 리트리버의 recall에서 갈리므로, 인덱스 파라미터가 정확도에 미치는 영향을 모르면 원인을 엉뚱한 데서 찾게 된다.
캐시는 원본과 사본이 갈라지는 순간부터 일관성 문제를 안고 시작하며, 정책은 크게 만료 기반(TTL)과 무효화 기반(쓰기 시 삭제·갱신)으로 나뉜다. 쓰기 경로에서 캐시를 갱신하면 동시 쓰기 순서가 뒤바뀌어 오래된 값이 남을 수 있어, 보통은 갱신보다 삭제가 더 안전하다.
How it works캐시 스탬피드는 인기 키가 만료되는 순간 다수 요청이 동시에 원본으로 몰리는 현상으로, 원본이 순간적으로 무너질 수 있다. 대응은 단일 비행(single-flight)으로 한 요청만 원본을 조회하게 하거나, 만료 시각에 무작위 지터를 주거나, 만료 전에 미리 갱신하는 조기 재계산, 그리고 갱신 중 낡은 값을 잠시 제공하는 stale-while-revalidate이다.
Why장애의 상당수는 캐시가 없어서가 아니라 캐시가 한꺼번에 비면서 뒤쪽 시스템이 무너지는 형태로 발생한다.
외부 정렬은 데이터가 메모리보다 클 때 쓰는 방법으로, 메모리에 들어가는 크기의 런(run)을 만들어 정렬해 디스크에 쓰는 단계와 이 런들을 다방향 병합으로 합치는 단계로 나뉜다. 병합 차수 k를 키우면 필요한 패스 수가 런 개수에 대한 log_k로 줄지만, 런마다 입력 버퍼를 나눠 가져야 해서 버퍼가 작아지면 순차 읽기 효율이 떨어지는 트레이드오프가 있다.
How it works런 생성 단계에서 replacement selection을 쓰면 평균적으로 메모리 크기보다 긴 런을 만들 수 있어 런 개수 자체를 줄일 수 있다. 병렬 정렬은 데이터를 나눠 각각 정렬한 뒤 병합하거나, 샘플링으로 분할 경계를 정해 각 파티션을 독립적으로 정렬하는 sample sort 방식을 쓰며, 이때 실제 병목은 비교 연산이 아니라 메모리 대역폭과 데이터 이동량이다.
Why인덱스 재구축, 대용량 조인, 로그 재처리처럼 메모리를 넘는 정렬은 실무에서 자주 나오고, 여기서 성능을 가르는 것은 알고리즘 선택보다 버퍼 크기와 병합 차수 설정이다.
데이터 모델은 논리적 표현이 아니라 물리적 접근 경로를 결정하기 때문에 성능의 상한을 먼저 정한다. 키 설계는 어떤 조회가 단일 탐색으로 끝나고 어떤 조회가 전체 스캔이 되는지를 정하고, 정규화 정도는 쓰기 시 중복 비용과 읽기 시 조인 비용 사이의 배분을 정하며, 파티셔닝·클러스터링 키는 어떤 범위 질의가 인접한 디스크 블록에서 처리되는지를 정한다.
How it works인덱스는 이 구조를 사후에 보정하는 수단이지만 쓰기 증폭과 저장 공간을 늘리므로 무한정 늘릴 수 없고, 근본적으로 잘못된 모델을 인덱스로 완전히 구제하지는 못한다. 그래서 실무 순서는 '어떤 질의를 어떤 빈도와 지연 목표로 처리할 것인가'를 먼저 적고 그 접근 패턴에 맞춰 모델을 정하는 것이며, 반대로 모델을 먼저 정하고 질의를 끼워 맞추면 나중에 마이그레이션 비용을 치르게 된다.
Why성능 문제 대부분은 코드 최적화가 아니라 접근 패턴과 어긋난 스키마에서 오고, 이 결정은 데이터가 쌓인 뒤에 되돌리기가 가장 비싼 결정이기도 하다.
랜덤 오라클 모델은 해시 함수를 모든 입력에 대해 균일 랜덤한 출력을 돌려주는 이상적인 함수로 가정하고 안전성을 증명하는 방법론이며, 실제 해시는 이 이상과 다르기 때문에 증명은 휴리스틱한 보증에 그친다. 그 간극의 대표 사례가 길이 연장 공격으로, Merkle-Damgård 구조 해시(SHA-256 등)의 출력은 사실상 내부 상태이므로 공격자는 원문을 몰라도 H(m)과 길이만 알면 H(m || padding || m')을 계산할 수 있다.
How it works따라서 secret을 앞에 붙인 H(k || m)을 MAC으로 쓰면 위조가 가능하고, 대신 두 단계 구조인 HMAC이나 스펀지 구조인 Keccak/SHA-3을 써야 한다. 도메인 분리는 서로 다른 용도의 해시 입력이 절대 겹치지 않도록 용도 태그나 접두사를 넣어 한 문맥의 서명·커밋먼트가 다른 문맥에서 재사용되지 못하게 하는 원칙이다.
Why서명 대상 메시지를 임의로 이어 붙여 해시하는 코드는 재사용 공격이나 위조로 이어지며, 이는 라이브러리가 아니라 애플리케이션이 만드는 취약점이다.
HMAC은 해시 함수와 비밀키로 만드는 메시지 인증 코드로, 키를 모르면 유효한 태그를 만들 수 없어 메시지의 무결성과 출처를 함께 보장한다. AEAD는 암호화와 인증을 한 번에 처리하는 모드로, 평문의 기밀성에 더해 암호문과 추가 인증 데이터(AAD)의 무결성까지 보장한다.
How it worksAES-GCM이나 ChaCha20-Poly1305 같은 대표적 AEAD는 같은 키로 nonce를 재사용하면 인증 키가 노출되거나 평문이 복구될 수 있어 치명적이며, 그래서 nonce 오용 저항 모드는 nonce가 반복되더라도 피해를 같은 평문이 같은 암호문으로 보인다는 수준으로 제한한다. 웹훅 검증은 기밀성이 아니라 인증 문제이므로 보통 HMAC을 쓰고, 서명 대상에 타임스탬프를 포함한 뒤 수신 측에서 허용 시간 창을 검사해 재전송 공격을 막는다.
Why웹훅 엔드포인트는 인터넷에 열려 있어 서명 검증이나 재전송 방어가 없으면 아무나 결제·정산 이벤트를 위조해 밀어 넣을 수 있기 때문이다.
난수 생성기는 시드에서 결정적으로 수열을 만드는 PRNG와, 예측 불가능성을 보장하도록 설계된 CSPRNG로 나뉜다. 통계적 검정 묶음은 출력이 균등성·독립성 면에서 이상한 구조를 보이는지 검사하지만, 검정을 통과했다는 사실이 암호학적 안전성을 뜻하지는 않는다.
How it works선형 합동법이나 메르센 트위스터처럼 통계적으로 무난한 생성기도 출력을 조금만 관측하면 내부 상태를 복원해 이후 값을 전부 예측할 수 있다. CSPRNG는 이전 출력을 알아도 다음 비트를 유의미하게 예측할 수 없어야 하고, 상태가 노출돼도 과거 출력을 되돌릴 수 없어야 하며, 시드는 OS 엔트로피 소스에서 받아야 한다.
Why서명 nonce, 세션 토큰, 키 생성이 모두 여기에 의존하며, 재현되는 난수 하나가 곧바로 개인키 노출로 이어진다. 특히 ECDSA는 서로 다른 두 서명에서 같은 nonce를 쓰면 대수적으로 개인키가 복원된다.
ECDSA는 타원곡선 위의 서명 스킴으로 서명마다 비밀 난수 nonce가 필요하고, 이 nonce가 재사용되거나 편향되면 서명 두 개만으로 개인키가 복원된다. 또 (r, s)와 (r, -s mod n)이 모두 유효해 서명 가변성(malleability)이 생기므로 이더리움은 s를 낮은 절반으로 제한하는 규칙을 두었고, 대신 서명에서 공개키를 복원할 수 있다는 특성 덕에 ecrecover 패턴이 가능하다.
How it worksEdDSA는 Schnorr 계열로 nonce를 비밀키와 메시지의 해시로 결정론적으로 만들어 nonce 재사용 사고를 구조적으로 없앴지만, 구현마다 cofactor 처리나 인코딩 정규성 검사 기준이 달라 같은 서명을 어떤 라이브러리는 받고 어떤 라이브러리는 거부하는 합의 위험이 있다. Schnorr 서명은 선형 구조 덕분에 여러 키와 서명을 하나로 집계할 수 있고, BLS는 페어링을 이용해 서명이 짧고 다수 서명을 무제한 집계할 수 있어 검증자 집합 서명 취합에 적합하지만 검증 연산이 상대적으로 무겁다.
Why서명 검증 코드의 미묘한 차이가 자금 도난이나 노드 간 합의 분기로 직결되고, nonce·malleability·rogue-key는 실제로 반복해서 사고를 낸 지점이다. 스킴을 고르는 일은 곧 어떤 함정을 떠안을지 고르는 일이다.
(t,n) 임계 서명은 비밀키를 n개 지분으로 나눠 t개 이상이 모여야 유효한 서명을 만들 수 있게 하는 방식으로, 어떤 시점에도 완전한 키가 한 곳에 존재하지 않는다. 원리는 Shamir 비밀 분산으로, t-1차 다항식 위의 점들을 배포하면 t개 점으로만 상수항(비밀)을 복원할 수 있고 t-1개로는 아무 정보도 얻지 못한다.
How it worksDKG는 신뢰할 딜러 없이 참가자들이 상호작용만으로 공동 공개키와 각자의 지분을 만들어내는 프로토콜이며, 검증 가능한 비밀 분산을 써서 부정 참가자를 걸러낸다. BLS 서명은 키와 서명이 그대로 더해지는 성질 덕분에 임계화가 자연스럽지만, ECDSA는 곱셈 구조 때문에 훨씬 복잡한 MPC 프로토콜이 필요하다.
Why브리지·커스터디·오라클 서명자 집합의 보안은 결국 키를 어떻게 나눠 갖느냐에 달려 있고, 실제 사고 상당수가 단일 키 유출에서 시작된다.
커밋먼트는 값을 봉인해 공개하되 나중에 그 값을 밝힐 수 있게 하는 원시 도구이며, 봉인된 값을 바꿔치기할 수 없는 binding과 봉인만 봐서는 값을 알 수 없는 hiding을 요구한다. Pedersen 커밋먼트는 두 생성원과 무작위 블라인딩 값을 써서 이산로그 가정 위에 세워지며, 정보이론적으로 완벽한 hiding과 계산적 binding을 가지고 덧셈에 대해 준동형이라 값들의 합을 커밋먼트끼리 더해 검증할 수 있다.
How it worksKZG는 다항식 커밋먼트로, 페어링을 이용해 커밋먼트와 임의 점에서의 평가 증명을 모두 상수 크기로 만들지만 구조화된 참조 문자열(trusted setup)이 필요하다. FRI는 해시와 리드-솔로몬 부호의 근접성 검사에 기반해 신뢰 셋업 없이 동작하고 증명 크기가 폴리로그로 커지지만, 가정이 해시 기반이라 양자 내성 관점에서 선호된다.
Why롤업과 ZK 시스템의 비용 구조, 데이터 가용성 설계, 신뢰 가정이 사실상 어떤 커밋먼트를 쓰느냐로 결정되기 때문에 이 트레이드오프를 모르면 아키텍처 선택 근거를 세울 수 없다.
다중정밀 산술은 기계어 워드보다 큰 정수를 워드 배열로 표현해 연산하는 기법이며, 암호 구현에서 가장 비싼 연산은 모듈러 곱셈이다. 나눗셈은 곱셈보다 훨씬 느리므로 모듈러 리덕션에서 실제 나눗셈을 피하는 것이 핵심 최적화다.
How it worksMontgomery 리덕션은 모듈러스와 서로소인 2의 거듭제곱 R을 잡아 수를 Montgomery 표현으로 옮긴 뒤, 곱셈과 시프트만으로 R의 역원을 곱한 결과를 얻어 리덕션을 수행한다. 표현 변환에 비용이 들기 때문에 지수승처럼 같은 모듈러스에서 곱셈을 연달아 할 때 유리하다.
Why타원곡선 서명 검증이나 ZK 증명 생성 시간의 상당 부분이 필드 곱셈에 들어가므로, 이 계층의 표현과 리덕션 선택이 곧 처리량과 가스 비용을 결정한다.
EVM에는 부동소수점이 없으므로 비율과 가격은 고정소수점, 즉 정수에 암묵적 스케일(예: 1e18)을 곱한 표현으로 다룬다. 곱셈은 스케일이 두 배가 되므로 나누어 되돌려야 하고, 이 나눗셈마다 절사 오차가 생기며 그 방향이 시스템의 불변식을 지키거나 깨뜨린다.
How it works원칙은 항상 프로토콜(풀·컨트랙트)에 유리한 방향으로 반올림하는 것으로, 사용자가 받는 양은 내림, 사용자가 내는 양은 올림으로 처리해 반복 거래로 잔여분을 긁어가는 dust leak을 막는다. LMSR처럼 exp와 ln이 필요한 비용함수는 정수 근사로 구현해야 하고, 근사 오차의 상한과 그 오차가 비용함수의 단조성·볼록성을 깨지 않는지를 함께 따져야 한다.
Why반올림 방향 하나를 반대로 잡으면 수학적으로는 미미한 오차가 무한 반복 가능한 무료 인출 경로가 된다.
유한체는 원소가 유한개이면서 덧셈과 곱셈, 그리고 0을 제외한 나눗셈이 모두 정의되는 대수 구조이고, 암호와 ZK에서는 주로 큰 소수 p에 대한 소수체 F_p를 쓴다. 이 위의 다항식 곱셈은 정의대로 하면 O(n^2)이지만, 곱셈군 안에 크기가 2의 거듭제곱인 부분군(즉 적당한 차수의 단위근)이 존재하도록 소수를 고르면 FFT와 같은 구조의 변환을 정수 위에서 오차 없이 수행할 수 있으며 이것이 NTT다.
How it worksNTT는 부동소수점 반올림 오차가 없고 결과가 체 원소로 정확히 떨어지므로 증명 시스템에 적합하고, 곱셈은 평가 도메인에서의 원소별 곱으로 바뀌어 전체가 O(n log n)이 된다. 구현에서는 Montgomery나 Barrett 축약으로 모듈러 곱 비용을 줄이고 버터플라이 연산에서 지연 축약을 적용해 나머지 연산 횟수를 줄이는 것이 핵심 최적화다.
WhyZK 증명 생성 시간의 큰 몫이 NTT와 다항식 연산에서 나오므로, 증명 비용을 추정하거나 튜닝하려면 이 계층을 이해해야 한다.
산술화는 '이 프로그램을 올바르게 실행했다'는 명제를 유한체 위의 다항식 제약 만족 문제로 바꾸는 단계로, 모든 ZK 증명 시스템의 첫 관문이다. R1CS는 계산을 A·z ∘ B·z = C·z 형태의 제약 집합으로 표현하는데, 여기서 z는 공개 입력과 witness를 담은 벡터이고 각 제약은 곱셈 게이트 하나에 대응하므로 표현이 단순한 대신 제약 수가 곱셈 개수에 비례해 커진다.
How it worksAIR는 계산을 실행 트레이스 표로 보고 '인접한 두 행 사이에 성립해야 하는 전이 제약'과 경계 제약으로 표현하며, 같은 연산이 반복되는 VM 실행에 특히 잘 맞아 제약 기술이 매우 간결해진다. PLONKish는 열(column)과 행(row)으로 이루어진 표에 임의 차수의 커스텀 게이트, 서로 다른 셀을 동일하게 강제하는 copy constraint(순열 논증), 그리고 lookup 논증을 얹은 산술화로, 비싼 비트 연산 같은 것을 미리 계산된 테이블 조회로 대체할 수 있다는 점이 큰 장점이다.
WhyZK 시스템의 증명 비용은 대부분 산술화 단계에서 회로가 얼마나 커지느냐로 결정되므로, 같은 로직도 어떤 산술화에 올리느냐에 따라 실용성이 갈린다.
다항식 IOP(Interactive Oracle Proof)는 증명자가 다항식을 오라클로 제출하고 검증자가 무작위 점에서의 평가를 질의하는 추상 프로토콜로, 계산의 정당성을 다항식 항등식 검사로 환원한다. 이 추상 계층은 실제 암호를 쓰지 않고 완전성·건전성만 논하며, 오라클을 실제 다항식 커밋먼트 스킴(PCS)으로 바꾸고 Fiat-Shamir로 비대화형화하면 구체적인 SNARK/STARK가 된다.
How it works그래서 산술화(R1CS, PLONKish, AIR)와 커밋먼트 방식이 분리되고, 시스템의 증명 크기·검증 시간·증명 시간·신뢰 설정 여부는 대부분 PCS 선택에서 갈린다. 페어링 기반 KZG는 커밋먼트와 평가 증명이 상수 크기이고 검증이 매우 빠르지만 구조화된 신뢰 설정이 필요하고 양자 내성이 없다.
Why온체인 검증 비용은 증명 크기와 검증자 연산량에 거의 비례하므로, 어떤 증명 시스템을 쓰느냐가 곧 가스비와 신뢰 가정의 선택이 된다.
재귀 증명은 어떤 증명이 검증을 통과했다는 사실 자체를 다시 증명하는 기법으로, 증명 검증 알고리즘을 회로로 표현한 뒤 그 회로의 실행을 증명하는 방식으로 구현한다. 이렇게 하면 임의로 긴 계산이나 여러 블록의 상태 전이를 하나의 작은 증명으로 접을 수 있어, 검증 비용이 원래 계산의 길이와 무관해진다.
How it works증명 집계는 여러 개의 독립적인 증명을 묶어 검증 비용을 줄이는 것으로, 재귀로 구현하기도 하고 배치 검증이나 커밋먼트의 선형 결합 같은 더 값싼 방법을 쓰기도 한다. 실무의 핵심 제약은 그 증명 시스템의 검증기를 회로 안에서 얼마나 싸게 표현할 수 있는가이며, 그래서 곡선 선택이나 증명 친화적 해시 함수 선택이 중요해진다.
Why롤업이 수많은 트랜잭션을 L1에서 한 번의 검증으로 정산하고 라이트클라이언트가 긴 히스토리를 작은 비용으로 따라잡을 수 있는 근거가 바로 이 구조이기 때문이다.
프라이버시 프리미티브의 공통 목표는 "권한이 있음"을 증명하는 일과 "누구인지"를 드러내는 일을 분리하는 것이다. 링 서명은 여러 공개키로 이루어진 집합 중 하나의 비밀키 소유자가 서명했음을 증명하되 어느 것인지는 숨기며, 익명성의 강도는 그 집합(anonymity set)의 크기와 구성에 달린다.
How it worksnullifier는 비밀값에서 결정적으로 유도한 고유 태그로, 이를 공개해 중복 사용을 막으면서도 어떤 예치·커밋먼트에서 나왔는지는 연결되지 않게 한다. 같은 비밀에서는 항상 같은 nullifier가 나오므로 두 번째 사용 시도는 즉시 검출된다.
Why공개 원장에서는 주소 하나가 전체 거래 이력과 잔고를 노출해 상대 포지션을 읽고 앞서 거래하는 것이 가능하며, 이는 개인정보 문제이자 곧바로 경제적 손실이다. 프라이버시 설계를 알아야 어느 정보를 굳이 온체인에 남길지 판단할 수 있다.
양자 컴퓨터는 Shor 알고리즘으로 이산로그와 소인수분해를 깨므로 현행 타원곡선 서명이 위협받고, Grover 알고리즘은 해시의 탐색 난이도를 낮추지만 출력 길이를 늘리는 것으로 비교적 쉽게 대응된다. 대체 알고리즘 자체는 격자·해시 기반 등으로 이미 표준화 과정을 거쳐 왔기 때문에 남은 어려움은 수학이 아니라 배포와 조정에 있다.
How it works블록체인에서 서명 스킴을 바꾸는 일은 합의 규칙 변경이라 하드포크가 필요하고, 지갑·하드웨어 서명기·브리지·인덱서·감사받은 컨트랙트가 동시에 움직여야 하며, 키와 서명이 커지면 블록 공간과 검증 비용도 함께 늘어난다. 이미 공개키가 체인에 노출된 계정이나, 지금 수집해 두었다가 나중에 해독하는 harvest-now-decrypt-later 위협 때문에 '위험이 현실화된 뒤에 옮긴다'는 전략이 성립하지 않는다는 점도 조정 압박을 키운다.
Why암호 전환의 실패 지점은 알고리즘 선택이 아니라 마이그레이션 경로가 없는 설계에 있고, 이는 지금 짜는 시스템의 키 관리와 업그레이드 가능성 설계에 바로 영향을 준다. 특히 키가 영구적으로 박제되는 온체인 시스템에서 치명적이다.
검증 가능한 시스템은 결과를 믿어달라고 요구하는 대신 상대가 스스로 결과의 정당성을 확인할 수 있게 만드는 것을 설계 목표로 삼는다. 핵심 축은 결정성(같은 입력에 같은 출력), 커밋먼트(머클 루트나 해시로 상태를 고정), 증명 방식(유효성 증명, 머클 증명, 사기 증명 중 무엇인지), 그리고 신뢰 가정과 데이터 가용성이다.
How it works검증 비용이 재실행 비용보다 확실히 작아야 검증 가능성이 실질적 의미를 가진다. 마지막으로 실패했을 때의 회복 경로 — 이의제기 기간, 에스컬레이션 절차, 최종 폴백 권한이 누구에게 있는지 — 까지 명시되어야 설계가 완결된다.
Why증명 시스템을 붙였다는 사실만으로 안전해지지 않으며, 신뢰 가정과 폴백 경로를 문서로 고정해두지 않으면 실제 사고 순간에 누가 무엇을 할 수 있는지 아무도 모른다.
트랜스포머 추론은 프롬프트 전체를 한 번에 처리하는 prefill 단계와 토큰을 하나씩 만들어내는 decode 단계로 나뉘고, 두 단계의 병목이 다르다. decode에서는 과거 토큰의 key/value를 매번 다시 계산하지 않도록 KV 캐시에 보관하는데, 이 캐시 크기가 시퀀스 길이와 동시 요청 수에 비례해 커져 GPU 메모리가 곧 동시성 한계가 된다.
How it worksPagedAttention은 KV 캐시를 연속된 큰 블록이 아니라 페이지 단위로 관리해 단편화와 과다 예약을 없애 동시 처리 요청 수를 늘린다. 연속 배칭은 요청 단위로 배치를 고정하지 않고 토큰 생성 스텝마다 끝난 요청을 빼고 새 요청을 넣어 GPU 유휴를 줄인다.
WhyLLM 서빙 비용과 지연은 모델 선택보다 KV 캐시 관리와 배칭 전략에서 훨씬 크게 갈리므로, 이 구조를 모르면 GPU를 더 사는 방식으로만 문제를 풀게 된다.
RAG는 질의에 대해 외부 지식 저장소에서 관련 문서를 검색한 뒤 그 근거를 붙여 답을 생성하는 구조이며, 품질은 검색 단계와 생성 단계로 분리해 평가해야 한다. 검색 품질은 정답 문서가 상위 k개 안에 들어왔는지를 보는 recall@k, 첫 정답의 순위를 보는 MRR, 순위별 가중치를 반영하는 nDCG 같은 지표로 측정한다.
How it works생성 품질은 답이 제시된 근거에 실제로 뒷받침되는가를 보는 근거성과 질의에 대한 적합성으로 나누어 보며, 근거 없는 진술은 검색이 아니라 생성 단계의 실패다. 평가 하네스는 고정된 질의와 기대 근거를 담은 골든 데이터셋, 근거가 없으면 답을 만들지 않는다는 식의 불변식을 검사하는 프로퍼티 테스트, 그리고 청킹·임베딩·프롬프트를 바꿀 때마다 기존 통과 케이스를 다시 돌리는 회귀 테스트로 구성한다.
WhyRAG 시스템의 성능 저하는 대개 조용히 일어나서, 회귀 하네스 없이는 청킹 크기 하나 바꾼 것이 특정 질의군을 망가뜨렸다는 사실을 사용자 불만이 쌓인 뒤에야 알게 된다.
에이전트 루프는 모델이 도구를 호출하고 결과를 다시 입력으로 받아 목표에 도달할 때까지 반복하는 제어 구조이다. 이 루프는 본질적으로 비결정적이므로, 안전성은 모델의 판단이 아니라 루프를 감싸는 시스템 쪽 제약으로 확보해야 한다.
How it works구체적으로는 도구별 최소 권한 부여, 되돌릴 수 없는 행위 앞의 명시적 게이트(승인·드라이런·한도), 반복 횟수와 비용 상한, 그리고 실패 유형을 구분한 재시도 정책이 필요하다. 재시도는 멱등성이 보장되는 도구에만 자동으로 적용해야 하며, 그렇지 않으면 같은 부작용이 중복 실행된다.
Why에이전트가 틀리는 것 자체는 막을 수 없고, 틀렸을 때 되돌릴 수 있는지와 무엇 때문에 틀렸는지 알 수 있는지가 실제 운영 가능 여부를 가른다.
ADR(Architecture Decision Record)은 하나의 아키텍처 결정을 맥락, 검토한 대안, 선택과 근거, 그리고 그로 인한 결과와 감수한 트레이드오프로 짧게 기록하는 문서이며, 이런 기록을 시간순으로 누적해 시스템이 왜 지금 모습인지를 보존한다. 위협 모델은 보호해야 할 자산과 신뢰 경계를 그린 뒤, 각 경계에서 공격자가 무엇을 할 수 있고 무엇을 노리는지 열거하고 대응책과 남는 잔여 위험까지 명시하는 문서다.
How it works두 문서의 공통점은 결론만이 아니라 전제와 대안을 남긴다는 점이고, 덕분에 전제가 바뀌면 그 결정을 다시 봐야 한다는 신호가 자동으로 생긴다. 형식보다 중요한 것은 범위를 결정 하나, 시스템 하나로 좁혀 실제로 끝까지 읽히는 분량을 유지하는 것이다.
Why기록되지 않은 결정은 몇 달 뒤 이유 없는 제약으로 취급되어 조용히 뒤집히고, 그때 그 결정이 막고 있던 위협도 함께 되살아난다.
Source: docs/knowledge/dev-100-curriculum.md (auto-generated by scripts/generate-curriculum-html.mjs — edit the curriculum, not this file)