본문 바로가기
반응형

전체 글261

[데이터베이스] 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.
[네트워크] TCP 혼잡제어의 원리와 발전, QUIC 프로토콜의 발달 (TCP congestion control) TCP Congestion Control: AIMD 메커니즘의 동작 원리TCP(Transmission Control Protocol)에서 사용하는 혼잡 제어(congestion control) 메커니즘 중 가장 기본적인 형태는 AIMD(Additive Increase Multiplicative Decrease)이다.이 메커니즘은 네트워크의 가용 대역폭을 효과적으로 탐지하고 활용하기 위한 접근 방식이다.AIMD의 기본 원리AIMD approach는 송신자가 패킷 손실(네트워크 혼잡 상태)이 발생할 때까지 전송 속도를 점진적으로 증가시키다가, 손실 이벤트 발생 시 전송 속도를 급격하게 감소시키는 방식으로 동작한다. 이 메커니즘은 두 가지 핵심 요소로 구성되어 있다.Additive Increase(가산적 증가.. 2025. 5. 19.
[데이터베이스] 트랜잭션 개념과 스케쥴 종류, 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.
[네트워크] 혼잡 제어의 원리와 종류 (Principles of Congestion Control) 혼잡 제어의 원리(Principles of Congestion Control)혼잡(Congestion)은 비공식적으로 "너무 많은 출발지가 너무 많은 데이터를 너무 빠른 속도로 전송하여 네트워크가 처리할 수 없는 상태"를 의미한다.네트워크에서 혼잡이 발생하면 긴 지연(long delays)과 패킷 손실(packet loss)과 같은 증상이 나타난다.이는 라우터 버퍼에서의 대기(queueing)와 버퍼 오버플로우로 인한 패킷 버림 현상으로 발생한다.혼잡 제어와 흐름 제어의 차이혼잡 제어(congestion control)와 흐름 제어(flow control)는 서로 다른 개념이다. 혼잡 제어는 너무 많은 송신자가 너무 빠르게 데이터를 보내는 상황을 관리하는 것이고, 흐름 제어는 한 송신자가 한 수신자에게 .. 2025. 5. 15.
[데이터베이스] 해싱의 종류와 동작 원리(Static, Dynamic Hashing, Linear, Extendible)와 비트맵 인덱스(Bitmap Index) Static Hashing의 기본 개념과 동작 원리기본 구조Static hashing은 고정된 수의 bucket을 사용하는 인덱싱 방식이다.Bucket은 항목들을 포함하는 저장 공간이다.일반적으로 bucket은 디스크 블록(약 4KB)과 같다.Hash function은 bucket의 위치를 찾는 데 사용된다.Hash function h는 search-key 집합에서 bucket 주소 집합으로의 함수이다.서로 다른 search-key가 같은 bucket에 매핑될 수 있다.Bucket 전체를 순차적으로 검색해야 한다.인덱스와 파일 구성에서의 사용:Hash index에서 bucket은 record 포인터가 있는 항목을 저장한다.Hash file-organization에서 bucket은 record 자체를 저장.. 2025. 5. 15.
[네트워크] TCP 연결 지향 프로토콜 구조와 동작 방식 - Connection-oriented transport: TCP Connection-oriented transport: TCP의 특징point-to-point: 하나의 송신자와 하나의 수신자 연결reliable, in-order byte stream: "메시지 경계"가 없는 바이트 스트림 방식full duplex data: 동일한 연결에서 양방향 데이터 흐름, MSS (maximum segment size)cumulative ACKs: 누적 확인응답 방식pipelining: TCP 혼잡 제어와 흐름 제어가 윈도우 크기 설정connection-oriented: 핸드셰이킹으로 데이터 교환 전 송수신자 상태 초기화flow controlled: 송신자가 수신자를 압도하지 않도록 제어 TCP 세그먼트 구조TCP 세그먼트는 다음과 같은 필드로 구성된다:소스 포트 번호와 목적지 .. 2025. 5. 12.
[ZooKeeper] 주키퍼 워처와 트리거를 활용한 시스템 장애 감지와 오토 힐러 클러스터 (Watcher, Trigger, Autohealer) 주키퍼의 워처와 트리거 메커니즘을 활용한 오토힐링 구현 가이드분산 시스템에서 노드 장애를 감지하고 자동으로 복구하는 메커니즘은 시스템의 안정성과 가용성을 유지하는 데 매우 중요하다.주키퍼(ZooKeeper)는 이러한 분산 시스템의 조정을 위한 강력한 도구를 제공하며, 그 중에서도 워처(Watcher)와 트리거(Trigger) 메커니즘은 장애 감지와 자동 복구에 필수적인 요소이다.이 글에서는 주키퍼의 워처와 트리거에 대해 상세히 알아보고, 이를 활용한 오토힐링 구현 방법을 살펴보겠다.주키퍼의 워처(Watcher)와 트리거(Trigger) 개념워처는 주키퍼에서 변경사항 발생 시 알림 이벤트를 받기 위해 등록하는 객체이다. 주키퍼는 getChildren(), getData(), exists() 같은 메서드를 .. 2025. 5. 11.
[운영체제] OS의 동기화(Synchronization) 개념과 기법 종류 (lock, semaphore, deadlock, condition variables, monitor) - 락, 세마포어, 교착상태, 모니터 운영체제 Synchronization운영체제에서 Synchronization은 프로세스 간 자원 접근을 관리하고 일관성을 유지하기 위한 중요한 메커니즘이다. 여러 프로세스가 동시에 실행될 때 공유 자원에 대한 접근을 제어함으로써 데이터 무결성을 보장한다. Background프로세스는 동시에 실행될 수 있으며(concurrently), 언제든지 중단될 수 있어 부분적으로만 실행이 완료될 수 있다. 공유 데이터에 대한 동시 접근은 데이터 불일치를 초래할 수 있다. 데이터 일관성을 유지하기 위해서는 협력하는 프로세스들의 순차적 실행을 보장하는 메커니즘이 필요하다. 문제 예시로, 모든 버퍼를 채우는 생산자-소비자 문제의 해결책을 제공하고자 한다. 이를 위해 가득 찬 버퍼의 수를 추적하는 정수형 counter를 .. 2025. 5. 10.
[데이터베이스] B+-Tree 자료구조와 인덱싱(Ordered Indexing), B-Tree 소개 B+ Tree의 구조와 동작B+ Tree의 정의와 기본 속성B+ Tree는 다음과 같은 특성을 만족하는 rooted tree이다.모든 root에서 leaf node까지의 경로 길이는 동일하다. (균형 트리, balanced tree)root와 leaf node가 아닌 모든 노드는 ⎡n/2⎤ 이상 n 이하의 자식 노드를 가진다. (⎡X⎤-> upper bound)leaf node는 ⎡(n-1)/2⎤ 이상, (n-1) 이하의 값을 가진다.특수한 경우:root가 leaf node가 아니라면 최소 2개의 자식 노드를 가진다.root가 leaf node라면(트리에 다른 노드가 없다면) 0개에서 (n-1)개 값까지 가질 수 있다. B+ Tree Node의 구조각 node는 다음과 같이 구성된다.Ki: search-.. 2025. 5. 8.

티스토리툴바