πFS - Hệ thống tệp lưu dữ liệu trong π thay vì trên ổ cứng

 (github.com/philipl)
2 điểm bởi GN⁺ 3 giờ trước | 1 bình luận | Chia sẻ qua WhatsApp
  • πfs là một hệ thống tệp hiện thực hóa ý tưởng lưu dữ liệu trong π thay vì lưu trên ổ cứng, nhờ đó không chiếm dung lượng; cốt lõi của nó là giả định rằng π chứa mọi tệp có thể tồn tại
  • Cách giải thích này dựa trên suy đoán rằng nếu π là một số chuẩn (normal), thì trong biểu diễn hệ thập lục phân của nó sẽ tồn tại mọi tệp hữu hạn
  • Nếu biết chỉ mục và độ dài của tệp trong π, có thể trích xuất tệp bằng Bailey–Borwein–Plouffe formula; để tối ưu hiệu năng, bản hiện thực này tra cứu từng byte của tệp riêng lẻ trong π
  • Khi chạy, dùng định dạng πfs -o mdd=<metadata directory> <mountpoint>; metadata directory dùng để lưu siêu dữ liệu như tên tệp và vị trí của tệp trong π
  • Để build cần các gói autoconf, automake, libfuse, và quy trình build là ./autogen.sh, ./configure, make, make install
  • Bản hiện thực hiện tại là nguyên mẫu giai đoạn đầu, và có ví dụ cho thấy việc lưu một tệp văn bản 400 dòng mất 5 phút
  • Các khả năng trong tương lai được liệt kê gồm tìm kiếm/tra cứu độ dài chạy biến thiên, Arithmetic Coding, tra cứu song song, tra cứu π trên nền tảng đám mây, và πfs cho Hadoop

Bài viết liên quan

