어떻게 스스로 SQL 실행 엔진 을 작성 합 니까?

머리말
데이터베이스 에 관 한 자 료 를 대량으로 읽 은 후에 필 자 는 자기도 모 르 게 데이터베이스 바퀴 를 만 들 겠 다 는 생각 이 들 었 다.데이터베이스 의 밑바닥 원리 에 대한 자신의 파악 이 믿 을 만 한 지 검증 해 보 자.필자 의 github 에서 이 database 에 Freedom 이 라 고 이름 을 지 었 다.
전체 구조
바퀴 를 만 든 이상 전단 의 네트워크 프로 토 콜 에서 백 엔 드 의 파일 저장 소 까지 모두 훑 어 봐 야 한다.다음은 Freedom 이 실현 하 는 전체적인 구조 이 고 그 안에 실현 되 는 대체적인 모듈 이 포함 되 어 있다.

최종 저장 구 조 는 당연히 고전적 인 B+트 리 구 조 를 사용한다.물론 B+트 리 와 파일 시스템 블록 사이 의 전환 은 Buffer(Page)Manager 를 통 해 이 루어 집 니 다.물론,업 무 를 완성 하기 위해 서 는 로그 매니저 를 통 해 WAL 프로 토 콜 을 사용 해 야 합 니 다.
Freedom 은 색인 조직 표를 사용 하여 DruidSQL Parse 를 통 해 sql 을 해당 하 는 색인 연산 자로 번역 하여 대응 하 는 의미 조작 을 합 니 다.
MySQL Protocol 구조
client/server 간 의 상호작용 은 MySQL 프로 토 콜 을 사용 하여 my sql client 와 jdbc 와 쉽게 상호작용 을 할 수 있 습 니 다.
query packet
my sql 은 3byte 의 고정 패키지 헤드 를 통 해 하 도 급 을 하여 tcp 흐름 의 읽 기 문 제 를 해결 합 니 다.하나의 sequenceId 를 통 해 패 킷 의 연속 여 부 를 판단 합 니 다.

result set packet
my sql 프로 토 콜 부분 에서 가장 복잡 한 내용 은 result set 에 대한 읽 기 이 고 NIO 방식 에서 복잡성 을 가중 시 켰 습 니 다.
Freedom 은 일련의 읽 기 상 태 를 설정 함으로써 Netty 프레임 워 크 에서 이 문 제 를 잘 해결 할 수 있 습 니 다.

row packet
또 하나의 간단 한 것 은 row 형식 을 읽 는 것 입 니 다.위의 그림 에서 보 듯 이 순서대로 해석 하면 됩 니 다.

협의 해석 부분 이 비교적 간단 하기 때문에,여기 서 는 더 이상 군말 하지 않 는 다.
SQL Parse
Freedom 은 성숙 하고 사용 하기 좋 은 Druid SQL Parse 를 해석 기로 사용 합 니 다.사실 sql 을 해석 하 는 것 은 텍스트 로 표시 하 는 것 입 니 다.
의 sql 의 미 는 일련의 조작 부호 로 표시 된다.
where 처리
예 를 들 어 where 뒤의 서술 어 는 트 리 구조 로 구 성 된 SQL 표현 식 으로 다음 그림 과 같다.

access 층 이 커서 를 통 해 일련의 row 를 제공 하면 이 트 리 표현 식 을 통 해 where 요구 에 부 합 된 데 이 터 를 걸 러 낼 수 있 습 니 다.Druid 는 Parse 에서 자주 사용 하 는 visitor 를 사용 하여 위의 표현 식 계산 작업 을 편리 하 게 처리 합 니 다.
join 처리
join 에 대한 가장 간단 한 처리 방안 은 두 장의 표 에 피리 칼 적 을 한 다음 에 위의 where condition 을 통 해 여과 하 는 것 이다.다음 그림 과 같다.

프 리 덤 의 피리 칼 적 축소 처리
Freedom 은 B+트 리 를 기본 저장 구조 로 사용 하기 때문에 where 서술 어 를 통 해 B+트 리 scan(검색)의 범 위 를 정할 수 있 습 니 다(즉,최대 검색 key 와 최소 검색 key 가 B+트 리 에 있 는 위 치 를 찾 을 수 있 습 니 다).고려 하 다

select a.*,b.* from t_archer as a join t_rider as b where a.id>=3 and a.id<=11 and b.id>=19 and b.id<=31

그러면 id 라 는 색인 에서 a 의 scan 범 위 는[3,11]로 정의 할 수 있 습 니 다.다음 그림 과 같 습 니 다.

b 의 scan 범 위 는[19,31]입 니 다.다음 그림 과 같 습 니 다(두 장의 표 데 이 터 를 가정 하면 그림 그리 기 에 편리 합 니 다).

