Xử lý các tập dữ liệu lớn trong Java/Clojure: dữ liệu littleBig

Question

Tôi đã làm việc trên một ứng dụng xử lý đồ họa/dữ liệu (you can see a screenshot here) sử dụng Clojure (mặc dù, đôi khi, có vẻ như tôi đang sử dụng Java nhiều hơn Clojure) và bắt đầu thử nghiệm ứng dụng của tôi với các tập dữ liệu lớn hơn. Tôi không có vấn đề với khoảng 100k điểm, nhưng khi tôi bắt đầu nhận được cao hơn, tôi chạy vào vấn đề không gian heap.

Bây giờ, về mặt lý thuyết, khoảng một nửa GB nên đủ để giữ khoảng 70 triệu đôi. Cấp, tôi đang làm nhiều thứ mà đòi hỏi một số chi phí, và tôi có thể trong thực tế được giữ 2-3 bản sao của dữ liệu trong bộ nhớ cùng một lúc, nhưng tôi đã không được tối ưu hóa nhiều, và 500k hoặc hơn vẫn là đơn đặt hàng của độ lớn ít hơn tôi có thể tải.

---

Tôi hiểu rằng Java có giới hạn nhân tạo (có thể thay đổi) vào kích thước của heap, và tôi hiểu những có thể thay đổi, một phần, với các tùy chọn bạn có thể chỉ là JVM khởi động. Điều này dẫn tôi đến câu hỏi của tôi đầu tiên:

• Tôi có thể thay đổi tối đa cho phép không gian đống nếu tôi đang sử dụng Swank-Clojure (thông qua Leiningen) JVM có khi khởi động?

• Nếu tôi đóng gói ứng dụng này (như tôi dự định) làm Uberjar, tôi có thể đảm bảo JVM của tôi có một số không gian lưu trữ tối thiểu không?

Nhưng tôi không hài lòng với việc chỉ dựa vào đống JVM để cấp nguồn cho ứng dụng của tôi. Tôi không biết kích thước của dữ liệu mà cuối cùng tôi có thể làm việc, nhưng nó có thể đạt tới hàng triệu điểm, và có lẽ đống không thể chứa được điều đó. Vì vậy, tôi rất thú vị trong việc tìm kiếm giải pháp thay thế để chỉ xếp chồng dữ liệu trên đó. Dưới đây là một số ý tưởng tôi đã có, và các câu hỏi về họ:

• nó có thể sẽ được đọc trong chỉ bộ phận của một (văn bản) tập tin lớn tại một thời điểm, vì vậy tôi có thể nhập và xử lý dữ liệu trong "khối", ví dụ: n dòng tại một thời điểm? Nếu vậy, làm thế nào?

• Có cách nào nhanh hơn để truy cập tệp tôi muốn đọc từ (có khả năng nhanh chóng, tùy thuộc vào việc triển khai), ngoài việc chỉ cần đọc từ một chút tại một thời điểm? Tôi đoán tôi đang yêu cầu ở đây cho bất kỳ lời khuyên/hack đã làm việc cho bạn trong quá khứ, nếu bạn đã làm một điều tương tự.

• Tôi có thể "lấy mẫu" từ tệp không; ví dụ. chỉ đọc từng dòng z, giảm bớt dữ liệu của tôi một cách hiệu quả?

Ngay bây giờ tôi đã lên kế hoạch, nếu có câu trả lời cho câu hỏi trên (tôi sẽ tiếp tục tìm kiếm), dẫn đến các giải pháp tương đương, đọc từng đoạn dữ liệu một lúc, vẽ đồ thị vào dòng thời gian (see the screenshot - dòng thời gian có màu xanh lục) và cho phép người dùng tương tác chỉ với bit đó cho đến khi cô ấy nhấp vào next chunk (hoặc thứ gì đó), sau đó tôi sẽ lưu các thay đổi được thực hiện cho một tệp và tải "dữ liệu" tiếp theo và hiển thị nó.

Hoặc, tôi sẽ hiển thị toàn bộ dòng thời gian của tất cả dữ liệu (được lấy mẫu xuống, vì vậy tôi có thể tải), nhưng chỉ cho phép truy cập vào một "đoạn" của nó tại một thời điểm trong cửa sổ chính (phần xem trên dòng thời gian màu xanh lục, như được phác thảo bởi hình chữ nhật khung nhìn trong dòng thời gian).

