서론
작년 2학기에 수강했던 보안프로젝트설계 강의에서는 완전 동형 암호(FHE) 스킴을 활용하여 프로젝트를 진행하는 과제가 있었다. 나는 FHE 덧셈 연산을 활용하여, 기밀성이 보장되는 개표가 가능한 투표 앱을 개발했다. 다만, 아쉬웠던 것은 곱셈 연산은 활용해볼 기회가 없었다는 점이다. 그래서 프로젝트가 끝난 이후, 곱셈 연산을 구현해보고 이를 Android에서 사용할 수 있는 여러 병렬 처리 환경에서 실험해보기로 했다. 미루고 미루다 개강 직전에야 끝냈는데, 실험 결과를 간단하게 정리해보자.
배경
여기서는 내가 알고 있는 것을 다시 리뷰하고, 혹시 있을지 모를 독자 분들을 위한 설명도 겸하여 필요한 배경 지식을 간단히 짚고 넘어가겠다.
완전 동형 암호 (FHE)
완전 동형 암호(FHE, Fully Homomorphic Encryption) 스킴이란 암호화 된 상태에서도 연산의 정확성이 보장되는 암호화 스킴을 말한다. 이해를 돕기 위해 기존의 암호화 방식과 비교하면 아래와 같은 엄청난 차이점이 있다:
- 일반 스킴 | 암호화된 2개의 수끼리 연산하기 위해서는 둘 다 모두 반드시 복호화를 해야만 함
- FHE 스킴 | 암호화된 2개의 수를 복호화하지 않고 그 상태 그대로 연산할 수 있음
기존의 AES 암호화와 같은 방식에서는 암호문 상태에서 산술 연산을 직접 지원하지 않으므로, 연산을 하고 싶다면 복호화가 필요하다. 물론 모든 서비스 제공자들은 "우리는 보안을 잘 지키고 있어요!" 하면서 사용자를 안심시키곤 하나, 최근 쿠팡이나 통신사들 탈탈 털리는 걸 본 사람들이라면 아마 저 말을 신뢰하기는 다소 어려울 수 있다는 점을 알 것이다.
FHE 스킴에서는 저런 걱정을 할 필요가 없다. 복호화 자체가 필요 없기 때문이다. 물론 연산 외 과정에서는 문제가 있을 수 있으나, 일단 복호화를 1번이라도 덜 거친다는 것 자체가 보안성에 있어 엄청난 메리트인 것은 틀림이 없다.
BFV 스킴의 연산
이 프로젝트에서 사용한 FHE 스킴은 정수를 대상으로 하는 BFV 스킴이다. 서울대학교 연구진이 개발한 실수 대상 CKKS 스킴도 있기는 하나, 득표 수는 자연수로 표현되므로 BFV를 채택했다. 이 스킴은 크게 2가지 연산을 제공하는데, 덧셈과 곱셈이다. 그러나 다음과 같은 특이 사항이 있다:
곰셈의 연산 부하가 덧셈에 비해 압도적으로 높다.
그 이유는 BFV는 내부적으로 연산 과정에서 암호문의 원본 평문을 추측하기 어렵도록 노이즈를 도입하고 있는데, 곱셈의 노이즈 증가가 덧셈에 비해 많이 크기 때문이다. 그래서 곱셈 연산에서는 노이즈를 줄여주기 위해 키 스위칭(key switching)이라는 과정을 한 번 더 거치는데, 이 과정에서 원본에 비해 차수가 커진 결과가 나오기 때문에, 차수를 줄이는 재선형화(relinearize)가 필요하다. 또한, 연산 과정에서 노이즈도 더 많이 발생하는 만큼, 일정 수준에 도달하면 노이즈를 깎아주는 부트스트래핑(bootstrapping)도 진행해야 한다. 과정이 더 붙은 만큼, 부하가 더 많이 가는 작업인 것이다.
따라서, BFV 스킴을 사용함에 있어 덧셈 연산만 쓰는 서비스보다 곱셈 연산을 쓰는 서비스에 더 많은 처리 성능이 필요하게 된다.
NDK와 JNI
Android NDK(Native Development Kit)는 Android에서 C/C++ 코드를 사용해야 할 때 사용하는 개발 도구이다. C/C++ 코드를 CMake와 함께 빌드하여 앱에 네이티브로 올릴 수 있게 도와준다. 그리고 그 과정에서 JNI(Java Native Interface)를 통해 소통하게 된다. 즉, 정리하면 Android의 C/C++ 코드들은 C/C++ → JNI → Kotlin의 도식으로 이어진다는 것이다.
또한, 한 가지 재미있는 점은 NDK를 통해 작성된 C/C++ 코드에서도 C/C++ 수준에서의 병렬 처리를 사용할 수 있다는 듯하다. 다시 말해, thread와 OpenMP를 사용할 수 있다는 것이다.
Coroutines와 Dispatchers
링크를 참고하라.
실험 설계
접근
위에서도 언급했듯이, BFV 덧셈보다 곱셈이 부하가 크다. 상당히 크다. 그래서 보통은 서버 단에서 연산을 처리하도록 하는 게 국룰이라고 들었으나, 경우에 따라 온디바이스 처리가 필요한 경우도 있을 것이다. 개인 프라이버시를 반드시 지켜야 하는 서비스라던지. 이 경우 디바이스에서 곱셈 연산을 진행해야 하는데, 부하가 큰 만큼 최대한 효율적으로 처리를 해야 할 필요가 있을 것이다.
이를 위해 나는 NDK를 사용하는 Android 앱에서 사용 가능한 아래의 4가지 환경에서 곱셈 연산을 병렬 처리로 실행해보고, 어떤 선택지가 가장 좋을지를 평가해보고자 한다:
- Kotlin Side
Dispatchers.IO- Kotlin Side
Dispatchers.Default- Kotlin Side
newFixedThreadPoolContext- C++ Side
thread
조건
모든 환경에서 동일하게 적용되는 공통 실험 조건은 아래와 같다:
- 연산 횟수 | 100 번
- 측정 대상 | 곱셈 연산을 100번 반복했을 때의 실행 시간
- 측정 기기 | Galaxy S24+ (10 코어 / 슈퍼 1, 빅 2, 미들 3, 리틀 4)
실험을 진행한 환경은 아래와 같다:
- C++
thread, 스레드 1개- C++
thread, 스레드 4개- C++
thread, 스레드 6개- C++
thread, 스레드 10개 (실제 물리 코어 수와 동일)- C++
thread, 스레드 20개- Kotlin
newFixedThreadPoolContext, 스레드 10개 (실제 물리 코어 수와 동일)- Kotlin
Dispatchers.IO, 스레드 10개- Kotlin
Dispatchers.IO, 스레드 100개- Kotlin
Dispatchers.Default, 스레드 10개- Kotlin
Dispatchers.Default, 스레드 100개
코드
벤치마킹 및 실험에 사용한 코드는 아래와 같다:
결과
실험 결과는 아래와 같다:
각 환경별 연산 소요 시간
| 언어 | 구분 | 스레드 수 | 시간 (ms) |
|---|---|---|---|
| C++ | thread | 1개 | 46,799 |
| C++ | thread | 4개 | 17,536 |
| C++ | thread | 6개 | 15,057 |
| C++ | thread | 10개 | 10,864 |
| C++ | thread | 20개 | 11,090 |
| Kotlin | newFixedThreadPoolContext | 10개 | 11,100 |
| Kotlin | Dispatchers.IO | 10개 | 11,324 |
| Kotlin | Dispatchers.IO | 100개 | 13,017 |
| Kotlin | Dispatchers.Default | 10개 | 11,199 |
| Kotlin | Dispatchers.Default | 100개 | 11,988 |
분석
베스트 케이스는 C++, 스레드 10개
최대 성능은 C++, 스레드 10개 사용 환경이었다.
아무래도 C++ 단에서 JNI와 통신하지 않으면서 모든 연산을 처리해버렸고, 동시에 스레드 수도 실제 물리 코어 수와 동일하게 유지하여 문맥 교환 비용을 줄인 것이 최대 성능의 주 이유라고 생각해볼 수 있을 것 같다. 그러나, 현재 내 기기가 빅-리틀 아키텍처를 택하는 만큼 각 코어의 성능이 다르기 때문에, 오히려 빅 코어의 활성화를 노리는 스레드 수를 정하는 게 단순히 물리 코어 수와 같은 스레드 수를 쓰는 것보다 더 높은 성능을 낼 수 있다는 점은 감안하고 봐야 할 것이다.
Kotlin 베스트 케이스는 newFixedThreadPoolContext
Kotlin 내에서는 스레드 풀을 아예 별도로 생성해버리는 newFixedThreadPoolContext 케이스가 가장 높은 성능을 냈다.
이는 Coroutine이 다른 작업에도 동원될 수 있는 Dispatchers와는 다르게, 이 경우 아예 Java의 ExecutorService 수준에서 별도의 스레드 풀을 생성해버리기 때문이다. 정말로 이 작업만을 위해 독점적으로 생성된 스레드 풀인 만큼, 작업 처리에 집중되어 높은 성능을 내는 것은 당연한 결과일 것이다.
성능은 스레드 20개보다 10개가 더 우수함
C++ 스레드 10개와 C++ 스레드 20개 대조군에서, 스레드 10개가 훨씬 더 높은 성능을 냈다.
이유로는 스레드 개수가 실제 물리 코어 개수보다 많아지면서, 여러 스레드가 물리 코어를 오가느라 문맥 교환이 상당히 많이 일어났기 때문이라고 추측해볼 수 있겠다.
또한 동일한 이유로 Kotlin Dispatchers.IO 스레드 10개와 스레드 100개 대조군, Kotlin Dispatchers.Default 스레드 10개와 스레드 100개 대조군에서도 성능 차이가 발생했다고 볼 수 있겠다.
처리 속도가 스레드 개수에 비례하진 않음
C++ 스레드 1개는 약 46초 소요, 베스트 케이스인 C++ 스레드 10개는 약 11초 소요되었다. 즉, 대충 잡아서 4.5배 정도의 성능 향상이 있었다는 것이다. 왜 스레드 개수는 10개 늘어났는데 성능은 4.5배밖에 늘지 않았을까? 그 이유는 내 스마트폰인 Galaxy S24+의 CPU가 빅-리틀 구조를 택하고 있기 때문으로 추측된다.
빅-리틀 구조는 성능이 매우 좋은 빅 코어 조금과 그보다는 낮은 리틀 코어 다수를 섞는 전략이다. 위에서도 말했듯, Galaxy S24+의 CPU는 슈퍼 1, 빅 2, 미들 3, 리틀 4, 총 10개의 코어로 구성되어 있다. 그리고 나는 실험 설계 시 각 코어에 동일한 횟수의 곱셈 연산을 할당했다. 즉, 빅 코어 1개와 리틀 코어 1개가 같은 수의 곱셈을 진행했다는 것이다. 당연히 빅 코어에서 작업이 먼저 끝났을 것이고, 빅 코어는 리틀 코어가 작업을 마치길 기다렸을 것이다. 이러한 작업 불균형은 사실 병렬 처리에서는 흔하게 마주치는 문제이며, 이걸 어떻게 잘 풀어낼 것인지가 병렬 처리 프로그래머의 실력을 가늠하는 척도이기도 할 것이다.
스레드 100개에서 보이는 Dispatchers.IO와 Dispatchers.Default 성능 차이
특이한 점은 Kotlin Dispatchers.IO, 스레드 100개에서는 약 13초가 소요되었지만, Kotlin Dispatchers.Default에서는 그보다 1초 적은 약 12초로 충분했다는 것이다. 왜 동일한 Kotlin Coroutines를 사용했고 스레드 개수도 같았는데 이런 차이가 생겼을까?
이는 두 전략의 최대 생성 가능한 스레드 개수가 다르기 때문이다. 이전 게시글에서도 설명했듯이, Dispatchers.IO는 max(64, CPU의 코어 수)개의 스레드를 생성할 수 있지만, Dispatchers.Default는 실제 물리 코어 개수까지만 제한되기 때문이다.
물론 코드에서 나는 무조건 실험 조건에서 지정해 두었던 스레드 개수만큼 스레드 생성을 명령했다. 정확히는 async 블록을 100개 생성하면서 Coroutine을 100개 생성하라고 명령한 것이다. 그러나 Dispatchers.Default는 내가 Coroutine을 100개를 생성하라고 명령해도 스레드를 알아서 내 스마트폰의 코어 개수인 10개로 제한하여 생성하는 것으로 보인다. 그러므로, 아래와 같은 차이가 발생하게 되는 것이다:
Dispatchers.Default| Coroutine 100개, 스레드 10개, 물리 코어 10개Dispatchers.IO| Coroutine 100개, 스레드 64개, 물리 코어 10개
Coroutine만 스레드에 적절히 배분해주면 되는 Dispatchers.Default와는 달리, Dispatchers.IO는 Coroutine에 더해 스레드를 어떻게 물리 코어에 배분하면 될지 2중으로 고민을 해야 한다. 그러니 처리 속도가 1초 이상 지연되는 것은 어쩌면 당연한 일일지도 모르겠다.
게다가 Dispatchers.IO가 이렇게 많은 스레드를 생성하는 이유는 IO 작업 시 발생하는 블로킹을 최대한 피하기 위해서이다. 사실 성능이 떨어지는 것은 IO 작업이 아닌 고부하 연산을 요청한 내가 목적에 맞지 않는 작업을 요구해서인 것 같기도 하다.
결론
Kotlin과 C++은 취향 차이
물론 C++, 스레드 10개 환경에서 가장 실험 결과가 좋기는 했다. 그러나 Kotlin 환경에서도 최고 기록이 약 10초에서 11초를 웃도는 수준으로 나왔기 때문에, 사실 그렇게 비약적인 차이는 없었다고 볼 수 있다.
둘의 차이라고 한다면, 아무래도 Android 앱의 동작 환경이 Kotlin인 만큼, Kotlin에서 코드를 작성하는 것이 디버그나 스택 추적 등에 훨씬 용이하다는 것이겠다. 실제로 NDK를 사용하는 Android 앱 디버깅을 실행할 경우, Android 런타임 쪽 디버거와 NDK C++ 쪽 디버거 2개가 동시에 동작하기 때문에, 에뮬레이터가 아니라 내 스마트폰에서도 앱 속도가 매우 느렸다.
다만 아무래도 C++ 단에서 모든 것을 처리하는 것이 이론상으로도 - JNI 통신 횟수를 줄일 수 있다 - 그리고 실제 실험 결과로도 - Kotlin에 비해 약 150 ms 우수 - 조금 더 성능이 좋다. 따라서 정말로 극한의 최적화를 원한다면 C++ 단에서 병렬 처리를 진행하면 된다.
정리하자면, 각 환경에서는 아래와 같은 이점이 있고...
- Kotlin에서는 디버깅 용이성 확보 가능
- C++에서는 작지만 확실한 성능 우위 확보 가능
이 둘은 어느 무엇이 낫다고 확실하게 말하기 어렵기 때문에, 결국 취향 차이라는 결론을 내릴 수 있을 것 같다.
결국 중요한 것은 CS
제일 성능이 좋았던 케이스는 C++, Kotlin을 불문하고 스레드 개수를 물리 코어 개수와 동일하게 썼을 때였다. 물리 코어 개수보다 많은 스레드를 생성할 경우 문맥 교환으로 추정되는 추가 비용으로 인해 오히려 성능이 악화되는 결과가 발생했다.
그리고 이러한 내용들은 사실 전부 학부 강의 중 운영체제나 멀티코어컴퓨팅 등에서 병렬 처리 다룰 때 배우는 부분들이다. Kotlin이나 C++ 등의 언어에서 고도로 추상화되어 잘 보이지 않았지만, 정작 까보니 중요한 것은 각 언어의 영향보다는 오히려 근본 CS 지식들이었다는 점을 느낄 수 있었던 실험이었다.
트러블슈팅
NDK에서 C++ 전역 변수 초기화 시 주의점
트러블슈팅 중 매우 중요한 지식을 하나 얻었다. NDK에서 C++ 코드 작성 시, 전역 변수는 반드시 포인터로 선언하고 초기화를 나중에 해줘야 한다는 것이었다.
TLS
전역 변수 중에서도 개발자가 성능 최적화를 목적으로 각 스레드가 복사본을 가지라고 특정한 변수들은 보통 스레드 안 TLS(thread local storage)에 저장된다. 여기서 TLS란?
TLS는 스레드 로컬 저장소(thread local storage)의 약자로, 각 스레드가 공유 자원에 접근할 때 발생하는 부하를 줄이기 위해 공유 자원의 복사본을 저장하는 공간.
...이다. 이해를 돕기 위해 풀어 설명해보면, 예를 들어 연산을 위해 특정한 전역 변수를 여러 스레드에서 접근해야 할 수 있다. 고전적으로는, 이를 잘 통제하기 위해 mutex 등 동시성 통제 정책을 적용하곤 했다. 그런데 이러한 방식을 적용하면 여러 스레드가 공유 자원 접근하겠다고 줄을 서느라 오히려 작업이 지연되는 현상이 발생한다. 성능 올리겠다고 스레드 여럿 썼는데 오히려 성능이 낮아지는 괴현상이 발생하는 것이다.
이를 방지하기 위해 각 스레드는 TLS라는 공간을 확보해두고, 개발자는 TLS에 저장할 변수에 옵션을 지정하여 런타임이 자동으로 스레드별 복사본을 잘 관리하도록 지시할 수 있다. 그리고 저장 시에 다양한 옵션을 설정할 수 있는데, C++의 OpenMP의 경우 다음과 같은 옵션을 지원한다:
private— 각 스레드가 초기화되지 않은 독립 복사본을 가짐firstprivate— 부모 스레드의 현재 값으로 초기화된 독립 복사본을 가짐lastprivate— 병렬 구간이 끝난 후, 마지막 이터레이션 스레드의 값이 원본에 write-back됨threadprivate— 전역/정적 변수를 TLS화하여 병렬 구간 간에도 값이 유지됨
확실하게 짚고 넘어갈 점은, 일부 옵션의 경우 복사 후에는 동기화나 갱신이 되지 않을 수 있다는 점이다. 따라서 TLS를 사용할 생각이라면, 목적과 상황에 따라 적절한 옵션을 지정해주는 것이 매우 중요하다. 그리고 그 판단은 온전히 개발자의 몫이다. 만약 특정 전역 변수를 복사하지 않고 말 그대로 '공유'하여 모든 스레드가 온전히 원본을 참고하도록 하고 싶다면 shared 옵션을 사용할 수 있다. 단, 이 경우에는 모든 스레드가 같은 변수를 공유하므로, mutex나 atomic 등 동기화가 필요할 것이다.
NDK에서 문제가 발생한 이유
NDK에서 일반적인 C++ 전역 변수(Ciphertext)를 포인터 없이 선언했는데 왜 TLS 오류가 났을까?
그 이유는 Gemini의 답변에 따르면, 전역 변수가 메모리에 로드되며 자동으로 실행된 생성자 내부에서 Microsoft SEAL 라이브러리의 MemoryManager를 호출했기 때문이다. 이 매니저가 성능 최적화를 위해 내부적으로 TLS(OpenMP의 threadprivate에 해당하는 것으로 추정되는 thread_local) 공간 할당을 요구했다. 그러나 아직 메인 스레드의 TLS는 준비되는 과정에 있었던 것이다. 라이브러리는 이제 막 메모리에 올라가고 있는 불안정한 타이밍(dlopen 함수가 끝나기도 전)에 동적인 TLS 할당을 시스템에 요구했고, Android OS가 이를 처리하지 못하고 뻗어버린 것이다.
해결 방법
따라서, Android에서 C/C++ 코드를 작성할 때에는, 전역 객체에서는 웬만하면 무거운 초기화는 피하고, JNI 레벨에서 명시적으로 초기화 함수를 호출하여 동적으로 할당 및 초기화해주는 게 권장된다고 한다.
병렬 처리에서 공유 자원에 접근 통제 진행 시 주의점
바로 위에서의 얘기와 이어지는 지점이다. 병렬 처리를 구현하면서 공유 자원에 mutex 등 동시성 통제 정책을 적용할 경우, 오히려 병렬 작업이 mutex의 임계 구역 설정으로 인해 순차 작업으로 바뀌어버리는 전혀 의도하지 않은 결과가 발생할 수 있다. 따라서, 병렬 처리를 구현하고 있다면 공유 자원에 무작정 통제 정책을 걸기 보다는 다른 방향의 해결책을 찾아보는 것이 병렬 처리로 얻는 성능적 이점을 극대화하기 좋을 것이다.
이번 실험에서는 공유 자원으로 사용했던 암호화 문맥(context)과 평가기(evaluator) 그리고 인코더(encoder)가 전부 병렬 처리를 위해 최적화되어 있어서 통제 정책을 걸 필요가 없었다. 더 정확히는, 암호화 문맥은 초기화 이후에는 값이 변하지 않기 때문에 읽기에 제한을 둘 필요가 없었다. 인코더와 평가기는 상태 없이 오직 로직만을 저장하고 있었기 때문에 또 동시 접근을 제한할 필요가 없었고. 이런 식으로 현명한 구현을 통해 병렬 처리의 성능을 최대로 끌어올리는 꼼수를 부릴 줄 아는 참된 개발자가 되어야 하겠다.
링크
GitHub 저장소에서 모든 코드 확인 가능.
