Luavis' Dev Story

🚦Multitasking 201 1편

2021-12-31T00:33:00+09:00

반성문

올 한해에는 개인적으로 많은 일들이 있었습니다. 해의 시작은 이직준비로 부터 시작되었고 TL로 마무리 지어야하는 프로젝트들도 있었습니다. 현재는 새로운 직장에서 비교적 하던 일과는 다른 다양한 플랫폼을 맡으면서 일하고 있는데 병특도 시작하고 회사일도 매우 바빠서 항상 핑계대면서 또 스스로 공부해야하는 방향도 살짝 잃어서 블로깅을 게을리 했습니다.

이 블로그는 스스로 무언가 깊게 공부하거나 실험해보고 난 결과를 이야기하고 싶었지만 최근에 공부하는 RL이나 알고리즘 쪽은 내가 잘 안다고 할만한 입장이 아닌것 같아서 쓰기 좀 부끄러워 글 쓰기도 회피하게 되고 안 쓰다 보니 블로그와 거리가 멀어진것 같습니다.

그래도 원래부터 써오던 도메인도 슬슬 만료기간이 다가와서 이전부터 바꾸고 싶었던 .kr 도메인도 버렸고, 연말을 맞아서 마음을 가다듬고 이전에 작성했던 글을 정리해 올리고, 앞으로는 조금 더 가벼운 주제도 가볍게 쓸 수 있도록 하고 배우고 느꼈던것들에 대해서도 간단히 적어보도록 하려합니다. 사실 이전에 적었던 글들이 글을 처음 써보는 입장이기도 했고 번역투인것도 많고 (지금이라고 다른건 아니지만) 미숙했던 점들이 많아서 좀 수정 보완하는 작업도 진행해보고 싶지만… 이건 시간이 많이 들어서 어떻게 될지 모르겠네요. 그래도 관련 키워드로 검색하면 맞춤 검색인지 모르겠지만 상단 노출되어서 (…) 부끄러워서라도 고쳐볼까 합니다.

본문

한 CPU에 여러 코어가 있는 multi-core 형태의 프로세서가 산업 표준이 되면서 한번에 하나의 작업을 처리하지 않고 작업을 다중으로 처리하는(multitasking) 것은 아주 오래전부터 사용되었고 구현하는 방법도 매우 다양합니다. 엔지니어가 가장 쉽게 multitasking을 구현하는 방법은 적어도 저에게는 thread일 것입니다. 고전적인 방법이지만 모든 언어와 플랫폼에서 지원하는 방식의 multitasking을 처리하는 방법입니다.

하지만 multitasking을 구현하는 방법은 thread를 이용하는 것만 있는것은 아니고 다양한 패턴을 활용하여 구현할 수 있습니다. multitasking에 관련된 용어나 방법들에 대해서는 저는 경험적으로 얻었던 지식이라 스스로도 정리가 잘 안되어있습니다. 그래서 이번에 개념과 용어를 프로그래밍 언어의 런타임에서는 어떻게 구현되어 있는지도 알아보려합니다. 이 글의 시리즈에서는 Concurrent vs Parallel, Preemptive vs Non-preemptive multitasking의 개념에 대해서 알아보고 이어서 Coroutine, Generator, Thread, Async/Await, Reactive의 개념들과 Python과 Go 언어에서는 각 개념을 어떻게 런타임에 구현했는지 커널 레벨에서 동작에 대해서 설명할 예정입니다.

Concurrent와 Parallel의 동질성

우선 Concurrent의 영영사전 뜻을 확인하면 다음과 같습니다.

Concurrent

the fact of two or more events or circumstances happening or existing at the same time.

복수의 사건이나 상황이 같은 시간에 벌어지거나 존재하는 것 이라는 해석이 가능합니다. 같은 시간이라는 말이 조금 애매하지만 아래 예제를 생각해보면 이해가 쉽습니다.

그 사람은 동시에 요리 3개를 할 수 있다.

예를 들어 요리를 하는데 파스타도 하고 스테이크도 구우면서 치킨도 같이 구워 손님에게 서빙할 수 있다면 이 사람은 동시성을 갖는 요리사라고 볼 수 있습니다.

동시라는 말은 애초에 단어의 한자 뜻에서 나타나 듯 (concurrent라는 영어도 마찬가지로) 같은 시간에 복수의 일을 처리하는 경우 붙일 수 있습니다. 위의 문장을 CS에서 사용하는 용어로 살짝 바꾸면.. 아래와 같습니다.

워커 하나가 동시에 요청 100개를 처리한다.

하나의 워커가 동시에 요청을 100개 처리하면 동시성을 갖는 워커라고 볼 수 있습니다. 일반적인 자바 서버로 보면 풀에 워커 프로세서가 있을것이고 워커마다 사용가능한 스레드 풀이 따로 있기에, 하나의 워커는 항상 동시에 복수의 요청을 처리할 수 있습니다. 따라서 하나의 워커는 항상 동시성을 갖고 있다 말할 수 있습니다.

다수의 작업을 동시에 처리하는 것을 두가지 방법이 있습니다. 작업자가 해야할 일을 나눠서 동시에 작업하는 방법이 있고 애초에 복수의 작업자가 동시에 처리하는 방법이 있을것 입니다.

아까 예를 들었던 요리의 예를 들자면 해야하는 요리는 총 3개라면 한명의 요리사가 가스렌지가 갖고 있는 가용성을 충분히 끌어내서 스테이크와 파스타를 적절한 타이밍을 맞춰가면서 만들어내고 그와 동시에 오븐에 치킨도 굽는다면 동시에 일을 동시에 처리했다고 볼 수 있습니다. 하지만 이런 방법 말고 3개의 요리를 애초에 서로 다른 3개의 주방에서 서로 다른 3명의 요리사가 각각 한명씩 자신만의 요리를 진행한다면? 이 또한 동시에 요리를 만들었다고 볼 수 있습니다.

위의 예제에서 후자는 동시성을 갖기 위해서 병렬적으로 일을 처리했다고 볼 수 있습니다. 두 개념을 비교하면 동시성은(concurrency)는 항시 다른 작업을 위해서 양보할 수 있는 상태(interruptability)를 말합니다. 병렬성(parallelism)은 다른 작업들이 모두 독립적으로 처리되고 있는 상태(independentability)를 일컫습니다.

마치 한명의 요리사가 동시 작업을 하면 스테이크를 뒤집고 나면 파스타를 살펴보며 소스를 넣어주고 그 다음에는 오븐의 예열이 끝난 알람을 듣고 치킨을 오븐에 넣는것 같이 말입니다. 하지만 병렬성을 갖는 방법인 후자의 방법은 모든 작업 즉 요리가 각자 독립성을 갖고 각각의 요리사가 요리하게 됩니다.

이를 CS에서 바라보면 다수 프로세서 (multiprocessor, 흔하게는 멀티 코어)를 이용해서 다수의 일을 처리하면 병렬적으로 동시성 있게 일을 처리하는 방법입니다. 만약 하나의 프로세서(이는 싱글코어)에서 다수의 일을 처리한다면 이는 동시성이 있다고 이야기할 수는 있지만 각 작업이 독립되어서 처리되지는 않기 때문에 병렬적이라고 이야기할 수 없습니다.

그러면 병렬적으로 일을 처리하면 항상 동시성을 갖을까요? 꼭 그렇지만은 않습니다.

병렬적이나 동시적이지 않을때

병렬로 일을 처리해도 항상 동시적이진 않습니다. 위의 요리예를 다시 한번 더 인용하면 3명의 요리사가 요리하는데 만약 가스레인지가 하나라면 (…) 서로 번갈아 가면서 사용하면서 요리해야하기 때문에 동시성을 갖기 힘듭니다. 이는 CS에서는 critical section이라고 이야기합니다. 공유 변수등의 문제로 인해서 병렬적으로 일은 처리하지만 다른 일이 처리가 끝나기를 mutex를 이용해서 기다리고 처리되야합니다. 이는 병렬적으로 일을 처리하고는 있으나 동시에 처리되는것은 아니게 됩니다. 따라서 동시성과 병렬성이 꼭 subset관계에 있다고 볼 수는 없습니다.

사라진 800MB를 찾아서

2020-12-22T16:33:00+09:00

메쉬코리아 부릉에서는 라이더분들이 배달을 실행하기 위해서 배달 요청을 잡는 일을 AI가 가장 효율적인 배차가 가능하도록 자동으로 할당해주는 시스템인 “추천배차”라는 시스템이 있습니다. 이 추천배차 시스템에서 사용하는 메모리량이 꾸준히 증가하고 있는 이슈가 생겨서 NewRelic과 sysfs를 이용해서 원인을 파악해보고 누수가 생긴 이유까지 찾은 이야기를 글로 적은 내용입니다.

문제를 찾아가는 과정

[꾸준히 상승하는 메모리 사용량]

7일만에 메모리가 약 3배 이상으로(대략 600M → 1.4G) 올라가면 문제가 있다고 판단했고 해당 문제의 원인을 파악해보기 위해서 소스코드를 확인해봤지만 별다른 이상한 점은 발견하기 힘들었습니다. 그렇다면 자바 Heap 영역에서 문제/누수가 발생하고 있는것은 아닌지 확인해볼 필요가 있어서 APM에서 나오는 Heap 메모리의 사용량도 확인해보았고, Thread stack 메모리가 사용하는 메모리는 아닐까 의심되어 확인해봤지만 Thread 수에도 큰 문제가 발생하지 않는것을 확인할 수 있었습니다.

[평화로운 JAVA heap memory]

문제가 java에 있지 않다면 NewRelic의 수집 방식에 문제가 있거나 혹은 linux 시스템적으로 사용하는 메모리가 증가하고 있을거라 생각이 되어서 k9s를 이용해서 kubernetes가 판단하고 있는 현재 메모리 사용률에 대해서 확인해봤습니다. 확인해본 결과 kubernetes에서 사용하는 판단하는 메모리 사용량은 635MB 정도로 자바가 차지하는 Heap memory를 고려할때 이상이 없는 수치라고 생각이 됩니다. 그러면 문제는 없어진 800M의 메모리는 어디로 간 것인가 입니다. 이 문제를 파악해보기 위해 많은 리서치를 해봤고 하나 알아낸것은 컨테이너를 매니징하는 프로그램(docker와 같은)과 newrelic이 생각하는 메모리와 kubernetes가 생각하는 메모리가 다르다는 것을 확인할 수 있었습니다.

리눅스는 머신이 갖고 있는 메모리를 swap, 캐시, 버퍼 캐시 등등 다양한 방법으로 최대한 많은 메모리를 사용하여 머신의 성능을 끌어올립니다. 따라서 한 process가 memory를 사용한다는 개념이 어떤 부분(RSS, cache, …)들을 사용량으로 볼 것인지 조금씩 다르다는것을 확인할 수 있었습니다.

docker와 NewRelic에서는 RSS와 그외 buffer / cache등 모든 메모리 사용의 총합을 고려해서 판단합니다. 하지만 이와 반대로 k8s에서는 memory 사용량을 kubelet으로 확인하면 물리적 메모리 사용량(RSS)를 가져가는것으로 확인했습니다. 이에 대한 discussion이 이 글에 자세히 나와 있습니다.

The value K8sContainerSample.memoryUsedBytes will pull the usageBytes metric from the /stats/summary endpoint of the kubelet, scoped to the container. As you noted that value included the linux buffers and cache.

따라서 위의 NewRelic 대시보드에 메모리 사용도 application에서 사용하는 실제 메모리가 아닌 시스템 레벨에서 사용되는 메모리에 문제가 있을 것이라 추측할 수 있었습니다. 따라서 추천배차 시스템에서 RSS의 사용량 추세가 수평적인지 선형적인지를 판단해보면 cache외의 메모리또한 증가세인지 확인할 수 있습니다. 이를 위해서는 NewRelic의 Insights를 통해서 NRQL을 사용해 확인해볼 수 있었습니다.

[평화로운 memoryWorkingSetBytes]

NRQL> SELECT average(memoryWorkingSetBytes / 1000000) AS ‘MB of Mem’ FROM K8sContainerSample FACET clusterName, podName, containerName TIMESERIES LIMIT 50 Since 1 week ago UNTIL 1595409275180 WHERE containerName IN (‘***’)

NewRelic에서는 RSS를 memoryWorkingSetBytes라는 이름으로 수집하고 있고 이 메모리 사용량만 확인해보면 기간 대비 평탄한 사용량을 갖고 있음을 확인할 수 있었습니다. 그러면 나머지 800M의 메모리는 어떻게 누가 먹고 있는가를 확인해보기 위해서 찾아봤습니다.

실제 컨테이너에 접속하여 확인해봤는데 ps, free 와 같은 커맨드를 사용할 수도 설치할 수도 없어서 확인이 어려웠지만, 이 프로그램들은 procfs를 읽어서 사용하기 때문에 컨테이너의 정보가 아닌 실제 물리머신 node의 성능이 나옵니다. 일례로 container에 접속하여 /proc/meminfo 를 확인하면 약 64기가, 물리 머신의 성능이 나오는 것을 확인할 수 있습니다.

...
MemTotal:      		65150604 kB
MemFree:       		41145196 kB
MemAvailable:       49117724 kB
Buffers:       		    2088 kB
Cached:       		 7098816 kB
...

따라서 현재 컨테이너를 확인해보고 싶다면 다른 방법을 찾아봐야합니다.

리눅스에서는 container라는 추상적인 개념을 cgroup를 이용해 구현했기 때문에 이 정보를 커널로부터 얻어올 수 있는 곳은 sysfs입니다. /sys/fs/cgroup에는 현재 cgroup에 관한 정보를 조회할 수 있습니다. 이 밑에 memory에는 다양한 메모리 지표를 뽑아서 확인할 수 있는 파일들이 있습니다. 가장 human readable한 정보가 나오는 곳은 /sys/fs/cgroup/memory/memory.stat 파일입니다.

$ cat /sys/fs/cgroup/memory/memory.stat
cache 822972416
rss 652750848
rss_huge 0
shmem 0
mapped_file 86016
...

확인해보면 cache memory가 822972416 B로 찾아다녔던 그 800M의 메모리인것을 확인할 수 있습니다. 그러면 memory.stat에서 말하는 cache라는 지표가 어떤 값을 의미하는지 확인해볼 필요가 있기 때문에 검색해 봤고 리눅스 커널 docs의 cgroup memory에 5.2 section에 아주 잘 설명되어 있습니다.

cache		- # of bytes of page cache memory.
rss		- # of bytes of anonymous and swap cache memory (includes
		transparent hugepages).
rss_huge	- # of bytes of anonymous transparent hugepages.
mapped_file	- # of bytes of mapped file (includes tmpfs/shmem)
pgpgin		- # of charging events to the memory cgroup. The charging
		event happens each time a page is accounted as either mapped
		anon page(RSS) or cache page(Page Cache) to the cgroup.
...

커널 documentation에서는 cache를 page cache memory 바이트 수라고 이야기하고 있습니다. page cache는 Block device I/O 시에 리눅스가 성능의 최적화를 위해서 사용하는 메모리로 파일 내용을 임시적으로 저장해두는 장소입니다. 자세한 설명

결론: 없어진 800M 은 페이지 캐시였다.

문제의 근본 원인을 찾아서

여기까지 왔을때는 아 그냥 캐시가 많이 쌓이네 뭐 상관 없지 않을까? 라고 생각했지만 다른 서비스는 전혀 이런 문제가 생기지 않는데 추천배차에서만 생긴다는것도 이상했고 무엇보다 file I/O 작업이 없는 서비스인데 이렇게 많은 캐시가 쌓이는 것도 이상하다는 생각이 들어서 조금 더 drill down 해보기로 했습니다.

혹여나 놓쳐진 부분이 있지 않을까 싶어서 procfs를 찾아서 열려있는 fd(file descriptor)를 확인해봤습니다. /proc/1/fd를 리스팅하면 모든 fd number와 해당하는 파일에 대해서 열람할 수 있습니다.

