안녕하세요? (주)칠로엔에서 서버관리를 맡고 있는 매드(MAD)입니다.
이번에는 (주)칠로엔에서 서비스 중인 B2B 모델 LinkMusic(https://www.linkmusic.io/product)에 대하여
약 두 달 간 진행된 ELK 스택을 활용한 분산 로깅 시스템 구축 - 기술적 도전과 해결 방안에 대하여 포스팅 합니다.
사내 내규 상 실제 구현 스크립트들은 공개할 수 없는 점 양해바랍니다.
[서론]
현대 소프트웨어 아키텍처에서 로깅 시스템은 단순한 디버깅 도구를 넘어 시스템 상태 모니터링, 성능 분석, 트러블슈팅의 핵심 요소로 자리 잡았습니다.
특히 마이크로서비스 아키텍처와 분산 시스템이 보편화 됨에 따라, 중앙화된 로깅 시스템의 중요성이 더욱 부각되고 있습니다.
이번 글에서는 LinkMusic 프로젝트에서 ELK 스택(Elasticsearch, Logstash, Kibana)을 활용해 구축한 분산 로깅 시스템의 기술적 측면과 도전 과제들을 심층적으로 살펴보겠습니다.
본문은 개발 일지에 보다 가깝습니다.
본문에 앞서 Elasticsearch에 대한 역 색인에 대하여 이해하는 것이 중요하다고 판단,
이해한 바를 바탕으로 풀어 씁니다.
[Elasticsearch의 역 색인(Inverted Index) 메커니즘: 수학적 이해]
1. 역 색인 토크 나이저의 수학적 기초
1.1 집합론적 정의
역 색인은 형식적으로 다음과 같은 함수로 정의할 수 있습니다:
여기서:
- : 모든 고유 용어(term)의 집합
- : 문서(document) 집합
- : 문서 집합의 멱집합(power set)
각 용어 에 대해, 역 색인 는 해당 용어를 포함하는 모든 문서의 집합을 반환합니다:
1.2 행렬 이론적 표현
역 색인은 용어-문서 행렬(term-document matrix)의 전치(transpose)로도 볼 수 있습니다. 만약 문서-용어 행렬을 라 하면:
여기서 각 원소 는:
는 용어 가 문서 에서 갖는 가중치입니다(예: 용어 빈도).
역 색인은 이 행렬의 전치 로 표현됩니다:
이 행렬에서 각 행 는 용어 가 등장 하는 모든 문서와 그 가중치를 나타냅니다.
1.3 그래프 이론적 해석
역 색인은 이분 그래프(bipartite graph) 로도 표현할 수 있습니다:
- 정점 집합: 용어 집합 와 문서 집합 의 합집합
- 간선 집합
각 간선 에는 가중치 가 부여될 수 있습니다.
2. 인덱싱 알고리즘과 자료구조
2.1 역 색인 구조의 수학적 표현
역 색인은 다음과 같은 구성요소로 이루어집니다:
- 사전(Dictionary): 매핑 함수
- 포스팅 리스트(Posting List): 각 용어 에 대해 형태의 튜플 리스트
- : 문서
- : 문서 에서 용어 의 빈도
- : 용어 가 문서 에 등장 하는 위치 목록
형식적으로, 역색인 는 다음과 같이 정의됩니다:
2.2 (🙏🏻 매우 중요) 인덱싱 알고리즘의 시간 복잡도 분석
2.2.1 단일 문서 인덱싱 복잡도
문서 의 인덱싱 시간 복잡도:
- 토큰화: ← 절댓값 주의😉
- 사전 조회 및 업데이트: , 여기서 는 문서 의 고유 용어 수, 는 전체 고유 용어 수
2.2.2 일괄 처리 인덱싱 복잡도
SPIMI(Single-Pass In-Memory Indexing) 알고리즘의 복잡도:
- 시간 복잡도: , 여기서 은 전체 토큰 수
- 공간 복잡도:
2.2.3 병합 기반 인덱싱
메모리 내 인덱스를 디스크로 플러시하고 병합하는 과정의 복잡도:
여기서:
- : 총 포스팅 수
- : 병합할 인덱스의 수
- : 블록 병합 요소(merge factor)
2.3 트라이 및 B-트리 기반 사전 구현
2.3.1 트라이(Trie) 기반 사전
트라이 노드 에 대한 재귀적 정의:
- : 자식 노드 맵
- v: 용어 종료 여부
- : 연관된 포스팅 리스트
검색 시간 복잡도: , 여기서 는 용어의 길이입니다.
2.3.2 B-트리 기반 사전
B-Tree에서 용어 를 찾는 시간 복잡도:
여기서 는 B-트리의 분기 요소(branching factor)입니다.