scan 은 원래 의 15*15(총 15 개 요소)회 순환 에서 4*4 회 순환,즉 순환 횟수 가 7.1%로 감소 하 였 습 니 다.
물론 join condition 이 존재 한다 면 Freedom 은 바 텀 cursor 재 귀적 처리 과정 에서 일부 데 이 터 를 미리 걸 러 내 상층 의 필 터 를 더욱 줄인다.
B+Tree 의 디스크 구조
leaf 디스크 구조
Freedom 의 B+Tree 는 디스크 에 저 장 됩 니 다.메모리 의 제한 과 부정 확 한 키 값 을 고려 하면 매우 복잡 해진 다.Freedom 은 페이지 단위 로 디스크 와 상호작용 을 합 니 다.잎 노드 와 비 잎 노드 는 모두 page 에 의 해 적재 되 고 디스크 에 긁 힌 다.구 조 는 다음 과 같다.

하나의 원 그룹(tuple/item)은 한 페이지 에서 정 해진 ItemPointer 와 정 해 지지 않 은 Item 두 부분 으로 나 뉜 다.
이 가운데 아 이 템 Pointer 에는 아 이 템 의 시작 오프셋 과 길이 가 저장 되 어 있 습 니 다.이 동시에 ItemPointer 와 Item 은 그림 에서 보 듯 이 중심 방향 으로 신장 되 는데 이런 구 조 는 비정 장 Item 을 효과적으로 조직 했다.
leaf 와 node 노드 가 Page 에서 다 릅 니 다.
leaf 와 node 는 page 에서 조직 구조 가 일치 하지만 아 이 템 에 포 함 된 항목 은 확실히 차이 가 있 습 니 다.Freedom 은 색인 조직 표를 사용 하기 때문에 leaf 가 클 러 스 터 색인(clusterIndex)과 2 급 색인(secondary Index)에서 item 에 대한 표현 에 도 차이 가 있 습 니 다.다음 그림 과 같 습 니 다.

이 중 2 급 색인 검색 시 secondary Index 를 통 해 index-key 를 통 해 해당 하 는 clusterId 를 찾 은 다음 통과 합 니 다.
clusterId 는 clusterIndex 에서 대응 하 는 row 기록 을 찾 습 니 다.
디스크 를 놓 으 려 고 하기 때문에 Freedom 은 node 노드 의 item 에 index-key 에 대응 하 는 pageno 를 기록 하 였 습 니 다.
이렇게 하면 디스크 에서 모든 색인 구 조 를 쉽게 복원 할 수 있다.
B+Tree 파일 에 있 는 조직
Page 구조 가 있 으 면 우 리 는 데 이 터 를 하나의 page 크기 의 메모리 에 불 러 올 수 있 고 page 를 해당 하 는 파일 에 새로 고 칠 수 있 습 니 다.node.item 의 pageno 가 있 으 면 파일 과 메모리 구조 간 의 상호 매 핑 을 쉽게 할 수 있 습 니 다.
B+트 리 가 디스크 파일 에 있 는 조직 은 다음 그림 과 같 습 니 다.

B+트 리 가 메모리 에 대응 하 는 맵 구 조 는 다음 그림 과 같 습 니 다.

파일 페이지 와 메모리 페이지 의 내용 은 기본적으로 일치 합 니 다.일부 메모리 페이지 에 있 는 특유 의 필드,예 를 들 어 dirty 등 을 제외 합 니 다.
색인 마다 B+트 리
Freedom 에서 모든 색인 은 B+트 리 로 기록 의 삽입 과 수정 은 모든 B+트 리 를 조작 해 야 합 니 다.
B+Tree 의 테스트
필 자 는 일련의 테스트 케이스 를 통 해 예 를 들 어 무 작위 로 길 어 지 는 기록 을 통 해 B+트 리 를 삽입 하고 떨 어 뜨리 며 그 중에서 몇 개의 매우 기괴 한 corner case 를 복원 했다.
B+Tree 의 todo
필 자 는 여기 서 가장 간단 한 B+트 리 구 조 를 완 성 했 을 뿐 동시 수정 하 는 잠 금 체 제 를 추가 하지 않 았 고 B+트 리 를 조작 할 때 log 를 기록 하여 B+트 리 가 지연 등 재난 상황 에서 의 일치 성 을 확보 하지 않 았 기 때문에 이렇게 많은 작업량 을 완 성 했 더 라 도 높 은 동시 다발 로 사용 할 수 있 는 bptree 와 매우 큰 거리 가 있다.
Meta Data
table 의 메타 정 보 는 create table 에서 만 듭 니 다.만 든 후에 Freedom 이 재 부팅 할 때 표 정 보 를 불 러 올 수 있 도록 메타 정 보 를 떨 어 뜨 립 니 다.각 표 의 메타 정 보 는 한 페이지 의 공간 만 차지 하고 page 구 조 를 재 활용 하 며 주로 클 러 스 터 색인 과 2 급 색인 정 보 를 저장 합 니 다.메타 정보 에 대응 하 는 Item 은 다음 그림 과 같다.

