diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/design/011-pure-transport.md | 10 | ||||
| -rw-r--r-- | docs/research/094-idle-links.md | 4 | ||||
| -rw-r--r-- | docs/research/095-restart-and-first-contact.md | 131 |
3 files changed, 140 insertions, 5 deletions
diff --git a/docs/design/011-pure-transport.md b/docs/design/011-pure-transport.md index d27aa5a..a49d702 100644 --- a/docs/design/011-pure-transport.md +++ b/docs/design/011-pure-transport.md @@ -1,6 +1,6 @@ # 011 — 연결 없는 전송: 전송의 상태를 앱의 데이터로 -작성일: 2026-09-28(같은 날 첫 판을 버리고 다시 씀). 상태: 설계. 1단계를 구현했고 M1을 쟀다. +작성일: 2026-09-28(같은 날 첫 판을 버리고 다시 씀). 상태: 설계. 1단계를 구현했고 M1, M2, M4를 쟀다. [외부 피드백 002](../outside-feedback/feedback-002.md)의 "QUIC을 능가할 자체 raw socket 프로토콜"에서 시작한다. 1단계(링크 시제품과 kill -9 검사)는 [093](../research/093-connectionless-link.md)에 있다. 어느 쪽을 죽여도 핸드셰이크 없이 @@ -10,8 +10,12 @@ M1은 [094](../research/094-idle-links.md)에 있다. 쉬는 링크 하나가 노드 메모리 132 B를 쓴다. 허용 목록 73 B와 들은 번호 약 60 B이고, 전송 상태는 0이다. quinn의 쉬는 연결은 38,106 B다. 1/289로 중단 기준(1/100)을 넘는다. 설계가 말한 "링크의 -행"은 앱이 이미 가진 들은 번호였다. 그래서 들은 번호를 목록으로 바꿨고, 저장소의 한 항목은 약 20 B다. 남은 걸림돌은 M2다. -활성 상태를 비우면 비밀도 잊으므로, 재시작한 노드는 링크마다 X25519를 한 번 한다. +행"은 앱이 이미 가진 들은 번호였다. 그래서 들은 번호를 목록으로 바꿨고, 저장소의 한 항목은 약 20 B다. + +M2와 M4는 [095](../research/095-restart-and-first-contact.md)에 있다. 비밀은 노드 키 옆 파일에 적어 둔다(메모). 기기 1만 +개가 초당 2,000건을 보내는 중에 받는 쪽을 kill -9 해도 저장이 멈춘 100 ms 칸이 없다. 0.2초 만에 따라잡고, 재시작에 비대칭 +연산이 들지 않으며, 잃거나 겹친 기록이 없다. quinn은 1초 멈추고 10.9초 뒤에 따라잡는다. 그동안 핸드셰이크 1만 번에 서버가 CPU +약 7초를 더 쓴다. 처음 만남은 1 RTT로, QUIC의 2 RTT의 절반이다. ## 첫 판을 버린 까닭 diff --git a/docs/research/094-idle-links.md b/docs/research/094-idle-links.md index 57fc736..573db98 100644 --- a/docs/research/094-idle-links.md +++ b/docs/research/094-idle-links.md @@ -133,8 +133,8 @@ H1의 뒷부분("프로세스 메모리는 활성 링크 수에만 비례")은 � ## 한계와 다음 - **재시작의 비대칭 연산.** 활성 상태를 비우면 비밀도 잊는다. 그래서 재시작한 노드는 링크마다 X25519를 한 번 한다(169 µs). - 011의 M2 중단 기준("이어지는 데 링크 수에 비례하는 비대칭 연산")에 걸린다. 다음 일은 비밀의 메모다. 키 파일 옆 파일에 - 보내는 이마다 64 B 칸을 두고 매핑한다. 쉬는 링크의 칸은 상주하지 않는다. + 011의 M2 중단 기준("이어지는 데 링크 수에 비례하는 비대칭 연산")에 걸린다. [095](095-restart-and-first-contact.md)에서 비밀의 + 메모로 풀었다. 키 파일 옆 파일에 보내는 이마다 64 B 칸을 두고 매핑한다. 쉬는 링크의 칸은 상주하지 않는다. - **받는 쪽의 처리량.** 새 보내는 이를 받는 속도는 초당 약 3,700이다. 노드 CPU의 대부분이 X25519다. - **보내는 쪽.** 링크마다 스레드와 소켓이 하나씩이다. 노드가 기기 100만 대에 보내는 방향은 아직 안 된다. 보내는 쪽도 한 스레드와 한 소켓에 여러 링크를 둬야 한다. diff --git a/docs/research/095-restart-and-first-contact.md b/docs/research/095-restart-and-first-contact.md new file mode 100644 index 0000000..eb0249d --- /dev/null +++ b/docs/research/095-restart-and-first-contact.md @@ -0,0 +1,131 @@ +# 095 — 재시작과 처음 만남: 링크 1만 개가 kill -9를 모른다 + +2026-09-28. [설계 011](../design/011-pure-transport.md)의 M2와 M4다. [094](094-idle-links.md)의 부하 생성기와 quinn +하네스를 그대로 쓴다. + +착수 기준: + +- **바꿀 결정.** 011의 H2다. 어느 노드를 kill -9 해도 다시 뜬 뒤 첫 패킷으로 이어지고, 핸드셰이크도 잃거나 겹치는 기록도 없다. + 중단 기준은 둘이다. + - 재시작 뒤 핸드셰이크 없이 이어지지 않는다. + - 이어지는 데 링크 수에 비례하는 비대칭 연산이 든다. + - 둘 중 하나라도 그러면 다시 설계한다. +- **최소 확인.** + - M2: 기기 1만 개가 5초마다 주문 하나를 보낸다. 받는 쪽이 초당 2,000건을 받는다. 20초쯤에 받는 쪽을 kill -9 하고 곧바로 + 다시 띄운다. 저장이 멈춘 시간, 밀린 것을 따라잡는 시간, 양쪽 CPU, 비대칭 연산 수, 잃음과 겹침을 본다. quinn도 같은 부하로 + 한다. 연결 1만 개가 다시 맺어진다. + - M4: 처음 보는 상대에게 주문 하나를 보내 저장됐다는 말을 받기까지 걸리는 왕복 수를 본다. +- **중단 기준.** 위와 같다. + +## 쉬운 말로 + +- 알아낸 것: + - 받는 노드를 kill -9 하고 다시 띄워도 기기 1만 개는 거의 모른다. 100 ms 단위로 저장이 멈춘 때가 없었다. 밀린 것은 0.2초 + 만에 따라잡았다. 다시 보낸 주문은 34건이고, 8만 건이 모두 정확히 한 번 적용됐다. 재시작한 노드의 비대칭 연산은 0이다. + - quinn은 같은 일에서 1초 동안 멈췄다. 연결 1만 개를 다시 맺느라 10.9초 뒤에야 따라잡았다. 그동안 핸드셰이크에 서버가 + CPU를 약 7초, 클라이언트들이 약 8초 더 썼다. + - 처음 보는 상대와 Pure는 1 RTT에 끝나고, QUIC은 2 RTT가 든다. 첫 패킷이 이미 봉인된 기록이기 때문이다. +- 아직 모르는 것: 전달당 CPU와 처리량(M5), 손실과 병목 아래의 공정성(M6), 저장소 옮기기(M3). +- 사용 경험의 차이: 서버를 배포하거나 죽었다 살아나도, 붙어 있던 기기와 사용자는 모른다. 재연결 폭주도 없다. + +## 한 것 + +### 비밀의 메모 + +[094](094-idle-links.md)의 받는 쪽은 쉬는 보내는 이의 활성 상태를 비운다. 그러면 비밀도 잊는다. 그래서 재시작한 노드는 +돌아오는 보내는 이마다 X25519를 한 번 했다. 이 Pi의 OpenSSL로 169 µs다. 이것이 M2의 두 번째 중단 기준에 걸렸다. + +비밀은 이제 노드 키 옆의 파일(`KEY.links`, 0600)에 적어 둔다. + +- 보내는 이마다 허용한 순서대로 64 B 칸이 하나씩 있다. 칸에는 키의 앞 28 B, 검사값(키와 비밀의 FNV-1a), 비밀이 든다. +- 파일은 매핑한다. 쉬는 보내는 이의 칸은 메모리에 올라와 있지 않다. +- 비밀을 먼저 쓰고, 칸을 그 키의 것으로 만드는 키는 나중에 쓴다. 검사값이 맞지 않는 칸은 다시 만든다. 손으로 한 칸의 비밀을 + 바꿔 봤고, 그 칸만 X25519로 다시 만들어졌다. +- 노드 키가 바뀌면 파일을 처음부터 쓴다. +- 칸의 비밀은 노드 키와 같은 무게다. 그래서 키 파일과 같이 주인만 읽는다. + +연결 없는 모델에서는 이것이 자연스럽다. 비밀은 두 정적 키의 함수라서 언제 계산해도 같다. 메모는 그 함수의 기록일 뿐이다. +세션이 아니므로 틀려도 다시 계산하면 된다. + +### 꾸준히 보내는 기기들 + +부하 생성기에 `run`을 더했다([links.c](../../research/experiments/019-idle-links/links.c)). + +- 기기마다 소켓, 키, outbox가 있다. 주기마다 기록을 하나 만든다. +- 저장되지 않은 것은 다시 보낸다. 답이 없으면 200 ms에서 시작해 1초까지 기다림을 늘린다. +- 받는 쪽이 새로 뜨면 답의 run이 바뀐다. 기기는 그 run의 키를 만들어 연다. 기기 쪽의 일은 그것뿐이다. +- 100 ms마다 저장된 수를 센다. + +### quinn 쪽 + +QUIC에 가장 좋은 조건을 줬다. + +- 서비스는 같은 포트에 같은 키로 다시 뜬다. 상태 없는 리셋 키도 그 키에서 만든다. 그래서 새 서비스가 옛 연결의 패킷에 + 곧바로 리셋을 보낸다. +- 클라이언트는 1초 안에 답이 없거나 연결이 끊기면 다시 연결해 같은 주문을 보낸다. +- 서비스는 디스크에 저장하지 않는다. 메모리의 번호만 적는다. 그래서 정확히 한 번은 Pure 쪽만 확인한다. +- tokio 한 스레드다. Pure의 받는 쪽도 암호는 한 스레드(리스너)가 한다. + +## 결과 + +라즈베리 파이 5이고, 저장소는 tmpfs다(SD 카드는 따로 적었다). 원시 결과는 `research/experiments/019-idle-links/`의 +`2026-09-28-restart-*.jsonl`과 `2026-09-28-first-contact-linux-aarch64.jsonl`에 있다. + +**M2.** 기기 또는 클라이언트 1만 개가 5초마다 주문 하나를 보낸다(초당 2,000건). 받는 쪽을 약 21초에 kill -9 하고 곧바로 +다시 띄웠다. 세 라운드의 중앙값이다. SD 카드는 한 라운드다. + +| | 다시 뜨기 | 저장이 멈춘 100 ms 칸 | 따라잡기 | 받는 쪽 CPU(재시작 뒤 10초) | 비대칭 연산 | 보내는 쪽 CPU(같은 10초) | 다시 보냄 | 저장까지 p99 / 최대 | +|---|---:|---:|---:|---:|---:|---:|---:|---:| +| Pure, 메모 | 14 ms | 0 | 0.2초 | 1.08초 | 0 | 0.99초 | 34건 | 4.1 ms / 206 ms | +| Pure, 메모 없음 | 15 ms | 0 | 0.3초 | 2.73초 | X25519 10,000 | 0.86초 | 34건 | 4.6 ms / 221 ms | +| Pure, 메모, SD 카드 | 29 ms | 2 | 0.3초 | 1.06초 | 0 | 0.94초 | 269건 | 111 ms / 267 ms | +| quinn | 1.5 ms | 10 | 10.9초 | 8.30초 | 핸드셰이크 10,115 | 9.14초 | 연결 10,115개 | 5.3초 / 11.2초 | + +- 평소에는 받는 쪽도 보내는 쪽도 초당 약 0.1초의 CPU를 쓴다. 재시작 뒤 10초는 그 10배 안팎이 평소 몫이다. + - Pure는 메모가 있으면 재시작 뒤 CPU가 평소와 같다. + - 메모가 없으면 1.6초 더 든다. X25519 1만 번(각 0.165 ms)의 값이다. + - quinn은 받는 쪽이 7.2초, 보내는 쪽이 8.0초 더 쓴다. 우리 클라이언트는 인증서를 확인하지 않으므로, 실제 클라이언트는 더 + 든다. +- Pure의 모든 라운드에서 만든 주문, 저장됐다는 말을 받은 주문, 받는 앱이 적용한 주문의 수가 같았다(8만여 건). 잃거나 겹친 것이 + 없다. +- Pure의 기기는 재시작을 알아채지 않는다. 답이 오지 않은 주문을 다시 보낼 뿐이다. 1만 개 가운데 그때 답을 기다리던 30여 개다. +- SD 카드에서는 저장마다 동기화가 느려 p50이 4.1 ms다. 재시작 중에 밀린 것이 조금 더 많았다(269건). 그래도 0.3초 만에 + 따라잡았다. +- quinn은 새 서비스가 옛 연결에 리셋을 보낼 수 있는데도, 첫 1초 동안 저장이 하나도 없었다. 클라이언트의 1초 시한과 같은 + 길이다. 리셋이 닿지 않은 연결이 시한을 기다렸을 것으로 보지만, 원인은 확인하지 않았다. 그 뒤 핸드셰이크가 서비스의 한 + 스레드를 채웠다. 스레드를 늘리면 따라잡는 시간은 줄지만, 핸드셰이크 1만 번의 CPU는 그대로다. 서버는 핸드셰이크마다 X25519 + 둘(임시 키와 합의)과 ECDSA 서명 하나를 한다. + +**M4.** 처음 보는 상대 100개에게 하나씩 주문 하나를 보내고, 저장됐다는 말(quinn은 답)을 받기까지를 쟀다. 비특권 네트워크 +이름공간에서 루프백의 UDP만 netem으로 늦췄다. + +| 한쪽 지연 | RTT | Pure p50 | Pure 왕복 | quinn p50 | quinn 왕복 | +|---:|---:|---:|---:|---:|---:| +| 5 ms | 10 ms | 10.6 ms | 1.06 | 21.0 ms | 2.10 | +| 25 ms | 50 ms | 50.9 ms | 1.02 | 101.2 ms | 2.02 | +| 50 ms | 100 ms | 100.7 ms | 1.01 | 201.2 ms | 2.01 | + +- Pure는 첫 패킷이 이미 봉인된 기록이다. 받는 쪽이 저장하고 답하면 끝이라 1 RTT다. 받는 쪽의 X25519와 저장은 1 ms 안쪽이다. +- QUIC은 핸드셰이크에 1 RTT, 주문에 1 RTT가 든다. 세션 티켓의 0-RTT는 다시 만날 때만 되고, 재전송 공격에 열려 있다. + 재시작한 서비스는 티켓 키를 저장해 두지 않는 한 티켓을 받지 못한다. + +## 판정 + +- **M2는 통과다.** 받는 쪽을 kill -9 해도 핸드셰이크 없이 이어진다. 메모가 있으면 재시작에 비대칭 연산이 들지 않는다. 기록을 + 잃거나 겹치지 않았다. 011의 두 중단 기준 모두에 걸리지 않는다. +- **M4는 1 RTT다.** QUIC의 절반이다. 봉인한 첫 패킷이 기록이기 때문이다. 011이 비교 대상으로 적은 QUIC의 1-RTT는 핸드셰이크만의 + 값이고, 기록까지는 2 RTT다. +- H2가 섰다. 093은 정확성을, 여기서는 값을 봤다. 재시작의 값은 연결 없는 모델에서 거의 0이다. 연결이 있는 모델에서는 연결 수에 + 비례한다. + +## 한계와 다음 + +- **처음 만남은 여전히 X25519 한 번이다.** 새 보내는 이를 받는 속도는 초당 약 3,700이다(094). 쓰레기 패킷으로 이것을 강요하는 + 공격은 메모로 알려진 키에 대해서는 사라졌다. 모르는 run의 첫 패킷마다 드는 HKDF 두 번은 남는다. 비율 제한은 보안 단계에서 + 둔다. +- **메모는 허용 순서에 묶인다.** 허용 목록의 순서가 바뀌면 칸이 맞지 않아 다시 계산한다. 정확성에는 영향이 없다. +- **QUIC 비교는 quinn 하나다.** ngtcp2는 아직이다. +- **보내는 쪽.** 링크마다 스레드 하나다(094). +- 다음은 011의 순서대로다. + - 에폭 바꿈(전방 비밀성), 경로 바뀜, 저장소 옮기기(H3, M3), 보안 검사를 한다. + - 그 뒤 M5와 M6 가드레일을 잰다. |