Hash Table 그리고 CPU

1.
미국 HFT 스타트업을 준비하는 회사의 개발자가 블로그를 운영하고 있습니다. 여기에 Limit Order Book을 어떻게 디자인할 것인지를 올렸습니다.

How to build a fast limit order book
왜 이런 이야기를 할까요? 작년 dolppi님이 주최한 HFT RoundTable을 정리한 글을 간단히 옮깁니다.

현재 시스템 트레이딩은 시그널만 발생시키는 것이고, 한 종목에 대한 전략만 쓸 수 있어요. 체결을 받는다거나 할 수 없어서 order book 관리가 안되는데, 만약 order book을 보면서 진행되는 전략을 써야한다면 시스템 트레이딩으로는 불가능하죠.

HFT를 위한 시스템을 준비하면서 기술적 분석이 가능하도록 구성하려는 생각들이 있는것 같은데, 저는 두가지가 양립하기 어렵다고 봅니다. 일단은, 국내 HTS에서 제공하는 기술적 분석 도구들이 엄청 발전해있고 시스템도 꽤 큰 시스템이거든요. 이걸 단순히 증권사 내부 트레이딩 용으로 구축하기는 많이 힘들것 같구요. HFT는 좀 작은 시스템이라는 생각이 듭니다. 

Strategy와 Order Book이 밀접히 관련이 있기때문에 블로그 운영자는 주요 이슈로 정리하였습니다. 여기까지는 별 문제가 없습니다.? 또다른 개발자가 위 블로그를 소개하면서 다음과 같은 주석을 달았습니다.

Fascinating blog on HFT implementation from WK. He commnts “a variation on this structure is to store the Limits in a sparse array instead of a tree. “ More detail on the implications for L1 and L2 cache behaviour of trees versus arrays for limits would be welcome. I’m assuming C++ implementation here of course, though WK points out you can make Java go fast if you avoid GC, which chimes with the experience of the LMAX guys. I ask because I interviewed with a big HFT firm last year: they gave me a programming exercise based on L1/2 cache behaviour.
Limit Order Book Implementation중에서 

“A programming exercise based on L1/2 cache behaviour.” 이 문장때문에 L1/L2 Cache에 대한 조사를 하였습니다. IT동아에서 아주 쉽게 잘 정리한 글이 있더군요.

캐시 메모리(cache memory)란, 속도가 빠른 장치와 느린 장치 사이에서 속도 차에 따른 병목 현상을 줄이기 위한 범용 메모리를 말하는 것이다. CPU 이외의 장치에서도 많이 사용되는 용어인데, CPU에서는 CPU 코어(고속)와 메모리(CPU에 비해 저속) 사이에서 속도 차에 따른 병목 현상을 완화하는 역할을 한다.
CPU의 캐시메모리는 어떤 역할을 하는가중에서 

그동안 프랍용 트레이딩시스템을 공급하던 회사들은 주문체결데이타를 관리하기 위하여 어떤 곳은 MMDBMS를, 어떤 회사는 Hash Table등을 사용하였습니다. 어떻게 제품과 기술로 구현하느냐에 따라 신규주문과 정정 및 쉬소주문을 처리할 때 속도차이가 있었습니다. 트레이딩시스템간 경쟁을 할 때 속도가 중요하기때문에 다양한 기술을 채택하려는 시도를 보았지만 컴퓨터구조로 접근한 경우를 한번도 보지 못했습니다. 그런데 L1/L2 Cache를 고려한 알고리즘을 사용하여 구현하여야 한다는 말을 하고 있습니다.

CPU와 메모리구조로 넘어가버렸습니다. 예전 나노초 측정을 다룰 때 OS 커널과 같습니다.

2.
좀더 깊이 들어가 보도록 하겠습니다. Kaist에서 강의 및 연구를 하신 분이 아주 멋진 글을 올려놓았습니다. 현대컴퓨터구조와 소프트웨어개개발과 관련한 내용입니다. 그중 앞서 다루었던 CPU,Cache등을 소개할 글이 있습니다. 현대 컴퓨터구조를 설명하는 이유를 다음과 같이 말합니다.

프로그램을 코딩할 때에 우리는 종종 컴퓨터 구조를 무시하거나, 망각하고 코딩하는 경우가 종종 있다. 이렇게 프로그래머들이 컴퓨터구조를 무시하는 이유는 내가 판단하기에 크게 두가지이다. 첫째는 잘 몰라 서이고, 둘째는 프로그래밍?생산성(productivity)을 증가시키기 위해 잘 추상화된, 즉 high-level abstraction을 제공하는 프로그래밍?언어의 사용 으로 인해서이다. 즉 프로그램 성능에 관한 문제를 완전히 또는 상당 부분 컴파일러나 인터프리터에게 맡겨버림으로써?더이상 컴퓨터 구조에 대한 고민을 하지 않아서이다. Java만 해도 포인터를 없앰으로써 메모리 관리에 대한 고민을 더이상 하지?않게 하지 않았는가? 이러한 프로그래밍 언어의 abstraction은 프로그램의 생산성은 크게 향상시켜 주었다. 하지만 프로그램의 성능(performance)에 대한 고민을 한다면, 저수준의 추상화를 제공하는 다른 프로그래밍 언어를 이용해 컴퓨터 구조에 잘맞는 프로그램의 작성이 요구될 것이다. 그리고 그것이 내가 생각하는 C/C++, Assembly가 아직도 성능이 우선시 되는 여러 프로그래밍 분야, 특히 시스템 프로그래밍에 널리 이용되는 이유이다.
Memory Hierarchy, Memory Wall and Memory Mountain중에서 

