분산DB와 블룸필터

• 분산 데이터베이스와 분산 원장에 대해 이해할 수 있다.
  
  • 클러스터링, 레플리케이션, 샤딩
• 머클트리의 동작 방식을 설명하세요.
  • 블록체인에서 머클트리가 어떻게 동작하는지 이해할 수 있다.
• 블룸필터의 동작 방식과 특징에 대해 설명하세요.
• DAG에 대해 설명할 수 있다.
  • 그래프의 종류와 특징을 이해할 수 있다.
  • 암호화폐에서 DAG가 어떻게 적용되는지 이해할 수 있다.
• DHT에 대해 설명할 수 있다.
  • 해시 테이블의 구조와 특징을 이해할 수 있다.
  • DHT에서 정보를 저장하고 조회하는 방식을 이해할 수 있다.

---

블록체인

네트워크를 통해 관리되는 분산DB의 한 종류

분산 데이터베이스

하나의 DB관리 시스템으로 여러 cpu에 저장장치들을 제어하는 형태의 db

물리적으로 여러위치에 분산 저장하고 흩어져 있는 시스템이지만, 논리적으로는 하나인것처럼 활용한다.

db접근 유저 입장에서는 하나의 db에 접근하는것과 같다

---

분산db의 대표기술

1.클러스터링

2.레플리케이션

3.샤딩

클러스터링(Clustering)

왜나옴? 서버가 죽으면..? -> 서버를 여러개로 만들자!

Active-Active : 항상 가동

Active-StandBy : 일부는 가동, 일부는 대기상태

서버이슈가 생겨도 지속적인 서비스 제공 가능, 서버가 여러대 -> 성능적 유리

db는 하나라 병목생김, 서버 여러대 -> 비용문제

레플리케이션(Replication)

왜나옴? 저장된 데이터가 손실되면 어떻게 하지? -> db를 여러개로 하자

부하 분산 방식

DB SELECT성능을 높일 수 있다

비동기 방식으로 운영되어 지연시간이 거의 없다

각 노드간 데이터 동기화 보장이 어렵다

MAIN 노드가 다운되면 복구 및 대처가 어렵다

분산 부하 방식

샤딩(Sharding)

왜나옴? 데이터가 너무 많아서 select 성능 느려.. 테이블 나누어서 저장해서 속도를 높여보자!

테이블을 로우단위로 나누어서 각각의 샤드로 저장한다.

서버의 수평확장 가능

스캔범위를 줄여 쿼리반응속도가 빨라진다

데이터를 적절히 분배 못하면 오히려 전보다 비효율적일수 있다

분할되면 이전으로 합치기 어렵다

데이터를 잘 분산시키는것이 중요한데, 이를 위해 샤드키를 통해 나눠진 샤드중 어떤 샤드를 결정할지에 대해 정한다.

1.해시 샤딩 (ex : id %3)

샤드의 수만큼 해싱하면 되기에 구현 간단

샤드가 늘어나면 해시함수가 달라져야해서 확장성 떨어짐

단순해시함수라 샤드별 공간에 대한 효율을 고려하지 않음

2.다이나믹 샤딩

locator service라는 테이블 구성요소를 통해 샤드키 구성

샤드가 하나더 추가되면 locator service에 샤드키 추가하는 방식으로 확장성 유연

데이터 재배치시 locator service 동기화 필요

locator service에 의존적이라 테이블에 문제 생기면 db에 문제 전이

1. 엔티티 그룹 샤딩

관계되어 있는 엔티티끼리 같은 샤드 내 공유

단일 샤드내에서 쿼리 효율적, 강한 응집도

다른 샤드의 엔티티와 연관이 되어있는 쿼리의 경유 실행 효율이 떨어짐

분산DB 장단점

투명한 분산 - 하나의 db를 사용하는 것처럼 crud 작업을 수행해야 한다.

투명한 트랜잭션 - 각 트랜잭션은 다중 db에 걸쳐 일관성 보장, 트랜잭션은 일반적으로 여러 하위트랜잭션으로 분리된 개별 서브 트랜잭션이 하나의 db에 대응한다.

분산 데이터베이스와 블록체인의 차이점

1. [합의 알고리즘] 악의적인 사용자를 전제하고 만들어진 시스템
2. [거버넌스] 운영주체가 사라져도 시스템 유지 가능

---

블룸필터

특정 원소가 집합에 속하는지 검사하는데 사용되는 확률형 자료구조

