QOSI-kr
QOSI - Quadrillion Open Source Indexer한국어판

QOSI - Quadrillion Open Source Indexer


용어 사전
파일 (File)
정의: 코드 또는 텍스트의 단일 컨테이너.
특징:
원본 토큰(소스 코드)의 연속으로 구성됨.
인덱싱, 후보 선정, 비교 단계에서는 직접 읽지 않음.
오직 뷰어 인터페이스에서만 직접 읽음.
타겟 (Target)
정의: 분석을 위해 사용자가 제공한 데이터셋.
특징:
사용자가 제공한 파일들로 구성됨.
수신 즉시 토큰화 및/또는 인덱싱 과정을 거침.
소스(Source)와 별도로 관리되고, 소스에 추가하지 않음.
소스 (Source)
정의: 서비스 제공자가 유지 관리하는 데이터셋 저장소.
특징:
타겟과 매칭하기 위한 참조 풀 역할을 함.
자주 업데이트 되지 않음. 일반적으로 주간 또는 월간 일정으로 이루어짐.
사전 인덱싱되어 사용자가 접근할 때 즉시 사용 가능함.
후보 인덱싱 주기는 데이터 구조 설계에 영향을 미치지 않음.
데이터셋 (Dataset)
정의: 파일의 집합적인 모음.
유형:
소스 데이터셋 (Source Dataset): 소스로 유지 관리되는 포괄적인 파일 모음.
이후, "소스(Source)"로 약칭.
타겟 데이터셋 (Target Dataset): 사용자가 제공한 완전한 파일 모음.
이후, "타겟(Target)"로 약칭.
토큰 (Token)
정의: 파일의 내용에서 파생된 가장 작은 데이터 단위.
토큰화 생성 방법:
코드 데이터: 코드의 구문을 기반으로 한 토크나이저에 의해 생성됨.
텍스트 데이터 (자연어):
서양 언어: 토큰은 공백으로 구분됨.
중국어: 각 문자(한자)를 개별 토큰으로 취급함.
한국어: 공백을 기준으로 토큰을 분할하고, 조사 및 접미사는 별도로 토큰화됨.
일본어: 형태소 분석을 통해 토큰이 결정되며, 문법과 문맥에 따라 단어를 분할함.
특별 고려사항: 한국어와 일본어 모두 형태와 구문의 복잡성을 정확히 처리하기 위해 전문 토크나이저가 필요함.
시퀀스 (Sequence) 및 부분 시퀀스 (Subsequence)
정의:
시퀀스 (Sequence): 파일 또는 세그먼트에서 파생된 토큰의 순서 있는 목록.
부분 시퀀스 (Subsequence): 전체 시퀀스 내에서 연속된 토큰의 하위 집합.
최소 토큰 시퀀스 (Minimum Token Sequence, MTS) 및 최소 토큰 시퀀스 유닛 (Mimimum Token Sequence Unit, MTSU)
정의:
최소 토큰 시퀀스 (MTS): 고정 크기 토큰으로부터 원본 시퀀스의 기본 부분 시퀀스 단위.
최소 토큰 시퀀스 유닛 (MTSU): 시스템 내에서 인덱싱, 후보 선정, 비교의 기본 단위.
특징:
MTSU는 MTS를 해싱하여 계산됨.
MTS는 여러 토큰으로 구성되므로, 단일 토큰보다 MTS의 중복 가능성이 낮음.
토큰화된 파일 (Tokenized File)
정의: 파일의 토큰화된 버전.
특징:
토크나이저에 의해 생성됨.
다음의 쌍으로 구성된 시퀀스로 이루어짐:
토큰의 인덱스
원본 문자(문자열)
쿼리 (Query), 쿼리 요청 (Query Request), 및 쿼리 결과 (Query Result)
!!TODO: 후보 쿼리(Candidate Query)와 쿼리(Query)를 명확히 정의
정의:
쿼리 (Query): 타겟 내에서 공통 부분 시퀀스를 가진 소스의 후보 파일을 검색하는 과정.
쿼리 요청 (Query Request): 타겟에서 발견된 특정 부분 시퀀스를 포함하는 소스 파일을 찾기 위해 사용되는 검색 매개변수의 집합.
쿼리 결과 (Query Result): 쿼리의 출력으로, 타겟 파일과 후보 소스 파일 목록의 쌍.
구성 요소:
타겟 데이터셋 내의 모든 파일을 포함함.
후보 쿼리를 사용하여 후보 소스 파일 및 관련 프로젝트 메타데이터를 검색함.
타겟 파일 내의 어떤 부분 시퀀스와 일치하는 토큰 부분 시퀀스를 포함하는 소스 파일을 식별함.
유형:
정확한 쿼리 (Exact Query): 소스와 타겟 간에 정확히 동일한 부분 시퀀스를 검색함.
유사한 쿼리 (Similar Query): 사전 정의된 유사성 매개변수에 기반하여 유사한 부분 시퀀스를 검색함.
결과:
소스 파일과 타겟 파일의 쌍: 소스 파일을 해당 타겟 파일과 연결함.
부분 시퀀스 인덱스의 쌍: 소스 및 타겟 파일 모두에서 일치하는 부분 시퀀스의 시작 및 끝 인덱스를 나타냄.
후보 쿼리 (Candidate Query)
!!TODO: 후보 쿼리(Candidate Query)와 쿼리(Query)를 명확히 정의
정의: 쿼리와 유사한 사전 검색 메커니즘으로, 소스에서 파일 목록만 반환함.
특징:
전체 소스 데이터셋에 대해 작동함.
허위 긍정을 허용하지만 허위 부정을 허용하지 않음.
유사한 쿼리를 직접 지원하지 않음.
그러나 더 작은 MTS 크기를 사용하여 유사한 기능을 달성할 수 있음.
배치 쿼리 (Batch Query)
정의: 효율성을 높이기 위해 여러 쿼리를 동시에 처리하는 방법.
특징:
단일 작업에서 2^16 ~ 2^24개의 MTS 배치 요청을 처리함.
배치 쿼리를 실행하기 전에 키를 정렬하고 분할함.
RocksDB/LevelDB와 같은 데이터베이스의 MultiGet API를 사용하여 배치 쿼리 처리를 최적화함.
인덱스 (Index)
!!TODO: 인덱스(Index)와 후보 인덱스(Candidate Index)를 명확히 정의
정의: 후보 쿼리에 의해 반환된 파일 목록으로부터 구축된 데이터 구조.
특징:
정확한 쿼리 및 유사한 쿼리에 기반한 상세 검색 작업을 최적화함.
인덱서(Indexer)에 의해 생성되며 인덱싱 후에는 변경 불가능함.
SSD와 같은 저장 장치에서의 효율적인 읽기 작업을 처리할 수 있도록 설계됨.
후보 인덱스 (Candidate Index)
정의: 전체 소스를 위한 초기 인덱싱.
특징:
파일 수준 목록을 제공하여 후보 쿼리를 지원함.
쿼리 작업 중 잠재적 일치 파일에 대한 고속 접근을 용이하게 함.
파티셔닝 (Partitioning)
정의: 쿼리 요청(Query Request) 내의 MTSU를 분할하여 **파인딩(Finding)**을 최적화하는 과정.
특징:
**인덱스(Index)**는 MTSU의 순서에 따라 정렬됨.
파일 아카이버 (File Archiver)
정의: **소스 파일(Source File)**의 파일 ID로부터 소스 파일을 반환함.
특징:
파일 ID를 기반으로 소스 파일을 효율적으로 검색하고 반환함.
아카이브된 파일 데이터를 관리하고 유지함.
인덱서 (Indexer)
정의: 소스 데이터셋으로부터 인덱스를 생성함.
특징:
**소스 파일(Source Files)**을 처리함:
**소스 파일(Source Files)**으로부터 **토큰화된 파일(Tokenized Files)**을 생성함.
**토큰화된 파일(Tokenized Files)**과 소스 파일의 메타데이터로부터 MTSU와 메타데이터를 기반으로 **인덱스(Index)**를 생성함.
쿼리어 (Querier)
정의: **타겟 파일(Target Files)**로부터 쿼리를 생성함.
특징:
**타겟 파일(Target Files)**을 처리함:
**타겟 파일(Target Files)**으로부터 **토큰화된 파일(Tokenized Files)**을 생성함.
**토큰화된 파일(Tokenized Files)**의 MTSU로부터 쿼리 요청을 생성함.
MTSU 목록과 관련된 **타겟 파일(Target Files)**의 메타데이터.
쿼리 작업에 최적화된 그룹화/중복 제거된 MTSU.
파인더 (Finder)
정의: 쿼리 작업 중 후보 파일을 처리함.
특징:
쿼리 요청으로부터 각 MTSU에 대한 후보 파일 목록(또는 후보 파일 목록 ID)을 **인덱스(Index)**에서 가져옴.
효율적인 후보 파일 검색을 지원함.
머저 (Merger)
정의: 쿼리 결과를 기반으로 후보 파일 목록을 병합함.
특징:
쿼리 결과를 기반으로 후보 파일 목록을 병합함.
쿼리 요청에 대한 최종 후보 파일 목록을 생성함.
해시 함수 (Hash Function)
정의: 입력 데이터(MTS)를 고정 크기의 바이트 문자열(MTSU)로 변환하는 함수.
특징:
고속성과 효율성을 위해 비암호화 해시를 사용함.
FarmHash는 현재 MTS 키 생성을 위해 사용되는 비암호화 해시 함수의 예시임.
해시 값의 균일한 분포를 보장하여 충돌을 최소화하고 인덱싱 성능을 최적화함.
언어 패밀리 (Language Family)
정의: 실제 표현의 유사성에 기반하여 프로그래밍 언어를 그룹화한 것.
특징:
동일한 패밀리 내의 언어는 공통의 문법 구조를 공유하여 서로 다른 언어 간에도 동일한 토큰 시퀀스를 가능하게 함.
한 언어는 여러 패밀리에 속할 수 있으며, 여러 그룹과 패턴을 공유하는 경우가 있음.
언어별 특성을 기반으로 소스 데이터를 분할하여 검색 및 인덱싱을 최적화함.
파티셔닝 (Partitioning)
정의: 데이터를 최적의 처리 및 쿼리를 위해 명확한 세그먼트로 나누는 과정.
특징:
언어 패밀리별로 데이터를 분할하여 토큰 시퀀스의 유사성을 활용함.
각 파티션 내에서 검색 공간을 줄여 쿼리 성능을 향상시킴.
인덱싱 및 검색 작업의 확장성과 효율성을 지원함.
파라미터 (Parameter)
정의: 쿼리 작업을 정제하고 맞춤화하기 위해 사용자가 정의한 기준.
유형:
유사도 비율 (Similarity Rate): 유사한 쿼리에서 일치의 요구되는 유사성 정도를 지정함.
검색 단위 (토큰 기준):
MTSU 크기 (MTSU Size):
정의: 검색 과정 중 부분 시퀀스를 해싱하는 데 사용되는 최소 단위 크기.
최소 검색 단위 크기 (Minimum Search Unit Size):
정의: 검색을 수행할 때 고려되는 최소 단위 크기.
프로젝트 요구 사항 (Project Requirements)
MTS 제약사항:
MTS는 크기가 3 토큰 이하이어야 함.
MTS는 인덱싱에 64비트 해시를 사용하는 고정 크기 키로 표현됨.
파일 사양:
파일 크기는 X KB에서 X KB 범위 (정확한 범위는 명시 필요).
인덱스 사양:
인덱서는 인덱스를 생성하며, 이후에는 변경 불가능함.
약 2^36개의 등록된 키를 처리하며, 균일한 분포를 가정함.
파일 목록 표현:
Roaring Bitmap을 사용하여 관리되며, 크기는 몇 바이트에서 몇 킬로바이트까지 다양함.
작업 처리:
각 작업은 2^16에서 2^24개의 MTS 배치 요청을 관리함.
검색 쿼리에서 허위 부정은 허용하지 않지만, 허위 긍정은 허용함.
쿼리의 10%에서 90%는 유효한 파일 목록을 반환함.
쿼리 최적화:
배치 쿼리를 실행하기 전에 키를 정렬하고 분할함.
RocksDB/LevelDB의 MultiGet API와 같은 효율적인 데이터베이스 API를 활용하여 처리함.
하드웨어 사양:
단일 머신(가전 모델) 또는 최대 8대의 머신(SaaS 모델)에 배포 가능함.
높은 동시성과 병렬 처리 요구 사항을 충족할 수 있도록 설계됨.
하드웨어 (Hardware)
정의: 인덱싱 및 쿼리 작업을 실행하는 물리적 머신 및 인프라.
특징:
단일 머신: 모든 작업이 하나의 시스템 내에서 이루어지는 가전 모델에 적합함.
분산 머신: SaaS 모델에 사용되어 더 큰 규모를 처리하고 확장성을 제공함.
SSD와 같은 저장 장치에서의 효율적인 데이터 접근을 최적화함.
고성능 요구 사항을 충족하기 위해 다중 동시 및 병렬 처리 작업을 처리할 수 있음.
해싱 및 키 분포 (Hashing and Key Distribution)
정의: 토큰을 고정 크기의 해시 값으로 변환하여 인덱스의 키로 사용하는 과정.
특징:
해시 함수의 특성상 키가 균일하게 분포됨을 가정함.
키 분포의 국소성을 제거하여 인덱스 전반에 걸쳐 균형 잡힌 부하를 보장함.
충돌을 최소화하여 인덱싱 및 검색 작업의 효율성을 향상시킴.
MultiGet API
정의: RocksDB 및 LevelDB와 같은 데이터베이스에서 단일 작업으로 여러 키-값 쌍을 검색할 수 있는 API.
특징:
여러 MTS 키를 동시에 가져와 배치 쿼리 처리를 향상시킴.
개별 쿼리 수를 줄여 전반적인 검색 성능을 개선함.
대량 작업을 위한 기본 데이터베이스 최적화를 활용하여 데이터 검색을 최적화함.
허위 긍정 및 허위 부정 (False Positives and False Negatives)
허위 긍정 (False Positive):
정의: 문서가 공통 토큰을 포함하지 않는데도 포함된 것으로 잘못 표시되는 경우.
허용 여부: 성능과 속도를 향상시키기 위해 시스템 내에서 허용됨.
허위 부정 (False Negative):
정의: 문서가 실제로 공통 토큰을 포함하고 있음에도 불구하고 이를 식별하지 못하는 경우.
허용 여부: 허용되지 않으며, 시스템은 모든 관련 문서가 검색되도록 보장해야 함.
로어링 비트맵 (Roaring Bitmap)
정의: 정수 집합을 효율적으로 표현하고 조작하기 위해 사용되는 압축된 비트맵 형식.
특징:
빠른 비트 연산과 효율적인 저장을 제공함.
일반적으로 몇 바이트에서 몇 킬로바이트 크기를 가짐.
각 인덱스 키와 연관된 파일 목록을 표현하는 데 이상적이며, 빠른 쿼리 응답을 가능하게 함.
배치 처리 (Batch Processing)
정의: 여러 쿼리나 작업을 동시에 처리하여 효율성을 높이고 처리 시간을 줄이는 방법.
특징:
단일 배치에서 대량의 MTS 요청을 관리함.
정렬되고 분할된 키를 활용하여 데이터 검색을 최적화함.
관련 작업을 그룹화하여 개별 쿼리 처리와 관련된 오버헤드를 줄임.
언어별 토큰화 (Language-Specific Tokenization)
정의: 특정 언어의 문법 및 구문 규칙에 따라 텍스트를 토큰으로 분해하는 과정.
특징:
각 언어는 텍스트를 정확히 파싱하고 토큰화하기 위해 전문 토크나이저가 필요함.
토큰 시퀀스가 각 언어의 문맥 내에서 일관되고 의미 있게 유지됨을 보장함.
다양한 언어 데이터셋 간의 토큰 기반 검색의 무결성을 유지하는 데 중요함.
SSD 최적화 (SSD Optimization)
정의: 데이터 접근 작업 중 SSD(Solid State Drive)의 성능을 극대화하기 위해 사용되는 기술과 전략.
특징:
읽기 및 쓰기 작업의 지연 시간을 최소화하고 처리량을 극대화함.
인덱싱된 데이터에 대한 효율적인 접근을 보장하여 전체 쿼리 응답 시간을 줄임.
빈번하고 빠른 데이터 접근이 요구되는 대규모 데이터셋을 처리하는 데 필수적임.
균일 키 분포 (Uniform Key Distribution)
정의: 인덱스 전체 키 공간에 걸쳐 해시 키가 고르게 분포되어 클러스터링과 핫스팟을 방지함.
특징:
FarmHash와 같은 고품질 해시 함수를 사용하여 달성됨.
인덱싱 구조 전반에 걸쳐 부하를 균형 있게 분산시켜 성능과 확장성을 향상시킴.
일관된 쿼리 응답 시간을 유지하고 성능 병목 현상을 방지하는 데 중요함.
이 확장된 글로서리는 원래의 정의와 기본 데이터에서 도입된 추가 개념을 모두 포함합니다. 데이터 구조, 처리 방법, 프로젝트 특정 요구 사항 등 시스템의 핵심 구성 요소를 다루어, 관련 용어와 아키텍처를 이해하는 데 필요한 포괄적인 참조 자료를 제공합니다.