이제 본격적으로 컴퓨터의 메모리구조에 대해 설명하고 있습니다. 아래의 그림으로 이해하시면 됩니다. 물론 깊은 내용은 위의 글을 읽어보시면 됩니다.

여기서 Cache Conscious 혹은 Cache Oblivious data structure라는 개념이 등장합니다. 역시나 같은 교수님의 주옥같은 글을 보도록 하죠.

이전의 컴퓨터 시스템과 현재의 컴퓨터 시스템의 차이를 들자면, 여러가지가 있겠지만 현재까지 누적되어온 중요한 차이점들은 다음과 같다.

1) 더 커진 메모리 용량(capacity) 하지만 그만큼 개선되진 못한 접근속도(latency), 그리고 메모리 접근속도의 개선속도보다 더 빠르게 상승한 clock speed의 CPU. 그리고 이러한 접근속도의 차이에 의해 발생한 이에 따른 메모리 벽(memory wall) 문제 (메모리 벽 문제에 대해서는 일전에 올려둔 글을 참고하세요)
2) 더 커지고 계층화된 HW cache와 이에 따른 메모리 계층(memory hierarchy)
3) Supersclalar CPU(Out-of-Order Instruction Execution), branch prediction, SIMD, 그리고 SMT(Symmetric Multithreading)와 같은 CPU에서의 개선기능들.
4) Multicore(CMP; Chil-level MultiProcessor), Cell Processor, GPU등과 같이 달라진 구조의 CPU
5) Flash Memory
6) FPGA(Field Programmable Gate Array)

즉, 현재의 시스템은 위와 같은 여러 추가적인 기능들을 제공하게 되는데, 기존의 코드들은 이러한 기능들을 제대로 이용하고 있지 않는다는 사실이다.그래서, 사람들은 Colume-oriented DBMS와 같은 data placement의 변경을 고안하기도 했으며,또한 메모리 벽 문제를 해결하기 위한 Cache-conscious와 Cache-oblivious algorithm들을 고안하였다.뿐만 아니라, CSB+-tree 처럼, B-tree와 같은 주요 자료구조들을 다시 바꾸기도 하였다. (Main-memory DBMS에서 이용하는 T-tree는 cache에 대한 고려가 전혀없는 구닥다리라나…) 또 칩 레벨의 멀티 프로세서를 지원하기 위한 여러 방법들이 고안되었고, GPU를 CPU 이외에 질의처리를 위한 보조 프로세서로 활용하기 위한 연구들도 2004년부터 소개되어왔다. 최근에는 I/O 비대칭성과 in-place update가 안되는, 하지만, latency와 요구전력이 HDD에 비해 월등히 낮은 Flash memory를 위한 여러 연구들도 진행되어 왔다.요새는 또 FPGA를 이용해 알고리즘을 HW로 구현하는 방식을 통해, 현재의 폰 노이만 방식의 컴퓨터 성능보다 몇십배 향상된 처리 성능을 보장하기도 한다.
DBMS on New Hardware중에서 

위의 글중 “메모리 벽 문제를 해결하기 위한 Cache-conscious와 Cache-oblivious algorithm들을 고안하였다.”라는 문장입니다.

?이제 개발자들을 위하여 관련된 Cache-Conscious Data Structure와 관련된 논문과 소스를 소개하도록 하겠습니다. 위키를 찾아 보았지만 마땅한 자료를 보지 못했는데 이 논문은 훌룽한 듯 합니다. 논문을 평가할 능력이 없기때문에 그냥 짐작으로 말합니다.

Cache-conscious String Data Structures, Sorting and Algorithms: theory and practice

Nikolas Askitis교수가 발표한 논문과 소스를 보실 수 있습니다.

Efficient Data Structures For Cache Architecture

3.
우연히 시작한 하루동안의 조사를 마무리하였습니다. 제가 할 수 있는 일은 여기까지입니다.

HFT 혹은 Low Latency 아니면 알고리즘트레이딩을 쉽게 생각했습니다. 그렇지만 들어가면 갈수록 컴퓨터의 하드웨어와 소프트웨어, 특히 OS커널을 잘아는 엔지니어가 필요하다는 생각을 합니다. 앞으로의 트레이딩은 소프트웨어 엔지니어와 금융공학엔지니어들의 역량에 달렸습니다. ?어떤 트레이딩시스템을 설계하더라도 전략 + 트레이딩기술이 결합한 모양입니다.

주변을 살펴 봅니다. 금융회사에 다니든, 소프트웨어개발회사에 다니든 발전해야할 부분이 많습니다. 시니어 엔지니어는 책을 놓은지 오래라 새로운 기술과 변화를 받아드릴 역량이 부족합니다. 주니어 엔지니어는 는 도메인지식을 배워 빨리 ‘밥값’을 해야 하는 상황입니다. 더구나 금융소프트웨어를 하겠다는 ?자원하는 분들은 그저 개발자인 경우가 많습니다.

앞으로 트레이딩기술의 화두는 HPC와 Low Latency입니다. OS와 컴퓨터 하드웨어를 이해하는 엔지니어가 많아졌으면 합니다. KRX가 차차세대를 준비하고 있습니다. 하나의 전환점이 되었으면 합니다. 경쟁력있는 시스템을 국산기술로 개발하여 여타 기관과 회사에 많이 보급하였으면 좋겠습니다.이를 위해 KRX가 정보기술 Lap을 만들어 능력있는 엔지니어를 영입하면 어떨까 상상을 해봅니다.

마지막으로 레드햇에서 작성한 논문을 소개합니다. “개발자가 반드시 알아야 하는 메모리(What Every Programmer Should Know About Memory)”라는 제목입니다. ‘반드시’라는 단서가 붙었습니다.

Download (PDF, 912KB)