고속 페일세이프 압축(계속)

이 기사는 이미 고속 데이터 압축 주제의 두 번째 기사입니다. 첫 번째 기사에서는 10GB/초의 속도로 작동하는 압축기에 대해 설명했습니다. 프로세서 코어당(최소 압축, RTT-Min).

이 압축기는 저장 매체 덤프의 고속 압축 및 암호화 강도 강화를 위해 포렌식 복사기 장비에 이미 구현되어 있으며, 가상 머신의 이미지와 RAM 스왑 파일을 고속으로 저장할 때 압축하는 데에도 사용할 수 있습니다. SSD 드라이브.

첫 번째 기사에서는 또한 크게 향상된 데이터 압축 매개변수를 사용하여 HDD 및 SSD 디스크 드라이브(중간 압축, RTT-Mid)의 백업 복사본을 압축하기 위한 압축 알고리즘의 개발을 발표했습니다. 이제 이 압축기는 완전히 준비되었으며 이 기사는 이에 관한 것입니다.

RTT-Mid 알고리즘을 구현하는 압축기는 고속 모드에서 작동하는 WinRar, 7-Zip과 같은 표준 아카이버에 필적하는 압축 비율을 제공합니다. 동시에 작동 속도는 최소한 한 단계 더 높습니다.

데이터 패킹/언패킹 속도는 압축 기술의 적용 범위를 결정하는 중요한 매개변수입니다. 10테라바이트의 데이터를 초당 15-XNUMX메가바이트의 속도(정확히 표준 압축 모드의 아카이버 속도)로 압축하는 것을 생각하는 사람은 거의 없을 것입니다. 전체 프로세서 로드 시 거의 XNUMX시간이 걸리기 때문입니다. .

반면, 동일한 테라바이트를 초당 2~3기가바이트 정도의 속도로 약 XNUMX분 만에 복사할 수 있습니다.

따라서 대용량 정보의 압축은 실제 입출력 속도 이상의 속도로 수행하는 것이 중요하다. 최신 시스템의 경우 이는 초당 최소 100MB입니다.

최신 압축기는 "빠른" 모드에서만 이러한 속도를 생성할 수 있습니다. RTT-Mid 알고리즘을 기존 압축기와 비교하는 것은 바로 이 현재 모드입니다.

새로운 압축 알고리즘의 비교 테스트

RTT-Mid 압축기는 테스트 프로그램의 일부로 작동했습니다. 실제 "작동하는" 응용 프로그램에서는 훨씬 빠르게 작동하고 멀티스레딩을 현명하게 사용하며 C#이 아닌 "일반" 컴파일러를 사용합니다.

비교 테스트에 사용된 압축기는 원리가 다르고, 데이터 종류에 따라 압축하는 방식이 다르기 때문에 테스트의 객관성을 위해 '병원 내 평균 온도'를 측정하는 방식을 사용했다...

Windows 10 운영 체제를 사용하는 논리 디스크의 섹터별 덤프 파일이 생성되었으며, 이는 실제로 모든 컴퓨터에서 사용할 수 있는 다양한 데이터 구조의 가장 자연스러운 혼합입니다. 이 파일을 압축하면 새로운 알고리즘의 압축 속도와 정도를 최신 아카이버에 사용되는 가장 진보된 압축기와 비교할 수 있습니다.

덤프 파일은 다음과 같습니다.

덤프 파일은 PTT-Mid, 7-zip 및 WinRar 압축기를 사용하여 압축되었습니다. WinRar 및 7-zip 압축기는 최대 속도로 설정되었습니다.

압축기 작동 중 7 지퍼:

프로세서를 100% 로드하는 반면 원본 덤프를 읽는 평균 속도는 약 60MB/초입니다.

압축기 작동 중 WinRAR과:

상황은 유사하며 프로세서 로드는 거의 100%이고 평균 덤프 읽기 속도는 약 125MB/초입니다.

이전 사례와 마찬가지로 아카이버의 속도는 프로세서의 기능에 따라 제한됩니다.

