코딩관계론

검색어 추천 서비스 V3(Redis + NoSQL) 본문

개발

검색어 추천 서비스 V3(Redis + NoSQL)

개발자_티모 2024. 8. 12. 20:27
반응형

이전 버전은 기능적, 성능적 만족을 이뤄냈지만 53일 간만 서비스가 유효하다는 치명적인 단점이 있었습니다. 이를 해결하기 위해서 저장공간이 많은 하드디스크를 이용하기로 했습니다. 따라서 버전 1,2에서 구성된 서비스 플로우는 아래와 같이 수정되어야만 했습니다.

 

사용자의 검색어에 따라서 트라이를 실시간 갱신하지 않고, 왜 Cron을 통해서 배치작업을 진행할까라는 의문점이 있을 수 있습니다.

저도 이런 의문점이 있었는데 생성된 트라이가 사용자의 몇 번의 요청으로 인기 검색어가 변경될 일은 잘 없을 것이고 사용자의 요청을 실시간으로 반영해서 트라이를 계속 생성하게 되면 성능적으로 매우 느려지게 될 것입니다.

 

또한 이 서비스가 실시간 급상승 검색어 순위와 같은 민감한 데이터가 아니고, 대용량의 데이터 처리이기 때문에 사용자가 적은 시간에 배치 작업을 통해 트라이를 생성하는 것이 시스템 적으로나, 서비스적으로나 좋다고 생각합니다. 

먼저 어떤 데이터베이스가 Trie 구조를 잘 표현할 수 있을까 고민했습니다.

 

제가 찾은 데이터베이스는 크게 Document, RDMS, Graph가 있습니다.  일단 RDMS의 경우에는 트라 구조를 JOIN과 결합하여 표현하게 됩니다. RDMS의 경우 JOIN이 빈번할수록 성능이 안 좋기 때문에 RDMS는 적합하지 않다고 생각했습니다.

 

또한 Graph 데이터베이스의 경우 제일 유명한 neo4j가 있었는데,  그래프 형식으로 구조를 설계할 수 있어서 매우 좋을 것 같다고 생각했지만, 대규모 처리와 과금에 있어서 제약이 생겨 사용할 수 없게 됐습니다.

 

따라서 No SQL에서 선택을 진행해야 했습니다. 대표적으로는 Cassandra와 Mongo와 Scylladb가 후보군으로 오르게 됐습니다. Scylladb는 Cassandra의 업그레이드 버전이었습니다. 카산드라 API를 사용하지만 성능이 더 빨랐습니다. 하지만 Scylladb도 선택받지 못하게 됐는데 그 이유는 유연성이 부족하기 때문입니다.

 

아직 서비스가 초기라는 점을 생각하면 추 후에 어떤 식으로의 확장이 있을지 모르기 때문에 유연성을 보장하고, RDMS보다 빠른 Mongo를 선택하게 됐습니다.

 

먼저 몽고디비의 컬렉션은 다음과 같이 구성했습니다. 다른 필드는 버전 2의 메모리 트라이 구조랑 비슷합니다. 다른 점은 부모를 찾아가기 위해서 parentId필드가 추가됐습니다.

 

추가적으로 중요한 점은 childs에는 모든 childs가 저장되어 있는 것이 아니고, 해당 노드를 루트로 하여 서브트리를 구성했을 때  endOfWord=true인 단어만 저장하도록 만들어 데이터베이스의 캐시를 만드는 역할로 성능을 향상 시키게 됩니다.

 

이전에 봤을 때 서브트리(C)에서 만들 수 있는 단어를 찾기 위에서 O(C)의 시간이 필요하다고 했는데 이 필드로 인해서 O(1)으로 탐색 시간을 줄일 수 있습니다. 따라서 최종적으로 데이터는 아래와 같이 구성됩니다.

 

문득 데이터베이스의 캐시 성능이 궁금해져서 테스트를 진행해 보니 데이터가 약 2만 건일 때 -> 100ms로 준수한 결과를 보이지만 데이터가 7만 건으로 늘어나니 1000ms로 기하급수적으로 성능이 안 좋아졌습니다.

 

그 이유를 생각해 보면 아무리 캐시 데이터가 있다고 하더라도, childs의 objectId를 이용해서 keyword조회를 한번 더 해야 한다. 즉 1 + N의 문제가 생겨나는 것이고, 따라서 속도가 기하급수적으로 느려지게 됩니다.

 

따라서 이를 해결하기 위해서 버전 2에서 논의한 캐시 저장소를 도입할 것입니다. 결론을 먼저 말씀드리자면 캐시 저장소를 도입함으로써 100배의 성능 개선을 이루어냈습니다. 아래의 그림과 같이 같은 데이터 셋에서도 속도는 약 10ms로 줄어들게 됐습니다.

 

그 이유를 설명해 보자면 우리의 알고리즘의 성능에 영향을 미치는 요소들은 다음과 같이 "O(P) + O(C) + O(C log C)"로 표기될 수 있습니다.

 

먼저 캐시데이터에서는 O(C)가 아니라 O(1)의 성능을 가지게 되는데 Redis에서는 N + 1의 문제가 없기 때문입니다.  그 이유는 데이터베이스에서 Trie를 생성해 레디스에 Trie를 업로드하기 전에 모든 Child의 ObjectId를 이용해 키워드를 추출하고 해당 키워드들을 리스트로 만들어서 캐시 저장소에 저장하기 때문입니다.

 

또 하나의 개선점이 키워드들을 리스트로 만들 때, 정렬을 수행하고 나서 캐시 저장소에 키워드 리스트를 저장해도 됩니다. 

 

즉 코드로 설명하면 아래와 같이 Child는 더 이상 연산이 필요 없는 상태로 저장되게 됩니다. 따라서 표기법은 "O(P) + O(1) + O(1)"로 변경됩니다.

@Getter
public class CacheNode {
	private List<String> child;
	private String keyword;

	public CacheNode(String keyword, List<String> child) {
		this.keyword = keyword;
		this.child = child;
	}
}

 

이제 O(P)를 줄여야 하는데 구글 키워드 추천 기능을 보시면 일정 글자 이상을 넘어가게 되면 검색어 추천 기능이 작동하지 않는 것을 볼 수 있습니다.  이게 바로 성능상 이슈로 인한 것인데 P의 길이가 짧아진다면 P의 노드로 가기까지 O(1)의 시간이 걸리게 됩니다.

 

따라서 우리의 성능은 "O(1) + O(1) + O(1)"로 도달하게 됩니다. 따라서 항상 빠름을 보장할 수 있게 됩니다.

 

이번 버전에서 우리는 레디스와 하드디스크의 조합으로 이전에 발생했던 메모리 문제도 해결했고, 성능 개선도 이뤘습니다. 하지만 아직 문제가 있는데 데이터 베이스의 메모리가 부족할 수도 있고, 레디스의 메모리가 부족해질 수도 있습니다. 

더보기

보통 레디스의 메모리는 16GB입니다

 

따라서 몽고 디비의 스케일 out과 샤딩, redis scale-out과 샤딩에 대해서 찾아보고 개선해 보겠습니다.

 

반응형