# B-Tree의 랜덤 쓰기
# 각 쓰기마다 디스크의 여러 위치를 수정해야 함
INSERT INTO users (id, name) VALUES (1, 'Alice');   # 디스크 위치 A 수정
INSERT INTO users (id, name) VALUES (2, 'Bob');      # 디스크 위치 B 수정
INSERT INTO users (id, name) VALUES (3, 'Charlie'); # 디스크 위치 C 수정
# → 디스크 헤드 이동이 많아 성능 저하

# Python으로 LSM Tree 쓰기 과정 시뮬레이션
class MemTable:
    def __init__(self, max_size=100):
        self.data = {}  # 메모리 내 정렬된 딕셔너리
        self.max_size = max_size
    
    def put(self, key, value):
        """메모리에 데이터 쓰기 (매우 빠름)"""
        self.data[key] = value
        
        # MemTable이 가득 차면 플러시
        if len(self.data) >= self.max_size:
            return self.flush()
        return None
    
    def flush(self):
        """MemTable을 디스크(SSTable)로 플러시"""
        # 정렬된 데이터를 SSTable로 변환
        sorted_data = sorted(self.data.items())
        sstable = SSTable(sorted_data)
        self.data.clear()  # MemTable 초기화
        return sstable

# 사용 예시
memtable = MemTable(max_size=5)

# 순차적으로 쓰기 (매우 빠름)
memtable.put("user:1", "Alice")
memtable.put("user:2", "Bob")
memtable.put("user:3", "Charlie")
memtable.put("user:4", "David")
memtable.put("user:5", "Eve")  # → MemTable 가득 참 → 플러시 발생

class WAL:
    """쓰기 전 로그 - 장애 복구를 위한 로그"""
    
    def __init__(self, log_file):
        self.log_file = log_file
    
    def append(self, key, value):
        """WAL에 순차적으로 쓰기 (매우 빠름)"""
        log_entry = f"{key}:{value}\n"
        with open(self.log_file, 'a') as f:
            f.write(log_entry)
    
    def replay(self):
        """장애 복구 시 WAL 재생"""
        operations = []
        with open(self.log_file, 'r') as f:
            for line in f:
                key, value = line.strip().split(':')
                operations.append((key, value))
        return operations

# 쓰기 과정
wal = WAL("wal.log")
wal.append("user:1", "Alice")  # WAL에 먼저 쓰기
memtable.put("user:1", "Alice")  # 그 다음 MemTable에 쓰기

class SSTable:
    """Sorted String Table - 디스크에 저장되는 정렬된 데이터"""
    
    def __init__(self, sorted_data):
        self.data = dict(sorted_data)
        self.min_key = min(self.data.keys())
        self.max_key = max(self.data.keys())
        self.size = len(self.data)
    
    def get(self, key):
        """SSTable에서 키 조회"""
        return self.data.get(key)
    
    def range_query(self, start_key, end_key):
        """범위 쿼리"""
        result = {}
        for key, value in self.data.items():
            if start_key <= key <= end_key:
                result[key] = value
        return result

# MemTable 플러시 → SSTable 생성
sstable = memtable.flush()
print(f"SSTable created: {sstable.min_key} to {sstable.max_key}")

class LSMTree:
    def __init__(self):
        self.memtable = MemTable()
        self.sstables = []  # 레벨별 SSTable 리스트
        self.wal = WAL("wal.log")
    
    def get(self, key):
        """키 조회 - 최신 데이터부터 검색"""
        
        # 1. MemTable에서 먼저 검색 (가장 최신)
        if key in self.memtable.data:
            return self.memtable.data[key]
        
        # 2. SSTable들을 최신 순서로 검색
        for sstable in reversed(self.sstables):
            if sstable.min_key <= key <= sstable.max_key:
                value = sstable.get(key)
                if value is not None:
                    return value
        
        # 3. 찾지 못함
        return None

# 읽기 예시
lsm = LSMTree()
lsm.put("user:1", "Alice")
lsm.put("user:2", "Bob")

# MemTable에서 바로 찾음 (빠름)
print(lsm.get("user:1"))  # "Alice"

# MemTable 플러시 후
lsm.memtable.flush()

# SSTable에서 찾음 (상대적으로 느림)
print(lsm.get("user:1"))  # "Alice"