...
lr-x------ 1 jhipster jhipster 64 Jul 21 10:02 28 -> /home/jhipster/app.war
lr-x------ 1 jhipster jhipster 64 Jul 21 10:02 28 -> /usr/local/openjdk-8/lib/charsets.jar
lrwx------ 1 jhipster jhipster 64 Jul 21 10:02 26 -> socket:[859629097
l-wx------ 1 jhipster jhipster 64 Jul 21 10:02 27 -> /tmp/spring.log
lr-x------ 1 jhipster jhipster 64 Jul 21 10:02 28 -> /tmp/instrumentation7299792729183652257.jar
...

fd에는 다양한 파일들이 있지만 jar, war 파일을 제외하면 Block I/O가 발생할 수 있는 파일은 27번 /tmp/spring.log 파일이 가장 유력해보였습니다.

$ du -h
32K  ./hsperfdata_jhipster
0    ./hsperfdata_root
794M .

800M가 없어진 원인을 찾았습니다. /tmp에 파일을 썼을때 쓴 만큼 cache 메모리에 쌓이는지 실험해봤고 비슷한 정도로 쌓이는 것을 확인할 수 있었습니다. 다른 애플리케이션과 대비해서 추천배차에서 문제가 있었던것은 log의 level이 잘못 설정되어 있어서 많은 로그가 쌓이게 되었고 이 로그가 컨테이너 안에 파일형태로 남게 되면서 쓰는 과정에 cache로 남아있는것을 확인할 수 있었습니다.

container는 로그를 포함함 쓰기 작업을 컨테이너 내에서 하는것을 비권장합니다. stateless하지도 않고 위와 같은문제가 발생할 수 있습니다. 특히나 로그는 docker logs와 같이 container manager의 로그 시스템과 연결되지 않는다면 로그 수집 과 관리가 어려움으로 이런 부분은 특히나 조심해야합니다. spring에서는 이 문제를 log appender의 설정을 변경하여 해결할 수 있습니다.

Spatial data를 10,000배 잘 다루게 된 방법

2020-11-19T14:53:00+09:00

올해 3월에 물류중점 회사 메쉬코리아로 이직하고 개인 사정도 있어서 블로그 작성을 게을리 했는데, 최근에 성능 개선한 case는 블로그 글로 작성해둘 필요가 있다고 생각되고, 이 글외에도 사내에서 공유했던 글들에 대해서도 잘 정제해서 블로그 글로 작성해야다는 생각이 들었습니다.

메쉬코리아는 음식, 화장품, 편의점 상품과 같은 상품을 실시간으로 배달하는 서비스, 부릉(Vroong)을 운영하는 회사입니다. 배달 주문을 처리하기 위해서는 상품을 판매하는 상점과 상품을 주문한 고객 사이의 거리와 장애물등을 고려하여 처리할 수 있는 처리할 수 있는 주문건인가 배달 기사님에게는 얼마만큼의 금액을 지불해야하고 상점에서는 얼마만큼의 금액을 받아내야하는가를 판단하기 위해서 spatial data를 이용해 각 상점의 배송 가능한 권역들 배달이 불가능한 권역들을 관리하는 권역 시스템을 운영하고 있습니다.

권역 시스템에서는 spatial data를 효율적으로 다루기 위해서 PostgreSQL에서 지원하는 PostGIS를 이용하고 있습니다. 여러가지 성능 문제가 있었지만 대부분의 경우는 가벼운 문제들이었습니다. 다만 지도 화면에서 보이는 영역과 행정동/법정동 polygon의 intersects를 계산하고 polygon을 가져오는 문제는 큰 성능 이슈를 갖고 있었습니다. worst case에서는 조회시간이 60초 정도 걸렸습니다. 문제가 되는 성능이 떨어지는 쿼리는 아래와 같았습니다.

SELECT region.*
FROM region
INNER JOIN address_polygon on region.pk=address_polygon.region_pk
INNER JOIN address on address_polygon.address_pk=address.pk
WHERE address.address_type = 'LEGAL'
AND region.region_type = 'ADDRESS_REGION'
AND region.status = 'ENABLED'
AND st_intersects(
    region.polygon,
    ST_MakeEnvelope(126.9373539, 37.5210172, 127.0540836, 37.5873607, 4326)
);

[쿼리1]

이 글은 이 문제를 어떻게 해결할 수 있는가 방법에 대한 과정과 최대 1만배 성능을 튜닝한 이야기입니다.

Spatial data의 intersects의 계산 방법

문제 상황에서 사용하는 spatial data는 2d의 polygon 입니다. 그리고 intersects는 두개의 polygon이 겹치는지를 판단하는 연산을 의미합니다. 이를 postgresql에서는 아래와 같이 사용합니다.

SELECT * FROM region WHERE region
AND st_intersects(
    region.polygon,
    ST_MakeEnvelope(126.9373539, 37.5210172, 127.0540836, 37.5873607, 4326)
);

[쿼리2]

위 쿼리는 region 테이블의 polygon 컬럼과 서울 종로구 부근의 영역을 비교하여 겹치는 영역이 있는가를 조건으로 select 합니다. 약 천만개의 row가 있는 region 테이블에서도 0.5초내외의 성능을 보여주면서 의외로 빠른 성능을 보여줍니다. intersects 연산이 단순하게 생각하면 무거운 연산일거라 추측할 수 있습니다. 이 쿼리가 어떻게 빠르게 동작할 수 있는것인지 의문이 드는데, 이게 가능한 방법이 있습니다. R-Tree라는 자료구조를 사용한 index 구조를 통해 계산하면 intersects 계산을 빠르게 할 수 있다고 합니다.

R-tree의 인덱싱 방법은 B-tree와 유사한데, polygon 데이터들의 최소한의 bounding box를 구하고 그 박스간의 포함관계를 B-tree의 형식으로 관리하는 index tree입니다. 이렇게하면 B-tree의 범위 조회와 같은 계산 방법으로 계산하면 포함관계와 교차관계(intersects)를 쉽게 계산할 수 있습니다. index search를 통해서 대충 intersects하는 polygon을 bounding box가 아닌 실제 polygon과의 intersects 연산을 한번 더 진행해서 진짜 원하는 polygon이 맞는지 한번 더 선별과정을 거칩니다.

이 권역 서비스는 처음부터 프로젝트에 involve된게 아니었기 때문에 위의 문제의 쿼리1을 만났을때는 쿼리2를 테스트 해보지 않았습니다. 따라서 천만개의 row에 대해서 intersects를 모두 계산한다고 생각해서 어떻게 해도 빠르게 할 수 있는 방법이 없다고 생각했습니다. 따라서 모든 폴리곤을 메모리에 올리고 최적화된 알고리즘을 구현해야겠다는 생각하면서 찾아보다가 R-tree에 대해서 알게되었습니다. R-tree 성능에 대해서 Python으로 구현해보고 충분히 빠른것을 확인했습니다. Python에서는 R-tree의 구현을 ctypes를 이용해 libspatialindex를 래핑한 라이브러리를 찾을 수 있었습니다.

그래서 PostGIS는 이런거 지원 안하나 싶어서 찾아보게 되었는데 PostGIS도 R-tree와 같은 bounding box indexing을 지원한다는 것을 알게되고 심지어 해당 인덱싱이 위의 쿼리에 polygon 컬럼에 적용되어 있는것을 확인했습니다.

정확히는 PostGIS는 R-Tree라는 이름으로 사용하지 않고 GIST 라는 이름으로 index 방법을 제공하고 있는것을 알게되었습니다. 그리고 위 GIST의 링크를 읽어보면 나와 있는데, bounding box간의 연산을 위해서 postgresql에서는 특수한 연산자를 따로 지원하고 있습니다. 또한 st_intersects는 이미 내부에서 && 연산자를 통해서 bounding box간의 연산을 하고 AND 조건으로 실제 polygon이 intersects 하는 가 판단한다는 것을 알게되었습니다. 이 사실을 알고 위 쿼리 2를 작성해서 쿼리해보고 0.5초의 성능이면 1분에 비해서는 성능이 엄청나게 좋은 성능이 나온다는것을 알게되어서 어떻게 이정도의 차이를 갖게 되는지 좀 더 정확히 알아보고자 explain analyze를 해보게 되었습니다.

Index Scan using polygon_geom_idx on region  (cost=0.42..513509.60 rows=... width=...) (actual time=0.136..515.878 rows=... loops=1)
    Index Cond: (polygon && '...'::geometry)
    Filter: _st_intersects(polygon, '...'::geometry)
    Rows Removed by Filter: 383
Planning Time: 0.244 ms
Execution Time: 522.464 ms

위 explain 결과를 보면 index condition으로 polygon column 과 && 연산을 통해서 bounding box를 주어진 polygon 데이터와 비교하고 후에 filter 조건으로 _st_intersects를 사용하는것을 확인할 수 있습니다.

그러면 문제는 어디서 발생하는걸까?

그러면 문제가 된 쿼리 1은 도대체 무슨 문제가 있었던 것인지 싶어서 해당 쿼리도 explain analyze를 돌려보았습니다.

Gather  (cost=1080.01..67698.36 rows=... width=1894) (actual time=117.101..66590.220 rows=... loops=1)
  Workers Planned: 1
  Workers Launched: 1
  ->  Nested Loop  (cost=80.01..66697.06 rows=8 width=1894) (actual time=66.379..65641.273 rows=134 loops=2)
        ->  Nested Loop  (cost=79.58..51221.10 rows=1996 width=8) (actual time=63.748..5975.698 rows=401872 loops=2)
              ->  Parallel Bitmap Heap Scan on address  (cost=79.14..10717.49 rows=1714 width=8) (actual time=57.163..61.659 rows=2526 loops=2)
                    Recheck Cond: ((address_type)::text = 'LEGAL'::text)
                    Heap Blocks: exact=107
                    ->  Bitmap Index Scan on address_address_type_index  (cost=0.00..78.42 rows=2914 width=0) (actual time=100.710..100.710 rows=5504 loops=1)
                          Index Cond: ((address_type)::text = 'LEGAL'::text)
              ->  Index Only Scan using address_polygon_pkey on address_polygon  (cost=0.43..23.23 rows=40 width=16) (actual time=0.579..2.307 rows=159 loops=5052)
                    Index Cond: (address_pk = address.pk)
                    Heap Fetches: 304308
        ->  Index Scan using region_primary_key on region  (cost=0.43..7.75 rows=1 width=1894) (actual time=0.147..0.147 rows=0 loops=803744)
              Index Cond: (pk = address_polygon.region_pk)
              Filter: ((optimized_polygon_30 && '...'::geometry) AND ((region_type)::text = 'ADDRESS_REGION'::text) AND ((status)::text = 'ENABLED'::text) AND _st_intersects(optimized_polygon_30, '...'::geometry)
              Rows Removed by Filter: 1
Planning Time: 3.403 ms
Execution Time: 66590.472 ms

해당 쿼리를 살펴보면 polygon의 index를 타지 않고 쿼리가 되는걸 확인했습니다. 다양한 방법으로 해당 쿼리를 시도해봤는데, 거의 대부분 address_address_type_index를 타는것을 확인할 수 있었습니다. 왜 그런지 이유를 찾아보고 싶었지만 명확하게 알수 있는 방법은 없었고 추론할 수 있는 근거들에 대해서는 몇 가지 알게되었습니다. 가장 타당하다고 생각되는 근거는 위 Spartial indexing에 대한 document에서 확인할 수 있었습니다.

it is not always faster to do an index search: if the search is going to return every record in the table, traversing the index tree to get each record will actually be slower than just sequentially reading the whole table from the start.

postgresql이 경우에 따라서 index를 타는 것이 비효율적이라 판단되면 풀서치하는 방향으로 optimize하는걸 알게되었습니다. 어떤 기준으로 하는지가 불명확하고 vacuuming 해도 index를 사용할때도 있고 안할때도 있어서 단순히 vacumming으로는 일관적인 성능을 보장하기는 어렵다고 판단했습니다.

위에 region의 테이블이 약 천만개의 row가 있는데 실제로 그중 행정동/법정동과 시군구, 시도의 모든 폴리곤을 58,000개 정도 밖에 안되서 postgresql이 spatial index를 타는게 이득이 될 수 있다 판단할 수 있도록 row 수를 줄이고, join을 풀어서 spatial index와 address_type index를 병렬로 사용할 수 있도록 하기 위해서 table을 합칠까 생각하던 중 materialized view를 떠올리게 되었습니다.

oracle, postgresql, mariadb 에서는 일반적인 view와는 달리 물리적으로 어느정도의 데이터를 저장하고 view의 columne에 index를 적용할 수 있는 materialized view를 지원합니다. join 조건을 materialized view로 만들어서 최적화하고 polygon 컬럼에 index를 적용 시켜준다면 spatial index 사이즈가 작아지면서 postgresql이 cost 계산을 더 잘 할 수 있을거라 추측해서 아래와 같이 적용해봤습니다.

CREATE MATERIALIZED VIEW address_region_view AS
SELECT ap.region_pk, region.polygon, ap.address_type FROM (
    SELECT address_polygon.region_pk, address.address_type FROM address
    LEFT JOIN address_polygon ON address.pk = address_polygon.address_pk
    WHERE address.address_type IN ('LEGAL', ...)
) ap
LEFT JOIN region ON region.pk = ap.region_pk
WHERE region.region_type = 'ADDRESS_REGION'
AND region.status = 'ENABLED';

CREATE INDEX address_region_view_idx ON address_region_view using gist(polygon);
CREATE INDEX address_region_view_address_type_idx ON address_region_view (address_type);

쿼리1의 조건을 view로 녹여내고 index를 적용한 address_region_view를 통해서 같은 결과가 나와야하는 쿼리를 재구성하여 explain을 통해 성능을 측정해봤습니다.

SELECT region.*
FROM address_region_view
LEFT JOIN region ON region.pk = address_region_view.region_pk
WHERE address_region_view.address_type='LEGAL'
    AND st_intersects(
        address_region_view.polygon,
        ST_MakeEnvelope(126.9373539, 37.5210172, 127.0540836, 37.5873607, 4326)
    );

위 쿼리를 사용하여 explain 해보면결과는 아래와 같습니다.

Nested Loop Left Join  (cost=166.64..825.34 rows=32 width=1533) (actual time=1.660..6.270 rows=... loops=1)
  ->  Bitmap Heap Scan on address_region_view  (cost=166.21..554.86 rows=32 width=8) (actual time=1.645..5.412 rows=... loops=1)
        Recheck Cond: ((polygon && '...'::geometry) AND ((address_type)::text = 'LEGAL'::text))
        Filter: _st_intersects(polygon, '...'::geometry)
        Rows Removed by Filter: 2
        Heap Blocks: exact=270
        ->  BitmapAnd  (cost=166.21..166.21 rows=95 width=0) (actual time=1.573..1.573 rows=0 loops=1)
              ->  Bitmap Index Scan on address_region_view_idx  (cost=0.00..52.81 rows=1137 width=0) (actual time=0.488..0.488 rows=1281 loops=1)
                    Index Cond: (polygon && '...'::geometry)
              ->  Bitmap Index Scan on address_region_view_address_type_idx  (cost=0.00..113.14 rows=4896 width=0) (actual time=1.003..1.003 rows=5048 loops=1)
                    Index Cond: ((address_type)::text = 'LEGAL'::text)
  ->  Index Scan using region_primary_key on region  (cost=0.43..8.45 rows=1 width=1533) (actual time=0.003..0.003 rows=1 loops=...)
        Index Cond: (pk = address_region_view.region_pk)
Planning Time: 0.686 ms
Execution Time: 6.408 ms

총 실행시간이 66,590ms에서 6.4ms에 가깝게 줄어든것을 확인할 수 있었습니다.

결론

spatial data를 한 테이블에 너무 많은 데이터를 넣으면 index연산할때 원하지 않는 방식으로 계산할 여지가 있습니다. 따라서 최대한 실제 application이 필요로 하는 데이터만을 추려서 materialized view로 만든다면 성능에 개선이 있을 수 있습니다. 줄여말하면, 기초에 충실하게 생각하면 된다는 교훈을 얻을 수 있습니다…

G1: Garbage first garbage collector

2019-06-21T21:50:00+09:00

최근에 Presto를 쓰면서 G1 GC를 기본값으로 설정하라는 설명을 보고선 2015년경에 번역을 허락 맡았던 글이 기억났다. 그 당시에는 무슨 객기로 번역을 허락 맡았는지 모르겠지만 지금에 와서 자바의 GC는 Parallel GC를 기본으로 사용했지만, Java 9부터는 G1 GC가 기본값으로 설정되면서 번역을 할 원동력이 생겨서 번역을 해본다. 다만 원본 글이 오래된 글이고, 이를 보충하기 위해서 주석을 다는 형식으로 번역해보았다. 밑에 부터의 글은 InfoQ에 작성된 Monica Beckwith님의 글 G1: One Garbage Collector To Rule Them All을 번역한 글이다.

이미 많은 글들에서 튜닝이 제대로 되지 않은 GC가 애플리케이션의 서비스 수준 협약(SLA)를 지키지 못하게 만드는지 이야기하고 있다. 예를들어 예기치 않게 지연된 GC로 인한 시스템 정지는 다른 정상적인 애플리케이션이 필요로하는 응답시간 요건을 넘어버린다. 게다가 CMS GC와 같이 compacting을 하지 않는 GC의 경우엔 파편화된 heap 메모리 회수하기 위해 STW(stop-the-world)를 걸리는 Serial한 Full GC를 사용하게되는데 이럴 경우 비정상성은 증가하게 됩니다.

메모리 할당을 위해 Young 영역에 메모리 할당을 시도했지만 실패하여 Young 영역에 GC가 발생하면, 살아남은 객체는 Old 영역로 올라가게 될 것이다. 더 나아가 파편화된 Old 영역의 메모리 공간이 새롭게 Young 영역의 객체가 올라오기에 충분한 공간이없다고 가정한다면, 이런 조건에서, heap 영역을 compaction작업을 동반한 Full GC 작업이 발생할 것이다.

CMS GC를 사용하면 Full GC 작업은 병렬처리되지 않고 heap 메모리를 회수하고 compact하기 위한 시간동안 애플리케이션의 모든 스레드를 중지시키는 STW가 발생하게 된다. STW로 중지되는 시간은 heap 사이즈와 살아남은 객체의 숫자에 따라 달라진다.

메모리 파편화를 방지하는 compaction 작업을 병렬로 처리한다 하더라도, Old 영역의 메모리 공간에 여유공간을 얻기 위해, Young과 Old를 포함한 Java의 모든 영역의 메모리를 Full GC를 수행해야하는 것은 변하지 않는다.

이는 Parallel Old GC의 일반적인 사례다. Parallel Old GC를 사용하면, Old 영역의 메모리 회수는 병렬로 Full GC를 처리하는데에 STW가 발생한다. CMS GC와는 달리 Full GC는 점진적으로 처리되지 않고 애플리케이션의 실행 없이 하나의 큰 STW가 발생하게 된다.

Note: HotSpot GC의 관한글을 여기서 읽어보길 바란다.

주) HotSpot GC에 관한 글은 Naver D2의 글에 잘 정리되어 있다.

위 글을 읽어보면 HotSpot의 가장 최신 GC인 G1(Garbage First) GC에 대해서 고려해볼만하다. (JDK7 update 4에 추가됨)

주) Java 9부터는 안정화를 거쳐 기본 GC가 G1 GC임

