Java のデータ圧縮ライブラリを極める #jjug_ccc #ccc_c7

テキストデータや画像・音声データなどの種類を問わずに適用できる 汎用的なデータ圧縮ライブラリ というと、deflate アルゴリズム の実装である zlib が古くからデファクトスタンダードとして存在しており、実際に広く使われています。ご多分に漏れず、zlib は Java にも組み込まれており、標準クラスライブラリを通じて利用できるようになっています。

一方で 2010 年代に入ってから、snappy, lz4, brotli, zstandard といった、zlib より優れた性能を提供する様々なデータ圧縮ライブラリが新たに開発・公開されており、利用が徐々に広まりつつあります。

このセッションでは、最近開発されたデータ圧縮ライブラリについて、Java で利用できるライブラリの紹介やそれぞれのライブラリの特性、どのライブラリを使うべきかの選定基準、また Java でそれらのライブラリを使う際のポイントについてお話いたします。

http://www.java-users.jp/ccc2018spring/#/session/a46bfcee-3f2f-47c5-a3e8-57c901f00140

Transcript

1. Java ͷ σʔλѹॖϥΠϒϥϦΛۃΊΔ JJUG CCC 2018 Spring / 2018-05-26 KOMIYA Atsushi
2. @komiya_atsushi / খٶ ಞ࢙
4. σʔλѹॖͷجૅ஌ࣝ
5. ଛࣦͷͳ͍ ൚༻తͳ σʔλѹॖΞϧΰϦζϜ
6. ଛࣦͷ༗ແ • ѹॖ͞Εͨঢ়ଶͷσʔλ͔ΒɺѹॖલͷσʔλΛ 1 bit ΋ ҧΘͣ෮ݩͰ͖Δ͔൱͔ • 1 bit Ͱ΋ҟͳΔͷͰ͋Ε͹ʮଛࣦ͋Γʯ • ଛࣦͷͳ͍ѹॖΞϧΰϦζϜͷྫ • Deflate (ZIP, gzip, PNG), LZW (GIF, compress) • ଛࣦͷ͋ΔѹॖΞϧΰϦζϜͷྫ • JPEG (ISO/IEC 10918-1:1994), MPEG-1
7. ൚༻తͳѹॖΞϧΰϦζϜ • ςΩετɾը૾ɾԻ੠ͳͲͷσʔλͷछྨΛ ໰Θͣʹద༻Ͱ͖ΔѹॖΞϧΰϦζϜͷ͜ͱ • ઌͷྫͩͱ Deflate ΍ LZW ͳͲ͕֘౰ • JPEG / MPEG ͷΑ͏ʹɺͦΕͧΕͷσʔλʹ ಛԽͨ͠ѹॖΞϧΰϦζϜͷํ͕Ұൠతʹ͸ ੑೳ͕Α͍
8. ѹॖΞϧΰϦζϜͷධՁ • ѹॖ཰ • ΋ͱͷσʔλαΠζ (όΠτ਺) ʹରͯ͠ɺͲΕͩ ͚খ͘͞Ͱ͖͔ͨʁ • খ͚͞Ε͹খ͍͞΄ͲΑ͍ • ʮѹॖલͷαΠζ / ѹॖޙͷαΠζʯͰද͞ΕΔ ͜ͱ΋͋ΔͷͰ஫ҙ͕ඞཁ • ͜ͷ৔߹͸ɺ஋͕େ͖͍ํ͕Α͍ੑೳͱͳΔ
9. ѹॖΞϧΰϦζϜͷධՁ • ॲཧ଎౓ • ୯Ґ࣌ؒ͋ͨΓʹѹॖɾ෮ݩͰ͖Δσʔλͷྔ (୯Ґ͸ MB/ඵͳͲ) • ΞϧΰϦζϜʹΑͬͯ͸ɺѹॖͱ෮ݩͦΕͧΕʹ͔͔Δ ͕࣌ؒେ͖͘ҟͳΔ͜ͱ΋͋Δ (ѹॖ͸஗͍͕෮ݩ͸଎ ͍ɺͳͲ) • ѹॖɾ෮ݩʹ͔͔Δ࣌ؒʹՃ͑ͯɺѹॖσʔλΛ఻ૹ͢ Δͷʹ͔͔Δ࣌ؒ΋ؚΊͨεϧʔϓοτΛग़͢͜ͱ΋͋ Δ
10. ѹॖΞϧΰϦζϜͷධՁ • ѹॖ཰ͱॲཧ଎౓ͷؔ܎ • τϨʔυΦϑͷؔ܎ʹͳΔ • ߴ͍ѹॖ཰ΛಘΔͨΊʹίϯϐϡʔςΟϯάϦ ιʔεΛࠅ࢖ͯ͠೉͍͠ॲཧΛ͢Δ → ॲཧ଎ ౓͸஗͘ͳΔ • ଎͍ॲཧ଎౓ΛٻΊΔͱɺ೉͍͠ॲཧ͸Ͱ͖ͳ ͘ͳΔ → ѹॖ཰͸௿͘ͳΔ
11. ѹॖΞϧΰϦζϜͷධՁ • ϝϞϦɾϑοτϓϦϯτ • ѹॖ͓Αͼ෮ݩͦΕͧΕͷॲཧʹ͓͍ͯඞཁͱͳΔ࠷େͷ ϫʔΩϯάϝϞϦྔ • ѹॖΞϧΰϦζϜ΍ύϥϝʔλʹΑͬͯେ͖͘ࠨӈ͞ΕΔ • ॲཧ଎౓ͱಉ͘͡ɺѹॖɾ෮ݩͦΕͧΕͷϝϞϦɾϑοτ ϓϦϯτ͕ඇରশʹͳΔ͜ͱ΋͋Δ • ෮ݩॲཧͰඞཁͳϝϞϦɾϑοτϓϦϯτ͕খ͍͞έʔ ε͕ଟ͍
12. ࠷ۙͷ σʔλѹॖΞϧΰϦζϜࣄ৘
13. 2010 ೥୅ʹೖΔ·Ͱ • Deflate ͕σϑΝΫτελϯμʔυͱͯ͠܅ྟ • ͦͦ͜͜ͷ଎౓Ͱɺ·ͣ·ͣͷѹॖ཰Λୡ੒Ͱ͖Δ • ϝϞϦɾϑοτϓϦϯτ͕ѹॖ࣌Ͱ΋਺ඦ KB ͱ
 (ࠓͱͳͬͯ͸ͱͯ΋) খͯ͘͞ࡁΉ • ଎౓ੑೳ͕ٻΊΒΕΔ৔໘Ͱ͸ LZO ͱ͍͏બ୒ࢶ͕͋ͬͨ • ͨͩ͠ϥΠηϯε͕ GPLv2 ͳͷͰѻ͍ͮΒ͍