class Compactor:
    """SSTable 병합 담당"""
    
    @staticmethod
    def compact(sstables):
        """여러 SSTable을 하나로 병합"""
        merged_data = {}
        
        # 모든 SSTable의 데이터를 병합 (최신 값 우선)
        for sstable in reversed(sstables):  # 최신부터
            for key, value in sstable.data.items():
                if key not in merged_data:  # 최신 값만 유지
                    merged_data[key] = value
        
        # 정렬된 새 SSTable 생성
        sorted_data = sorted(merged_data.items())
        return SSTable(sorted_data)
    
    @staticmethod
    def level_compact(level_sstables, next_level_sstables):
        """레벨 간 병합 (Leveled Compaction)"""
        # L1의 SSTable들을 L2와 병합
        all_sstables = level_sstables + next_level_sstables
        return Compactor.compact(all_sstables)

# Compaction 예시
sstable1 = SSTable([("a", "1"), ("b", "2")])
sstable2 = SSTable([("b", "3"), ("c", "4")])  # b가 업데이트됨

# 병합 (최신 값 우선)
merged = Compactor.compact([sstable1, sstable2])
print(merged.data)  # {'a': '1', 'b': '3', 'c': '4'}

# Bloom Filter 없이 키 검색
def get_without_bloom_filter(key):
    # 모든 SSTable을 검색해야 함
    for sstable in sstables:
        if key in sstable:  # 디스크 I/O 발생!
            return sstable.get(key)
    return None

# 문제: 존재하지 않는 키도 모든 SSTable을 검색해야 함
# → 불필요한 디스크 I/O 발생

# Bloom Filter로 키 검색
def get_with_bloom_filter(key):
    for sstable in sstables:
        if sstable.bloom_filter.might_contain(key):  # 메모리에서 빠르게 확인
            if key in sstable:  # 실제로 존재할 때만 디스크 I/O
                return sstable.get(key)
    return None

# 장점: 존재하지 않는 키는 디스크 I/O 없이 빠르게 거부

import mmh3  # MurmurHash3
import math

class BloomFilter:
    """Bloom Filter 구현"""
    
    def __init__(self, capacity, error_rate=0.01):
        """
        capacity: 예상 원소 개수
        error_rate: 허용 가능한 False Positive 비율
        """
        self.capacity = capacity
        self.error_rate = error_rate
        
        # 비트 배열 크기 계산
        # m = -n * ln(p) / (ln(2)^2)
        self.bit_array_size = int(-capacity * math.log(error_rate) / (math.log(2) ** 2))
        
        # 해시 함수 개수 계산
        # k = (m/n) * ln(2)
        self.hash_count = int((self.bit_array_size / capacity) * math.log(2))
        
        # 비트 배열 초기화
        self.bit_array = [0] * self.bit_array_size
    
    def _hash(self, item, seed):
        """해시 함수 (MurmurHash3 사용)"""
        return mmh3.hash(item, seed) % self.bit_array_size
    
    def add(self, item):
        """원소 추가"""
        for i in range(self.hash_count):
            index = self._hash(item, i)
            self.bit_array[index] = 1
    
    def might_contain(self, item):
        """원소 존재 가능성 확인"""
        for i in range(self.hash_count):
            index = self._hash(item, i)
            if self.bit_array[index] == 0:
                return False  # 확실히 존재하지 않음
        return True  # 존재할 가능성이 있음 (False Positive 가능)

# 사용 예시
bloom = BloomFilter(capacity=1000, error_rate=0.01)

# 원소 추가
bloom.add("user:1")
bloom.add("user:2")
bloom.add("user:3")

# 존재 확인
print(bloom.might_contain("user:1"))  # True
print(bloom.might_contain("user:999"))  # False (확실히 없음)
print(bloom.might_contain("user:1001"))  # True or False (False Positive 가능)

def calculate_false_positive_rate(n, m, k):
    """
    n: 실제 원소 개수
    m: 비트 배열 크기
    k: 해시 함수 개수
    """
    # False Positive 확률 = (1 - e^(-kn/m))^k
    import math
    return (1 - math.exp(-k * n / m)) ** k

# 예시
n = 1000  # 1000개 원소
m = 9585  # 비트 배열 크기 (error_rate=0.01일 때)
k = 7     # 해시 함수 개수

fp_rate = calculate_false_positive_rate(n, m, k)
print(f"False Positive Rate: {fp_rate:.4f}")  # 약 0.01 (1%)

