건초더미에서 바늘 찾기: PHP로 맨땅에 구현해보는 벡터 검색 (HNSW)
RAG의 핵심인 벡터 검색, 대용량 데이터에서도 성능을 보장하는 HNSW 알고리즘의 원리와 PHP 구현 과정을 상세히 살펴봅니다.
김영태
테크리드
안녕하세요. 풀링포레스트 테크리드 김영태입니다.
요즘 RAG(Retrieval-Augmented Generation)다 뭐다 해서 벡터 검색이 화두죠. 저희 팀에서도 최근 관련 기능을 도입하면서 많은 고민을 했습니다. 처음에는 단순하게 생각했습니다. "그냥 코사인 유사도(Cosine Similarity) 돌리면 되는 거 아냐?" 하고요. 네, 작동은 합니다. 데이터가 적을 때는요. 하지만 데이터가 수십만, 수백만 건으로 늘어나는 순간, 서버 CPU가 비명을 지르는 걸 목격하게 됩니다.
오늘은 '건초더미에서 바늘을 찾되, 건초를 다 뒤지지 않는 방법'인 HNSW(Hierarchical Navigable Small World) 알고리즘을 PHP로 구현해보며 그 원리를 파헤쳐보려 합니다.
무식한 방법의 한계: 선형 탐색(Linear Search)
우리가 흔히 쓰는 단순 벡터 검색은 기본적으로 선형 탐색(O(N))입니다. 도서관 사서가 책을 찾아주는데, 도서관에 있는 1,000만 권의 책 제목을 처음부터 끝까지 하나하나 다 읽어보고 있는 상황을 상상해 보세요. 책 한 권 확인하는 데 0.001초가 걸려도 전체를 다 보려면 몇 시간이 걸립니다. 실무에서 이런 속도는 재앙에 가깝습니다.
우리는 이 시간을 '밀리초' 단위로 줄여야 합니다. 이때 등장하는 구원투수가 바로 HNSW입니다.
고속도로와 골목길: HNSW의 핵심 원리
HNSW라는 이름이 어렵게 느껴질 수 있지만, 원리는 우리가 길을 찾는 방식과 똑같습니다.
낯선 도시에서 특정 주소를 찾아간다고 가정해 봅시다. 우리는 처음부터 골목길을 뒤지지 않습니다.
고속도로를 타고 그 도시 근처로 크게 이동합니다.
국도를 타고 해당 동네로 진입합니다.
큰 길을 따라가다가 골목으로 들어갑니다.
마지막으로 번지수를 확인합니다.
HNSW는 데이터를 이런 계층(Layer) 구조로 관리합니다.
상위 레벨 (고속도로): 데이터 포인트가 듬성듬성 있고, 서로 멀리 연결되어 있습니다. 큰 보폭으로 이동하기 좋습니다.
하위 레벨 (골목길): 모든 데이터가 촘촘하게 연결되어 있습니다. 정밀하게 찾기 좋습니다.
코드: 위에서 아래로 줌인(Zoom-in)
이 로직을 PHP로 구현한 오픈소스 프로젝트(Vektor)의 코드를 보며 뜯어보겠습니다. 핵심은 위성지도를 보며 점점 확대해 들어가는 과정입니다.
public function search(array $queryVector, int $k, int $ef): array {
// 가장 높은 레벨(고속도로)에서 시작
$entryPoint = $this->readHeader();
// 현재 위치와 찾으려는 벡터 사이의 거리 계산
$currObj = $entryPoint;
$currDist = Math::cosineSimilarity($queryVector, $this->getVector($currObj));
// 최상위 레벨부터 1레벨까지 차근차근 내려갑니다.
for ($lc = $maxLevel; $lc >= 1; $lc--) {
while (true) {
$changed = false;
// 현재 위치에서 연결된 이웃 노드들을 살펴봅니다.
$node = $this->readNode($currObj);
$neighbors = $node['connections'][$lc] ?? [];
// 이웃 중에 내가 찾는 목표물과 더 가까운 녀석이 있는지 확인합니다.
foreach ($neighbors as $neighborId) {
$dist = Math::cosineSimilarity($queryVector, $this->getVector($neighborId));
if ($dist > $currDist) { // 더 가까운 곳 발견!
$currDist = $dist;
$currObj = $neighborId; // 그쪽으로 이동
$changed = true;
}
}
// 더 이상 가까운 곳이 없다면, 해당 레벨에서의 탐색을 멈추고
// 아래 레벨로 '하강'합니다.
if (!$changed) break;
}
}
// 루프가 끝나면 우리는 0레벨(골목길)에 도착해 있습니다.
}이 코드는 마치 내비게이션이 목적지 근처 IC까지 우리를 안내하는 과정과 같습니다. 단순히 전체를 훑는 게 아니라, 방향성(기울기)을 가지고 목적지에 가까워지는 쪽으로만 이동합니다.
정밀 타격: 0레벨과 후보군 관리 ($ef)
이제 목적지 코앞인 0레벨에 도착했습니다. 여기엔 모든 데이터가 존재합니다. 여기서부터는 단순히 '가장 가까운 하나'가 아니라 '가장 가까운 K개'를 찾아야 합니다. 이때 $ef라는 파라미터가 중요해집니다. $ef는 탐색할 '후보 목록'의 크기입니다.
이 값이 클수록 더 많은 골목길을 뒤지니까 결과는 정확해지지만 속도는 느려집니다. 반대로 작으면 빠르지만 엉뚱한 결과를 낼 수도 있죠. 실무에서는 이 $ef 값 튜닝이 성능 최적화의 열쇠가 되곤 합니다.
public function searchLayer(int $entryPoint, array $queryVector, int $ef, int $level, ?int $k = null): array {
// 우선순위 큐(Priority Queue)를 사용해 유망한 노드부터 탐색합니다.
$candidates = new SplPriorityQueue();
$winners = [$entryPoint => $entrySim];
while (!$candidates->isEmpty()) {
$c = $candidates->extract();
// 더 이상 탐색해도 좋은 결과가 나올 것 같지 않으면 과감하게 중단합니다.
if ($cSim < $worstSim && count($winners) >= $ef) {
break;
}
// 후보의 이웃들을 뒤져봅니다.
$node = $this->readNode($c);
$neighbors = $node['connections'][$level] ?? [];
foreach ($neighbors as $neighborId) {
if (!isset($visited[$neighborId])) {
$visited[$neighborId] = true;
$sim = Math::cosineSimilarity($queryVector, $this->getVector($neighborId));
// 유망한 이웃이라면 후보군에 넣고 계속 탐색합니다.
if ($sim > $worstSim || count($winners) < $ef) {
$candidates->insert($neighborId, $sim);
$winners[$neighborId] = $sim;
// 후보군 크기를 $ef로 유지하며 최악의 후보는 탈락시킵니다.
// ... (생략) ...
}
}
}
}
// 최종적으로 상위 K개를 반환합니다.
}이 부분에서는 'Greedy(탐욕적)' 접근을 씁니다. 당장 눈앞에 보이는 가장 유사한 이웃으로 이동하죠. 하지만 꽉 막힌 골목에 갇히지 않기 위해 우선순위 큐를 사용해 여러 경로를 동시에 고려합니다.
마무리하며
HNSW는 모든 데이터를 비교하지 않고도 놀라울 만큼 정확하게 유사한 데이터를 찾아냅니다. 물론 세상에 공짜는 없습니다. 빠른 속도를 얻는 대신, 그래프 구조를 유지하기 위한 메모리를 더 많이 사용하고, 데이터를 입력할 때 인덱스를 구성하는 시간도 필요합니다.
개발자로서 라이브러리가 제공하는 search() 함수만 호출해서 쓸 수도 있습니다. 하지만 이렇게 내부 구현을 한번 들여다보고 나면, 왜 메모리가 튀는지, 왜 검색 결과가 가끔 부정확한지 이해하는 해상도가 달라집니다. 여러분도 사용하는 도구의 뚜껑을 한번 열어보시는 건 어떨까요? 생각보다 그 안의 세상은 흥미롭습니다.
