Skalabilitas 'sort -u' untuk file raksasa

23

Apa batas skalabilitas yang wajar dari 'sort -u'? (dalam dimensi "panjang garis", "jumlah garis", "ukuran file total"?)

Apa alternatif Unix untuk file yang melebihi ini dalam dimensi "jumlah baris"? (Tentu saja saya dapat dengan mudah mengimplementasikannya, tetapi saya bertanya-tanya apakah ada sesuatu yang dapat dilakukan dengan beberapa perintah Linux standar?)

sort Grzegorz Wierzowiecki
sumber
Bagi mereka yang mungkin ingin mencari biner di dalamnya atau tahu caranya: unix.stackexchange.com/q/247508/9689
Grzegorz Wierzowiecki
2
Ada situasi di mana a uniqsebelum sort -umembantu. BTW, untuk data ASCII LC_ALL=C sortmempercepat sortbanyak sekali GNU (lihat jawaban ini )
Walter Tross

Jawaban:

39

Yang sortAnda temukan di Linux berasal dari paket coreutils dan mengimplementasikan gabungan R-Way Eksternal . Ini membagi data menjadi potongan-potongan yang dapat ditanganinya dalam memori, menyimpannya pada disk dan kemudian menggabungkannya. Potongan dilakukan secara paralel, jika mesin memiliki prosesor untuk itu.

Jadi jika ada batasan, itu adalah ruang disk bebas yang sortdapat digunakan untuk menyimpan file sementara yang harus digabung, dikombinasikan dengan hasilnya.

Anthon
sumber
3
Perhatikan bahwa GNU sort dapat memampatkan file temp tersebut untuk mengemas lebih banyak (dan meningkatkan kinerja dengan disk lambat).
Stéphane Chazelas
1
@ StéphaneChazelas Terima kasih atas pembaruannya. Saya bertanya-tanya sendiri apakah sortir cukup pintar untuk menghapus file chunk ketika seseorang sepenuhnya digabung (yang dapat dengan mudah terjadi jika sumbernya sudah sebagian diurutkan) sebagai pengoptimalan ruang. Saya tidak punya waktu untuk menyelam ke dalam kode sumber hari ini :-(
Anthon
3
Selain memori, ada juga batas lain yang berlaku untuk fase penggabungan: jumlah file yang dapat dibuka secara bersamaan. Ini biasanya batas yang diberlakukan oleh sistem operasi. GNU juga mengatasinya dengan menggabungkan beberapa file yang dapat dibuka lama secara bersamaan!
Diomidis Spinellis
@ StéphaneChazelas Jika saya merancang alat khusus untuk menyortir file yang sangat besar, saya akan menyimpan baris sebagai indeks ke dalam file asli. Apakah GNU sort melakukan ini, atau hanya menggunakan algoritma kompresi konvensional?
Random832
3
@ Random832 dan itu dimaksudkan untuk dapat menimpa file itu sendiri ( sort -o file file)
Stéphane Chazelas
1

Saya tidak dapat berbicara untuk implementasi khusus vendor, tetapi UNIX sortimplementasinya membagi file besar menjadi file yang lebih kecil, mengurutkan file-file ini dan kemudian menggabungkan file yang lebih kecil yang diurutkan menjadi output yang diagregasi.

Satu-satunya batasan adalah ruang disk untuk file yang lebih kecil dibuat oleh sort, tetapi file dapat diarahkan ke direktori arbitrer dengan mengatur variabel lingkungan TMPDIR.

schily
sumber
3
Apa sebenarnya yang Anda sebut implementasi semacam UNIX ? Apakah ini yang asli dari Unix versi 3? Halaman manual di sana mengatakan tidak dapat mengurutkan file lebih besar dari 128KiB.
Stéphane Chazelas
Apa yang Anda pahami oleh Unix versi 3? Versi dari 1973? Implementasi semacam UNIX asli telah ditingkatkan selama bertahun-tahun dan IIRC, versi Solaris bahkan lebih cepat daripada versi GNU. Tentu saja, 25 tahun yang lalu semacam ditingkatkan untuk memahami karakter multi-byte dan apa yang saya ingat dari diskusi USENET, adalah bahwa ini telah dilakukan secara efisien pada Solaris. BTW: man largefiledaftar sortsebagai sadar file besar.
schily
2
Jadi, apakah Anda benar-benar berbicara tentang versi khusus vendor Oracle sort? Atau turunan dari beberapa versi semacam AT&T Unix? Atau versi bersertifikat Unix sort(seperti GNU sortdi OS / X)?
Stéphane Chazelas
Kualitas sortimplementasi modern sehubungan dengan karakter multi-byte dapat bervariasi, fakta bahwa sortmenggunakan split intermediate files adalah umum untuk semua implementasi UNIX yang didasarkan pada kode asli. BTW: versi Solaris adalah OSS sebagai "OpenSolaris", lihat sourceforge.net/p/schillix-on/schillix-on/ci/default/tree/usr/…
schily
25 tahun yang lalu, UTF-8 belum ditemukan? Dukungan untuk lokal UTF-8 ditambahkan di Solaris 7 ( 1 , 2 ). Apakah Anda merujuk ke beberapa set karakter multibyte lainnya?
Stéphane Chazelas
1

Berdasarkan https://blog.mafr.de/2010/05/23/sorting-large-files/ dan /unix//a/88704/9689 :

split -n l/20 input input-
for inpf in input-* ; do
    sort --parallel="$(nproc --all)" "${inpf}" > sorted-"{$inpf}"
done
sort -m sorted-input-* > sorted-input

Memperbarui:

Dari jawaban di atas kita melihat bahwa sortsudah melakukan apa yang disebutkan potongan - yaitu Eksternal R-Way merge . Jadi setelah semua berjalan saja:

sort --parallel="$(nproc --all)" -u input > output

Harus cukup.

Asumsi saya saat ini (tanpa memeriksa kode) tentang batasan adalah:

  • panjang garis maksimum dibatasi oleh jumlah memori fisik. Sortir perlu memuat setidaknya dua ke dalam memori
  • jumlah garis - Saya tidak tahu
  • ukuran file - tentu saja berdasarkan sistem file
  • jumlah file yang dibuka secara paralel - tergantung pada Sistem Operasi (Terima kasih Diomidis Spinellis untuk menunjukkan ini!)

(Jawaban ini ditandai sebagai komunitas wiki - merasa terdorong untuk memperbaikinya! :))

Grzegorz Wierzowiecki
sumber
2
GNU sortmenyortir paralel secara default (sejak 2010 setelah halaman yang Anda tautkan), --parallelada untuk mengurangi jumlah utas bersamaan daripada membiarkan sortmenentukan yang optimal. Sortir sudah melakukan pemisahan dan penggabungan secara internal dengan cara yang lebih efisien. Saya ragu melakukan hal itu akan membantu.
Stéphane Chazelas