현재 압축기 테스트 프로그램이 실행 중입니다. RTT-중간:

스크린샷은 압축된 데이터를 업로드할 곳이 없기 때문에 프로세서가 50%로 로드되고 나머지 시간 동안 유휴 상태임을 보여줍니다. 데이터 업로드 디스크(디스크 0)가 거의 완전히 로드되었습니다. 데이터 읽기 속도(디스크 1)는 크게 다르지만 평균적으로 200MB/초를 초과합니다.

이 경우 압축 데이터를 디스크 0에 쓰는 기능으로 인해 압축기 속도가 제한됩니다.

이제 결과 아카이브의 압축 비율은 다음과 같습니다.

RTT-Mid 압축기가 최고의 압축 작업을 수행했음을 알 수 있습니다. RTT-Mid 압축기가 생성한 아카이브는 WinRar 아카이브보다 1,3기가바이트 작고 2,1z 아카이브보다 7기가바이트 작습니다.

아카이브 생성에 소요된 시간:

• 7-zip – 26분 10초;
• WinRar – 17분 40초;
• RTT-중간 – 7분 30초.

따라서 RTT-Mid 알고리즘을 사용하는 최적화되지 않은 테스트 프로그램에서도 XNUMX배 이상 빠르게 아카이브를 생성할 수 있었지만 아카이브는 경쟁사보다 훨씬 작은 것으로 나타났습니다...

스크린샷을 믿지 못하시는 분들은 직접 확인해보세요. 테스트 프로그램은 다음에서 이용 가능합니다. 링크, 다운로드하여 확인하세요.

그러나 AVX-2를 지원하는 프로세서에서만 이러한 명령을 지원하지 않으면 압축기가 작동하지 않으며 이전 AMD 프로세서에서 알고리즘을 테스트하지 않으며 AVX 명령 실행 측면에서 속도가 느립니다...

사용된 압축 방법

알고리즘은 반복되는 텍스트 조각을 바이트 단위로 인덱싱하는 방법을 사용합니다. 이 압축 방식은 오래전부터 알려졌으나 매칭 작업에 필요한 리소스 측면에서 매우 비싸고 사전을 구축하는 것보다 훨씬 더 많은 시간이 필요하기 때문에 사용되지 않았습니다. 따라서 RTT-Mid 알고리즘은 "미래로 돌아가는" 전형적인 예입니다...

PTT 압축기는 고유한 고속 일치 검색 스캐너를 사용하여 압축 프로세스 속도를 높일 수 있습니다. 자체제작 스캐너, 이게 "나의 매력...", "완전히 손수 만든거라 꽤 비싸다"(어셈블러로 작성).

일치 검색 스캐너는 XNUMX단계 확률 체계에 따라 만들어집니다. 먼저 일치 항목의 "부호" 존재 여부를 스캔하고, 이 위치에서 "부호"가 식별된 후에만 실제 일치 항목을 검색하는 절차를 수행합니다. 시작됩니다.

일치 검색 창은 처리된 데이터 블록의 엔트로피 정도에 따라 예측할 수 없는 크기를 갖습니다. 완전히 무작위인(압축할 수 없는) 데이터의 경우 크기는 메가바이트이고, 반복되는 데이터의 경우 항상 메가바이트보다 큽니다.

그러나 많은 최신 데이터 형식은 압축할 수 없으며 이를 통해 리소스 집약적인 스캐너를 실행하는 것은 쓸모없고 낭비이므로 스캐너는 두 가지 작동 모드를 사용합니다. 먼저, 원본 텍스트에서 반복 가능성이 있는 섹션을 검색합니다. 이 작업도 확률적 방법을 사용하여 매우 빠르게(4-6GB/초의 속도) 수행됩니다. 그러면 일치 가능성이 있는 영역이 기본 스캐너에 의해 처리됩니다.

인덱스 압축은 그다지 효율적이지 않으며 중복된 조각을 인덱스로 교체해야 하며 인덱스 배열은 압축 비율을 크게 줄입니다.