def optimal_bloom_filter_params(capacity, error_rate):
    """최적의 Bloom Filter 파라미터 계산"""
    import math
    
    # 비트 배열 크기
    m = int(-capacity * math.log(error_rate) / (math.log(2) ** 2))
    
    # 해시 함수 개수
    k = int((m / capacity) * math.log(2))
    
    return {
        'bit_array_size': m,
        'hash_count': k,
        'memory_bytes': m / 8,  # 비트를 바이트로 변환
        'bits_per_element': m / capacity
    }

# 예시: 100만 개 원소, 1% 오류율
params = optimal_bloom_filter_params(1_000_000, 0.01)
print(f"비트 배열 크기: {params['bit_array_size']:,} bits")
print(f"해시 함수 개수: {params['hash_count']}")
print(f"메모리 사용량: {params['memory_bytes'] / 1024 / 1024:.2f} MB")
print(f"원소당 비트 수: {params['bits_per_element']:.2f}")

# 출력:
# 비트 배열 크기: 9,585,058 bits
# 해시 함수 개수: 7
# 메모리 사용량: 1.14 MB
# 원소당 비트 수: 9.59

class SSTableWithBloomFilter:
    """Bloom Filter가 포함된 SSTable"""
    
    def __init__(self, sorted_data):
        self.data = dict(sorted_data)
        self.min_key = min(self.data.keys())
        self.max_key = max(self.data.keys())
        
        # Bloom Filter 생성
        self.bloom_filter = BloomFilter(
            capacity=len(self.data),
            error_rate=0.01
        )
        
        # 모든 키를 Bloom Filter에 추가
        for key in self.data.keys():
            self.bloom_filter.add(key)
    
    def get(self, key):
        """Bloom Filter로 필터링 후 조회"""
        # 1. Bloom Filter로 빠른 필터링
        if not self.bloom_filter.might_contain(key):
            return None  # 확실히 없음 → 디스크 I/O 없음
        
        # 2. 실제 데이터 조회 (디스크 I/O 발생)
        return self.data.get(key)

class OptimizedLSMTree:
    """Bloom Filter가 통합된 LSM Tree"""
    
    def __init__(self):
        self.memtable = MemTable()
        self.sstables = []
        self.wal = WAL("wal.log")
    
    def get(self, key):
        """최적화된 읽기 - Bloom Filter 활용"""
        
        # 1. MemTable 검색 (메모리, 가장 빠름)
        if key in self.memtable.data:
            return self.memtable.data[key]
        
        # 2. SSTable 검색 (Bloom Filter로 필터링)
        for sstable in reversed(self.sstables):
            # Bloom Filter로 먼저 확인 (메모리, 빠름)
            if sstable.bloom_filter.might_contain(key):
                # 실제로 존재할 가능성이 있음 → 디스크에서 조회
                value = sstable.get(key)
                if value is not None:
                    return value
        
        return None

# 성능 비교
def benchmark_read_performance():
    """읽기 성능 벤치마크"""
    import time
    
    lsm_without_bf = LSMTree()  # Bloom Filter 없음
    lsm_with_bf = OptimizedLSMTree()  # Bloom Filter 있음
    
    # 테스트 데이터 준비
    for i in range(10000):
        lsm_without_bf.put(f"key:{i}", f"value:{i}")
        lsm_with_bf.put(f"key:{i}", f"value:{i}")
    
    # 존재하지 않는 키 검색 (가장 큰 차이)
    start = time.time()
    for i in range(10000, 20000):
        lsm_without_bf.get(f"key:{i}")  # 모든 SSTable 검색
    time_without_bf = time.time() - start
    
    start = time.time()
    for i in range(10000, 20000):
        lsm_with_bf.get(f"key:{i}")  # Bloom Filter로 빠르게 필터링
    time_with_bf = time.time() - start
    
    print(f"Bloom Filter 없음: {time_without_bf:.4f}초")
    print(f"Bloom Filter 있음: {time_with_bf:.4f}초")
    print(f"성능 향상: {time_without_bf / time_with_bf:.2f}배")

# benchmark_read_performance()
# 출력 예시:
# Bloom Filter 없음: 2.3456초
# Bloom Filter 있음: 0.1234초
# 성능 향상: 19.01배

import rocksdb

# RocksDB 열기
db = rocksdb.DB("test.db", rocksdb.Options(create_if_missing=True))