14. ࠷ۙ (2010೥Ҏ߱) ͷτϨϯυ • طଘΞϧΰϦζϜͷѹॖ཰ΛྗٕͰ࠷దԽ • Zopfli (Deflate), Guetzli (JPEG) • ॲཧ଎౓ͷ଎͞ʹಛԽ • Snappy, LZ4 • ॲཧ଎౓ͱѹॖ཰ͷόϥϯεΛॏࢹ • Zstandard, Brotli
15. ࠷ۙ (2010೥Ҏ߱) ͷτϨϯυ • طଘΞϧΰϦζϜͷѹॖ཰ΛྗٕͰ࠷దԽ • Zopfli (Deflate), Guetzli (JPEG) • ॲཧ଎౓ͷ଎͞ʹಛԽ • Snappy, LZ4 • ॲཧ଎౓ͱѹॖ཰ͷόϥϯεΛॏࢹ • Zstandard, Brotli
16. Snappy • Google ੡ • LZ77 Λϕʔεͱͨ͠ΞϧΰϦζϜ • όΠτ୯Ґͷ I/O • ѹॖ͓Αͼ෮ݩͷॲཧ଎౓͕଎͍ • ͦͷ෼ɺѹॖ཰͸΄Ͳ΄ͲͰܾͯ͠ྑ͘͸ͳ͍ • BSD-type ϥΠηϯε
17. LZ4 • Snappy ͱಉ༷ʹɺLZ77 ϕʔε & όΠτ୯Ґͷ I/O Λ࠾༻ • ಛʹ෮ݩॲཧͷ଎౓Λॏࢹ͍ͯ͠Δ • ѹॖ཰͸ Snappy ͱಉఔ౓͔ͪΐͬͱѱ͍͙Β͍ʁ • ѹॖॲཧʹ͔͔Δ࣌ؒΛ٘ਜ਼ʹͭͭ͠ɺߴ͍ѹॖ཰ΛಘΔ HC (high compression) Φϓγϣϯ΋ఏڙ͍ͯ͠Δ • Deflate ΞϧΰϦζϜʹഭΔѹॖ཰Λୡ੒Ͱ͖Δ • BSD ϥΠηϯε
18. LZ4 ར༻࣮੷͕ͱͯ΋๛෋
19. Zstandard • LZ77 ͱ ANS (Asymmetric numeral system) ͷҰ࣮૷Ͱ͋Δ FSE (Finite state entropy) Λ૊Έ߹ΘͤͨΞϧΰϦζϜ • FSE ͷ୅ΘΓʹ Huffman ූ߸Λ࢖͏͜ͱ΋Ͱ͖Δ • Deflate ͱಉ౳͔ɺͦΕҎ্ͷѹॖ཰͓Αͼॲཧ଎౓Λୡ੒͢Δ • ෮ݩ଎౓͸ Snappy, LZ4 ΄ͲͰ͸ͳ͍ʹͯ͠΋ Deflate ΑΓ଎͍ • σʔλʹಛԽͨࣙ͠ॻΛߏங͠ɺͦΕΛ༻͍ͯѹॖ཰Λ޲্ͤ͞Δ࢓૊ΈΛඋ͑ͯ ͍Δ • LZ4 ͱಉ͡։ൃऀ (ݱࡏ͸ Facebook ʹॴଐ) • BSD / GPLv2 ͷσϡΞϧϥΠηϯε • Ҏલ͸͋ͷ Facebook BSD + Patents ϥΠηϯεͩͬͨ
20. Brotli • Google ੡ • LZ77 ͱ 2 ࣍ͷ౷ܭతϞσϦϯάΛར༻ͨ͠ Huffman ූ߸ͷ૊Έ ߹Θͤ • Zstandard ͱಉ༷ʹɺDeflate ͱಉఔ౓Ҏ্ͷੑೳΛୡ੒͢Δ • HTTP ѹॖʹ͓͚ΔΤϯίʔσΟϯάͷҰͭͱͯ͠࠾༻͞Ε͍ͯΔ • ࣄલఆٛ͞Ε Brotli ʹ૊Έࠐ·ΕͨࣙॻΛ༻͍ͯɺѹॖ཰Λ޲্ ͤ͞Δ࢓૊Έ͕උΘ͍ͬͯΔ • MIT ϥΠηϯε
21. Brotli Chrome Ͱ www.google.com ʹΞΫηεͯ͠ΈΔͱ…
22. Java ʹ͓͚Δ
 σʔλѹॖϥΠϒϥϦ