G1 GC는 위에서 언급한 CMS GC나 Parallel Old GC에 비해서 스레드 정지가 예측 가능한 시간 안에 이루어지는 점진적으로 처리되는 병렬 compacting GC이다. 병렬성과 동시성, 다중화된 masking cycle로 인해 G1 GC는 최악의 경우의 수를 생각해도 괜찮은 정도 수준의 스레드 정지가 발생하기에 더 큰 Heap을 다룰 수 있게되었다. G1 GC의 가장 기본 아이디어는 heap 메모리의 범위(heap 메모리의 크기를 -Xms로 최소치를, -Xmx로 최대치를 설정한다)와 현실적인 목표 스레드 정지 시간(-XX:MaxGCPauseMillis 옵션 사용)을 설정하고 GC가 작업을 할 수 있도록 만들어주는 것이다.

G1 GC를 이해하기 위해서는 기존의 HotSpot에서 사용하는 전통적인 방식인 통으로 되어 있는 자바 heap 메모리를 young 영역와 old 영역로 둘로 나누는 개념을 잊어야한다. G1 GC에서는 “region”이라는 개념을 새로 도입했다. 큰 자바 heap 공간을 고정된 크기의 region들로 나눈다. 이 region들을 free한 region들의 리스트 형태로 관리한다. 메모리 공간이 필요로 해지면, free region은 young 영역나 old 영역로 할당한다. 이 region의 크기는 1MB 에서 32MB로 전체 heap 사이즈 용량이 2048개의 region으로 나누어 질 수 있도록 하는 범위 내에서 결정된다. region이 비어지면 이 region은 다시 free region 리스트로 돌아간다. G1 GC의 기본 원리는 자바 heap의 메모리를 회수할때 최대한 살아 있는 객체가 적게 들어 있는 region을 수집하는 것이다 (목표 정지시간에 최대한 부합하게 하며). 가장 살아 있는 객체가 적을 수록 쓰레기란 의미고 따라서 이름도 쓰레기 우선 수집(Garbage First)이란 이름이 붙게되었다.

그림 1: 전통적인 GC Layout

G1 GC에서 중요한 점은, 전통적인 GC의 힙 구조와는 달리 Young 이나 Old 영역이 인접해 있지 않다는 점이다. 이는 영역의 사이즈가 필요에 따라서 동적으로 바뀔 수 있다는 점에서 편리하다.

Adaptive 사이즈가 지원되는 Parallel Old GC와 같은 GC 알고리즘은 각 영역들이 확장될 일을 대비해 여분의 공간을 남겨둔다. 그렇게 함으로서 Young 영역과 Old 영역을 인접한 상태로 둘 수 있다. CMS의 경우엔 자바의 heap 사이즈와 영역의 사이즈를 조정하기 위해서는 Full GC가 필요하다.

반면 G1 GC는 영역의 개념이 물리적으로 존재하지 않고 논리적으로만 존재함으로써 공간과 시간을 아낄 수 있다. (young 영역의 region들과 그 외에는 old 영역의 region들이 있지 이를 물리적 위치로 구분하지 않는다.)

허나 알아둘것은, G1 GC 알고리즘은 HotSpot의 기본적인 개념은 활용한다는 점이다. 예를 들면 메모리 할당의 개념, survivor 공간으로 카피하고, old generation으로 이동하는 등의 개념은 기존 HotSpot GC의 구현과 비슷하다. Eden region과 survivor region이 여전히 young 영역을 만든다. 무지하게 큰 메모리 할당이 아닌 경우 대부분의 할당은 eden에서 발생한다. (Note: For G1 GC, objects that span more than half a region size are considered “Humongous objects” and are directly allocated into “humongous” regions out of the old generation.) G1 GC는 설정된 스레드 중지 목표 시간에 기반하여 young 영역의 사이즈를 선택한다. young 영역은 설정된 min 부터 max까지의 사이즈 중에서 결정된다. eden이 용량 한계에 다다르면 Young garbage collection이 발생한다. 살아 있는 객체들을 eden인 region에서 부터 ‘from-space’ survivor인 region들로 이동되는데 까지 걸리는 시간동안 STW가 발생한다.

그림 2: Garbar First GC Layout

그 다음, ‘from-space’ survivor region에서 살아남은 객체들은 ‘to-space’ survivor region으로 이동되거나, 객체의 살아남은 횟수가 한계를 넘으면(tenuring threshold), old 영역의 region으로 이동하게 된다. 모든 young 세대의 garbage collection은 병렬로 처리되는 시간과 순차 처리되는 시간이 포함되어 있습니다. 이를 자세히 설명하기 위해 Java에서 나오는 log를 사용해 설명하겠습니다.

원본 글에서는 원본 글에서는 Java 7의 7u25를 사용했지만 이 글에서는 많이 사용되는 Java 8(Java(TM) SE Runtime Environment (build 1.8.0_192-b12))에서 발생하는 로그를 사용했다. 원본 글에서는 GCTestBench 프로그램을 직접 제작한듯 싶은데, 이 글에서는 직접 개발한 GC가 발생되게 하는 소스코드를 직접 작성해서 사용했다.

밑에 있는 커멘드 라인 명령을 통해서 아래의 GC log를 받을 수 있다.

$ java -Xmx1G -Xms1G -XX:+UseG1GC -XX:+PrintGCDetails -XX:+PrintGCTimeStamps benchmark.GCBenchmark

Note: 목표 GC 시간을 기본값으로 사용했고, 이는 200ms이다.