압축 비율을 높이기 위해 바이트 문자열의 전체 일치 항목뿐만 아니라 문자열에 일치하는 바이트와 일치하지 않는 바이트가 포함된 경우 부분 항목도 색인화됩니다. 이를 위해 인덱스 형식에는 두 블록의 일치하는 바이트를 나타내는 일치 마스크 필드가 포함됩니다. 더 큰 압축을 위해 인덱싱을 사용하여 부분적으로 일치하는 여러 블록을 현재 블록에 겹쳐 놓습니다.

이 모든 것을 통해 PTT-Mid 압축기에서는 사전 방법을 사용하여 만든 압축기와 비교할 수 있는 압축 비율을 얻을 수 있지만 훨씬 더 빠르게 작동할 수 있습니다.

새로운 압축 알고리즘의 속도

압축기가 캐시 메모리(스레드당 4MB 필요)를 독점적으로 사용하여 작동하는 경우 작동 속도 범위는 700-2000MB/초입니다. 프로세서 코어당 압축되는 데이터 유형에 따라 다르며 프로세서의 작동 주파수에 거의 의존하지 않습니다.

압축기의 멀티스레드 구현을 통해 효과적인 확장성은 세 번째 수준 캐시의 크기에 따라 결정됩니다. 예를 들어, 9MB의 캐시 메모리가 "온보드"에 있으면 두 개 이상의 압축 스레드를 실행해도 아무런 의미가 없으며 이로 인해 속도가 증가하지 않습니다. 그러나 20MB의 캐시를 사용하면 이미 XNUMX개의 압축 스레드를 실행할 수 있습니다.

또한 RAM의 지연 시간은 압축기의 속도를 결정하는 중요한 매개변수가 됩니다. 알고리즘은 OP에 대한 무작위 액세스를 사용하는데, 그 중 일부는 캐시 메모리에 들어가지 않고(약 10%) OP에서 데이터를 기다리면서 유휴 상태를 유지해야 하므로 작업 속도가 느려집니다.

압축기의 속도와 데이터 입출력 시스템의 작동에 큰 영향을 미칩니다. I/O 블록에서 OP에 대한 요청은 CPU의 데이터에 대한 요청으로 인해 압축 속도도 감소됩니다. 이 문제는 랩탑과 데스크탑의 경우 중요하지만, 서버의 경우에는 고급 시스템 버스 액세스 제어 장치와 다중 채널 RAM으로 인해 덜 중요합니다.

기사의 텍스트 전체에서 우리는 압축에 대해 이야기하지만 압축 해제는 "모든 것이 초콜릿으로 덮여 있기 때문에" 이 기사의 범위를 벗어납니다. 압축 해제는 훨씬 빠르며 I/O 속도에 의해 제한됩니다. 하나의 스레드에 있는 하나의 물리적 코어는 3~4GB/초의 압축 풀기 속도를 쉽게 제공합니다.

이는 압축 중에 프로세서 및 캐시 메모리의 주요 리소스를 "먹는" 압축 해제 프로세스 중에 일치 검색 작업이 없기 때문입니다.

압축된 데이터 저장의 신뢰성

데이터 압축(아카이버)을 사용하는 전체 소프트웨어 클래스의 이름에서 알 수 있듯이 수년이 아닌 수세기, 수천년 동안 정보를 장기간 저장하도록 설계되었습니다.

저장 중에 저장 매체에서 일부 데이터가 손실됩니다. 예는 다음과 같습니다.

이 "아날로그" 정보 매체는 천년이 되었으며 일부 조각이 손실되었지만 일반적으로 정보를 "읽을 수" 있습니다...

최신 디지털 데이터 저장 시스템 및 디지털 미디어의 책임 제조업체 중 어느 누구도 75년 이상 동안 완전한 데이터 안전을 보장하지 않습니다.
그리고 이게 문제인데 미뤄둔 문제라면 우리 후손들이 해결해 주겠지...

