Constant Hash지금 공부하고 있는 데이터베이스는 하나의 컴퓨터에 모든 데이터를 저장하는 것을 가정하고 있다.하지만 규모가 큰 서비스를 운영하다보면 매우 많은 데이터를 다루므로 하나의 컴퓨터에 저장할 수 없다.따라서 규모가 큰 데이터는 결국 여러 컴퓨터에 쪼개서 저장할 수 밖에 없다. 데이터를 나누어서 저장한다면 우선 그림과 같이 같은 스키마를 갖는 테이블을 여러 개 만들어야 한다.이때 어떤 데이터가 어떤 테이블에 저장될 지 결정하기 위해 각각의 테이블에 0번부터 i 번까지 인덱스를 매긴다.그리고 데이터를 저장할 테이블을 결정할 때는 데이터의 PK를 해싱한 값으로 결정한다.이때 해시 값은 0부터 i 사이의 값이 나올 것이다.해시함수는 단순하게 고려한다면, PK 값이 숫자일 때 이 수를 (i+1..
Nullnull 은 알지 못하는 값, 존재하지 않는 값을 명시적으로 나타내는 값이다. 만약 어떤 직원이 퇴사하면서 데이터가 삭제되면 그 직원의 피부양자가 모두 삭제되도록 구현하는 테이블이 있다고 해보자.이때 실제로 데이터를 지우는 Hard Delete 방식 외에도, 그냥 피부양자에 대한 내용을 null 로 바꿈으로서 지우는 Soft Delete 방식을 적용할 수도 있다. 다만 Null 값을 사용할 때는 PK 에 null 이 들어갈 수 없다는 것만 기억하자.따라서 테이블을 설계할 때, PK에는 별도의 제약조건을 명시히지 않아도, 기본적으로 NOT NULL 제약조건이 걸린다. General Constraint무결정 제약조건을 걸 때, 키 제약조건, 널 제약조건, 참조 제약조건 등 다양한 제약 조건을 걸 수..
관계 대수에서는 없었지만, SQL에는 테이블에 있는 데이터들에 대해 다음의 5가지 집계 함수를 제공한다. 1. count()2. sum()3. avg()4. max()5. min() 이때 각 함수에는 하나의 컬럼이 들어가며, 1, 2, 3 은 그 컬럼에 대해 Distinct 를 취할 수도 있다.(4, 5번에도 사용은 가능하나 DISTINCT 를 취해도 같은 결과가 나온다.) 1. 모든 선원의 평균 나이SELECT avg(S.age)FROM sailors S; 2. 등급이 10인 선원의 평균 나이SELECT avg(S.age)FROM sailors SWHERE S.rating = 10; 3. 가장 나이가 많은 선원의 이름과 나이SELECT S.sname, S.ageFROM sailors SWHERE ..
SQL의 쿼리는 FROM, WHERE, HAVING 절 안에서도 중첩되어 등장할 수 있다.103번 보트를 예약한 선원의 이름을 출력할 때 다음과 같이 중첩된 쿼리를 통해서도 문제를 해결할 수 있다. 이는 마치 중첩된 반복문을 작성하는 것과 비슷하다.선원 테이블에서 모든 선원을 가져오고, 각 선원에 대해서 돌면서 (for each) 예약테이블을 돌면서 선원 정보를 찾는 것과 비슷하다.이때 IN 연산자는 집합 연산자로서 해당 서브쿼리의 결과 집합에 S.sid 가 존재하는 sid 만을 조회한다. 서브쿼리와 관련된 간단한 연습문제를 몇 가지 풀어보자. 1. 빨간색 배를 예약한 적이 있는 / 없는 선원 이름 조회SELECT S.snameFROM sailors SWHERE S.sid IN ( SELECT ..
SQL을 다루기에 앞서 다음과 같은 테이블을 사용한다. sailors 테이블 reserves 테이블 Boats 테이블 기본 문법 SQL 기본 문법의 형태는 위와 같다.이때 실행 순서는 FROM - WHERE - SELECT 순서이다.From 절로 릴레이션 리스트를 가져오고, 가져온 릴레이션에서 WHERE 절로 조건에 맞는 행을 고른 뒤, 그 안에서 보고 싶은 컬럼을 select 하면 된다.만약 DISTINCT 키워드가 있다면 select 결과에 대해 중복값을 제거한다. FROM 절에 들어가는 relation-list 에 여러개의 릴레이션을 넣으면 각 릴레이션에 대해 cross product 한 결과를 만들어낸다.WHERE 절은 관계 대수에서 selection 에 해당하는 부분이며, qualificati..
인터렉티브 시스템은 사용자의 요청에 얼마나 빠르게 응답하는지를 중점적으로 보는 시스템이다.따라서 인터렉티브 시스템은 선점형 스케줄링 알고리즘을 사용하며 response time 을 낮추는 것을 목표로 하였다. 이번 글에서는 인터렉티브 시스템의 스케줄링 알고리즘들을 정리해보자. Round Robin Scheduling라운드 로빈 스케줄링은 이름 그대로 빙글빙글 돌아가면서 프로세스를 실행하는 알고리즘이다.배치 시스템 스케줄링에서 봤었던 FCFS 스케줄링처럼 앞에 것을 실행하고 뒤로 보내는 것을 반복하면서 마치 원형큐를 사용하듯 쓰는 방법인데, 여기에 선점형 스케줄링의 속성이 추가되었다고 보면 된다. (a) 그림에 있는 프로세스들이 runnable 프로세스 ( = ready 상태에 있는 프로세스, run..
지난 글에서 정리한 것처럼, 배치 시스템은 프로세스 스위칭을 최소화하고 성능을 높이는 것을 목표로 한다.배치 시스템에서 사용하는 다양한 스케줄링 알고리즘을 정리해보자. FCFS (First-Come-First-Served)선입 선처리 스케줄링 또는 FCFS 스케줄링라고 부른다.이름 그대로 CPU 사용을 요청한 순서대로 할당해주는 방식의 알고리즘이다. 이를 위해서 하나의 큐를 사용하며, 현재 실행중인 프로세스가 Blocked 상태로 가면 큐의 맨 앞에 있는 프로세스를 running 상태로 올린다. 만약 blocked 상태에 있던 프로세스가 ready상태가 되면, 큐의 맨 뒤에 해당 프로세스를 넣는다. 이 스케줄링 알고리즘은 비선점 스케줄링 알고리즘이다.큐에 들어온 순서대로 순차적으로 실행만 하고, 실행하..
Scheduling과거 배치 시스템과 TimeSharing 방식의 컴퓨터가 있었을 때는 CPU가 매우 희귀한 자원이었다.그래서 이 비싸고 귀중한 CPU 자원을 최대한 많은 프로세스를 처리하는데 효율적으로 쓰기 위해서 여러가지 고민이 필요했다. 시간이 지나면서 CPU 성능이 증가하고 개인용 컴퓨터 시대가 온 뒤에는 과거만큼 CPU를 효율적으로 사용하기 위한 스케줄링 알고리즘의 고민 필요성이 낮아졌지만, 그럼에도 불구하고 서버 컴퓨터와 같은 고성능 컴퓨터에서는 스케줄링 알고리즘에 대한 고민이 필요하다.(보통 서버컴퓨터는 접속하는 클라이언트마다 프로세스를 생성하기 때문이다.) 그리고 프로세스는 계속 상태가 변하면서 번갈아 실행이 되는데,이렇게 실행하는 프로세스를 교체하는 것을 가리켜 프로세스 스위칭 또는 컨텍..
NFANondeterministic Finite Accepter DFA와 마찬가지로 유한한 저장공간을 가지며, 답을 yes / no 로만 내는 기계를 말한다.다만 Nondeterministic 이므로, 현재 상태에서 특정 인풋이 주어졌을 때, 다른 상태로 넘어갈 수 있는 길이 여러개가 있거나 없을 수 있는 기계를 말한다. 구성요소 자체는 DFA와 동일하므로 DFA와 유사하게 정의된다. 이때 𝜹 에 들어갈 수 있는 transition function는 DFA와 다르다.델타에는 DFA와 마찬가지로 𝜹(Qx, a) = Qy 로 표기할 수 있다.다만 이때 Qy가 하나의 상태가 아니라 여러 개의 상태 집합일 수 있으며, 입력 심볼에도 빈 문자열 람다가 들어올 수 있다. 위 정의에서 말하는 2^Q 는 pow..
그림과 같이 음식과 포크가 주어져있다.이때 각 음식 앞에는 철학자들이 있고, 철학자들은 생각을 하거나 음식을 먹는다. 철학자들은 다음과 같은 순서로 식사를 진행한다. 1. 생각을 하다가 왼쪽 포크가 사용가능하면 집는다.2. 생각을 하다가 오른쪽 포크가 사용가능하면 집는다.3. 두 포크를 모두 집었다면 일정시간 식사를 한다.4. 식사를 마치고 오른쪽 포크를 내려둔다.5. 왼쪽 포크를 내려둔다.6. 1~5반복 이를 코드로 구현하면 아래와 같다. 이때 만약 모든 철학자가 동시에 식사를 시작하면 모두 동시에 왼쪽 포크를 집어들고 오른쪽 포크를 서로가 영원히 기다리므로 식사를 할 수 없게 된다. 이렇게 서로가 이미 점유한 자원에 서로 의존하여 모든 프로세스가 동작을 멈추는 상황을 '데드락(교착 상태)' 이라고..
