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와 같은 고품질 해시 함수를 사용하여 달성됨.
  • 인덱싱 구조 전반에 걸쳐 부하를 균형 있게 분산시켜 성능과 확장성을 향상시킴.
  • 일관된 쿼리 응답 시간을 유지하고 성능 병목 현상을 방지하는 데 중요함.

---

이 확장된 글로서리는 원래의 정의와 기본 데이터에서 도입된 추가 개념을 모두 포함합니다. 데이터 구조, 처리 방법, 프로젝트 특정 요구 사항 등 시스템의 핵심 구성 요소를 다루어, 관련 용어와 아키텍처를 이해하는 데 필요한 포괄적인 참조 자료를 제공합니다.