Apa implikasi kinerja untuk jutaan file dalam sistem file modern?

30

Katakanlah kita menggunakan ext4 (dengan dir_index diaktifkan) untuk meng-host sekitar file 3M (dengan rata-rata ukuran 750KB) dan kita perlu memutuskan skema folder apa yang akan kita gunakan.

Dalam solusi pertama , kami menerapkan fungsi hash ke file dan menggunakan folder dua tingkat (menjadi 1 karakter untuk tingkat pertama dan 2 karakter ke tingkat kedua): karena itu filex.forhash sama dengan abcde1234 , kami akan menyimpannya di / path / a / bc /abcde1234-filex.for.

Dalam solusi kedua , kami menerapkan fungsi hash ke file dan menggunakan folder dua tingkat (menjadi 2 karakter untuk tingkat pertama dan 2 karakter ke tingkat kedua): karena itu filex.forhash sama dengan abcde1234 , kami akan menyimpannya di / path / ab / de /abcde1234-filex.for.

Untuk solusi pertama kita akan memiliki skema berikut /path/[16 folders]/[256 folders]dengan rata - rata 732 file per folder (folder terakhir, di mana file akan berada).

Sedangkan pada solusi kedua kita akan memiliki rata/path/[256 folders]/[256 folders] - rata 45 file per folder .

Mengingat kita akan banyak menulis / memutus tautan / membaca file ( tetapi sebagian besar membaca ) dari skema ini (pada dasarnya sistem caching nginx), apakah perlu, dalam hal kinerja, jika kita memilih satu atau solusi lain?

Juga, alat apa yang bisa kita gunakan untuk memeriksa / menguji pengaturan ini?

leandro moreira
sumber
7
Jelas pembandingan akan membantu. Tetapi ext4 mungkin merupakan sistem file yang salah untuk ini. Saya akan melihat XFS.
ewwhite
4
Saya tidak akan hanya melihat XFS, saya akan segera menggunakannya tanpa basa-basi lagi. Pohon B + mengalahkan tabel hash setiap waktu.
Michael Hampton
Terima kasih atas tipsnya, membuat tolok ukur agak sulit, saya mencoba hdparm -Tt /dev/hdXtetapi mungkin bukan alat yang paling tepat.
leandro moreira
2
Tidak hdparmbukan alat yang tepat, itu adalah pemeriksaan kinerja mentah dari perangkat blok dan bukan tes sistem file.
HBruijn

Jawaban:

28

Alasan seseorang akan membuat struktur direktori semacam ini adalah karena filesystem harus menemukan file di dalam direktori, dan semakin besar direktori, semakin lambat operasinya.

Berapa lambatnya tergantung pada desain sistem file.

Sistem file ext4 menggunakan B-tree untuk menyimpan entri direktori. Pencarian pada tabel ini diharapkan memakan waktu O (log n) , yang sebagian besar waktu kurang dari tabel linear naif yang ext3 dan filesystem sebelumnya digunakan (dan ketika tidak, direktori terlalu kecil untuk itu untuk sangat penting).

Sistem file XFS menggunakan pohon B + sebagai gantinya. Keuntungan dari ini di atas tabel hash atau B-tree adalah bahwa setiap node dapat memiliki beberapa anak b , di mana dalam XFS b bervariasi dan dapat setinggi 254 (atau 19 untuk node root; dan angka-angka ini mungkin sudah ketinggalan zaman ). Ini memberi Anda kompleksitas waktu O (log b n) , peningkatan besar.

Salah satu dari sistem file ini dapat menangani puluhan ribu file dalam satu direktori, dengan XFS secara signifikan lebih cepat daripada ext4 pada direktori dengan jumlah inode yang sama. Tetapi Anda mungkin tidak ingin direktori tunggal dengan inode 3M, karena bahkan dengan pohon B + pencarian dapat memakan waktu. Inilah yang menyebabkan menciptakan direktori dengan cara ini di tempat pertama.

Adapun struktur yang Anda usulkan, opsi pertama yang Anda berikan adalah persis apa yang ditunjukkan dalam contoh nginx. Ini akan bekerja dengan baik pada kedua sistem file, meskipun XFS masih memiliki sedikit keuntungan. Opsi kedua mungkin berkinerja sedikit lebih baik atau sedikit lebih buruk, tetapi mungkin akan cukup dekat, bahkan pada tolok ukur.