---

Hầu hết tất cả, tuy nhiên, là có một cách tốt hơn? Lưu ý rằng tôi không thể downsample dữ liệu của cửa sổ chính, vì tôi cần để có thể xử lý nó và cho phép người dùng tương tác với nó (ví dụ, nhấp vào một điểm hoặc gần một để thêm một "điểm đánh dấu" vào điểm đó: một quy tắc dọc trên điểm đó).

Tôi đánh giá cao bất kỳ thông tin chi tiết, câu trả lời, đề xuất hoặc chỉnh sửa nào! Tôi cũng sẵn sàng giải thích về câu hỏi của tôi theo bất kỳ cách nào bạn muốn.

Điều này hy vọng, ít nhất một phần, có nguồn mở; Tôi muốn một cách đơn giản để sử dụng nhưng nhanh chóng để tạo xy-lô của rất nhiều dữ liệu trong thế giới Clojure.

---

EDIT downsampling có thể chỉ khi vẽ đồ thị, và không phải lúc nào sau đó, tùy thuộc vào các phần được vẽ đồ thị. Tôi cần truy cập vào tất cả dữ liệu để thực hiện phân tích. (Chỉ cần dọn dẹp mà lên!) Mặc dù tôi chắc chắn nên nhìn vào downsampling, tôi không nghĩ rằng sẽ giải quyết vấn đề bộ nhớ của tôi trong ít nhất, như tất cả tôi đang làm cho đồ thị được vẽ trên một BufferedImage.

Answer 1

Tôi có thể thay đổi tối đa cho phép không gian đống nếu tôi đang sử dụng Swank-Clojure (thông qua Leiningen) JVM có khi khởi động?

Bạn có thể thay đổi kích thước heap Java bằng cách cung cấp tùy chọn -Xms (min heap) và -Xmx (max heap) khi khởi động, xem docs.

Vì vậy, một cái gì đó như java -Xms256m -Xmx1024m ... sẽ cung cấp cho bộ nhớ ban đầu 256MB với tùy chọn tăng lên 1GB.

Tôi không sử dụng Leiningen/Swank, nhưng tôi hy vọng rằng có thể thay đổi nó.Nếu không có gì khác, cần có một kịch bản khởi động cho Java ở đâu đó, nơi bạn có thể thay đổi các đối số.

Nếu tôi đóng gói ứng dụng này (như tôi kế hoạch) như là một Uberjar, sẽ Tôi được thể đảm bảo JVM của tôi có một số loại không gian đống tối thiểu?

Bộ nhớ không được kiểm soát từ bên trong tệp jar, nhưng từ tập lệnh khởi động, thường là tệp .sh hoặc .bat gọi java và cung cấp đối số.

Tôi có thể "lấy mẫu" từ tệp không; ví dụ. chỉ đọc mọi dòng z?

java.io.RandomAccessFile cung cấp quyền truy cập tệp ngẫu nhiên theo chỉ mục byte mà bạn có thể tạo để lấy mẫu nội dung.

nó có thể sẽ được đọc trong chỉ bộ phận của một (văn bản) tập tin lớn tại một thời điểm , vì vậy tôi có thể nhập khẩu và quá trình dữ liệu trong "khối", ví dụ, n dòng ở một thời gian ? Nếu vậy, làm thế nào?

line-seq trả về một chuỗi chậm của mỗi dòng trong một tệp, do đó bạn có thể xử lý nhiều lần tùy thích.

Ngoài ra, sử dụng các cơ chế Java trong java.io-BufferedReader.readLine() hoặc FileInputStream.read(byte[] buffer)

Có một số cách nhanh hơn truy cập tập tin tôi được đọc từ (có khả năng nhanh chóng, tùy thuộc vào việc thực hiện ), ngoài việc chỉ đơn giản là đọc từ nó một chút tại một thời điểm?

Trong Java/Clojure có BufferedReader hoặc bạn có thể duy trì bộ đệm byte của riêng bạn và đọc khối lớn hơn tại một thời điểm.

Để tận dụng tối đa bộ nhớ bạn có, hãy giữ dữ liệu thô sơ nhất có thể.

Đối với một số con số thực tế, chúng ta hãy giả sử bạn muốn vẽ đồ thị các nội dung của một đĩa CD âm nhạc:

