반응형 Computer Science/Databases21 [데이터베이스] recovery 알고리즘 종류과 checkpoint 동작 원리 데이터베이스 장애와 복구, 데이터 접근 구조Failure Classification(장애 분류)데이터베이스 시스템에서 발생할 수 있는 장애(failure)는 크게 세 가지로 분류된다.Transaction failure(트랜잭션 장애)Logical errors: 트랜잭션 내부 오류로 인해 완료되지 못하는 경우System errors: 데드락(deadlock) 등 시스템이 트랜잭션을 강제로 종료해야 하는 경우System crash(시스템 크래시)전원 장애, 하드웨어/소프트웨어 오류 등으로 시스템이 중단되는 현상Fail-stop assumption: 비휘발성 저장장치의 데이터는 시스템 크래시로 손상되지 않는다고 가정데이터베이스 시스템은 무결성(integrity) 체크를 통해 데이터 손상 방지Disk failu.. 2025. 6. 12. [데이터베이스] 타임스탬프 기반과 버전 기반 제어 프로토콜의 동작 원리 - Timestamp-Ordering(TSO), Validation-based, Optimistic Concurrency Control(OCC) Timestamp-Based Protocols각 transaction Ti는 고유한 timestamp TS(Ti)를 가진다.Timestamp는 transaction이 시작할 때 할당되며, 새로운 transaction들은 이전 것들보다 큰 timestamp를 가진다.Timestamp는 logical counter를 기반으로 할 수 있다.Real time은 unique하지 않을 수 있으므로 (wall-clock time, logical counter)를 사용하여 uniqueness를 보장할 수 있다.Timestamp-based protocol은 timestamp order = serializability order가 되도록 concurrent execution을 관리한다.Timestamp-Ordering P.. 2025. 6. 6. [데이터베이스] 데드락과 팬텀현상을 해결 위한 동시성 제어 프로토콜의 종류 (deadlock, 교착상태, Phantom, Granularity) - Index Locking, Next-Key Locking Protocol Deadlock HandlingDeadlock이란 transaction들의 집합에서 각 transaction이 집합 내의 다른 transaction을 기다리고 있는 상황이다. 이러한 deadlock 상황을 처리하는 방법에는 prevention, detection, recovery가 있다. Deadlock PreventionDeadlock prevention protocol은 시스템이 deadlock 상태에 절대 진입하지 않도록 보장하는 기법들이다.1. Pre-declaration 방식각 transaction이 실행을 시작하기 전에 필요한 모든 data item들을 미리 lock하는 방법이다.2. Graph-based Protocol모든 data item에 partial ordering을 부과하고, tra.. 2025. 6. 6. [데이터베이스] 동시성, 격리 수준 이론과 락(lock) 기반 프로토콜의 종류 - 2PL, graph based protocol, tree, lock table Concurrency ControlDBMS에서 Concurrency Control의 목표는 다음과 같다.스케줄링 결정이 conflict serializable 또는 view serializable이어야 하며,recoverable하고 가능하면 cascadeless해야 한다.Scheduler는 높은 수준의 concurrency(동시성)를 제공해야 한다.단일 트랜잭션만 실행하는 정책은 serial schedule을 만들지만 concurrency가 매우 낮다.Concurrency-control scheme은 허용하는 concurrency의 양과 발생하는 오버헤드 사이에서 tradeoff를 가진다.어떤 scheme은 conflict-serializable schedule만 생성하고, 어떤 scheme은 confl.. 2025. 6. 6. [데이터베이스] Query Processing 단계, 비용과 최적화, 내부 동작 원리 Query ProcessingQuery processing(질의 처리)은 사용자가 작성한 고수준 쿼리(SQL 등)를 내부적으로 효율적으로 실행할 수 있는 저수준 연산으로 변환하고, 최적의 실행 계획을 선택하여 실제로 결과를 산출하는 일련의 과정을 의미한다. 이 과정은 데이터베이스 시스템의 성능과 효율성에 직접적으로 영향을 미친다.Query Processing의 3단계1. Parsing and Translation사용자가 입력한 쿼리의 문법(syntax)과 의미(semantics)를 검사한다.쿼리를 내부 표현(주로 relational algebra expression, 관계 대수식)으로 변환한다.파서는 SQL 문법 오류를 체크하고, 존재하지 않는 relation이나 attribute가 사용되었는지 검증한다.. 2025. 5. 24. [데이터베이스] 쓰기 중심 특화 자료구조 : LSM Tree, Skip list, Redis zset (Write Optimized Indices) Write Optimized Indices와 LSM Tree, Skip list, Redis zsetWrite Optimized IndicesB+ tree는 write-intensive workload(쓰기 중심 작업) 환경에서 성능이 저조할 수 있다.모든 internal node가 메모리에 있다고 가정해도, leaf node당 한 번의 I/O가 필요하다.자기 디스크(magnetic disk) 사용 시, 디스크당 초당 100번 미만의 insert 처리 성능을 보인다.플래시 메모리(flash memory)에서는 insert마다 한 페이지를 overwrite한다.쓰기 비용(write cost)을 줄이기 위한 대표적 접근법 중 하나가 Log-structured merge tree(LSM tree)이다.Log .. 2025. 5. 24. [데이터베이스] 트랜잭션 개념과 스케쥴 종류, Serializability의 종류(Transaction, Serializability, Schedule) Transaction 개념Transaction은 다양한 데이터 항목에 접근하고 업데이트할 수 있는 프로그램 실행 단위이다.Transaction은 데이터베이스의 일관성을 유지하면서 안전하게 데이터를 처리하기 위한 메커니즘으로, 주로 두 가지 주요 문제를 다룬다: 하드웨어 고장이나 시스템 충돌과 같은 다양한 종류의 failure와 여러 transaction들의 concurrent execution이다.Transaction의 기본 예시: 계좌 이체Transaction의 개념을 이해하기 위해 계좌 이체 예시를 살펴보자. 계좌 A에서 계좌 B로 $50을 이체하는 transaction은 다음과 같은 단계로 구성된다:read(A) - 계좌 A의 잔액을 읽는다A := A - 50 - 계좌 A에서 $50을 차감한다wri.. 2025. 5. 18. 이전 1 2 3 다음