디지털 데이터 저장 시스템은 75년이 지나면 데이터가 손실될 수 있을 뿐만 아니라 데이터 오류가 기록 중에도 언제든지 나타날 수 있으므로 중복성을 사용하고 오류 수정 시스템으로 이를 수정하여 이러한 왜곡을 최소화하려고 노력합니다. 중복 및 수정 시스템은 손실된 정보를 항상 복원할 수는 없으며 복원 작업이 올바르게 완료되었다는 보장도 없습니다.

그리고 이것은 또한 큰 문제이지만 연기된 문제는 아니지만 현재의 문제입니다.

디지털 데이터를 보관하는 데 사용되는 최신 압축기는 사전 방법을 다양하게 수정하여 구축되었으며 이러한 아카이브의 경우 정보 손실은 치명적인 사건이 될 것입니다. 이러한 상황에 대해 "깨진" 아카이브라는 용어도 확립되어 있습니다. ...

사전 압축을 사용하여 아카이브에 정보를 저장할 때 신뢰성이 낮은 것은 압축된 데이터의 구조와 관련이 있습니다. 이러한 아카이브의 정보에는 원본 텍스트가 포함되어 있지 않으며 사전의 항목 수가 여기에 저장되며 사전 자체는 현재 압축된 텍스트에 의해 동적으로 수정됩니다. 아카이브 조각이 손실되거나 손상된 경우 사전 항목 번호가 무엇에 해당하는지 명확하지 않기 때문에 모든 후속 아카이브 항목을 내용이나 사전 항목 길이로 식별할 수 없습니다.

이러한 "깨진" 아카이브에서 정보를 복원하는 것은 불가능합니다.

RTT 알고리즘은 압축된 데이터를 저장하는 보다 안정적인 방법을 기반으로 합니다. 반복되는 조각을 설명하는 인덱스 방법을 사용합니다. 이러한 압축 접근 방식을 사용하면 저장 매체에 대한 정보 왜곡의 결과를 최소화할 수 있으며 대부분의 경우 정보 저장 중에 발생한 왜곡을 자동으로 수정할 수 있습니다.
이는 인덱스 압축의 경우 아카이브 파일에 두 개의 필드가 포함되어 있기 때문입니다.

• 반복 섹션이 제거된 소스 텍스트 필드
• 인덱스 필드.

정보복구에 꼭 필요한 인덱스 필드는 크기가 크지 않으며, 복제가 가능하여 안정적인 데이터 보관이 가능합니다. 따라서 원본 텍스트 또는 인덱스 배열의 일부가 손실되더라도 "아날로그" 저장 매체를 사용한 그림과 같이 다른 모든 정보는 문제 없이 복원됩니다.

알고리즘의 단점

단점이 없으면 장점도 없습니다. 인덱스 압축 방법은 짧은 반복 시퀀스를 압축하지 않습니다. 이는 인덱스 방식의 한계 때문입니다. 인덱스 크기는 최소 3바이트이며 최대 12바이트까지 가능합니다. 이를 설명하는 인덱스보다 작은 크기의 반복이 발생하면 압축 파일에서 이러한 반복이 얼마나 자주 감지되는지에 관계없이 고려되지 않습니다.

기존의 사전 압축 방법은 짧은 길이의 여러 반복을 효과적으로 압축하므로 인덱스 압축보다 높은 압축률을 달성합니다. 사실, 이는 중앙 프로세서의 높은 부하로 인해 달성됩니다. 사전 방법이 인덱스 방법보다 더 효율적으로 데이터를 압축하기 시작하려면 실제 데이터 처리 속도를 초당 10-20MB로 줄여야 합니다. 전체 CPU 로드를 갖춘 컴퓨팅 설치.

이러한 낮은 속도는 최신 데이터 저장 시스템에서는 허용되지 않으며 실용적이기보다는 "학문적" 관심이 더 큽니다.

이미 개발 중인 RTT 알고리즘(RTT-Max)의 다음 수정에서는 정보 압축 정도가 크게 높아질 예정입니다.

그럼 언제나처럼 계속해서...

출처 : habr.com