23. ϥΠϒϥϦʹ๬·ΕΔཁૉɾಛੑ • ѹॖΞϧΰϦζϜͷ࣮૷ (JNI binding vs pure Java) • σʔλѹॖ͸ಘͯͯ͠ CPU-intensive ͳॲཧʹͳΔ • ϦϑΝϨϯε࣮૷ͷωΠςΟϒϥΠϒϥϦΛ JNI binding ͢Δͷ͕଎౓ੑೳతʹ๬·͍͠ • ֤छ OS / ΞʔΩςΫνϟ޲͚ͷϏϧυࡁΈωΠςΟϒ ϥΠϒϥϦΛ༻ҙ͠ͳ͚Ε͹ͳΒͳ͍͕ ☹ • Pure Java ࣮૷͸ɺ଎౓ੑೳҎ֎ʹ΋ࡉ͔ͳڍಈͷҧ͍΍ ΞϧΰϦζϜͦͷ΋ͷͷਐԽͱ͍ͬͨ఺ͰϦϑΝϨϯε࣮ ૷ͱဃ཭͕ੜ͡΍͍͢
24. ϥΠϒϥϦʹ๬·ΕΔཁૉɾಛੑ • ఏڙ͞ΕΔΠϯλϑΣʔε • ϦϑΝϨϯε࣮૷ͷϥΠϒϥϦ͕ఏڙ͢ΔΠϯλϑΣʔεʹՃ ͑ͯɺjava.io ύοέʔδͷ InputStream / OutputStream ʹैͬͨΠϯλϑΣʔεΛఏڙ͍ͯ͠Δͷ͕๬·͍͠ • ଞݴޠͷόΠϯσΟϯάͱͷ૬ޓӡ༻ੑ • ྫ͑͹ɺJava ͷϥΠϒϥϦͰѹॖͨ͠σʔλΛ Ruby ͷόΠϯ σΟϯάͰ෮ݩͰ͖Δ͔ʁ • LZ4 ͷΑ͏ʹɺඪ४ͷϑϨʔϜϑΥʔϚοτ͕ଘࡏ͠ͳ͔ͬͨ ѹॖΞϧΰϦζϜ͸ಛʹ஫ҙ͕ඞཁ
25. Java ޲͚ͷσʔλѹॖϥΠϒϥϦ • Snappy • 'org.xerial.snappy:snappy-java' • LZ4 • 'org.lz4:lz4-java' • Zstandard • 'com.github.luben:zstd-jni' • Brotli • 'org.meteogroup.jbrotli:jbrotli'
26. snappy-java • JNI binding ʹΑΔ࣮૷ • ଟ༷ͳ OS / ΞʔΩςΫνϟΛαϙʔτ • ਺஋ྻσʔλͷѹॖ཰ΛߴΊΔ BitShuffle ͷ࣮૷Λఏڙ • ૬ޓӡ༻ੑͷ͋ΔΠϯλϑΣʔε • SnappyFramedInputStream • SnappyFramedOutputStream
27. lz4-java • JNI binding, Unsafe API, pure Java ͷ 3 ͭͷ࣮૷Λఏڙ • JNI binding ͸ओཁͳ OS / ΞʔΩςΫνϟΛαϙʔτ • ͳΔ΂͘ߴ଎ͳ࣮૷͕࢖ΘΕΔ࢓૊Έʹͳ͍ͬͯΔ • JNI biding → Unsafe API → pure Java ͷ༏ઌॱҐ • ૬ޓӡ༻ੑͷ͋ΔΠϯλϑΣʔε • LZ4FrameInputStream • LZ4FrameOutputStream • ࠷৽όʔδϣϯ (1.4.1) Ͱ͸ High compression Φϓγϣϯ͕ࢦఆͰ͖ͳ ͍ͳͲͷ੍ݶ͕͋Δ
28. zstd-jni • JNI binding ʹΑΔ࣮૷ • ओཁͳ OS / ΞʔΩςΫνϟΛαϙʔτ • ૬ޓӡ༻ੑͷ͋ΔΠϯλϑΣʔε • ZstdInputStream • ZstdOutputStream • όοϑΝϦϯάͷ࢓૊Έ͕࣮૷͞Ε͍ͯͳ͍ͷͰɺ ZstdOutputStream#write(int) Λසൟʹݺͼग़͢ͳͲͷ࢖ ͍ํΛ͢Δͱ JNI ༝དྷͷΦʔόʔϔουͰ஗͘ͳΔՄೳੑ͕͋Δ
29. jbrotli • JNI binding ʹΑΔ࣮૷ • ωΠςΟϒϥΠϒϥϦ͸ຊମίʔυͷ jar ϑΝΠϧ ͱ͸ผʹఏڙ͞Ε͍ͯΔ • OS / ΞʔΩςΫνϟ͝ͱʹ jar ϑΝΠϧ͕༻ҙ͞ Ε͍ͯΔͷͰɺ։ൃ؀ڥ / ࣮ߦ؀ڥʹ߹ͬͨϥΠ ϒϥϦ͚ͩґଘؔ܎ʹ௥Ճ͢Ε͹Α͍ • BrotliLibraryLoader.loadBrotli() ͷ͓· ͡ͳ͍͕ඞཁ
30. jbrotli • ૬ޓӡ༻ੑͷ͋ΔΠϯλϑΣʔε • BrotliInputStream • BrotliOutputStream • ࠷৽όʔδϣϯ (0.5.0) Ͱ͸ෆ۩߹͕͋ΔΑ͏Ͱɺ BrotliOutputStream Ͱѹॖͨ͠σʔλΛ BrotliInputStream Ͱ෮ݩͰ͖ͳ͍͜ͱ͕͋Δ
31. Java ΞϓϦέʔγϣϯʹ͓͚Δ ѹॖΞϧΰϦζϜͷબఆج४
32. ͲͷѹॖΞϧΰϦζϜΛબ୒͢΂͖͔ʁ • ॲཧ଎౓ͱѹॖ཰ɺͲͪΒΛॏࢹ͢Δͷ͔ʁ • ॲཧ଎౓Λॏࢹ: LZ4, Snappy • ѹॖ཰Λॏࢹ: Zstandard (, Brotli) • ରԠ͍ͯ͠Δ OS / ΞʔΩςΫνϟͷଟ༷͞ • Deflate (JDK built-in), LZ4 (pure Java) • ࣍఺: Snappy
33. ࢀߟ: Docker ίϯςφ಺Ͱͷར༻ • Alpine Linux ͱ JNI binding ͳσʔλѹॖϥΠϒϥϦ ͷ૊Έ߹Θͤ͸໰୊͕ൃੜ͠΍͍͢ͷͰ஫ҙ͕ඞཁ • https://github.com/xerial/snappy-java/issues/181 • https://github.com/luben/zstd-jni/issues/38 • https://github.com/luben/zstd-jni/issues/43 • (ͦΕͧΕ࠷৽όʔδϣϯͰ͸ղফࡁΈ)
34. ࢀߟ: ѹॖ଎౓ɾѹॖ཰ͷൺֱ ϥΠϒϥϦ
    ύϥϝʔλ ѹॖॲཧ଎౓
    <.#T> ѹॖ཰
    <> EFqBUF    EFqBUF    EFqBUF    M[KBWB ,#   M[KBWB .#   TOBQQZKBWB ,#   [TUEKOJ    [TUEKOJ    [TUEKOJ    -BSHF
    UFYU
    DPNQSFTTJPO
    CFODINBSL
    ͷϑΝΠϧ
    FOXJL
    ΑΓઌ಄
    .#
    Λ੾Γग़ͯ͠ධՁʹར༻
35. ࢀߟ: ෮ݩ଎౓ɾѹॖ཰ͷൺֱ ϥΠϒϥϦ
    ύϥϝʔλ ෮ݩॲཧ଎౓
    <.#T> ѹॖ཰
    <> EFqBUF    M[KBWB ,#   TOBQQZKBWB ,#   [TUEKOJ   
36. ·ͱΊ
37. ·ͱΊ • ѹॖ཰ͱॲཧ଎౓ɺͲͪΒΛॏࢹ͢Δ͔Ͱɺద੾ͳѹॖΞ ϧΰϦζϜ͸มΘͬͯ͘Δ • ݸਓతͳݟղͱͯ͠͸… • ѹॖ཰ (ͱॲཧ଎౓ͷόϥϯε) ॏࢹ: Zstandard • ॲཧ଎౓ॏࢹ: LZ4 • ѹॖΞϧΰϦζϜͱσʔλͱͷʮ૬ੑʯ͕͋Γ͏ΔͷͰɺ
 ࣮ࡍʹѻ͏σʔλͰϕϯνϚʔΫΛऔͬͯΈΔ͜ͱ͕େࣄ
38. Thank you!
39. We’re hiring! • ͢΂ͯͷืू৬छ • bit.ly/SmartNews-Hiring • Φʔϓϯϙδγϣϯ / ϙδγϣϯαʔν • bit.ly/SmartNews-OpenPosition