CPU

그래프 연산이나 저장 구조를 최적화할 때 빠지지 않고 등장하는 자료구조가 CSR(Compressed Sparse Row)입니다. 1977년 예일 대학교가 발표한 Yale Sparse Matrix Package 보고서에서 처음 소개되어 Yale Format이라고도 불리는데, 희소 행렬(sparse matrix)을 효율적으로 저장하고 처리하기 위해 고안되었습니다. 희소 행렬이란 희소 행렬은 대부분의 원소가 0인 행렬을 말합니다. 과학 계산, 그래프 이론, 머신러닝 등 현대 컴퓨팅의 거의 전 영역에서 마주치게 되는데, 현실의 데이터를 행렬로 옮기면 십중팔구 이런 모양이 됩니다. SNS를 예로 들면, 사용자가 100만 명이라 해도 한 사람의 친구 수는 보통 500명 안팎입니다. 그런데 이것을 그대로 행렬로 표현하려면 1조(10^12) 크기, 그러니까 7.3PB에 달하는 행렬이 필요해집니다. 실제 정보량에 비해 저장 공간이 터무니없이 커지는 셈입니다. ...

이 글은 넷플릭스 테크 블로그의 Seeing through hardware counters: a journey to threefold performance increase를 제가 이해한 대로 요약하고, 관련 배경 지식을 나름대로 정리해 덧붙인 글입니다. 원문이 정확한 출처이니, 구체적인 수치나 세부 사항이 궁금하시다면 반드시 원문을 확인해주세요. 문제 발생 넷플릭스가 운영하던 어떤 서비스가 CPU 부족을 겪어서, 노드 스펙을 3배로 늘리는 scale-up을 진행했습니다. CPU-intensive한 워크로드였으니 처리량도 그에 비례해서 늘어날 거라 기대했지만, 실제로 개선된 폭은 25% 남짓이었습니다. 심지어 tail latency는 오히려 더 나빠졌습니다. ...

락을 구현하는 방식은 크게 두 갈래로 나뉩니다. 유저 공간에서 CPU 명령어만으로 도는 Spinlock과, 커널의 도움을 받는 Mutex입니다. 둘 다 결국 상호 배제(mutual exclusion)를 보장한다는 목적은 같지만, 내부 동작 방식이 다르기 때문에 적합한 워크로드도 갈립니다. Spinlock Spinlock은 유저 공간(userspace)에서 구현되는 락입니다. 동작 방식은 단순합니다. CAS(Compare-And-Swap) 연산이 성공할 때까지 무한히 반복합니다. while (!CAS(lock, 0, 1)) 대부분의 CPU는 이런 CAS 연산을 위한 전용 명령어를 갖고 있습니다. x86이라면 LOCK CMPXCHG가 여기에 해당합니다. 문제는 이 CAS 연산이 성공하려면 해당 캐시 라인에 대한 독점적인 쓰기 권한이 필요하다는 점입니다. 이 권한을 얻는 과정에서 CPU 코어 사이에 캐시 일관성 프로토콜이 개입하고, 캐시 라인의 소유권을 주고받는 과정에서 잦은 invalidation, 이른바 캐시 라인 바운싱이 발생합니다. 이 과정은 보통 4~80ns 정도 걸립니다. ...