# 쓰기 (매우 빠름 - 순차 쓰기)
db.put(b"user:1", b"Alice")
db.put(b"user:2", b"Bob")
db.put(b"user:3", b"Charlie")

# 읽기 (Bloom Filter로 최적화)
value = db.get(b"user:1")
print(value)  # b"Alice"

# 배치 쓰기 (더 빠름)
batch = rocksdb.WriteBatch()
batch.put(b"user:4", b"David")
batch.put(b"user:5", b"Eve")
db.write(batch)

# 범위 스캔
it = db.iteritems()
it.seek(b"user:")
for key, value in it:
    print(f"{key}: {value}")

class AdaptiveBloomFilter:
    """데이터 크기에 따라 자동 조정되는 Bloom Filter"""
    
    def __init__(self, initial_capacity=1000):
        self.capacity = initial_capacity
        self.bloom_filter = BloomFilter(initial_capacity)
        self.actual_count = 0
    
    def add(self, item):
        """원소 추가 시 용량 자동 확장"""
        self.bloom_filter.add(item)
        self.actual_count += 1
        
        # 실제 개수가 예상 용량의 80%를 넘으면 확장
        if self.actual_count >= self.capacity * 0.8:
            self._expand()
    
    def _expand(self):
        """Bloom Filter 확장"""
        old_filter = self.bloom_filter
        self.capacity *= 2
        self.bloom_filter = BloomFilter(self.capacity)
        
        # 기존 데이터 재구성 (실제로는 SSTable 재생성 시 수행)
        # 여기서는 시뮬레이션
        print(f"Bloom Filter expanded to {self.capacity}")

class BlockBloomFilter:
    """SSTable의 각 블록마다 별도의 Bloom Filter"""
    
    def __init__(self, block_size=4096):
        self.block_size = block_size
        self.block_filters = {}  # 블록별 Bloom Filter
    
    def add_to_block(self, key, block_id):
        """특정 블록의 Bloom Filter에 추가"""
        if block_id not in self.block_filters:
            self.block_filters[block_id] = BloomFilter(
                capacity=self.block_size
            )
        self.block_filters[block_id].add(key)
    
    def might_contain_in_block(self, key, block_id):
        """특정 블록에 키가 존재하는지 확인"""
        if block_id not in self.block_filters:
            return False
        return self.block_filters[block_id].might_contain(key)

class CompactionStrategy:
    """Compaction 전략 선택"""
    
    @staticmethod
    def size_tiered_compact(sstables):
        """Size-Tiered: 비슷한 크기 파일들 병합"""
        # 같은 크기 범위의 SSTable들을 그룹화
        size_groups = {}
        for sstable in sstables:
            size_range = sstable.size // 1000  # 1KB 단위로 그룹화
            if size_range not in size_groups:
                size_groups[size_range] = []
            size_groups[size_range].append(sstable)
        
        # 각 그룹에서 4개 이상이면 병합
        merged = []
        for size_range, group in size_groups.items():
            if len(group) >= 4:
                merged.append(Compactor.compact(group))
            else:
                merged.extend(group)
        
        return merged
    
    @staticmethod
    def leveled_compact(levels):
        """Leveled: 레벨별 크기 제한"""
        for level, sstables in enumerate(levels):
            max_files = 10 * (level + 1)  # 레벨이 높을수록 더 많은 파일 허용
            if len(sstables) > max_files:
                # 초과 파일들을 다음 레벨과 병합
                return Compactor.level_compact(
                    sstables[:max_files],
                    levels[level + 1] if level + 1 < len(levels) else []
                )
        return levels

class MemoryAwareMemTable(MemTable):
    """메모리 사용량을 모니터링하는 MemTable"""
    
    def __init__(self, max_size=100, max_memory_mb=100):
        super().__init__(max_size)
        self.max_memory_mb = max_memory_mb
        self.current_memory_mb = 0
    
    def put(self, key, value):
        """메모리 사용량 체크"""
        key_size = len(str(key).encode())
        value_size = len(str(value).encode())
        entry_size_mb = (key_size + value_size) / (1024 * 1024)
        
        if self.current_memory_mb + entry_size_mb > self.max_memory_mb:
            # 메모리 초과 → 즉시 플러시
            return self.flush()
        
        self.current_memory_mb += entry_size_mb
        return super().put(key, value)
    
    def flush(self):
        """플러시 후 메모리 초기화"""
        result = super().flush()
        self.current_memory_mb = 0
        return result