my batis 가 Freedom 에 관 한 코드 를 자동 으로 생 성 할 수 있 도록 하려 면 특정한 sql 을 실현 하여 Freedom 의 메타 정 보 를 보 여 줘 야 합 니 다.이것 은 필자 의 또 다른 프로젝트 라이 더 에서 이러한 실현 이 있다.원 리 는 다음 그림 과 같다.

상기 4 가지 SQL 을 실현 한 후에 my batis-generator 는 jdbc 를 통 해 Freedom 에서 메타 정 보 를 얻 고 코드 를 자동 으로 생 성 할 수 있 습 니 다.
트 랜 잭 션 지원
현재 Freedom 은 합병 을 보장 하지 않 기 때문에 사무 에 대한 지원 은 가장 간단 한 WAL 프로 토 콜 만 했 습 니 다.redo/undolog 를 기록 함으로써 원자 성 을 실현 합 니 다.
redo/undo 로그 프로 토 콜 형식
Freedom 은 수정 작업 을 할 때마다 로 그 를 만 듭 니 다.그 중에서 수정 전(undo)과 수정 후(redo)의 줄 정 보 를 기록 하고 undo 는 스크롤 백 을 사용 하 며 redo 는 다운 복구 에 사 용 됩 니 다.구 조 는 다음 그림 과 같다.

WAL 프로 토 콜
WAL 프로 토 콜 은 트 랜 잭 션 commit 전에 현재 트 랜 잭 션 에서 발생 하 는 모든 로그 기록 을 디스크 에 저장 하 는 것 을 잘 이해 합 니 다.
Freedom 도 자 연 스 럽 게 이 조작 을 해서 다운 된 후에 log 를 통 해 모든 데 이 터 를 복원 할 수 있 습 니 다.

굴 러 가 는 실현
로그 에 undo 가 기록 되 어 있 기 때문에 하나의 트 랜 잭 션 의 스크롤 백 은 로 그 를 통 해 undo 를 진행 하면 됩 니 다.다음 그림 에서 보 듯 이:

다운 복구
Freedom 은 page 가 모두 디스크 를 닦 은 후에 꺼 지면 page 를 불 러 오 는 방식 으로 원래 의 데 이 터 를 얻 을 수 있 습 니 다.
그러나 갑자기 다운 되면 kill-9 이후 WAL 프로 토 콜 에 기 록 된 redo/undo log 를 통 해 다시 시작 할 수 있 습 니 다.
모든 데 이 터 를 복구 합 니 다.시간 과 정력 이 제한 되 어 있 기 때문에 필 자 는 LSN 을 바탕 으로 하 는 검사 점 체 제 를 실현 하지 못 했다.
자유 운행
git clone https://github.com/alchemystar/Freedom.git
//포장 배치 작업 을 하지 않 았 기 때문에 가장 쉬 운 방법 은 자바 편집기 에 있 습 니 다.
run alchemystar.freedom.engine.server.main
다음은 필자 가 프 리 덤 을 실제 운행 한 예 이다.

join 조회

삭제 스크롤 백

막바지
바퀴 를 만 드 는 과정 에서 처음에는 매우 열정 적 이 고 즐 거 웠 다.그러나 시스템 이 점점 커지 고 복잡성 이 높 아 지면 서 진도 가 점점 느 려 질 것 이다.그리고 가끔 은 자신의 원래 구상 을 뒤 집 고 재 설계 한 다음 에 관련 된 모든 코드 를 공동 수정 하 는 것 이 마치 늪 처럼 점점 깊 어 질 것 이다.이로써 필 자 는 소프트웨어 공학 의 가장 중요 한 사실은 복잡 도 를 통제 하 는 것 임 을 깨 달 았 다.시종 간결 한 인터페이스 와 우아 한 디자인 을 유지 하 는 것 은 대형 시스템 을 실현 하 는 필수 조건 이다.
github 링크:https://github.com/alchemystar/Freedom
이상 은 SQL 실행 엔진 의 상세 한 내용 을 어떻게 직접 작성 하 는 지 입 니 다.SQL 실행 엔진 을 직접 작성 하 는 것 에 관 한 자 료 는 다른 관련 글 을 주목 하 십시오!