數(shù)據(jù)結(jié)構(gòu)壓縮

這個(gè)故事是關(guān)于我們最近在Plumbr進(jìn)行的容量?jī)?yōu)化任務(wù)。 一切始于將無(wú)害的要求添加到現(xiàn)有組合中。

您可能知道，Plumbr監(jiān)視解決方案作為連接到服務(wù)器的Java代理分發(fā)。 只需少量添加即可跟蹤一段時(shí)間內(nèi)所有已連接的代理，以便可以實(shí)時(shí)回答以下問(wèn)題：

• 我們有多久沒(méi)有收到這個(gè)特定JVM的消息了？
• 另一個(gè)JVM的最后一次已知停機(jī)時(shí)間是什么？

當(dāng)每個(gè)代理每秒發(fā)送一次心跳時(shí)，我們?cè)诜?wù)器端需要做的就是跟蹤所有心跳。 由于每個(gè)心跳都附加有唯一的時(shí)間戳，因此幼稚的解決方案就像將所有心跳扔到Set或Map中一樣容易。 那么-簡(jiǎn)單，完成，接下來(lái)，請(qǐng)？

但是，一些快速的數(shù)學(xué)運(yùn)算表明，最初的想法可能行不通。 考慮到：

• 時(shí)間戳記的類型很長(zhǎng) ，需要8個(gè)字節(jié)才能容納
• 一年中有365 x 24 x 60 x 60 = 31,536,000秒

我們可以快速進(jìn)行數(shù)學(xué)計(jì)算，發(fā)現(xiàn)單個(gè)JVM僅使用一年的原始數(shù)據(jù)就需要240MB 。 僅原始數(shù)據(jù)的大小就已經(jīng)足夠嚇人了，但是當(dāng)打包到HashSet時(shí)，結(jié)構(gòu)的保留大小 爆炸到大約2GB ，而所有開(kāi)銷的java.util.Collection API實(shí)現(xiàn)都隱藏在它們的腹部 。

幼稚的解決方案已經(jīng)無(wú)法解決，我們需要一個(gè)替代方案。 最初我們不必走得很遠(yuǎn)，因?yàn)樵谕籮ava.util包中，一個(gè)等待被發(fā)現(xiàn)的驚喜叫java.util.BitSet 。 根據(jù)該類的javadoc：

BitSet類實(shí)現(xiàn)一個(gè)按需增長(zhǎng)的位向量。 位集合的每個(gè)分量都有一個(gè)布爾值。 BitSet的位由非負(fù)整數(shù)索引。 可以檢查，設(shè)置或清除各個(gè)索引位。

那么，如果我們將從代理獲取的心跳存儲(chǔ)為由心跳時(shí)間戳索引的布爾值，該怎么辦？ Java中的時(shí)間戳表示為當(dāng)前時(shí)間與UTC 1970年1月1日午夜之間的毫秒差。 知道這一點(diǎn)后，我們可以將UTC表示為2015年9月1日12:00 UTC，即數(shù)字1441108800。那么，如果當(dāng)我們看到某個(gè)Agent在時(shí)間戳1441108800處向我們發(fā)送心跳信號(hào)時(shí)，我們會(huì)將索引1441108800的位置設(shè)置為true ，否則被保留為默認(rèn)false ？

解決方案的問(wèn)題隱藏在一個(gè)事實(shí)中，即BitSet中的位是用整數(shù)而不是long索引的。 為了繼續(xù)進(jìn)行此解決方案，我們將需要一種將整數(shù)映射到long而不丟失任何信息的方法。 如果似乎不可能，那么讓我們回顧一下這樣一個(gè)事實(shí)，即需要一秒而不是一毫秒的精度。 知道了這一點(diǎn)，我們可以將索引縮小1,000倍，并以秒而不是毫秒的精度標(biāo)記時(shí)間。

但是僅使用整數(shù)就可以表示多少秒？ 顯然，Integer.MAX_VALUE足夠大，足以表示從1970年1月1日到19.01.2038的每一秒。 除了制造2038年的問(wèn)題外，它還應(yīng)該足夠好，對(duì)嗎？

不幸的是，正如我們對(duì)餐巾紙的計(jì)算所得出的那樣，一年的數(shù)據(jù)仍然需要約800MB的堆空間。 這是從最初的HashSet 2GB向正確方向邁出的一小步，但對(duì)于實(shí)際使用而言仍然太高了。

為了克服該問(wèn)題，可能需要重新閱讀/重新考慮“足以代表1970年1月1日的每一秒”的部分。 （不幸的）先生。 直到1995年，高斯林才發(fā)明了Java虛擬機(jī)。18年后，Plumbr自己看到了曙光。 因此，我們直到1970年才需要回顧歷史，并且每個(gè)整數(shù)都有一堆零。 可以從01.01.2013開(kāi)始，而不是從01.01.1970開(kāi)始，并使用一個(gè)索引0對(duì)應(yīng)于01.01.2013 00:00（UTC）。

重做我們的餐巾紙數(shù)學(xué)，并在實(shí)踐中檢查結(jié)果使我們成為贏家。 現(xiàn)在一年的數(shù)據(jù)量只能存儲(chǔ)在20MB中 。 與原始2GB相比，我們將所需容量減少了100倍 。 由于現(xiàn)有的基礎(chǔ)架構(gòu)已經(jīng)可以解決這個(gè)問(wèn)題，因此已經(jīng)處于舒適區(qū)域，因此我們沒(méi)有在優(yōu)化路徑上走得更遠(yuǎn)。

故事的道德啟示？ 當(dāng)您有需求時(shí)，請(qǐng)找出對(duì)應(yīng)用程序性能的影響。 我的意思是性能的各個(gè)方面，因?yàn)椴粌H有延遲和吞吐量，還應(yīng)該忘記容量。 并且–了解您的域名。 沒(méi)有它，您將無(wú)法做出決策，如果僅僅配備了有關(guān)數(shù)據(jù)結(jié)構(gòu)的智能書(shū)籍，這些決策就顯得不安全且危險(xiǎn)。

翻譯自: https://www.javacodegeeks.com/2015/09/squeezing-data-into-the-data-structure.html

數(shù)據(jù)結(jié)構(gòu)壓縮

總結(jié)

以上是生活随笔為你收集整理的数据结构压缩_将数据压缩到数据结构中的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。