Michael Hampton
sumber
Dan untuk XFS atau ext4, perangkat keras yang Anda gunakan pada sistem file akan berdampak besar pada kinerja. Drive SATA lambat 5400 rpm dapat melakukan sekitar 50 operasi IO acak / detik, drive SAS 15.000 rpm yang baik dapat melakukan beberapa ratus, dan SSD kemungkinan akan dibatasi bandwidth dan mungkin mendapatkan beberapa juta operasi IO acak / detik jika tidak lebih.
Andrew Henle
1
Sebenarnya, $ O (\ log_b n) $ untuk fixed $ b $ adalah kompleksitas yang sama dengan $ O (\ log n) $. Tetapi untuk OP, konstanta yang sebenarnya akan penting.
Hagen von Eitzen
Kecuali ada sesuatu yang salah dengan sistem file saya, ext4 tidak dapat menangani 10.000 file dalam satu direktori. Melakukan hal sederhana ls -lmemerlukan satu menit penuh jika direktori telah menjatuhkan cache inode. Dan ketika di-cache, masih membutuhkan waktu satu detik. Ini dengan SSD dan Xeon dengan banyak RAM pada server web traffic yang cukup rendah.
Abhi Beckert
@AbhiBeckert Apakah ini ditingkatkan dari ext3? Jika demikian, coba buat direktori baru dan pindahkan file ke sana.
Michael Hampton
@Hampton Tidak. Ini adalah server setup (cukup) baru-baru ini pada perangkat keras modern. Saya telah menangani masalah ini dengan sysadmin / pusat data kami selama beberapa bulan. Kami membayar ribuan dolar per bulan untuk menyewa server dan tidak mendapatkan kinerja yang dapat diterima darinya. Tampaknya satu-satunya pilihan adalah pindah ke struktur direktori baru - mungkin menggunakan hash bukan tanggal untuk nama file untuk menyebarkannya secara lebih merata.
Abhi Beckert
5

Dalam pengalaman saya, salah satu faktor penskalaan adalah ukuran dari inode yang diberikan strategi partisi nama-hash.

Kedua opsi yang Anda usulkan membuat hingga tiga entri inode untuk setiap file yang dibuat. Juga, 732 file akan membuat inode yang masih kurang dari 16KB biasa. Bagi saya, ini berarti salah satu opsi akan melakukan hal yang sama.

Saya salut pada hash pendek Anda; sistem sebelumnya saya telah bekerja pada sha1sum mengambil file yang diberikan dan direktori spliced ​​berdasarkan string itu, masalah yang jauh lebih sulit.

sysadmin1138
sumber
1
Apa yang membuat penggunaan jumlah SHA1 (dan lainnya, jumlah hash yang lebih lama) "masalah yang jauh lebih sulit"? Memang sulit bagi pengguna manusia, ya, tetapi semuanya sama untuk OS, sistem file, dan program lainnya.
kbolino
4

Tentu saja salah satu opsi akan membantu mengurangi jumlah file dalam direktori menjadi sesuatu yang tampaknya masuk akal, untuk xfs atau ext4 atau sistem file apa pun. Tidak jelas mana yang lebih baik, harus diuji untuk diceritakan.

Tolok ukur dengan aplikasi Anda mensimulasikan sesuatu seperti beban kerja nyata sangat ideal. Kalau tidak, datang dengan sesuatu yang mensimulasikan banyak file kecil secara khusus. Ngomong-ngomong, inilah sumber terbuka yang disebut smallfile . Dokumentasinya merujuk pada beberapa alat lain.

hdparmmelakukan I / O berkelanjutan tidak berguna. Itu tidak akan menampilkan banyak I / O kecil atau entri direktori raksasa yang terkait dengan sangat banyak file.

John Mahowald
sumber
1

Salah satu masalah adalah cara memindai folder.

Bayangkan metode Java yang menjalankan pemindaian pada folder.

Ini harus mengalokasikan sejumlah besar memori dan membatalkan alokasi dalam waktu singkat yang sangat berat untuk JVM.

Cara terbaik adalah mengatur struktur folder dengan cara masing-masing file dalam folder khusus misalnya tahun / bulan / hari.

Cara pemindaian penuh dilakukan adalah bahwa untuk setiap folder ada satu fungsi yang dijalankan sehingga JVM akan keluar dari fungsi, membatalkan alokasi RAM dan menjalankannya lagi di folder lain.

Ini hanya contoh tetapi memiliki folder yang sangat besar tidak masuk akal.

Andrew Smith
sumber
2
Anda menganggap Java dan memindai folder. Tidak disebutkan dalam pertanyaan, dan ada cara lain untuk memproses folder di Jawa selain memindai itu.
user207421
1

Saya pernah mengalami masalah yang sama. Mencoba menyimpan jutaan file di server Ubuntu di ext4. Berakhir menjalankan tolok ukur saya sendiri. Menemukan bahwa direktori datar berkinerja lebih baik sekaligus lebih mudah digunakan:

patokan

Menulis sebuah artikel .

Hartator
sumber
Itu jelas bukan hasil yang diharapkan. Sebelum Anda pergi dengan ini atau merekomendasikannya, Anda harus melihat lebih dalam mengapa Anda mendapatkan hasil yang tidak terduga ini.
Michael Hampton