1 bình luận

 
GN⁺ 3 giờ trước
Ý kiến trên Hacker News

  • Làm nhớ tới thời tôi từng định dùng Thư viện Babel như một công cụ nén dữ liệu
    Nhờ vậy mà tôi sa vào một rabbit hole khá thú vị, và cũng là lần đầu tiếp xúc với lý thuyết thông tin
    Kết luận là để biểu diễn địa chỉ vị trí của dữ liệu cũng cần lượng thông tin gần như tương đương với chính dữ liệu đó, nên hầu như không hiệu quả cho việc nén mà gần hơn với một thí nghiệm tư duy thú vị
    Điều đáng chú ý theo tiêu chuẩn hiện nay là LLM, theo một nghĩa nào đó, thực sự đạt được cốt lõi của mục tiêu mà các công cụ kiểu này đã thất bại, dưới dạng nén mất dữ liệu. Tất nhiên là có tổn thất, và cần một nền tảng khổng lồ

    • Video này có vẻ đáng xem: Reinventing Entropy Compression is Intelligence Part 1, 3Blue1Brown
      https://youtu.be/l6DKRf-fAAM?is=ne73FCJ7ErXhzZ-v
    • 3Blue1Brown vừa đăng một video nói về mối liên hệ giữa trí tuệ và nén
      https://youtu.be/l6DKRf-fAAM
    • Theo một nghĩa nào đó, khoa học là hình thức nén cực đoan nhất. Cơ học Newton giải thích một lượng hiện tượng khổng lồ chỉ bằng vài dòng mô tả
    • Nghĩ về mức độ nén thì khá ấn tượng. Tôi vẫn thấy bình luận mình viết trước đây vẫn đúng, dù tôi đã sai ở chỗ phải là bit chứ không phải byte: https://news.ycombinator.com/item?id=39559969
      Một phép tính gần đúng cho việc lưu các 4-gram hợp lệ, tức chuỗi bốn từ, là 10 tỷ × 14 bit mỗi từ = khoảng 17GB cho toàn bộ 10 tỷ chuỗi. Thế mà những LLM nhỏ hơn 100 lần so với mức này vẫn có thể viết văn xuôi mạch lạc

  • Làm nhớ tới nsafs, tức National Security Agency Filesystem. Vì chính phủ trả tiền nên được xem là “miễn phí”: https://github.com/freedomtools/nsafs

    • Đây là bộ nhớ chỉ ghi có thêm vài thủ tục đi kèm
      https://en.wikipedia.org/wiki/Write-only_memory_(joke)
    • Trước đây trong một buổi phỏng vấn ở một công ty, người phỏng vấn nói rằng với vai trò nhà đầu tư mạo hiểm, ông ấy đã đầu tư vào một dự án tạo ra luồng số ngẫu nhiên khổng lồ
      Ý tưởng là chọn một chỉ mục bất kỳ rồi chia sẻ khóa riêng tương ứng với đối phương, sau đó có thể dùng văn bản làm one-time pad. Lập luận là nếu NSA muốn giải mã thì họ sẽ phải đệm và lưu toàn bộ luồng được tạo ra ở tốc độ GB/s, nhưng điều đó không có vẻ thực tế lắm

  • Cũng đáng lưu ý rằng khi độ dài dữ liệu tăng lên, khả năng chỉ mục và độ dài của chuỗi đó trong π nhỏ hơn dữ liệu gốc sẽ cực kỳ thấp

    • Có vẻ giải quyết dễ thôi. Chỉ cần ghi lại chỉ mục và độ dài trong π bằng chính chỉ mục và độ dài trong π nữa là được
    • Hồi đại học tôi từng nghĩ có thể nén số điện thoại bằng cách biểu diễn nó bằng chỉ mục trong π, nhưng số điện thoại 7 chữ số lại nằm ở một chỉ mục 8 chữ số
      Tôi không có đủ tài nguyên tính toán để tìm một số 10 chữ số gồm cả mã vùng
    • Chỉ mục cho một tệp 20 dòng sẽ thành <số dài 20TB>
    • Bài gốc có đề cập phần này

      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 π.

  • Đây là các bài liên quan. Còn nữa không?
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=36357466 - tháng 6 năm 2023, 107 bình luận
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=28699499 - tháng 9 năm 2021, 30 bình luận
    PiFS – The Data-Free Filesystem - https://news.ycombinator.com/item?id=26208704 - tháng 2 năm 2021, 1 bình luận
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=21359338 - tháng 10 năm 2019, 1 bình luận
    The π Filesystem for FUSE: Store Your Data in π - https://news.ycombinator.com/item?id=19223032 - tháng 2 năm 2019, 1 bình luận
    pifs - Avoid disk space usage by saving your files in the digits of Pi - https://news.ycombinator.com/item?id=18687275 - tháng 12 năm 2018, 1 bình luận
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=13869691 - tháng 3 năm 2017, 105 bình luận
    Πfs: Stores your data in π - https://news.ycombinator.com/item?id=10856108 - tháng 1 năm 2016, 1 bình luận
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=10847693 - tháng 1 năm 2016, 1 bình luận
    File system that stores location of file in Pi - https://news.ycombinator.com/item?id=8018818 - tháng 7 năm 2014, 98 bình luận
    100% Compression Using Pi - https://news.ycombinator.com/item?id=6698852 - tháng 11 năm 2013, 32 bình luận
    Bài đăng lại sau khoảng 1 năm thì vẫn ổn, còn liên kết đến các thread cũ là dành cho độc giả muốn tìm hiểu thêm

    • Không rõ các danh sách kiểu này được tạo ra như thế nào

  • Cái này cũng khiến tôi nhớ đến: https://www.spronck.net/sloot.html
    Đọc thêm: https://en.wikipedia.org/wiki/Sloot_Digital_Coding_System

    • Tôi đã tìm hiểu sơ qua trước đây, và điều Sloot làm ít nhất cũng có phần mới mẻ
      Cách mã hóa thực tế là lưu từng dòng của video vào cơ sở dữ liệu, rồi mã hóa mỗi khung hình thành một chuỗi các lượt tra cứu dòng, sau đó lại lưu các khung hình đã mã hóa đó vào một cơ sở dữ liệu khác. Mỗi video trở thành một chuỗi các lượt tra cứu khung hình
      Đó là lý do họ có thể trình diễn việc phát mượt 16 video cùng lúc trên phần cứng cuối thập niên 90. Vì mỗi khung hình là một chuỗi các lượt tra cứu dòng, nên ngay cả khi chia màn hình thành 16 phần theo chiều ngang để phát đồng thời 16 video, tổng tải cũng không lớn hơn việc phát một video duy nhất trên toàn màn hình
      Tương tự, vì mỗi khung hình được giải mã riêng lẻ nên tua nhanh và tua lùi cũng mượt. Không giống nén video truyền thống phải tính chênh lệch từ các keyframe, nên phát ở tốc độ 2x cũng không khó hơn 1x
      Tất nhiên họ không thể lưu các tệp video với kích thước kiểu 8KB, nhưng ví dụ nếu cả một mùa phim truyền hình có trong cơ sở dữ liệu thì phần giới thiệu mở đầu và credit kết thúc chỉ cần lưu một lần

    • 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.
      Nhưng π là vô hạn. Vậy nên chừng nào định luật Moore vẫn còn đứng về phía chúng ta thì cỗ máy thiên tài này sẽ hoạt động

  • One of the properties that π is conjectured to have is that it is normal
    Từ khóa ở đây là conjectured
    Tôi thích khi một vấn đề nhỏ về tính chặt chẽ mà tôi hay ám ảnh lại xuất hiện. Việc một số vô tỉ không được kiến tạo có phải là số chuẩn hay có chứa mọi chuỗi hữu hạn hay không thì đến nay vẫn chưa có điều nào được chứng minh

    • Tôi thắc mắc ở đây “không được kiến tạo” nghĩa là gì

  • In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π.
    Xét riêng từng bit có lẽ sẽ cho hiệu năng tốt hơn. Chỉ cần các chỉ mục 2 và 33, và có thể ánh xạ chúng một cách hiệu quả vào các bit của bộ nhớ

  • Thật khó chịu khi nhận ra rằng π chứa mọi tri thức của quá khứ và tương lai, thậm chí cả việc tôi sẽ chết khi nào

    • Với mọi chuỗi bit ngẫu nhiên vô hạn khác cũng vậy. Phần trái với trực giác không đến từ π mà đến từ sự vô hạn
      Cũng không thể nói rằng nó chứa mọi tri thức về quá khứ và tương lai. Vì mọi điều sai có thể có về quá khứ và tương lai cũng nằm trong đó theo cách không thể phân biệt với sự thật
      Việc mã hóa thông tin thành độ lệch của một chuỗi giả ngẫu nhiên kém hiệu quả lưu trữ hơn so với lưu trực tiếp thông tin
    • Tệ nhất là trong đó còn có cả Star Wars 4~6 của một dòng thời gian thay thế nơi Chris Pratt được chọn vào vai Han Solo
      Sự thật thú vị: “Chrispratt” trong tiếng California cổ có nghĩa là “Joel McHale không muốn vai đó”
    • Có lẽ bạn sẽ thấy The Library of Babel của Jorge Borges rất thú vị
      https://dn760100.eu.archive.org/0/items/TheLibraryOfBabel/ba...
    • Người bắt đầu đọc vượt trước π sẽ luôn nhận được những chữ số mới nhất. Mật mã hoàn hảo
    • Trong đó cũng có mọi tin giả của quá khứ và tương lai, và không thể biết bên nào là thật

  • Tôi mơ hồ nhớ rằng trước đây từng có một bài dự thi benchmark nén nào đó đã lách luật bằng cách coi tên tệp là một phần đầu vào của thuật toán giải nén
    Vì benchmark chỉ đo kích thước tệp nên nó có thể qua mặt chỉ số đó

  • Chẳng phải điều này đang dựa vào những tính chất của π mà đến nay vẫn chưa được chứng minh sao? Cần có tính bao hàm mọi chuỗi hữu hạn hoặc tính chính quy, nhưng cả hai đều chưa được chứng minh