어떤 원소가 집합에 속한다고 판단되는 경우,실제로원소가 속하지 않는 긍정오류가 발생하는것이 가능하지만, 반대로 원소가 집합에 속하지 않는것으로 판단되었는데 실제로 원소가 속하는 부정오류는 절대 발생하지 않는다.

검색패턴을 구현하기 위한 효율적인 방법 제공

SPV 노드가 블룸필터를 사용해 이웃 노드들에게 특정거래 제공 요청 -> 이때 노드는 검색중인 노드가 어떤 주소인지 밝힐 필요가 없다.

길이n의 이진배열과 1부터N까지 출력값을 갖는 J개의 해시함수가 있다. N,J를 조절 -> 프라이버시 보호수준 조절

False Negative (거짓 - 부정, 존재하지만 부정하는 것) 는 존재하지 않는다고 보장할 수 있습니다.

하지만 False Positive (거짓-긍정, 존재하지 않지만 있다고 하는 것) 가 존재할 수 있습니다.

즉 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면, 이 원소는 확실하게 없다고 할 수 있습니다.

삽입만 가능하고 제거가 안됨.

처리능력 대비 적은 메모리 공간을 필요로하는 장점 떄문에 많은곳에서 사용

[작동 원리]

블룸 필터의 작동 원리는 매우 간단합니다. 일반적으로 블룸 필터는 비트 배열로 구성됩니다. 이 비트 배열의 모든 값은 0으로 초기화됩니다. 각각의 입력 데이터에 대해 k개의 해시 함수를 사용하여 k개의 위치를 계산합니다. 이 k개의 위치에 대해 비트 배열의 값을 1로 설정합니다.다음으로, 해당 데이터가 필터에 있는지 여부를 확인하려면, 같은 k개의 해시 함수를 사용하여 k개의 위치를 계산합니다. 이 k개의 위치에 대해 비트 배열의 값이 모두 1인지 확인합니다. 만약 모두 1이면 해당 데이터가 필터에 존재할 가능성이 있습니다. 하지만, 모두 1이 아니면 해당 데이터는 필터에 없을 확률이 100%입니다.블룸 필터는 오류율이 존재한다는 것을 유념해야 합니다. 필터 크기와 해시 함수 개수에 따라 오류율이 달라집니다. 즉, 필터에 없는 데이터가 있을 수도 있습니다. 따라서, 블룸 필터는 정확성이 중요한 경우에는 사용되지 않습니다.

---

DAG (Directed Acyclic Graph)

방향성 비순환 그래프, 그래프 형태의 데이터 구조

그래프 : 여러개의 점이 서로 복잡하게 연결된 관계

진입차수(in-degree) / 진출차수(out-degree)

인접

자기루프

DAG는 한 정점에서 시작해 다시 해당 정점으로 돌아오지 않는 일방향성이라는 특징을 갖는다.

블록 개념이 존재하지 않고, 각 정점은 블록이 아닌 개별 트랜잭션이다.

블록이 없기 때문에 채굴이 필요하지 않다. 대신 트랜잭션들은 서로를 참조함으로써 해당 트랜잭션의 유효성을검증한다.

트랜잭션이 선형적으로 처리되는 것이 아닌, 병렬적으로 처리되기 때문에 블록체인에 비해 속도가 빠르다

채굴과정이 없기에 채굴자에게 낼 수수료도 없다.

DAG는 트랜잭션이 늘어날수록 새로운 트랜잭션들이 이전 트랜잭션을 많이 검증할 수 있기 때문에 확장성에서 자유롭다

DAG를 사용하는 암호화폐 플랫폼에는 대표적으로 IOTA와 ByteBal이 있음

해시 테이블(Hash Table)

키를 입력값으로 해시함수를 사용하여 변환한 해시값을 색인으로 삼아 키와 데이터를 저장하는 자료구조

저장,검색,삭제 -> O(1)

해시충돌 발생할 수 있고, 저장되기 전에 저장공간을 미리 만들어놔야 해서 공간효율성 떨어짐.

해시함수의 의존도가 높아짐

해싱 충돌이 발생할 경우 저장소의 모든 색인(index)(삽입) 혹은 데이터(value)(삭제, 검색)를 찾아봐야 하므로 O(n)이 된다.

---

DHT(Distirbuted Hash Table)

DHT(분산 해시테이블)는 해시 테이블을 활용해, 키-값 쌍 방식으로 데이터를 검색하는 분산형 데이터베이스

Peer-to-Peer 환경에서 데이터를 분산하여 저장할 때 사용