중복을 없애서 저장시키는 공간을 절약시키는 기술이다.
공간을 줄일 수 있는 대표적인 기술에는 압축이 있다.
한 번 압축한 파일을 다시 압축하면 다시 작아지지 않는다.
압축의 원리가 어떻게 될까? 반복되는 패턴을 찾아서 작은 스트링으로 대체시키는 것이다.
12345가 백만번 반복되는 파일은
12345 * 백만으로 저장한 후 사용할때 풀어서 쓰면 될 것이다.
암호화가 된다는 것은 반복적인것이 없다는 것이다 암호화된 스트링에 반복적인 것이 있다는 얘기는 그 반복적인 패턴이 추측이 가능하다는 것이고, 해석이 가능하다는 뜻이다.
따라서 암호화된 스트링은 반복적인 것이 없다.
각 블록을 해시함수를 돌려서 비교하면 같은 블록을 찾을 수 있다.
각 블록에 대한 유니크 블록만 저장하고 위치는 해시테이블을 만들어서 인덱스 값만 기억한다.
만약 file2 앞에 한바이트만 넣어서 다른 비트들이 한 바이트씩 shift된다면 블록이 달라지는 문제가 있다.
fixed block,static chunking 을 하게 되면 맨 앞의 한 바이트가 들어오면 망한다.
이런 상황처럼 앞에 1비트만 추가되어도 deduplication을 하기 힘들어진다.
이런 상황을 해결하기 위해 나온 것이
variable block , dinamic chunking이다.
일괄적으로 같은 길이만큼 청킹하는 것이 아니라,
특정 조건을 만족하면 거기서 청킹하는 것이다.
예를 들어 알파벳 g가오면 청킹하는 것이다.
이 방법을 사용하면 첫 청크를 제외한 부분은 청킹이 가능해진다.
하지만 g가 계속 나오면 너무 짧고 많은 청크가, g가 나오지 않으면 청크가 전체 하나만 생길 것이다.
따라서 특정 캐릭터를 기준으로 하는게 아닌 다른 알고리즘이 필요하다.
Sliding Window based Rolling Hash
사진에서는 윈도우 사이즈를 8로 잡았는데 8비트를 한 스트링으로 간주하겠다는 것이다.
그렇게 정한 8비트를 해시해서 특정 조건을 만족하면 청킹한다.
예를 들어 모듈러 100을해서 0이 나오면 청킹한다고 헀을때, 1/100의 확률로 청킹될 것이다.
만약 청킹되지 않았다면 이 8비트 윈도우를 한바이트 shift 시키고 반복한다.
보안 분야에서
원본 패킷으로 피켓으로 뽑아서 저장해놓는다.