• Một CD có hai kênh, mỗi với 44.100 mẫu mỗi giây
  • 60 phút. âm nhạc là sau đó ~ 300 triệu điểm dữ liệu
• Người đại diện như 16 bit (2 byte, một đoạn ngắn) mỗi datapoint: 600MB
• Người đại diện như mảng int nguyên thủy (4 byte cho mỗi datapoint): 1.2GB
• Người đại diện như mảng Integer (32 byte cho mỗi datapoint): 10GB

Sử dụng các số từ this blog cho kích thước đối tượng (16 byte overhead mỗi đối tượng, 4 byte cho int nguyên thủy, các đối tượng liên kết đến ranh giới 8-byte , Con trỏ 8 byte trong mảng = 32 byte cho mỗi điểm dữ liệu Số nguyên).

Thậm chí 600MB dữ liệu là một đoạn để lưu giữ tất cả cùng một lúc trên một máy tính "bình thường", vì có thể bạn sẽ sử dụng nhiều bộ nhớ ở nơi khác. Tuy nhiên, việc chuyển đổi từ số nguyên gốc sang số tự đóng sẽ tự giảm số lượng các vùng dữ liệu bạn có thể giữ trong bộ nhớ theo thứ tự độ lớn.

Nếu bạn vẽ đồ thị dữ liệu từ đĩa CD 60 phút trên khung thời gian "tổng quan rộng 1900 pixel", bạn sẽ có một pixel để hiển thị hai giây nhạc (~ 180.000 điểm dữ liệu). Điều này rõ ràng là cách quá ít để hiển thị bất kỳ mức độ chi tiết nào, bạn sẽ muốn một số dạng subsampling hoặc dữ liệu tóm tắt ở đó.

Vì vậy, giải pháp bạn mô tả - xử lý toàn bộ tập dữ liệu một đoạn tại một thời điểm để hiển thị tóm tắt trong dòng thời gian 'tổng quan' và chỉ giữ lại tập con nhỏ cho cửa sổ "chi tiết" chính trong bộ nhớ - âm thanh hoàn toàn hợp lý.

Cập nhật:

Mở file nhanh, đọc: - (!) This article lần so với tập tin tốc độ đọc 13 cách khác nhau để đọc một file 100MB trong Java các results thay đổi từ 0,5 giây đến 10 phút. Nói chung, đọc nhanh với kích thước bộ đệm khá (4k đến 8k byte) và (rất) chậm khi đọc một byte tại một thời điểm.

Bài viết cũng có comparison to C trong trường hợp ai đó quan tâm. (Spoiler: Java đọc nhanh nhất là trong một yếu tố 2 của một tập tin ánh xạ bộ nhớ trong C.)

Answer 2

Ném ra một vài ý tưởng từ lĩnh vực trái ...

Bạn có thể thấy một cái gì đó hữu ích trong thư viện Colt ... http://acs.lbl.gov/software/colt/

Hoặc có lẽ bộ nhớ ánh xạ I/O.

Answer 3

Một vài suy nghĩ:

• Cách tốt nhất để xử lý lớn trong bộ nhớ bộ dữ liệu trong Java/Clojure là sử dụng mảng nguyên thủy lớn. Nếu bạn làm điều này, bạn về cơ bản chỉ sử dụng bộ nhớ nhiều hơn một chút so với kích thước của dữ liệu cơ bản. Bạn xử lý các mảng này trong Clojure tốt với chức năng aget/aset

• Tôi muốn bị thu hẹp, nhưng vẫn duy trì cách truy cập một cách lười biếng vào các điểm chi tiết "theo yêu cầu" nếu bạn cần, ví dụ: trong trường hợp tương tác của người dùng. Giống như cách Google Maps cho phép bạn nhìn thấy toàn thế giới và chỉ tải chi tiết khi bạn phóng to.

• Nếu bạn chỉ quan tâm đến hình ảnh đầu ra từ ô xy, thì bạn có thể xây dựng nó bằng cách tải trong một vài nghìn điểm tại một thời điểm (ví dụ như tải vào mảng nguyên thủy của bạn), âm mưu chúng sau đó loại bỏ sau đó. Bằng cách này, bạn sẽ không cần phải giữ toàn bộ tập dữ liệu trong bộ nhớ.