πFS - 데이터를 하드 드라이브 대신 π에 저장한다는 파일 시스템

 (github.com/philipl)
2P by GN⁺ | ★ favorite | 댓글 1개
  • πfs는 데이터를 하드 드라이브에 저장하는 대신 π에 저장해 공간을 쓰지 않는다는 구상을 구현한 파일 시스템이며, π가 존재 가능한 모든 파일을 담는다는 전제를 핵심으로 함
  • π가 정규수(normal) 라는 추측이 참이면 16진수 표현 안에 모든 유한 파일이 존재한다는 설명에 기반함
  • 파일의 π 내 인덱스와 길이를 알면 Bailey–Borwein–Plouffe formula로 파일을 추출할 수 있으며, 이 구현은 성능을 위해 파일의 각 바이트를 개별적으로 π에서 조회함
  • 실행 시 πfs -o mdd=<metadata directory> <mountpoint> 형식을 사용하며, metadata directory에는 파일명과 π 안의 파일 위치 같은 메타데이터를 저장함
  • 빌드에는 autoconf, automake, libfuse 패키지가 필요하며, ./autogen.sh, ./configure, make, make install 흐름으로 빌드함
  • 현재 구현은 초기 프로토타입이며, 400줄 텍스트 파일 저장에 5분이 걸렸다는 예시가 있음
  • 향후 가능성으로 가변 실행 길이 검색·조회, Arithmetic Coding, 병렬 조회, 클라우드 기반 π 조회, Hadoop용 πfs가 나열됨

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 바벨의 도서관을 데이터 압축 도구로 써보려 했던 때가 떠오름
    그 덕분에 재미있는 rabbit hole에 빠졌고, 정보 이론을 처음 접하게 됐음
    결론은 데이터의 위치 주소를 표현하는 데도 데이터 자체와 거의 같은 양의 정보가 필요해서 압축에는 별로 효과가 없고, 재미있는 사고실험에 가깝다는 것
    요즘 기준으로 흥미로운 점은 LLM이 이런 도구들이 실패한 목표의 요지를 실제로 달성하는 손실 압축의 한 형태라는 점임. 물론 손실이 있고, 거대한 기반이 필요함

    • 이 영상이 흥미로울 듯함: Reinventing Entropy Compression is Intelligence Part 1, 3Blue1Brown
      https://youtu.be/l6DKRf-fAAM?is=ne73FCJ7ErXhzZ-v
    • 3Blue1Brown이 방금 지능과 압축의 연결을 다룬 영상을 올렸음
      https://youtu.be/l6DKRf-fAAM
    • 어떤 의미에서는 과학이 가장 극단적인 압축 형태임. 뉴턴 역학은 몇 줄의 글로 엄청나게 많은 현상을 설명함
    • 압축 수준을 생각해보면 꽤 인상적임. 예전에 쓴 댓글이 아직도 맞다고 보는데, 바이트가 아니라 비트여야 하므로 그 점에서는 틀렸음: https://news.ycombinator.com/item?id=39559969
      유효한 4-그램, 즉 네 단어 시퀀스를 저장하는 대략 계산은 100억 개 × 단어당 14비트 = 전체 100억 개에 약 17GB임. 그런데 이보다 100배 작은 LLM도 일관된 산문을 쓸 수 있음

  • nsafs, 즉 National Security Agency Filesystem이 떠오름. 정부가 비용을 내니까 “무료”라는 설정임: https://github.com/freedomtools/nsafs

    • 이건 절차만 더 붙인 쓰기 전용 메모리임
      https://en.wikipedia.org/wiki/Write-only_memory_(joke)
    • 예전에 어떤 회사 면접에서, 면접관이 벤처투자자로서 거대한 난수 스트림을 생성하는 프로젝트에 투자했다고 말했음
      임의의 인덱스를 고르고 그 개인 키를 상대와 공유하면, 이후 텍스트를 일회용 패드로 쓸 수 있다는 구상이었음. NSA가 해독하려면 GB/s로 생성되는 전체 스트림을 버퍼링하고 저장해야 한다는 논리였는데, 별로 실용적으로 보이지 않았음

  • 데이터 길이가 늘어날수록, π 안에서 해당 시퀀스의 인덱스와 길이가 원본 데이터보다 작을 가능성은 극도로 낮아진다는 점은 짚고 넘어갈 만함

    • 쉽게 해결 가능해 보임. π 안에서의 인덱스와 길이를 다시 π 안에서의 인덱스와 길이로 기록하면 됨
    • 대학 때 전화번호를 π 안의 인덱스로 알려주면 압축할 수 있겠다고 생각했는데, 7자리 전화번호가 8자리 인덱스에 있었음
      지역번호까지 포함한 10자리 번호를 찾을 계산 자원은 없었음
    • 20줄짜리 파일의 인덱스가 <20TB number>가 됨
    • 원문이 이 부분을 다룸

      Now, we all know that it can take a while to find a long sequence of digits in π, so for practical reasons, we should break the files up into smaller chunks that can be more readily found.
      In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π.

  • 관련 글들임. 더 있음?
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=36357466 - 2023년 6월, 댓글 107개
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=28699499 - 2021년 9월, 댓글 30개
    PiFS – The Data-Free Filesystem - https://news.ycombinator.com/item?id=26208704 - 2021년 2월, 댓글 1개
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=21359338 - 2019년 10월, 댓글 1개
    The π Filesystem for FUSE: Store Your Data in π - https://news.ycombinator.com/item?id=19223032 - 2019년 2월, 댓글 1개
    pifs - Avoid disk space usage by saving your files in the digits of Pi - https://news.ycombinator.com/item?id=18687275 - 2018년 12월, 댓글 1개
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=13869691 - 2017년 3월, 댓글 105개
    Πfs: Stores your data in π - https://news.ycombinator.com/item?id=10856108 - 2016년 1월, 댓글 1개
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=10847693 - 2016년 1월, 댓글 1개
    File system that stores location of file in Pi - https://news.ycombinator.com/item?id=8018818 - 2014년 7월, 댓글 98개
    100% Compression Using Pi - https://news.ycombinator.com/item?id=6698852 - 2013년 11월, 댓글 32개
    재게시물은 1년쯤 지나면 괜찮고, 과거 스레드 링크는 더 궁금한 독자를 위한 것임

    • 이런 목록은 어떻게 생성하는 건지 궁금함

  • 이것도 떠오름: https://www.spronck.net/sloot.html
    추가 읽을거리: https://en.wikipedia.org/wiki/Sloot_Digital_Coding_System

    • 예전에 조금 찾아봤는데, Sloot이 한 일은 적어도 약간은 새로웠음
      실제 인코딩 방식은 비디오의 각 줄을 데이터베이스에 저장하고, 각 프레임을 줄 조회들의 시퀀스로 인코딩한 뒤, 그 인코딩된 프레임을 또 다른 데이터베이스에 저장하는 구조였음. 각 비디오는 프레임 조회들의 시퀀스가 됨
      90년대 후반 하드웨어에서 16개 비디오를 동시에 부드럽게 재생했다는 시연이 가능했던 이유가 이것임. 각 프레임이 줄 조회들의 시퀀스라서 화면을 가로로 16개로 나눠 16개 영상을 동시에 재생해도 전체 화면에 단일 영상을 재생하는 것보다 더 부담이 크지 않음
      마찬가지로 각 프레임을 개별 디코딩하므로 빨리감기와 되감기도 부드러웠음. 전통적인 비디오 압축처럼 각 키프레임에서 차이를 계산할 필요가 없어서 2배속 재생도 1배속보다 더 힘들지 않았음
      물론 비디오 파일을 8KB 같은 크기로 저장할 수는 없었겠지만, 예를 들어 TV 시리즈 한 시즌이 데이터베이스에 있다면 오프닝과 엔딩 크레딧은 한 번만 저장하면 됐음

    • The SDCS is only possible if keys are allowed to become infinite, or the data store is allowed to become infinite (...) This would, of course, make the idea useless.
      하지만 π는 무한함. 그러니 Moore의 법칙이 계속 우리 편인 한 이 천재적인 장치는 작동할 것임

  • One of the properties that π is conjectured to have is that it is normal
    여기서 핵심은 conjectured임
    내가 자주 집착하는 사소한 엄밀성 문제가 나와서 반가움. 구성되지 않은 무리수가 정규수이거나 모든 유한 문자열을 포함한다는 것은 아직 어떤 것도 증명되지 않았음

    • 여기서 “구성되지 않은”이 무슨 뜻인지 궁금함

  • In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π.
    각 비트를 따로 보면 더 성능이 좋을 것임. 인덱스 2와 33만 있으면 되고, 이를 저장소의 비트로 효율적으로 매핑할 수 있음

  • π가 과거와 미래의 모든 지식, 심지어 내가 언제 죽는지도 포함한다는 걸 깨닫는 건 불편함

    • 다른 모든 무작위 무한 비트열도 마찬가지임. 직관에 어긋나는 부분은 π가 아니라 무한에서 나옴
      또한 과거와 미래의 모든 지식을 담고 있다고도 할 수 없음. 과거와 미래에 대한 가능한 모든 거짓도 진실과 구별할 수 없는 방식으로 함께 들어 있기 때문임
      정보를 의사난수 시퀀스의 오프셋으로 인코딩하는 건 정보를 직접 저장하는 것보다 저장 효율이 좋지 않음
    • 최악은 Chris Pratt가 Han Solo로 캐스팅된 대체 시간선의 Star Wars 4~6도 들어 있다는 점임
      재미있는 사실: “Chrispratt”는 고대 캘리포니아어로 “Joel McHale이 그 역할을 원하지 않았다”는 뜻임
    • Jorge Borges의 The Library of Babel을 재미있게 읽을 듯함
      https://dn760100.eu.archive.org/0/items/TheLibraryOfBabel/ba...
    • π를 앞질러 읽기 시작한 사람은 언제나 가장 신선한 숫자를 얻게 됨. 완벽한 암호임
    • 과거와 미래의 모든 가짜 뉴스도 들어 있고, 어느 쪽이 진짜인지 알 수 없음

  • 예전에 어떤 압축 벤치마크 참가작이 파일 이름을 압축 해제 알고리즘의 입력 일부로 취급해서 벤치마크를 교묘히 통과했던 기억이 어렴풋이 남
    벤치마크는 파일 크기만 측정했기 때문에 그 지표를 이길 수 있었음

  • 이건 π에 대해 아직 증명되지 않은 성질에 의존하는 것 아닌가? 모든 유한 문자열 포함성이나 정규성이 필요하지만, 둘 다 증명되지 않았음

답변달기