0.276: [GC pause (G1 Humongous Allocation) (young) (initial-mark), 0.0018587 secs]
   [Parallel Time: 0.7 ms, GC Workers: 8]
      [GC Worker Start (ms): Min: 275.9, Avg: 275.9, Max: 276.0, Diff: 0.1]
      [Ext Root Scanning (ms): Min: 0.3, Avg: 0.3, Max: 0.4, Diff: 0.1, Sum: 2.8]
      [Update RS (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.0]
         [Processed Buffers: Min: 0, Avg: 0.0, Max: 0, Diff: 0, Sum: 0]
      [Scan RS (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.0]
      [Code Root Scanning (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.0]
      [Object Copy (ms): Min: 0.1, Avg: 0.2, Max: 0.3, Diff: 0.1, Sum: 1.5]
      [Termination (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.0]
         [Termination Attempts: Min: 1, Avg: 3.5, Max: 6, Diff: 5, Sum: 28]
      [GC Worker Other (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.1]
      [GC Worker Total (ms): Min: 0.5, Avg: 0.5, Max: 0.6, Diff: 0.1, Sum: 4.4]
      [GC Worker End (ms): Min: 276.5, Avg: 276.5, Max: 276.5, Diff: 0.0]
   [Code Root Fixup: 0.0 ms]
   [Code Root Purge: 0.0 ms]
   [Clear CT: 0.2 ms]
   [Other: 1.0 ms]
      [Choose CSet: 0.0 ms]
      [Ref Proc: 0.2 ms]
      [Ref Enq: 0.0 ms]
      [Redirty Cards: 0.1 ms]
      [Humongous Register: 0.0 ms]
      [Humongous Reclaim: 0.4 ms]
      [Free CSet: 0.0 ms]

indent로 병렬처리되는 부분과 순차처리되는 부분을 구분하고 있다. 병렬 처리되는 부분은 아래와 같이 나누어진다.

External Root Scanning: 병렬로 GC worker thread가 Collection Set를 가리키고 있는 register나 thread stack과 같은 external roots를 스캐닝 하는데에 걸리는 시간.
Update Remembered Sets (RSets): RSets는 reference의 region을 알려주어 G1 GC를 돕는다. 여기서의 시간은 병렬처리되는 worker thread가 RSets을 업데이트 하는데에 걸리는 시간이다.
Processed Buffers: worker thread를 통해서 얼마만큼의 Update Buffer가 처리되었는지 보여준다.
Scan RSets: region을 가리키고 있는 RSets을 스캐닝하는데에 얼마만큼의 시간이 걸렸는지 보여준다. 이 시간은 RSets의 구조의 복잡성에 따라 달라진다.
Object Copy: Young GC가 발생하는 동안 GC는 모든 살아 있는 객체를 eden영역이나, from-space survivor영역에서 to-space survivor나 old영역의 region으로 복사한다. worker thread가 이 일을 처리하는데에 걸리는 만큼 시간이 소모된다.
Termination: object scan과 copy등의 작업이 완료되면, 각각의 worker thread는 termination protocol에 들어간다. 종료(terminating) 이전에, worker thread는 다른 thread로 부터 가져올 수 있는 일이 있는지 확인하고 없다면 종료된다. 여기에서 걸린 시간은 worker thread가 종료되기 위해서 종료를 위해서 걸린 시간을 의미한다.
Parallel worker ‘Other’ time: Worker thread가 위에 있는 어떤 항목에도 포함되어 있지 않지만 소모된 시간을 의미한다.

순차처리되는 일들은(물론 각각의 작업은 병렬로 처리될 수 있다.) 아래와 같이 나누어진다.

Clear CT: RSet의 메타데이터를 스캐닝한 Card Table을 클리어 하는데에 걸리는 시간.
그리고 Other 의 시간은 밑에 항목들로 이루어져 있다.
- Choose Collection Set (CSet): Garbage collection cycle은 CSet에 있는 region의 set를 수집하는 일이다. GC 발생시 생기는 정지는 특정 CSet에 있는 살아있는 객체를 비우거나 수집한다. 여기서 걸린 시간은 CSet에 추가되어 있는 region을 finalizing하는데에 걸리는 시간이다.
- Reference Processing: soft, weak, final나 phantom와 같은 GC가 처리과정에서 우선 제외되었던 레퍼런스들을 처리하는데에 걸린 시간이다.
- Reference En-queuing: 레퍼런스들을 pending list에 등록하는데에 걸리는 시간이다.
- Free CSet: collect된 region의 메모리를 비우는데에 걸리는 시간이다. RSets을 비우는데 걸린 시간도 포함된다.

위 글에서 RSets나 RSets의 구조의 복잡성, update buffer, CSet이나 앞으로 나올 SATB(Snapshot-At-The-Beginning) 알고리즘과 barrier등의 개념에 대해서 자세한 설명을 하지 않고 아주 간단히 이야기 했다. 그러나 이를 더 자세히 알기 위해선 G1 GC의 내부 구조에 대해 매우 깊이 알아야한다. 이는 재밌는 주제이지만, 이 글의 주제를 벗어남으로 다른 글에서 이야기하는게 좋을것 같다.

주) 그래도 설명하는 편이 좋을것 같아 간략히 정리해둡니다.

Remember Set (RSet): 객체가 어떤 region에 저장되어 있는지 기록한 자료구조입니다.

Collection Set (CSet): GC가 수행될 region이 저장되어 있는 자료구조입니다.

GC 로그에서 이 Reference 정보를 갱신(Update)하고 검색하는데 소요되는 시간을 보여준다.

Young GC가 어떻게 old영역을 채워나가는지 이해했으니, 그 다음으로는 mark의 threshold(marking threshold)를 이해할 필요가 있다. 전체 heap의 사용률이 이 threshold를 넘는 순간, G1 GC는 다양한 단계가 동시처리되는 marking cycle이 시작된다. 이 threshold를 설정하는 커맨드 라인 옵션은 -XX:InitiatingHeapOccupancyPercent으로, 기본값은 전체 자바 힙 사이즈의 45%로 설정되어 있다. G1 GC는 Snapshot-At-The-Beginning (SATB)라 불리는 marking algorithm을 사용한다. SATB은 marking cycle이 시작할때, heap 메모리에 있는 살아 있는 객체의 set을 logical snapshot으로 저장한다. 이 알고리즘은 logical snapshot의 일부인 객체들을 기록하거나 mark하기 위해서 미리 작성한 barrier를 사용한다. 그러면 다양한 단계가 동시에 처리되는 marking 알고리즘의 각 단계를 GC log를 통해서 알아보자.

0.262: [GC pause (G1 Humongous Allocation) (young) (initial-mark), 0.0021268 secs]
   [Parallel Time: 0.7 ms, GC Workers: 8]
      [GC Worker Start (ms): Min: 262.1, Avg: 262.2, Max: 262.2, Diff: 0.1]
      [Ext Root Scanning (ms): Min: 0.3, Avg: 0.3, Max: 0.4, Diff: 0.1, Sum: 2.5]
      [Update RS (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.0]
         [Processed Buffers: Min: 0, Avg: 0.0, Max: 0, Diff: 0, Sum: 0]
      [Scan RS (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.0]
      [Code Root Scanning (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.0]
      [Object Copy (ms): Min: 0.2, Avg: 0.2, Max: 0.3, Diff: 0.1, Sum: 1.6]
      [Termination (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.0]
         [Termination Attempts: Min: 1, Avg: 2.6, Max: 5, Diff: 4, Sum: 21]
      [GC Worker Other (ms): Min: 0.0, Avg: 0.0, Max: 0.1, Diff: 0.0, Sum: 0.2]
      [GC Worker Total (ms): Min: 0.5, Avg: 0.5, Max: 0.6, Diff: 0.1, Sum: 4.4]
      [GC Worker End (ms): Min: 262.7, Avg: 262.7, Max: 262.7, Diff: 0.0]
   [Code Root Fixup: 0.0 ms]
   [Code Root Purge: 0.0 ms]
   [Clear CT: 0.3 ms]
   [Other: 1.1 ms]
      [Choose CSet: 0.0 ms]
      [Ref Proc: 0.3 ms]
      [Ref Enq: 0.0 ms]
      [Redirty Cards: 0.2 ms]
      [Humongous Register: 0.1 ms]
      [Humongous Reclaim: 0.4 ms]
      [Free CSet: 0.0 ms]
   [Eden: 1024.0K(51.0M)->0.0B(50.0M) Survivors: 0.0B->1024.0K Heap: 381.0M(1024.0M)->416.0K(1024.0M)]
 [Times: user=0.00 sys=0.00, real=0.01 secs]
0.264: [GC concurrent-root-region-scan-start]
0.265: [GC concurrent-root-region-scan-end, 0.0003932 secs]
0.265: [GC concurrent-mark-start]
<snip> [Zero or more embedded young garbage collections are possible here,
          but removed for brevity.]
0.265: [GC concurrent-mark-end, 0.0002262 secs]
0.265: [GC remark 0.265: [Finalize Marking, 0.0008048 secs] 0.266: [GC ref-proc, 0.0000684 secs] 0.266: [Unloading, 0.0004770 secs], 0.0015978 secs]
 [Times: user=0.01 sys=0.01, real=0.00 secs]
0.268: [GC cleanup 10M->10M(1024M), 0.0009233 secs]
 [Times: user=0.00 sys=0.00, real=0.00 secs]

밑에 내용은 각 영역의 설명이다.

The Initial Mark Phase: G1 GC는 intial-mark 단계에서 roots를 mark한다. 위 로그에서 첫번째 라인에 intial-mark가 써있음을 볼 수 있다. 이 초기 단계는 young GC와 동시에 끝나게 된다 (piggy backed). 따라서 로그를 확인하면 Young GC에서 멈춘 시간과 비슷한것을 확인할 수 있다.
The Root Region Scanning Phase: 이 단계에선 G1 GC는 initial-mark의 survivor영역을 스캔하여 old영역에 대한 reference를 구하고 reference되고 있는 객체로 mark한다. 이 단계가 진행중에는 STW가 발생하지 않고, application과 함께 동작한다. 다음 young GC가 발생하기 전에 이 단계가 끝나는게 중요하다.
The Concurrent Marking Phase: 이 단계에서는 G1 GC는 모든 Java heap에서 접근 가능한 살아 있는 객체를 찾는다. 이 단계는 STW 없이 application과 동시에 진행된다. 그리고 이 단계는 위에서 보이듯 Young GC로 인해서 중간에 방해 받을 수 있다.
The Remark Phase: Remark 단계는 mark의 마무리 짓는 단계이다. STW가 발생하여 G1 GC는 남아 있는 SATB 버퍼를 비우고, 아직 추적하지 않은 생존 객체를 찾는다. 또한 G1 GC는 이 단계에서 phantom reference나 soft reference, weak reference와 같은 일반 object와는 다른 reference object를 처리한다(reference processing).
The Cleanup Phase: 이 단계가 marking cycle의 마지막 단계다. G1 GC는 free region과 부분적으로 점유하고 있는 후보군 region을 구분하기 위해서 가끔 STW 걸어두고 객체의 region의 생존정도를 측정하고 RSets를 비운다. 하지만 region을 비우고 free region들의 list로 되돌려 놓을때는 STW를 걸지 않고 애플리케이션과 동시에 처리된다.

이로써 G1 GC의 marking이 완료되면 Old GC를 시작해야하는지 알 수 있다. 이 이전까지는 G1 GC가 Old 영역에 해당되는 region의 marking 정보를 들고 있지 않았기 때문에 Old 영역의 GC가 불가능했다. Old 영역을 compaction하고 비우는게 가능한 collection 작업은 G1 GC에서는 mixed collection이라 부른다. G1 GC에서는 eden이나 survivor 영역의 region 뿐만 아니라 Old 영역도 collection하기 때문이다.

Old region의 메모리를 처리하기 때문에 한 차례가 아닌 여러번의 시도하도록 되어 있다. 만약 Old region이 충분히 collect되면 G1 GC는 다음 marking cycle이 끝날때 까지 Young GC를 다시 시도한다. 아래는 CSets에 들어가는 old region들의 수를 정확히 컨트롤 하는 플래그들이다.

-XX:G1MixedGCLiveThresholdPercent: mixed collection시 old영역의 region에 살아있는 객체가 이 비율을 넘게 되면(threshold) GC 대상에서 제외된다.
-XX:G1HeapWastePercent: Heap 메모리에 남아도 괜찮은 쓰레기의 비율을 나타낸다. (쓰레기가 이 수치 아래로 떨어지면 Mixed GC가 멈춘다.)
-XX:G1MixedGCCountTarget: G1MixedGCLiveThresholdPercent를 만족하는 region을 수집하는데에 mixed GC가 동작하는 목표 횟수이다.
-XX:G1OldCSetRegionThresholdPercent: mixed collection중에 최대로 수집할 수 있는 Old region의 한계치.

mixed collection cycle이 만들어내는 G1 GC log를 확인해보자.

1.269: [GC pause (mixed), 0.00373874 secs]
   [Parallel Time: 3.0 ms]
      [GC Worker Start (ms): 1268.9 1268.9 1268.9 1268.9
    Avg: 1268.9, Min: 1268.9, Max: 1268.9, Diff: 0.0]
   [Ext Root Scanning (ms): 0.2 0.2 0.2 0.1
    Avg: 0.2, Min: 0.1, Max: 0.2, Diff: 0.1]
   [Update RS (ms): 0.0 0.0 0.0 0.0
    Avg: 0.0, Min: 0.0, Max: 0.0, Diff: 0.0]
      [Processed Buffers : 0 0 0 1
       Sum: 1, Avg: 0, Min: 0, Max: 1, Diff: 1]
   [Scan RS (ms): 0.1 0.0 0.0 0.1
    Avg: 0.1, Min: 0.0, Max: 0.1, Diff: 0.1]
   [Object Copy (ms): 2.6 2.7 2.7 2.6
    Avg: 2.7, Min: 2.6, Max: 2.7, Diff: 0.1]
   [Termination (ms): 0.1 0.1 0.0 0.1
    Avg: 0.0, Min: 0.0, Max: 0.1, Diff: 0.1]
      [Termination Attempts : 2 1 2 2
       Sum: 7, Avg: 1, Min: 1, Max: 2, Diff: 1]
   [GC Worker End (ms): 1271.9 1271.9 1271.9 1271.9
    Avg: 1271.9, Min: 1271.9, Max: 1271.9, Diff: 0.0]
   [GC Worker (ms): 3.0 3.0 3.0 2.9
    Avg: 3.0, Min: 2.9, Max: 3.0, Diff: 0.0]
   [GC Worker Other (ms): 0.1 0.1 0.1 0.1
    Avg: 0.1, Min: 0.1, Max: 0.1, Diff: 0.0]
  [Clear CT: 0.1 ms]
  [Other: 0.6 ms]
   [Choose CSet: 0.0 ms]
   [Ref Proc: 0.1 ms]
   [Ref Enq: 0.0 ms]
   [Free CSet: 0.3 ms]

결론적으로 G1 GC는 region을 통해서 논리적으로 존재하는 old/young 영역을 만들어서 기존에 있던 GC를 개선한것이다. region은 더 정밀한 Old 영역의 incremental collection이 가능하도록 했다. G1은 메모리 회수를 살아 있는 객체를 카피해서 진행하기 때문에 compaction도 이루어진다. compaction 단계가 없이 Old 영역에 deallocation을 진행해서 빵꾸 뚫린 모습에 비하면 훨씬 났다.

첫번째 메모리 회수는 marking cycle의 Cleanup 단계에서 region에 살아있는 객체가 아무것도 없을때 이루어진다. 그렇게 해서 메모리가 부족해지만 점진적으로 부분적으로만 빈 region의 GC를 처리한다(incremental mixed garbage collections). 만약 이 모든 단계가 실패할 경우 전체 Java heap을 대상으로 GC가 돌아간다. 이는 잘 알려진 fail-safe Full GC이다. 이 모든 단계가 Old 영역의 메모리 회수를 쉽게 만들고 계층화 시킨다.

References

React, Typescript, Webpack환경에서 번들링 속도 올리기

2019-06-07T18:44:00+09:00

제니퍼소프트에서 진행하는 프로젝트에서 Webpack과 TypeScript, React를 사용하고 있다. SPA는 필수적인 선택지였다. classic한 개발 방식으로는 web page는 몰라도 web application을 개발하기엔 부적합하다. 그 중에서도 React를 선택한 이유는 훌륭한 레퍼런스들과 안정적인 소스 관리, 무엇보다 가장 잘 쓸줄 아는 것을 선택했다.

Webpack은 그 외의 선택의 여지가 약하기 때문에 webpack을 선택했지만, 이 프로젝트를 시작하면서 실전에서는 처음으로 TypeScript를 선택해서 사용했다. TS를 사용한 효과를 간략히 설명하면, TS를 사용함으로써 버그가 줄었는가는 모르겠지만 TS를 사용함에 따라 자동완성과 Go to definition에서 오는 생산성 향상은 확실히 체감할 수 있었다.

처음에는 webpack의 빌드의 속도는 큰 문제가 없었지만, 소스코드가 늘어남에 따라 hot reload가 더 이상 hot하지 않게되었다. 하지만 설정을 통해 webpack으로 빌드시에 26초 정도 걸렸던것을 초기 빌드 속도는 7초 캐시 사용시에는 4초 정도로 떨어졌다.

loader 줄이기.

당연하지만 load는 줄일 수 있을만큼 줄이면 좋다. 개발 당시에는 babel-loader와 ts-loader를 둘 다 사용했지만, Typescript의 기능만으로도 JSX 컴파일과 구 ES을 타겟으로 하는 컴파일이 가능하고 최신 ES의 기능을 그렇게 많이 사용하는 편도 아닌지라 babel-loader를 걷어내고 ts-loader만을 사용하기로 했다.

Typescript를 컴파일 시키는 방법으로는 지금에는 3가지 정도의 방법이 있는듯 싶다. awesome-typescript-loader를 쓰는 방법과 ts-loader를 쓰는 방법, babel-loader에 typescript-preset을 얹는 방법이 있다. 다만 awesome-typescript-loader는 사용하는것을 지양하는 편이 좋다고 이야기들 한다.

물론 반박하는 이를 반박하는 글 또한 있지만 많이들 사용하는 쪽으로 선택하기로 했다. 또한 babel-loader를 통하는 방법은 아직 다양한 옵션이 부족한듯 싶고 transpile과 type check가 분리되는지에 대해 확신이 서지 않기 때문에, 보류하기로 했다.

transpileOnly, experimentalWatchApi

ts-loader는 기본 옵션이 TS를 JS로 변환하는 transpile 작업과 type check 작업을 같은 스레드에서 동시에 실행한다. type check는 개발자에게 편의 제공을 위한 기능이지 type이 브라우저에게 넘어갈 결과물에 까지는 영향을 주지 않기 때문에, type check 작업은 분리되어도 상관없다. 따라서 ts-loader에는 transpile 작업만을 진행하는 옵션이 있다. 이를 설정하고 ts-loader는 transpile 작업을 진행하고, type check는 fork-ts-checker-webpack-plugin 플러그인을 통해서 체크하도록 했다.

파일이 변경되면 변경된 파일만 컴파일해서 합치면 변경시의 컴파일 속도를 올릴 많이 올릴 수 있다. 기존에는 TS가 사용하는 watch API가 공개되어 있지 않아서 따로 구축했다. experimentalWatchApi 옵션을 사용하면 ts-loader가 TypeScript의 내부 watch mode API를 사용하여 재컴파일해야하는 파일 수를 크게 줄일 수 있다.

{
    test: /\.tsx?$/,
    loader: [
        {
            loader: 'ts-loader',
            options: {
                transpileOnly: true,
                experimentalWatchApi: true,
            },
        },
    ],
    exclude: /node_modules/,
},

node_modules를 제외하고 .tsx?에 해당하는지 확인하고 해당할 경우 ts-loader를 통과하는데 transpileOnly 옵션과 experimentalWatchApi 옵션을 설정하고 통과하게된다.

그외 webpack optimization

// ...
output: {
    pathinfo: false,
},
optimization: {
    removeAvailableModules: false,
    removeEmptyChunks: false,
    splitChunks: false,
},
// ...

Webpack의 공식 문서에서 개발 모드시에 켜두기를 권장하는 몇몇 설정들이 있다. pathinfo 설정의 경우엔 GC를 최소화 시킬 수 있고, 그 외의 optimization 옵션은 production시에는 필요하지만 개발 버전에서는 크게 유용하지 않은것들에 대한 기능들을 사용하지 않는것이다. (자세한 내용은 Webpack의 Build Performance 항목을 참조)

Cache

이미 컴파일된 소스코드를 최대한 캐시하여 처리하여 빌드속도를 올릴 수 있다. 일반적으론 cache-loader를 사용한다. 하지만 hard-source-webpack-plugin가 더 성능이 좋은 경우가 있다고 하고, 비교 했을때 조금 더 성능이 나아져서 이쪽을 사용했다.

// ...
plugins: [
    new ForkTsCheckerPlugin(),
    new HardSourcePlugin(),
],
// ...

References

Athena를 Zeppelin과 함께 쓰기

2019-03-14T19:16:00+09:00

회사 업무 중에 대용량의 데이터를 조회하고 분석할 일이 생겼다. 데이터는 DynamoDB에 쌓여있다. DynamoDB에서는 복잡한 조건을 갖고 쿼리를 할 수 있는 구조가 아니고, 가격과 성능 문제도 있기 때문에, 선택할 수 있는 도구에 대해서 수소문 해봤고, Google cloud platform에서 제공하는 BigQuery나 AWS에서 제공하는 Athena가 가장 편하고 흔하게 사용하는 듯 하다.

하지만 모든 데이터가 AWS의 DynamoDB에 있고, 회사에서는 이미 AWS를 적극적으로 사용중임으로, BigQuery보다는 Athena를 선택하게 되었다.

DynamoDB에 있는 데이터를 S3에 쌓고 이를 Athena를 통해서 질의하는 방법에 대한 설명은 메가존에서 번역한 AWS의 기술 블로그 글이 있다.

이 글 안에, Athena로 질의한 내용에 대해서 시각화 하는 방법으로 AWS의 QuickSight를 사용했다. QuickSight는 데이터를 시각화하여 대시보드를 만들고 회사 내에 데이터를 공유하는데에 초점이 맞춰져 있다. 하지만 내가 하고 싶은 일은 질의를 통해서 데이터를 분석하는데에 초점이 맞춰있기 때문에 Notebook형식의 Apache Zeppelin이 더 편해보였다. 따라서 로컬에 Docker를 통해서 Zeppelin을 설치하고, Zeppelin에서 Athena에 쿼리할 수 있는 방법에 대해 자료가 부족하여 정리해보고자 했다.

docker-compose을 이용한 Zeppelin 설치

Dockerhub에 이미 Apache에서 공식으로 제공하는 Zeppelin이 docker image가 있다. 관리를 위해서는 docker-compose를 이용해서 컨테이너를 만드는게 좋다. 우선 Zeppelin에서 작성한 노트북은 Host machine에서 접근할 수 있으면 좋겠고, Zeppelin의 기본 포트인 8080은 개발시에 자주 사용하는 포트인지라, 5000번 포트로 접근할 수 있도록 설정했다.

version: '3'

services:
  zeppelin:
    image: apache/zeppelin:0.8.1
    container_name: zeppelin-notebook
    ports:
      - "5000:8080"
    volumes:
      - ./notebook:/notebook
    environment:
      - ZEPPELIN_NOTEBOOK_DIR=/notebook

$ docker-compose up --build를 통해서 zeppelin을 실행하면 브라우저를 통해 http://localhost:5000 에서 쉽게 접근할 수 있다.

Zeppelin과 Athena 연결

Zeppelin은 java를 이용해서 작성했고, 따라서 JDBC를 통해서 Athena에 접근한다. AWS에서는 JDBC 드라이버를 제공하고 있고 두 가지의 버전이 있는데 이 글에서는 최신 버전의 Athena JDBC 드라이버를 기준으로 설명한다. (이전 버전의 JDBC 다운로드 링크)

최신 Athena의 JDBC 드라이버는 이 페이지에서 다운로드 받을 수 있다. docker-compose.yml에서 사용하고 있는 0.8.1버전의 zeppelin 이미지는 java 8이 돌아가고 있기 때문에 AthenaJDBC42_2.0.6.jar를 다운로드 받아서 docker-compose.yml의 디렉토리에 jar라는 서브 디렉토리를 만들어서 다운로드 받은 jar파일을 저장했다.

이제 다운로드 받은 jar 파일과 AWS의 credential 디렉토리(AWS의 자격증명 만들기에 대한 설명은 여기에)를 docker-compose.yml을 통해서 zeppelin이 동작 중인 컨테이너와 연결시켜 준다.

version: '3'

services:
  zeppelin:
    image: apache/zeppelin:0.8.1
    container_name: zeppelin-notebook
    ports:
      - "5000:8080"
    volumes:
      - ./notebook:/notebook
      - ./jar:/usr/local/jar
      - ~/.aws:/root/.aws
    environment:
      - ZEPPELIN_NOTEBOOK_DIR=/notebook

이제 docker-compose up --build를 다시 실행해서 컨테이너를 재시작 시켜주고, zeppelin에 접속해서 athena interpreter를 설정해준다.

zeppelin에 다시 접속하여 계정 이름을 클릭하면 zeppelin에 있는 모든 인터프리터를 볼 수 있는Interpreters 메뉴가 있다.

새로운 인터프리터를 만들어야하는데 Interpreter Name은 적당히 athena로 정하고, Interpreter group은 jdbc로 설정했다. jdbc로 설정하면 Properties가 자동으로 채워지는데, 이 중에 몇 가지를 바꿔야한다. default.driver는 com.simba.athena.jdbc.Driver로 설정하고, default.url은 굉장히 긴 텍스트를 설정해야한다.

jdbc:awsathena://athena.ap-northeast-2.amazonaws.com:443;S3OutputLocation=s3://aws-athena-query-results-...-ap-northeast-2;Schema=default;AwsCredentialsProviderClass=com.simba.athena.amazonaws.auth.profile.ProfileCredentialsProvider;AwsCredentialsProviderArguments="..."

하나씩 보면

jdbc:awsathena://athena.ap-northeast-2.amazonaws.com:443 리전코드만 athena에 따라 바꾸면 된다.
S3OutputLocation=s3://aws-athena-query-results-…-ap-northeast-2 쿼리 결과가 저장되는 S3 위치를 설정하면 된다. Athena의 AWS Console에 Settings를 살펴보면 기본 Query result locaiton을 알 수 있다.
Schema=default 사용할 스키마를 설정한다.
AwsCredentialsProviderClass=com.simba.athena.amazonaws.auth.profile.ProfileCredentialsProvider 건드릴 필요 없다.
AwsCredentialsProviderArguments=”…” Credential의 이름을 정하면 되는듯하다. 이름은 ~/.aws/credential 내용의 대괄호 안의 내용이다. 일반적으론 default로 설정되어 있다.

default.user와 default.password를 비워두고 Dependecies의 artifact를 /usr/local/jar/AthenaJDBC42_2.0.6.jar로 설정하면 AWS에서 다운로드 받은 JAR 파일을 zeppelin이 사용하도록 설정할 수 있다.

Save하고 새로운 노트북을 만들면 athena로 쿼리를 보낼 수 있다.

타원곡선 디피 헬만

2019-02-17T19:10:00+09:00

AES나 DES와 같은 암호화 알고리즘을 이용해서 보안 통신을 하기 위해서는 암호키가 필요하다. 암호키를 통해서 제 3자가 이를 해독하기 어렵게 만드는것이다. 암호키를 제 3자가 알면 암호를 깨고 데이터를 복호화할 수 있기 때문에 안전하게 암호화 키를 공유할 필요가 있다. 디피 헬만은 위와 같은 암호화 통신에서 안전하게 키를 교환하는 방법 중 하나로 TLS에서 많이 사용해 왔다.

최근에 TLS를 공부하면서 타원곡선 디피 헬만(Elliptic Curve Diffie Hellman)에 대해 알아보고 싶어서 공부를 시작했다. 일반적으로 타원곡선 디피 헬만은 적은 CPU와 메모리 자원과 더 작은 키 값으로도 일반 디피 헬만에 비해 안전한것으로 알려져 있다. 일반 디피 헬만의 키 사이즈가 2048bit면 ECDH에서는 224bit 사이즈의 키로 같은 안전성을 보장한다.

ECDH의 원리 이해를 위해서는 정수론에 대한 이해가 필요했다. 따라서 글을 모듈러 연산과 군, 이산로그 그리고 타원곡선 디피 헬만 순으로 나눴다.

Modular 연산 (나머지 연산)

정수를 정수와 나누면 나머지가 발생한다. 거의 모든 프로그래밍 언어에 항상 빠지지 않고 등장하는 흔한 이항연산자다.

\[a \mod N = b\]

a는 피제수, N은 제수, b는 나머지다. Modular 연산의 예를 들면 아래와 같다.

\[40\mod17 = 6\]

알지 못할 수 있지만 음수에 대한 나머지 연산도 가능하다. 음수의 나머지 연산을 계산할 경우, 피제수의 값을 양수라 생각하고, 제수의 차를 구한다. 예를 들어 $-40 \mod 17$의 경우 40의 mod 17 값인 6과 17의 차인 11이 정답이다.

합동

Modular 연산에서의 합동은 나머지가 같은 값들을 의미한다. 예를들어, 17에 대하여, 40과 합동인 수는 6, 23, 57, …등이다. 이를 식으로 나타내면 $40 \equiv 6 \mod 7$이 된다. 이 개념을 갖고 식에 적용하면 합동식이 되는데 예를들면 $3x \equiv 7 \mod4$ 과 같이 적을 수 있다. 이를 풀이하면 3의 배수 중에서, 4와 나눴을때 나머지 값이 7과 4를 나눈 나머지와 같은 수를 의미한다.

Modular 역수

$40 ^{-1} \equiv x \mod 17$에서 $x$는 얼마일까? 곱샘 연산자에서는 연산을 진행해도 같은 수가 나오는 항등원은 1이다. (덧샘에서는 0) $40 ^{-1}$과 $40$은 서로 곱하면 항등원인 1이 나오는 곱샘에서의 역원 관계에 있다. 따라서 17에 대한 나머지 연산에서 40과 곱했을때 연산 결과가 1이 나오는 값이 40의 역원인 $40 ^{-1}$과 같은 값입니다. 예를들어 40의 법 17에 대한 역수는 3이다.

\[40 \times 3 \equiv 1 \mod 17\]

따라서 $40 ^{-1} \equiv 3 \mod 17$이라 할 수 있다.

군 (Group)

군은 하나의 이항 연산자에 대해서 특수한 조건을 갖고 있는 수의 집합이다.

군은 정의된 연산자에 대해서 닫혀있어야 한다.
연산자에 대해서 결합법칙이 성립되어야 한다.
군 안에는 항등원과 역원이 있어야 합니다.

위와 같은 조건을 충족하는 집합의 사례를 들어보자. 모든 정수는 덧셈에 대해서 군을 이룬다. 위 조건에 부합하는지 알아보자, 우선 정수를 정수와 더하면 정수가 나올것이다. 또한 덧샘은 결합법칙이 성립하는 연산이다. 그리고 정수 안에는 덧샘의 항등원인 0이 있고, 역원인 음수가 있다. 예를들면 42의 역원은 -42이고 항등원은 0이다. 증명하는 방법이야 있겠지만 모든 정수가 덧셈에 대해서 군을 이룬다는 것은 자명한 사실이다. 정수와 같이 덧셈에 대한 군을 덧셈군이라 부른다. 이와 마찬가지로 곱샘에 대해서 군이 성립하면 곱샘군이라 할 수 있다.

그러면 정수는 곱셈군이라 부를 수 있을까? 아쉽게도 그렇지 않다. 우선 역원이 없다. 예를 들면 2의 곱셈에 대한 역원은 1/2인데 이는 정수가 아닌 유리수이다. 그렇다면 유리수는 곱셈군을 이룬다 볼 수 있는가? 이 또한 그렇지 못 한다. 유리수에는 0이 있는데, 0은 곱셈에 대한 역원이 존재하지 않는다. (1/0은 계산할 수 없다.) 따라서 0을 제외한 유리수가 곱셈군을 이룬다 볼 수 있다.

Modular N에 대한 정수 ( $\mathbb{Z}/n\mathbb{Z}$ )

Modular N에 대해서 모든 정수의 나머지의 집합을 이야기한다. 예를 들면 8에 대한 나머지 집합인 $\mathbb{Z}/8\mathbb{Z}$ 이라 표기하고 0, 1, 2, … 7까지의 숫자들이다. Modular 연산을 한 정수 집합은 덧셈군이 될까? 덧셈군은 성립한다. 예를들면 $3 + 7 \mod 8$의 값이 $\mathbb{Z}/8\mathbb{Z}$안에 있어야하고, 역수와 항등원이 존재해야한다. 우선 정수를 정수끼리 더하면 정수가 나올것이다. 그리고 항등원은 0이 있고 계산하면 0이 나오는 역원 또한 존재한다. Modular 8에 대한 정수 집합에서 보면 7에게는 1이 역원이고, 5에게는 3이 역원이 될 것이다. 모든 Modular N에 대한 정수는 일반 정수와 마찬가지로 덧셈군이 성립된다. 그렇다면 곱셈군도 성립할 수 있을까?

우선 정수와 마찬가지 이유로 0은 제외해야 한다. 하지만 Modular N에 대한 정수에서는 0을 제외해도 문제가 숫자가 있다. 2, 4, 6입니다. 이 수 들은 어떤 수와 곱했을때 8의 배수가 될 여지가 있다. 그러면 Modular 연산하면 제외된 0이 나온다. 6으로 예를 들면,

\[\begin{align} &6 \times 4 \equiv 0 \mod 8 \\ &\because 6 \times 4 = 24 \end{align}\]

24는 8의 배수임으로, 나머지 값이 0이 나오고 0을 제외한 집합에 대해서 닫혀있지 않은 연산이 된다. 이렇듯 곱셈 연산에 닫혀 있기 위해서는 0, 2, 4, 6을 제외한 1, 3, 5, 7이 Modular N에 대한 곱셈군(Multiplicative group of integers modulo n)이 된다. 기호로는 $(\mathbb{Z}/n\mathbb{Z})^\times$ 이렇게 표기한다.

Modular N에 대한 곱셈군(Multiplicative group of integers modulo n)

위에서 확인한 곱셈군인 1, 3, 5, 7은 8과 어떤 관계에 있는가? 곱셈군에 포함되지 않았던 값들은 다른 수와 곱했을때 8의 배수가 될 여지가 있는 수였다. 따라서 어떤수와 곱해도 8이 될 여지가 없는 수가 된다는 의미고, 이 말은 8과 서로소(두 수의 최대공약수가 1) 관계에 있다는 의미가 된다.

N이 서로소가 많고 큰 수 라면, Modular N에 대한 곱셈군의 크기(order)가 커진다. 서로소가 많은 수는 소수가 있다. 소수는 모든 정수와 서로소 관계에 있다. 예를 들면 소수 7은 $\mathbb{Z}/7\mathbb{Z}$는 0, 1, 2, 3, 4, 5, 6이 있고 이 중 0을 제외하면 모두 서로소 관계에 있다. 따라서 0을 제외하면 모두 $\mathbb{Z}/7\mathbb{Z}^\times$에 포함되어 있단 의미가 된다.

이산로그 문제 (discrete logarithm problem)

암호화 알고리즘에게 있어서 중요한 문제는, 암호화를 하는 과정은 굉장히 간단하고 빠르게 진행되어야하지만 이를 복호화하는 과정은 매우 어려워야한다. 이를 일방향 함수(One-way function)라 이야기하는데 이산 로그 문제는 아주 전형적인 One-way function이다.

위에서 이야기한 $\mathbb{Z}/7\mathbb{Z}^\times$를 생각해보자, 이 집합은 1, 2, 3, …6까지의 수를 포함하고 있고, 모듈로 곱셈에 대해서 닫혀 있다. 따라서 거듭제곱 연산에 대해서도 닫혀있다 할 수 있다. 이를 이산 거듭제곱이라 이야기하는데, 예를 들어, $3^6 \mod 7$한 값은 729을 7로 나눈 나머지 1가 된다.

\[\begin{align} &3^6 \equiv 1 \mod 7 \\ \end{align}\]

여기서 결과값이 1이 되는 최솟값인 지수가 이산로그 값이다. 지수를 알고 계산하면 결과값을 계산하는데에 일반적인 연산에 가깝지만, 결과와 지수 연산의 밑만 가지고선 지수를 추론하는 과정은 1부터 시작해서 하나하나 비교하는 방법 외에는 없다.

$\mathbb{Z}/7\mathbb{Z}^\times$의 경우 군의 크기가 6으로 작지만 7 대신 굉장히 큰 소수를 사용하면 군의 크기가 커지고, 이산 로그 문제를 해결하는 알고리즘은 군의 크기의 자릿수에 지수적인 복잡도를 갖고 있다. 이를 조금 효율적으로 찾는 방법은 있지만 의미있게 빠른 방법은 아직 없는것으로 알려져 있다. 또한 밑(위의 예제의 경우엔 3)을 정의하는 것이 중요한데, 밑 값을 제곱하여 modular 연산한 결과의 값이 $\mathbb{Z}/n\mathbb{Z}^\times$의 모든 원소를 포함해야 추론이 어려워지기 때문이다. 위와 같은 밑을 Primitive root라 이야기한다. 따라서 많은 보안 통신을 하는 프로그램들이 $\mathbb{Z}/n\mathbb{Z}^\times$의 소수 N과 Primitive root값인 g값에 대해선 사전에 정의해두고 사용한다.

결론적으로 일반적인 이산 로그 문제는 Modular N에 대한 곱셈군에서 곱셈의 반복 연산인 제곱의 역연산 값 로그 값을 구하기 어려운 문제를 이야기한다. 이는 RSA, 디피 헬만에 유용하게 쓰인다.

타원곡선

타원곡선이란 $y^2 = x^3 + ax + b$ 꼴의 형태로 나타내지는 곡선을 의미한다. 그래프로 표현하면 아래와 같은 꼴이 된다.

그래프의 모양이나 방정식의 형태나 둘다 타원과는 크게 상관 없고, 타원의 둘레를 구하기 위한 적분에서 이름이 유래되었다고 한다.

타원 곡선의 연산

타원 곡선에서는 두 점에 대한 특이한 덧셈 연산이 존재한다. 점 P와 Q를 타원 곡선에서 더한 결과 R은 아래의 그림과 같다.

P와 Q를 지나는 직선을 긋고 이 직선이 타원 곡선과 만나는 점에 대해서 X축 대칭점이 R의 결과다. P의 좌표를 $(x_P, y_P)$ Q의 좌표를 $(x_Q, y_Q)$, R의 좌표를 $(x_R, y_R)$로 두고 R의 좌표를 계산하는 방법은 아래와 같다.

\[\begin{align} & P + Q = R\\ & \\ &s = \frac{y_P - y_Q}{x_P - x_Q} \\ &x_R = s^2 - (x_P + x_Q) \\ &y_R = s(x_P - x_R) - y_P \end{align}\]

위 식을 보면 $y_P$ 와 $y_Q$가 다른데, $x_P$ 와 $x_Q$가 같으면 s의 값이 무한으로 발산한다는 것을 알 수 있다. 이 말은 P와 Q가 동일한 X 좌표를 갖고 있으면 R의 값을 구할 수 없다는 이야기다. 그림으로만 봐도 구할 수 없게 생겼다.

위와 같은 경우 R의 점을 무한점(∞)이라 정의한다. 무한점의 성질에 대해서 한 가지 더 정의하면 타원 곡선의 덧셈 연산 정의가 끝난다. P가 ∞인 경우에 P + Q에 대한 결과 문제다. 이 경우엔 Q를 지나고 X축과 직교하는 선을 그리고 이때 타원 곡선과 만나는 점을 -R로 두고 위와 같은 방식으로 X축과 대칭점인 R을 구한다. 이렇게 구한 값은 Q와 동일하다. 그림으로 보면 이해하기 쉽다.

그렇다면 $y_P$ 와 $y_Q$가 같고, $x_P$ 와 $x_Q$도 같은 즉, P를 두번 더한 경우는 어떻게 계산할 수 있을까? 이때는 타원 곡선 위의 점 P와 접하는 직선과 교차하는 점이 R값이 된다.

이를 수식으로 표현하면 아래와 같다. 이 때 a는 $y^2 = x^3 + ax + b$의 a값이다.

\[\begin{align} & P + P = R\\ & \\ &s = \frac{3x_P^2 + a}{2y_P} \\ &x_R = s^2 - 2x_P \\ &y_R = s(x_P - x_R) - y_P \end{align}\]

위에서 이야기 한 타원 곡선에 대한 연산을 정리하면

P와 Q를 지나는 직선과 만나는 점의 X축 대칭점을 R로 계산한다.
P와 Q를 지나는 직선이 X축과 직교하면 R은 무한점(∞)이다.
무한점(∞)과 점 P를 더하면 결과값 R은 P와 같다.

와 같이 정리할 수 있다. 위 정리를 보면 무한점은 위에서 이야기한 항등원이란 사실을 알 수 있다. 이 때의 역원은 X축의 대칭점일 것이다. 따라서 점 P의 X축 대칭점은 -P라 이야기할 수 있다. 무한점을 포함하면 $y^2 = x^3 + ax + b$을 지나는 모든 점에 대해 해당 연산은 닫혀 있고, 결합법칙이 성립한다고 한다(이 부분은 증명이 어려움). 따라서 타원 곡선과 무한점을 포함한 집합은 이 연산에 대해서 군을 이룬다.

타원곡선의 이산로그 문제

타원곡선의 연산을 사용해서 점 P를 P와 더하는 것을 2P라고 정의한다면 P를 세번 더한 값을 3P로 나타내면 k번 더한 결과 Q를 $kP$라 나타낼 수 있다.

\[Q = kP = P + P + P + .... + P\]

위에서 이야기 했던 이산로그 문제와 마찬가지로 Modular N에 대한 타원곡선 덧셈군에 대해서 반복 연산인 곱셈의 역연산 값을 추론하기 어렵다. 따라서 P와 k를 갖고 Modular N연산을 한 Q를 계산하는 것은 쉽지만, Q와 P만 가지고는 k값을 찾는것은 굉장히 어렵단 이야기다. 예를 들면 타원곡선을 $y^2 = x^3 + 2x + 2 \mod 17$로 두고 P를 (5, 1)로 정의하자, 이때 결과값 Q를 P를 4번 더한 값은 (3, 1)이 된다. 만약 Q값인 (3, 1)과 P값인 (5, 1)만 보고 몇 번 더한것인지 추론하려 한다면, 이는 굉장히 어렵다는 이야기다(이산로그 문제).

따라서 일반적인 이산로그 문제와 마찬가지로 P값과 Modular N값을 잘 정의하면, 이를 일반적인 디피 헬만과 마찬가지 방법으로 암호키 교환 알고리즘에 사용할 수 있다.

타원곡선 디피 헬만

일반 디피 헬만과 마찬가지로 Alice와 Bob 둘이 통신하고 이를 중간에서 Eve가 훔쳐보고 있다 가정하자. 우선 Alice와 Bob이 각자의 비밀키를 만든다. 이를 $\alpha$, $\beta$라 하자. 그리고 기준이 되는 타원곡선 함수를 $y^2 = x^3 + ax + b \mod N$로 정의하고, 기준점을 G라 하자. 그러면 Alice와 Bob, 그리고 훔쳐보는 Eve는 모두 a, b, N, G 값을 알고 있다. 이 때 Alice와 Bob은 각자 공개키를 만들어서 나누어 갖는다.

\[Alice \hspace{50 pt} Eve \hspace{50 pt} Bob \\ A = \alpha G \hspace{50 pt} \hspace{50 pt} B = \beta G\\ B \hspace{50 pt} A, B \hspace{50 pt} A\\ K = \alpha B = \alpha\beta G \hspace{50 pt} K = ? \hspace{50 pt} K = \beta A = \alpha\beta G\\\]

Eve는 A나 B로 부터 $\alpha$, $\beta$를 추론할 수 없어 K를 구할 수 없지만 Alice와 Bob은 받은 공개키 값을 각자의 비밀키 값과 곱해서 이를 알아낼 수 있다.

예를 들어보자, 타원곡선을 $y^2 = x^3 + 2x + 2 \mod 17$로, G를 (5, 1)로 정의하자. 이 때 Alice와 Bob이 스스로 비밀키를 고르고 공개키를 나누는 과정을 보면 아래와 같다.

\[Alice \hspace{50 pt} Eve \hspace{50 pt} Bob \\ \alpha = 3 \hspace{50 pt} \hspace{50 pt} \beta=9 G\\ A = 3G = (10, 6) \hspace{50 pt} \hspace{50 pt} B = 9G = (7, 6)\\ B \hspace{50 pt} A, B \hspace{50 pt} A\\ K = 3B = (13, 7) \hspace{50 pt} K = ? \hspace{50 pt} K = 9A = (13, 7)\\\]

따라서 Eve가 키 값 K를 알아내기 위해선 $y^2 = x^3 + 2x + 2 \mod 17$의 G에 대한 모든 경우의 수를 알아내 A나 B값을 통해 비밀키를 구할 수 있으면 된다.(이산로그 문제)

References

알아두면 쓸데없는 신비한 TLS 1.3

2018-12-15T13:28:00+09:00

이 글은 계간 잡지 마이크로소프트웨어 394호에 기고된 글입니다.

TLS

우리가 개발하는 서비스 중에서 인터넷에 연결이 필요 없는 서비스는 거의 없다고 봐야한다. 이런 서비스는 우리가 만든 앱 혹은 웹을 통해서 데이터를 받아 서버에 저장한다. 오프라인 모드로 즐기는 게임마저도 장애 로그 또는 통계 데이터를 인터넷 연결로 받는 사례가 늘고있다. 다만 이 데이터에는 굉장히 민감한 정보가 포함돼 있다는 것이 요점이다. 카드 번호나 주소는 기본이고, 심지어 우리 집 거실에 있는 공유기의 맥어드레스까지도 데이터화 돼 전송된다. 그래서 중간에 데이터가 조작되거나 변조되지 않도록 암호화해 데이터를 보내야한다.

우리는 이런 민감한 정보를 보낼 때 HTTP보다는 HTTPS(‘Secure’를 의미하는 ‘S’)를 사용하라고 배웠다. HTTPS의 안전성은 TLS라는 프로토콜을 통해 보장된다. TLS는 과거 우리가 SSL이라 부르던 프로토콜에서 시작했다. SSL은 1990년대에 브라우저를 개발했던 넷스케이프(Netscape)에서 보안성이 높은 HTTP 통신을 지원하기 위해 만든 프로토콜이다. 넷스케이프가 SSL을 IETF(Internet Engineering Task Force, 국제 인터넷 표준화 기구)에게 양도하면서 바뀐 이름이 TLS 1.0이다. (TLS 1.0은 단순히 이름만 바뀐 것이기 때문에, SSL 3.0과 동일한 프로토콜로 본다.)

우리가 사용하는 웹브라우저 대부분은 HTTP/2를 사용하기 위해 TLS 사용을 강제하고 있다. 특히 최고의 브라우저 점유율을 갖고 있는 구글 크롬(Google Chrome) 브라우저의 최신 버전에서는 HTTP로 접속하면 ‘안전하지 않은 사이트’라는 경고를 띄운다.

[그림1] 안전하지 않은 청와대

과거만 해도 TLS/SSL를 사용하기 위해서는 인증서를 구매 해야 했고, 이 구매 비용이 (생각보다) 부담스럽기 때문에 TLS를 사용하지 않는다는 사람들도 있었다. 하지만 이제는 인증서 마저도 렛츠인크립트(Let’s Encrypt) 같은 서비스를 이용하면 무료로 발급받을 수 있다. 이런 추세와 시도로 많은 사이트가 TLS를 사용해 조금 더 안전한 인터넷 세상을 만들 수 있게 변하고 있다.

TLS 1.2의 문제점

TLS의 전신인 SSL은 1990년대에 등장한 프로토콜이다. 초기 SSL을 디자인할 당시에는 설계상 허점으로 인해 구현체가 실제 구현 결과와 다른 부분(Heuristic)이 있었다. 또한 보안 프로토콜에서 발생하는 문제가 어떤 방식인지 자료나 학습이 부족했다. 허점이 발견된(Heuristric) 부분이나 문제가 되는 부분은 구현체가 만들어지는 과정에서 많이 고쳐지면서 현재의 TLS 1.2가 탄생했다. 하지만 TLS의 설계적인 허점과는 별개로 TLS와 관련된 직간접적인 보안 이슈가 많이 발생했다.

가장 먼저 떠오르는 보안 관련 이슈로 하트블리드(Heartbleed, CVE-2014-0160)가 있다. 하트블리드는 많은 언어, 프레임워크, 서버 프로그램에서 TLS연결을 위해 사용하던 오픈소스 라이브러리인 OpenSSL에서 발생한 버퍼 오버플로우(BOF) 버그다. 엄밀하게는 TLS 구현체 자체에서 해결해야하는 문제점이므로 TLS와는 상관 없다고 할 수 있다. (OpenSSL은 ‘BERserk’, ‘goto fail;’ 등 구현체 수준의 다른 문제도 제기됐다.)

하지만 TLS 프로토콜 자체에도 문제점이 있다. 이론적인 레벨도 있지만 ‘LogJam(CVE-2015-4000)’, ‘FREAK(CVE-2015-0204, CVE-2015-1637, CVE-2015-1067), ‘SWEET32(CVE-2016-2183)’ 같은 위협적인 문제도 있고, 실제 적용할 수 있는 ‘POODLE(CVE-2014-8730)’과 ‘ROBOT’과 같은 문제점들도 있다.

TLS 1.2는 느리다

TLS의 가장 최신 버전이었던 ‘1.2’는 2008년에 나왔다. 2008년 당시 네이버를 떠올려보자. 그 시절 네이버는 로그인 서비스 같은 보안이 중요한 부분을 제외하고는 평문(Plaintext)으로 서버와 클라이언트가 통신했다. 하지만 최근 추세는 조금 다르다. 지금은 모든 페이지를 TLS로 서비스하고 있다.

당연히 이런 노력은 긍정적인 변화로 봐야 한다. 중간에서 통신을 도청당해도 안전하고, 인젝션(Injection)과 같은 공격도 걱정할 필요가 없다. 다만 단점은 새로운 연결을 맺기까지 조금 느려진다. TLS는 처음 커넥션을 핸드셰이크(Handshake)라 부르는 과정을 통해서 암호화 방식이나 암호화 키를 교환한다. 이를 위해 클라이언트와 서버 간 라운드 트립(Round Trip)이 2회 정도 추가된다.

      Client                                               Server

      ClientHello                  -------->
                                                      ServerHello
                                                     Certificate*
                                               ServerKeyExchange*
                                              CertificateRequest*
                                   <--------      ServerHelloDone
      Certificate*
      ClientKeyExchange
      CertificateVerify*
      [ChangeCipherSpec]
      Finished                     -------->
                                               [ChangeCipherSpec]
                                   <--------             Finished
      Application Data             <------->     Application Data

[그림2] TLS 1.2(RFC5246)의 전체 핸드셰이크 과정

엄청난 차이라고 느끼지 않을 수도 있다. 하지만 서버와 클라이언트가 서로 지구 반대편에 있는 최악의 상황을 떠올려 보자. 데이터가 빛의 속도로 움직인다고 가정하면, 빛이 지구 반대편에 도달하고 다시 돌아오는데 걸리는 시간은 약 133ms다. 이를 2번 시행하면 매번 커넥션을 열 때마다 약 270ms가 지연(Delay)된다. 당연히 이 지연 현상은 비용으로 추가된다.

TLS 1.3은 다른가?

TLS 1.3 표준은 IETF의 RFC 8446에서 맡고 있다. 더 빠르고 안전한 인터넷을 만들기 위해 4년간 논의하고 28회의 초안을 거쳤다. 문제점이 제기된 암호화 방식을 버리고, 핸드셰이크 과정을 최소화해 암호화 통신하는 방법을 추가했다. TLS 1.3의 큰 차이점은 다음과 같다.

TLS 1.3의 특징

핸드셰이크에 ‘0-RTT’ 모드 추가.
정적인 RSA와 디피-헬먼 암호화 스위트(Diffie-Hellman Cipher Suite) 제거.
핸드셰이크를 가능한 최대한 암호화.
타원 곡선 알고리즘을 기본으로 지원.
키 교환과 암호화 방식을 암호화 스위트(Cipher Suite)방식이 아니라, 개별적으로 결정.

TLS 1.2와 1.3의 성능과 안전성 차이는 뒤에서 자세히 알아보자.

더 이상 묶음 판매 안 합니다.

이전의 TLS에서는 핸드셰이크 과정에서 암호화 스위트(Cipher Suite)라는 묶음으로 인증과 키 교환 방법을 정했다. 핸드셰이크 과정에는 서로 합의해야 하는 알고리즘이 4가지가 있다. 대칭키 교환 방식, 인증서 서명 방식, 대칭키 알고리즘, HMAC 알고리즘이다. TLS에서는 서버와 클라이언트가 이 4가지 알고리즘을 묶음으로 합의하고, 합의된 알고리즘으로 애플리케이션 계층(Application Layer)의 내용을 암호화해서 전송한다.

보통 암호화 스위트는 [그림3]의 ‘TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384’와 같이 대문자로 표기한다. [그림3] 예시는 다음과 같은 내용이다.

대칭키 교환 방식은 ECDHE(Elliptic Curve Diffie Hellman Ephemeral)을 사용.
인증서 서명 방식은 RSA로 서명된 인증서로 상호 간의 신원을 확인.
대칭키 암호화 알고리즘은 AES 256bit와 GCM을 사용.
HMAC 알고리즘으로는 SHA-384를 사용해서 메시지의 무결성을 확인.

[그림3] 암호화 스위트 표기 예시

암호화 스위트는 여러 종류가 있다. 그 중에서 클라이언트(Client)가 지원하면서 취약하지 않은 암호화 스위트의 리스트를 서버에게 알려주면, 서버는 그 중에 지원하는 암호화 스위트를 선택해 합의한다. 실제 구현에서는 <그림5> 예시 같은 문자열이 아니라, 각 암호화 스위트마다 IANA(Internet Assigned Numbers Authority, 인터넷 할당 번호 관리기관)에서 지정한 2바이트(Bytes)를 사용한다. 문제는 키 교환, HMAC 알고리즘, 암호화 알고리즘 등 각 부분이 다양해지기 시작했다. HMAC 함수만 해도 SHA-1, SHA-128, SHA-384, SHA-256, MD5와 같은 방법이 있고 암호화 방식도 AES, DES, RC4와 같은 방법이 있다. 조합마다 코드를 만들기에는 너무 다양하고, 이미 존재하는 구성요소라 해도 새로운 조합법이 나올 때마다 업데이트해야 하므로 구현체에도 부담이 된다.

[그림4] TLS 1.3의 암호화 스위트 합의 예시

TLS 1.3에서는 이런 문제를 해결하기 위해, 암호화 스위트의 각 부분을 나눠서 합의한다.

암호화 알고리즘
키 교환 방법
인증서 서명 알고리즘

암호화 알고리즘, 키 교환 방법, 인증서 서명 알고리즘을 각각 합의함으로써 앞으로 등장할 수 있는 방식에 유연하게 대처할 수 있다. 게다가 핸드셰이크는 2번 발생하는 라운드 트립을 1번으로 줄일 수 있게 만들었다.

1-RTT Handshake

TLS 1.2는 커넥션을 하나 생성하면 라운드 트립을 2번 거쳐서 핸드셰이크해야 한다. TLS 1.3에서는 암호화 스위트 선택 방법을 최대한 단순화했다. 그리고 키 교환 방식으로 RSA를 배제해서 옵션 또한 최대한 줄였다. 그래서 클라이언트는 시작부터 키 교환 방식으로 DH를 사용한다고 가정할 수 있게 됐다. DH도 여러 가지 방식(X25519, P256 등)이 있지만, RSA나 그 외의 방식까지 고려해서 서버에게 여러 가지 키 교환 방식의 지원 여부를 물어봐야 했던 과거에 비해 훨씬 간단하게 추측할 수 있다.

RFC 문서에 나와 있는 TLS 1.3의 전체 핸드셰이크를 1.2와 비교하면 쉽게 이해할 수 있다. TLS 1.2에서는 커넥션이 맺어지면, 클라이언트는 ‘ClientHello’를 보내서 클라이언트가 지원하는 암호화 스위트 목록을 보낸다. 서버는 그중 하나 선택해서 ‘ServerHello’ 메시지를 보낸다. 만약 디피-헬먼 방식을 이용해 키를 교환한다면 서버의 공개키(Public Key)도 동시에 보낸다.

앞에서 이야기한 것처럼 TLS 1.3에서는 암호화 방식을 각각 합의한다. 그리고 키 교환 방식도 ECDHE 혹은 DH만을 지원한다. 따라서 클라이언트는 시작할 때부터 ‘ClientHello’를 보낼 때 지원하는 키 교환 방식에 해당하는 모든 방법을 TLS 핸드셰이크 확장기능(TLS Handshake extension)인 ‘key_share’와 함께 동시에 보낸다.

        Client                                               Server

        ClientHello
        + key_share             -------->
                                                  HelloRetryRequest
                                <--------               + key_share
        ClientHello
        + key_share             -------->
                                                        ServerHello
                                                        + key_share
                                              {EncryptedExtensions}
                                              {CertificateRequest*}
                                                     {Certificate*}
                                               {CertificateVerify*}
                                                         {Finished}
                                <--------       [Application Data*]
        {Certificate*}
        {CertificateVerify*}
        {Finished}              -------->
        [Application Data]      <------->        [Application Data]

[그림5] TLS 1.3 (RFC8446) 전체 핸드셰이크 과정

예를 들어, 크롬 브라우저에서 TLS 1.3을 사용한다면 ‘ECDHE X25519’ 키 교환 방식을 서버가 지원한다고 가정하고 보낸다.

0-RTT Resumption

HTTP/1.1만 지원하는 서버에 브라우저가 접속하면, 동시에 리소스를 받아오기 위해서 TCP 커넥션(TCP Connection)을 만든다. (크롬 브라우저의 경우 6개를 만든다.)만약 해당 서버가 TLS를 사용 중이라면, TCP 커넥션을 만들 때마다 TLS 핸드셰이크 과정을 거쳐야 해, 굉장히 많은 리소스를 소모해야 한다. 그래서 TLS 1.2에서는 처음 핸드셰이크 과정을 거칠 때 ‘Session id’를 받아둔 후, 다시 핸드셰이크할 때 ‘Session id’와 서로 교환했던 키를 이용해 핸드셰이크를 마무리한다. 하지만 ‘Session id’를 이용해 TLS 핸드셰이크를 다시 진행할 때는 라운드 트립이 1번 발생해야 한다. TLS 1.3에서는 이 부분을 개선해 라운드 트립이 발생하지 않도록 만들었다.

      Client                                                Server

      ClientHello                   -------->
                                                       ServerHello
                                                [ChangeCipherSpec]
                                    <--------             Finished
      [ChangeCipherSpec]
      Finished                      -------->
      Application Data              <------->     Application Data

TLS 1.2 (RFC5246) 약식 핸드셰이크

         Client                                               Server

         ClientHello
         + early_data
         + key_share*
         + psk_key_exchange_modes
         + pre_shared_key
         (Application Data*)     -------->
                                                         ServerHello
                                                    + pre_shared_key
                                                        + key_share*
                                               {EncryptedExtensions}
                                                       + early_data*
                                                          {Finished}
                                 <--------       [Application Data*]
         (EndOfEarlyData)
         {Finished}              -------->
         [Application Data]      <------->        [Application Data]

TLS 1.3(RFC8446) 0-RTT 핸드셰이크

[그림6] TLS 1.2와 TLS 1.3 비교

TLS 1.3의 핸드셰이크는 키 하나를 만들어서 공유한다. 이 키를 PSK(Pre-Shared Key)라 부른다. 이를 암호화된 통신으로 주고받으면, 다음 커넥션이 맺어질 때 진행하는 핸드셰이크에서는 클라이언트가 PSK와 애플리케이션 데이터(Application Data)를 포함 시켜서 보낸다. (애플리케이션 계층이 HTTP라면 HTTP로 요청한다.) TLS 1.3에서 0-RTT 재개(0-RTT Resumption) 방식으로 TLS 핸드셰이크 과정을 거친다면, 핸드셰이크를 위한 클라이언트-서버 간 통신 없이도 새로운 TCP 커넥션을 맺을 수 있다.

강력한 안전성 추구

RSA를 사용하면 클라이언트가 핸드셰이크 초반에 서버로 RSA 공개키를 요청해야 하고, 공개키를 받은 후 대칭키를 서로 공유하는 커넥션을 다시 한번 맺어야 한다. 즉, 앞에서 이야기한 방법처럼 라운드 트립 1번으로 핸드셰이크를 마칠 수 없게 된다. 그래서 TLS 1.3은 더는 RSA를 이용한 키 교환 방식을 지원하지 않는다.

RSA를 더는 지원하지 않는 이유에는 보안 취약성도 있다. RSA 키 교환 방식은 서버가 본인의 인증서를 CA(Certificate Authority)로부터 받는 공개키-비밀키 쌍을 가지고 키를 교환한다. 이는 현재 서버 어딘가에 RSA의 고정 된 비밀키가 저장돼 있다는 이야기다. 만약 누군가가 모든 통신 과정을 감청하고 있고, 이를 저장해뒀다가 서버의 치명적인 취약점을 발견해서 비밀키가 탈취된다면, 감청한 데이터를 해독할 수 있다. 현실성이 떨어져 보이지만, 국가 단위에서는 충분히 가능한 방법이다. 이런 문제점을 RSA가 PFS(perfect forward secrecy)가 아니라고 이야기한다.

TLS 1.3에서 사용하는 디피-헬먼(Diffie-Hellman)은 정적인 디피-헬먼은 지원하지 않고, 일시적인 디피-헬먼(Ephemeral Diffie-Hellman)만 지원한다. 이는 서버와 클라이언트가 키를 교환하기 위한 비밀키를 매번 바꿔서 사용한다는 의미다. 비밀키를 매번 바꾸기 때문에, 서버와 클라이언트가 감청당하더라도 서버가 나중에 해킹당했을 때 이전의 통신한 내용을 해독할 수 없다.

TLS 1.2에서 문제가 됐던 많은 키 교환 방식이나 암호화 방식을 1.3에서는 없애버렸다. 그 중에는 오래된 RC4, DES, 3DES 같은 것이 있고, MD5나 SHA-1과 같이 취약한 MAC 함수도 더 이상은 지원하지 않는다. 1.2에서는 취약한 암호화 스위트를 지원하지 않도록 설정해야 했다. 그렇지 않으면 중간자가(Man in the Middle) 클라이언트에서 취약한 암호화 스위트만 지원하는 것처럼 행동해 공격하는 경우가 있다. 하지만 1.3에서는 이미 취약하다고 알려진 암호화를 삭제함으로써 서버 관리자의 관리 이슈가 줄어들었다.

TLS 1.3 지원

[그림7] 브라우저별 TLS 1.3 지원 현황

크롬 브라우저는 63버전부터 TLS 1.3을 지원한다. 그 외에도 안드로이드용 크롬 브라우저와 파이어폭스(Firefox)에서도 TLS 1.3을 지원한다. 현재까지 TLS 1.3을 지원하지 않는 브라우저는 MS 엣지(MS Edge)와 인터넷 익스플로러(Internet Explorer), 오페라(Opera) 등이 있다. (MS 엣지는 개발 중이다.)

애플 사파리는 기본적으로 지원하지 않지만, macOS High Sierra의 Safari 11.1버전에서는 <코드1>의 명령어를 입력하면 TLS 1.3을 지원하도록 설정할 수 있다.

$ sudo defaults write /Library/Preferences/com.apple.networkd tcp_connect_enable_tls13 1

[코드1] Safari 11.1에서 TLS 1.3을 활성화 하는 명령어

서버 프로그램 중 엔진엑스(Nginx)는 1.13버전 부터 TLS 1.3을 지원하고 있으므로 ‘ssl_protocols’ 설정에 1.3만 추가해주면 된다. 아파치(Apache)에서는 TLS 1.3을 지원하는 OpenSSL이 이제 막 나온 단계라 아직 지원하지 않는다. 그리고 MS의 IIS도 아직 TLS 1.3을 지원하지 않는다.

그래서 지금 당장 써도 될까?

TLS같이 인터넷 연결 과정에서 중추가 되는 프로토콜은 많은 장비가 관여하고 있어서 함부로 버전을 올리기에는 부담이 클 수 있다. TLS 1.3에서는 이런 부분을 고려해 완벽하게 하위 호환될 수 있도록 제작했다. TLS 1.3은 드래프트(Draft) 과정을 거치면서 많은 테스트 과정을 거쳤고, 점유율이 가장 높은 크롬 브라우저가 이를 지원하고 있다. CDN/DNS 제공 업체인 클라우드플레어(Cloudflare) 외 페이스북(Facebook)과 인스타그램(Instagram)도 TLS 1.3을 지원하고 있다.

TLS 1.3은 이전 버전에서 가지고 있던 많은 레거시(Legacy)를 없애면서 더 안전하고 빠른 프로토콜이 됐다. TLS 1.2에서 노출된 취약점과 위협요소가 언제 우리를 위협할지 알 수 없다. TLS 1.3을 조금이라도 빨리 적용해서, 발생할 수 있는 보안사고를 미리 예방하는게 좋지 않을까?

[참고1] TLS 1.3 - CloudFlare London Tech Talk

References

Static type의 맹점

2018-08-10T11:07:00+09:00

이 글은 “Programming JavaScript Applications” (O’Reilly)의 저자 Eric Elliott의 The Shocking Secret About Static Types을 번역한 글 입니다.

TL;DR

정말 버그를 줄이고 싶다면 TDD를 사용하세요. 멋진 툴과 함께 하고 싶은것 이라면 static type을 사용해보세요.

static type은 만병통치약인가?

Typescript의 인기는 폭발적으로 증가해왔습니다. 저는 Typescript와 static type을 좋아합니다.(사내 프로젝트를 Typescript로 진행했고 typing을 선호합니다.) 하지만 Typescript를 단순히 타입 시스템 때문에 사용하는 것이 아니라 다른 훌륭한 기능 때문에 사용합니다. Typescript는 명칭적 타이핑(Nominal)보다는 구조적 타이핑(Structural)에 가깝습니다.(Nominal typing과 Structural typing의 차이에 대해서) 이 말인즉슨 타입의 이름이나 식별자를 기반으로 한 타입 시스템이라기 보다는 duck typing이 자동화되어 동작하는것에 가깝다는 의미입니다. 이는 Javascript와 같은 동적인 언어의 장점을 잘 살린 부분입니다.

사람들이 오해하는 것 중에 하나가 Typescript가 실제로 해결할 수 없는 문제를 해결해 줄 것이라 믿는 것 입니다.

Typescript의 가장 강한 강점으로 소개하는 내용은 “대규모의 웹 애플리케이션은 static type 없이는 힘들다.” 입니다. Typesciprt를 통해 static type을 사용하면 jump to definition이나 automatic refactoring과 같은 기능을 사용할 수 있도록 만들어줍니다. 그리고 이런 기능은 우리의 생산성이 높아진 것처럼 느끼게 해줍니다.(그리고 실제로도 더 생산적이게 만들어 줍니다.)

하지만 많은 사람들은 static type을 사용하면 애플리케이션의 버그가 줄어드는데에 도움을 줄 것이라고 믿습니다. static type을 사용하면 중대한 버그는 잡을 수 있습니다. 이는 부정하기 힘든 사실입니다. 하지만 정말로 static type은 전반적으로 버그율을 낮추는데 도움이 될까요?

static type은 거짓된 안정감을 줍니다.

두 가지의 연구 자료에서 Github의 데이터를 사용해 얼마나 많은 버그율을 갖고 있는지 조사했습니다.

확실히 말하기는 힘들지만 위 차트에서는 강력한 타입언어가 우리가 버그를 덜 만들도록 만들어 준다고 확신하기는 어렵다. - Daniel Lebrero, “The Broken Promise of Static Typing”

좀 더 권위있는 연구에서는 Static type이 조금 더 도움이 된다고 이야기하고 있습니다: “A Large Scale Study of Programming Languages and Code Quality in Github” from Baishakhi Ray, Daryl Posnett, Vladimir Filkov, Premkumar T Devanbu, from UC Davis.

데이터를 통해서 절차지향 언어보다는 함수형 언어가, 약한 타이핑보다는 강한 타이핑이, 동적 타입보다는 정적 타입이 그리고 unmanaged memory보다는 managed memory가 더 버그를 적게 만든다는 것을 알 수 있다.

여기까지만 보면 Static type이 더 좋다는 이야기 같지만,

이 관계들은 통계적으로는 중요하지만 영향도는 좀 적었다.

제게도 static type이 버그를 줄이는데 중대한 역할을 한 경험적 증거가 없습니다. 개발자가 사용할 수 있는 멋진 개발툴과 static type은 실제로 전반적인 버그를 잡는데에 도움이 되지 않습니다.

타입의 정확도는 프로그램의 정확도를 보장하지 않습니다.

코드를 실제로 돌려보지 않고서는 이 코드가 진짜 동작할지 전혀 알 수가 없습니다. 물론 static type을 사용하면 변수가 선언되지 않았느지, object가 넘어가야할 함수 파라미터에 array가 넘어갔다던지 이런 문제는 해결할 수 있습니다. 하지만,

타입 체크만으로는 잡을 수 없는 버그가 수없이 많습니다. 그리고 …
이걸 잡을 수 있는 다른 여러가지 방법이 있습니다.

그래서 정말로 버그를 잡을 수 있는 효과적인 방법은 뭔가요?

테스트 주도 개발!(Test Driven Development, TDD) 특히 테스트 우선 방법론!

TDD만이 구원이다.

몇몇 좋은 연구에서 TDD의 효과에 대해서 이야기하고 있습니다. Microsoft, IBM, 그리고 Springer 같은 유명한 곳에서 나온 연구도 있습니다. Springer의 연구에서는 비슷한 두 프로젝트 중에서 테스트 우선적인 방법을 사용해서 개발한 프로젝트가 40%-90%의 버그가 줄어들었다고 합니다. 테스트를 우선해서 개발했을 때와 테스트를 개발 후에 했을때, 테스트를 전혀 안 했을때를 비교한 Springer 이외의 다른 연구에서도 비슷한 결과를 보여줍니다. 특히 테스트 우선 개발시에는 탁월한 버그 감소율을 보여주는데 40%-80%의 버그가 줄어듭니다.

TDD야 말로 버그를 반으로 줄여주는 가장 효과적인 방법입니다. 그리고 이 주장을 뒷받침해주는 많은 사례들이 있습니다.

그래서 Typescript를 쓰지 말라는 말인가?

그럼에도 우리는 static type을 사용하고 싶습니다. 그러나 이 선택지를 고르는 이유가 Typescript가 주는 굉장한 기능들 때문이여야하지 버그를 잡아줄 것이라 기대하면서 사용하면 안됩니다.

standard javascript에 타입 표시 기능을 추가한 rtype에 영향을 받은 Typescript의 첫 인상은 굉장했습니다. 하지만 사용을 적극 권장하지 않는데에는 몇 가지 이유가 있습니다.

코드를 Typescript로 작성하기에는 거부감이 드는것은 단지 ECMAScript 표준과 Typescript와 키워드, 타입 기능들이 충돌하는 것 때문이 아닙니다.(interface와 implements와 같은 키워드)

Typescript의 장점 중 하나는 이런 충돌이 생긴다 하더라도, 컴파일러가 충분히 번역해서 ECMAScript에 맞는 표준으로 다르게 컴파일 할 수 있다는 점입니다. 하지만 단점으로는 Javascript 표준으로 더 이상 작성하지 않는다는 점입니다. 제 예상으로는 Typescript가 Javascript의 superset자리를 계속 유지한다기 보다는 다른 형태로 갈라져 나올것이라 생각합니다.

그리고 제게는 이 부분이 굉장히 걱정하는 부분입니다. Javascript를 가르치는 입장에서 많은 개발자들이 사용하는 다양한 개발툴과 개발 프레임워크에 적용가능한 것을 가르치고 싶습니다. 여러분은 이런 점을 걱정하지 않겠지만, 여러분의 코드는 다른 개발자에게도 읽고 배우기 쉬워야하고 무엇보다 그 코드에 기여하기 쉬워야합니다. 당신 혼자는 Typescript에 적응했을지 모르지만 그 외의 다른 사람들은 Typescript에 적응하기 어려울 수 있습니다.

지금 당장에는 엄청난 속도로 Typescript가 성장해나가고 있지만, 전체 Javascript의 환경에 비해서는 아직 작습니다. 심지어 jQuery보다도. 물론 성장해 나아가는 속도는 놀랍고, Javascript로 컴파일 가능한 대체제(Coffeescript, …) 중에서는 지배적인 위치에 다다랐습니다.

어떤 도구는 단점을 알고도 사용하기에 가치있지만, Typescript는 제게는 지금 당장 사용하기엔 올바르지 않은것 같습니다. 하지만 MS의 Code와 Typescript의 궁합은 한 번쯤은 사용해봐도 좋습니다. 맘에 들것을 확신합니다.

Conclusion

버그를 줄여주는 점을 강점으로 보기에는

Static type는 과대평가되어 있습니다.

그러나 다른 기능들과 함께 보면 static type은 여전히 멋지고 사용하기에 가치가 있습니다. 결론을 내자면,

정말 버그를 줄이고 싶다면 TDD를 사용하세요. 멋진 툴과 함께 하고 싶은것 이라면 static type을 사용해보세요.

알아두면 쓸데없는 신비한 TLS

2018-06-22T18:09:00+09:00

TLS란,

초기에 HTTP 통신은 암호화되지 않은 통신이었다. 당연히 문제가 되었고, 이 문제를 보완하고자 Netscape사는 browser에서 사용하기 위한 규격인 SSL을 제작했다. SSL은 널리 보급되었고, 나중엔 HTTP 외에 다른 Application layer protocol에서도 사용가능하도록 만든 protocol이 TLS(Transport Layer Security)다.

TLS는 크게 2단계로 구분할 수 있는데, 서로 protocol 버전과 암호화할 키를 주고 받는 handshake 단계와 실제 application이 동작하는 단계다. application의 내용이 주고 받아지는 부분에서는 대칭키 암호화(symmetric cryptography)가 이루어지지만, handshake 단계에서는 모든 내용이 평문으로 주고 받게 된다 (TLS 1.3부터는 handshake 중에도 암호화가 됨).

TLS의 동작 원리까지 깊이 알 필요는 없고, 오히려 handshake 과정에서 필요한 개념들이 응용이 가능하거나, SSL 인증서 발급할때 내가 무슨짓을 하고 있는건지 알 수 있을 것이다. 이 글에서는 TLS가 필요로 하는 다양한 표준, 암호화 방법에 대해서 이야기 하고, TLS 동작에 대해서는 간략하게 이야기할 것이다(자세한 내용이 궁금하면 구현체 소스를 보자).

HMAC

메시지를 두 peer간 통신을 할 때 메시지의 내용이 손상될 수 있다. 메시지의 손상 여부를 파악하기 위해서 사용하는 기술이 MAC(Message Authentication Code)이다. 그 중 TLS에서는 HMAC(Hash MAC)이라는 방법을 사용한다. 만약 A라는 메시지의 내용을 보낸다고 가정하고, 송신 peer는 A를 수신 peer와 합의한 Hash함수를 이용해서 hash 값을 만들고 메시지 A에 hash 덧붙인 A`을 보낸다. 이를 수신 측 peer에서는 A와 hash값을 분리하고 A의 hash 값을 구한 뒤 받은 값과 비교해, 제대로 메시지가 도착했는지 검증한다.

디지털 서명(Digital signature)

월세 계약과 같은 부동산 계약을 하고 나면 계약서에 확정일자란 것을 받는다. 확정일자는 공증인(여기서는 국가가 된다)이 해당 계약내용을 확인하고 증명해주는 것이다. 확정일자를 받으면 도장 혹은 공증서를 받게 되는데, 이 개념을 컴퓨터 파일에 적용한 것이 디지털 서명이다. 신뢰 받는 기관(Root CA와 같은)에서 내 문서가 사실임을 확인 받고 다른 사람들도 이 사실이 진짜임을 확인 가능하게 해주는 체계이다.

일반적인 디지털 서명은 RSA 알고리즘을 이용한다. 모두에게 신뢰 받는 기관에서는 요청자의 문서의 hash 값을 구하고 RSA 개인키로 암호화한다. 그리고 암호화한 값(서명)을 해당 문서 뒤에 첨부한다. 이 문서를 받은 사람은 서명한 기관의 공개키로 서명을 복호화한다(여기서 모두가 신뢰 받는 기관의 공개키는 알고 있다). 그리고 서명을 제외한 나머지 부분을 같은 hash 함수로 hash 값을 구하고 복호화한 서명과 비교한다. 일치한다면 해당 문서는 위변조가 없고, 신뢰 받은 기관에서 서명 받은 문서라고 판단할 수 있다.

Chain of trust

모든 도메인을 한 두 곳의 신뢰받는 기관에서 인증해주면 좋겠지만, 현실적인 한계가 있다. 그래서 client가 알고 있는 수많은 신뢰받는 기관이 있고 이 기관을 대행할 중간 인증 기관들이 있다. 이 중간 인증 기관은 신뢰받고 있는 기관(Root CA)로 부터 인증서를 발급 받고, 중간 인증 기관은 그 하위의 중간 인증 기관을 인증해주는 과정을 거쳐서 최종적으로 내 사이트를 인증해 주는 chain 형태로 인증방식을 갖는다. 이를 그림으로 표현하면 아래와 같다.

Root CA는 각 국가, OS, 브라우저에 따라서 정책이 다양하다. 이는 클라이언트가 갖고 있는 인증서이기에 변화가 어렵다. 그러나 chain형식으로 관리하면 SSL 인증서 발급의 유연성을 확보할 수 있다. 위 그림에서 보면 self-sign이란 표현이 있다. Root CA의 인증서는 self-sign하는데, 상위의 CA가 없으므로 자신의 개인키를 갖고 자신의 인증서를 디지털 서명해둔다. 이 서명은 Root CA의 공개키를 사용해서 인증서의 신뢰성을 판단한다.

PKCS

PKCS(Public Key Cryptography Standard)는 RSA Security Inc.에서 발행하는 공개키 암호화 표준이다. RSA를 암호화하는 방법은 제곱 연산이나, 나머지 연산과 같은 수식으로 이루어져 있어서(c = m^e mod N), 데이터를 어떻게 숫자로 나타낼 것인가에 대한 표준이 정해져야 한다. 여기에 보안성을 더 강화하기 위해서 데이터를 복잡하게 만들거나, 암호화 하고자 하는 데이터의 크기를 늘려서 암호화하는 방식을 정의한 것이 PKCS다.

X.509

SSL 인증서를 발급 받을때 .der 혹은 .pem으로 되어 있는 인증서 파일을 받는다. X.509는 이런 인증서의 표준이다. 사이트의 도메인과 CA의 이름, 유효기간, 사이트의 RSA 공개키가 들어간다. 그리고 마지막에는 CA에서 서명한 디지털 서명이 포함된다. X.509v3 인증서의 구조는 아래와 같이 생겼다.

Certificate
- Version 인증서의 버전을 나타냄
- Serial Number CA가 할당한 정수로 된 고유 번호
- Signature 서명 알고리즘 식별자
- Issuer 발행자 (CA의 이름)
- Validity 유효기간
  - Not Before 유효기간 시작 날짜
  - Not After 유효기간 만료 날짜
- Subject 소유자 (주로 사이트의 소유자의 도메인 혹은 하위 CA의 이름)
- Subject Public Key Info 소유자 공개 키 정보
  - Public Key Algorithm 공개 키 알고리즘의 종류 (RSA, …)
  - Subject Public Key 공개 키
- Extensions 확장 필드
  - …
Certificate Signature Algorithm 디지털 서명의 알고리즘 종류 (sha256WithRSA, sha1WithRSA, …)
Certificate Signature 디지털 서명 값

CA는 해당 인증서의 Certificate부분을 PKCS#1 v1.5 padding 방법을 이용해서 디지털 서명하고 hash방법에 대해서는 Certificate Signature algoritm에 명시한다.

위 인증서 구조를 보면 Subject가 하나만 있다. Subject에는 도메인이 명시되는데, X.509 구조에서는 하나의 인증서는 하나의 도메인 밖에 인증해줄 수 밖에 없다. 만약 웹 사이트 관리자가 example.com과 www.example.com를 두 개의 도메인을 갖지만 같은 서비스를 운영한다면, 인증서를 두 개 만들어야한다. 이를 보완하고자, X.509 v3 인증서 표준에서는 확장 기능으로 SAN(Subject Alternative Name)이라는 기능을 제공한다. 여기에 Subject의 이름 외에도 다른 도메인들을 명시해서 하나의 인증서지만 복수의 도메인을 인증받을 수 있다.

Cipher Suite

TLS에서는 암호화하는 방법을 표준으로 특정하지 않고, server와 client가 합의해서 결정한다. 서로 합의해야 하는 알고리즘은 4가지인데, 대칭키 전달 방식, 인증서 서명 방식, 대칭키 알고리즘, HMAC 알고리즘이다. TLS에서는 서버와 클라이언트가 이 4가지 알고리즘을 세트로 합의하고, 합의된 알고리즘으로 application layer의 내용을 암호화해서 전송한다.

cipher suite는 TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384와 같이 표기한다. 이 cipher suite를 읽어보면, 다음과 같이 해석할 수 있다.

대칭키 전달 방식은 ECDHE(Elliptic Curve Diffie Hellman Ephermeral)을 사용하며,
인증서 서명 방식은 RSA로 서명된 인증서로 상호간의 신원을 확인하고,
대칭키 암호화 알고리즘은 AES 256bit와 GCM를 채택하고,
HMAC 알고리즘으로는 SHA 384를 사용해서 메시지의 무결성을 확인한다.

cipher suite는 여러가지 있다. 그중에서 client가 지원하면서 취약하지 않은 cipher suite의 리스트를 서버에게 알려주면, 서버는 그중에 지원하는 cipher suite를 선택해서 보내 합의한다.

TLS의 동작

TLS는 application protocol의 내용을 암호화하는데에 목적을 둔다. 암호화 전에, TLS Handshake protocol은 TLS 버전과 cipher suite를 합의하고, 인증서를 교환한다. 그리고 필요하면 Diffie-Hellman 키도 공유한다.

  Client                                               Server

  ClientHello                  -------->
                                                  ServerHello
                                                 Certificate*
                                           ServerKeyExchange*
                                          CertificateRequest*
                               <--------      ServerHelloDone
  Certificate*
  ClientKeyExchange
  CertificateVerify*
  [ChangeCipherSpec]
  Finished                     -------->
                                           [ChangeCipherSpec]
                               <--------             Finished
  Application Data             <------->     Application Data

         Figure 1.  Message flow for a full handshake

* Indicates optional or situation-dependent messages that are not
always sent.

ClientHello 메시지에는 리스트로 된 cipher_suites 필드가 있다. 클라이언트가 지원하는 cipher suite를 이곳에 모두 적어주면 서버는 이 중에서 자신이 지원하는 cipher suite를 ServerHello 메시지에 넣어서 보낸다(만약 서로 지원하지 못하면 연결이 끊어진다). 정상적인 ClientHello를 받은 서버는 ServerHello를 시작으로 다른 메시지를 보내기 시작하는데, ServerHello는 ClientHello 메시지의 답변에 해당하는 내용이 들어간다(구조도 비슷하게 생겼다).

Certificate 메시지는 서버의 인증서와 그 인증서를 확인한 CA들의 모든 인증서인 certficate chain을 보낸다. 합의한 키 교환 방식이 DH(Diffie-Hellman)인 경우, ServerKeyExchange메시지를 통해서 서버의 key를 보낸다. 모든 메시지를 보냈으면 ServerHelloDone을 보낸다.

ServerHelloDone을 받은 client는 Certificate 메시지의 certificate chain 서명을 확인한다. 서버로부터 CertificateRequest를 받았다면, 클라이언트의 Certificate를 서버에게 전송한다. 여기서도 마찬가지로 키 교환 방식이 DH인 경우에는 ClientKeyExchange메시지를 통해 클라이언트의 키를 교환한다(이 과정을 이해하려면 Diffie-Hellman 알고리즘을 찾아봐야 한다).

이 과정이 끝나면 client와 server는 TLS의 버전, 사용할 cipher suite를 결정하고, 상호간의 신원 확인이 끝난 상태가 된다. 이제부터는 본격적으로 암호화 통신이 가능하다. client는 ChangeCipherSpec 메시지를 보내고, 그 시점부터 모든 메시지는 암호화된 패킷인 TLSCiphertext라는 구조로 보내진다(참고로 handshake의 과정은 TLSPlaintext 구조로 메시지를 주고 받는다).

client가 보내는 Finished 메시지는 서로 주고 받은 키가 정확한지에 대해서 검증하기 위한 과정이다. 여태까지 보낸 모든 Handshake 통신의 내용을 SHA-256을 통해서 hash한 값을 대칭키로 암호화해서 보내고 server에서는 교환한 대칭키로 복호화해서 client가 올바른 키를 갖고 있는지 검증한다. 그리고 server도 똑같이 Finished 메시지를 보내서 server가 제대로 키를 구했는지 client도 확인할 수 있도록 한다.

server가 Finished 메세지를 보냄으로서 handshake 과정은 끝난다. handshake가 끝나면 합의한 암호화 방법으로 application level 통신을 시작한다. 예를들어, HTTP라면 일반적인 HTTP의 내용(GET / HTTP/1.1\r\n…)을 TLSCiphertext의 content 필드에 담아서 보내게 된다.

SNI

SNI(Server Name Indication)는 ClientHello의 확장 기능으로, client가 요청한 server의 도메인을 적어서 보내는 것이다. handshake 과정을 보면 ClientHello 이후에 서버에서는 인증서를 보내준다. 하지만 하나의 서버에서 다양한 도메인을 처리할 수 있는 VirtualHost 기능 때문에, 서버에서는 어떤 도메인의 인증서를 보내줘야 할지 모른다. 과거에는 이런 문제로 SSL 인증서를 서버당 하나의 도메인에만 설정할 수 있었다. 이를 해결하기 위해 SNI라는 확장 기능을 도입했다. 이는 TLS의 extension을 다룬 RFC 6066에 나와있다.

ALPN

ALPN(Application Layer Protocol Negotiation)은 ClientHello의 확장 기능으로, TLS handshake 이후에 application layer의 프로토콜과 버전을 결정하기 위한 기능이다. 일례로 HTTP/2에서는 HTTP의 버전을 합의하기 위해서 ALPN을 사용한다. 먼저 client가 자신이 HTTP/1.1과 2를 지원한다는 사실을 ALPN으로 보낸다. 만약 서버가 ALPN과 HTTP/2를 지원한다면 ServerHello의 확장 필드에 h2를 적으면 handhshake 이후 HTTP/2로 통신이 시작된다. ALPN을 지원하지 않으면, ServerHello에 ALPN 필드가 없으므로 HTTP/1.1로 통신하게 된다. 자세한 내용은 RFC 7301에 정의되어 있다.

TLS handshake 과정에 대한 자세한 예시는 구현체를 보자.

Luavis' Dev Story

🚦Multitasking 201 1편

반성문

본문

Concurrent와 Parallel의 동질성

병렬적이나 동시적이지 않을때

사라진 800MB를 찾아서

문제를 찾아가는 과정

문제의 근본 원인을 찾아서

Spatial data를 10,000배 잘 다루게 된 방법

Spatial data의 intersects의 계산 방법

그러면 문제는 어디서 발생하는걸까?

결론

G1: Garbage first garbage collector

References

React, Typescript, Webpack환경에서 번들링 속도 올리기

loader 줄이기.

transpileOnly, experimentalWatchApi

그외 webpack optimization

Cache

References

Athena를 Zeppelin과 함께 쓰기

docker-compose을 이용한 Zeppelin 설치

Zeppelin과 Athena 연결

타원곡선 디피 헬만

Modular 연산 (나머지 연산)

합동

Modular 역수

군 (Group)

Modular N에 대한 정수 ( \(\mathbb{Z}/n\mathbb{Z}\) )

Modular N에 대한 곱셈군(Multiplicative group of integers modulo n)

이산로그 문제 (discrete logarithm problem)

타원곡선

타원 곡선의 연산

타원곡선의 이산로그 문제

타원곡선 디피 헬만

References

알아두면 쓸데없는 신비한 TLS 1.3

TLS

TLS 1.2의 문제점

TLS 1.2는 느리다

TLS 1.3은 다른가?

TLS 1.3의 특징

더 이상 묶음 판매 안 합니다.

1-RTT Handshake

0-RTT Resumption

강력한 안전성 추구

TLS 1.3 지원

그래서 지금 당장 써도 될까?

References

Static type의 맹점

static type은 만병통치약인가?

static type은 거짓된 안정감을 줍니다.

타입의 정확도는 프로그램의 정확도를 보장하지 않습니다.

그래서 정말로 버그를 잡을 수 있는 효과적인 방법은 뭔가요?

그래서 Typescript를 쓰지 말라는 말인가?

Conclusion

정말 버그를 줄이고 싶다면 TDD를 사용하세요. 멋진 툴과 함께 하고 싶은것 이라면 static type을 사용해보세요.

알아두면 쓸데없는 신비한 TLS

TLS란,

HMAC

디지털 서명(Digital signature)

Chain of trust

PKCS

X.509

Cipher Suite

TLS의 동작

SNI

ALPN

References