Skalowalność „sort -u” dla gigantycznych plików

Co to jest rozsądny limit skalowalności „sort -u”? (w wymiarach „długość linii”, „ilość linii”, „całkowity rozmiar pliku”?)

Jaka jest uniksowa alternatywa dla plików przekraczających ten wymiar w zakresie „ilości linii”? (Oczywiście, że mogę z łatwością je wdrożyć, ale zastanawiałem się, czy można coś zrobić za pomocą kilku standardowych poleceń Linuksa?)

sort

— Grzegorz Wierzowiecki
źródło

Dla tych, którzy mogą chcieć w nim wyszukiwać binarnie lub wiedzieć, jak: unix.stackexchange.com/q/247508/9689

— Grzegorz

Są sytuacje, w których uniqprzed sort -upomaga. BTW, dane ASCII LC_ALL=C sortprzyspieszają GNU sortokropnie dużo (zobacz tę odpowiedź )

— Walter Tross

Odpowiedzi:

To sort, co znajdziesz w Linuksie, pochodzi z pakietu coreutils i implementuje scalenie External R-Way . Dzieli dane na części, które może obsługiwać w pamięci, przechowuje je na dysku, a następnie łączy. Fragmenty są wykonywane równolegle, jeśli maszyna ma do tego odpowiednie procesory.

Więc jeśli miałby istnieć limit, to wolne miejsce na dysku, które sortmożna wykorzystać do przechowywania plików tymczasowych, które musi scalić, w połączeniu z wynikiem.

— Anthon
źródło

Zauważ, że GNU sort może kompresować te pliki tymczasowe, aby spakować jeszcze więcej (i zwiększyć wydajność dzięki wolnym dyskom).

— Stéphane Chazelas,

@ StéphaneChazelas Dzięki za aktualizację. Zastanawiałem się, czy sortowanie jest wystarczająco inteligentne, aby usunąć pliki fragmentów, gdy jeden jest całkowicie scalony (co może się łatwo zdarzyć, jeśli źródło jest już częściowo posortowane) jako optymalizacja przestrzeni. Obecnie nie mam czasu na zanurzenie się w kodzie źródłowym :-(

— Anthon

Oprócz pamięci istnieje także inny limit dotyczący fazy scalania: liczba plików, które można jednocześnie otworzyć. Zazwyczaj jest to limit narzucony przez system operacyjny. Sortowanie GNU również sobie z tym radzi, poprzez rekurencyjne łączenie liczby plików, które można otworzyć jednocześnie!

— Diomidis Spinellis

@ StéphaneChazelas Gdybym projektował narzędzie specjalnie do sortowania bardzo dużych plików, zapisałbym linie jako indeks w oryginalnym pliku. Czy GNU sortuje to, czy po prostu używa konwencjonalnego algorytmu kompresji?

— Random832 27.04.16

@ Random832 i ma nadpisywać plik nad sobą ( sort -o file file)

— Stéphane Chazelas 27.04.16

Nie mogę mówić o implementacjach specyficznych dla dostawcy, ale UNIX sortimplementacja dzieli duże pliki na mniejsze pliki, sortuje te pliki, a następnie łączy posortowane mniejsze pliki w zagregowane posortowane dane wyjściowe.

Jedynym ograniczeniem jest miejsce na dysku dla mniejszych plików utworzonych pośrednio sort, ale pliki można przekierować do dowolnego katalogu, ustawiając zmienną środowiskową TMPDIR.

— schily
źródło

Co dokładnie nazywasz implementacją sortowania UNIX ? Czy to jest oryginalny z Uniksa w wersji 3? Strona man mówi, że nie może sortować plików większych niż 128 KB.

— Stéphane Chazelas,

Co rozumiesz przez Unix w wersji 3? Wersja z 1973 roku? Oryginalna implementacja sortowania UNIX została ulepszona przez lata, a IIRC, wersja Solaris jest nawet znacznie szybsza niż wersja GNU. Oczywiście, 25 lat temu sortowanie zostało ulepszone, aby zrozumieć znaki wielobajtowe, a to, co pamiętam z dyskusji USENET, to fakt, że zostało to zrobione skutecznie w Solarisie. BTW: man largefilewyświetla listę sortjako dużych plików.

— szczęśliwie

Więc tak naprawdę mówisz o konkretnej wersji Oracle sort? A może jakaś pochodna jakiejś wersji systemu AT&T Unix? Czy jakaś certyfikowana wersja Uniksa sort(jak GNU sortna OS / X)?

— Stéphane Chazelas,

Jakość współczesnych sortimplementacji w odniesieniu do wielobajtowych znaków może być różna, fakt, że sortużywa podzielonych plików pośrednich jest wspólny dla wszystkich implementacji UNIX opartych na oryginalnym kodzie. BTW: wersja Solaris to OSS jako „OpenSolaris”, patrz sourceforge.net/p/schillix-on/schillix-on/ci/default/tree/usr/…

— schily

25 lat temu UTF-8 nie został jeszcze wynaleziony? Obsługa ustawień regionalnych UTF-8 została dodana w Solaris 7 ( 1 , 2 ). Czy masz na myśli jakiś inny zestaw znaków wielobajtowych?

— Stéphane Chazelas,

Na podstawie https://blog.mafr.de/2010/05/23/sorting-large-files/ i /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

Aktualizacja:

Z powyższych odpowiedzi widzimy, że sortjuż robi to, o czym wspominał fragment - tj. Zewnętrzne scalenie R-Way . W końcu działa tylko:

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

Powinno wystarczyć.

Moje obecne założenia (bez sprawdzania kodu) dotyczące limitów to:

maksymalna długość linii jest ograniczona ilością pamięci fizycznej. Sortuj trzeba zmieścić co najmniej dwa w pamięci
ilość linii - nie jestem tego świadomy
rozmiar pliku - oczywiście według systemu plików
ilość otwartych plików równolegle - w zależności od systemu operacyjnego (Dziękujemy Diomidis Spinellis za zwrócenie na to uwagi!)

(Ta odpowiedź jest oznaczona jako wiki społeczności - zachęcamy do jej poprawy! :))

— Grzegorz Wierzowiecki
źródło

sortDomyślnie GNU sortuje równolegle (od 2010 r. Po tej stronie, do której prowadzi link), --parallelnależy zmniejszyć liczbę współbieżnych wątków zamiast pozwalać na sortokreślenie optymalnego. Sortowanie już dokonuje wewnętrznego podziału i łączenia w bardziej efektywny sposób. Wątpię, czy to dodatkowe rozdzielenie pomoże.

— Stéphane Chazelas,