設計一個計數器

            添加時間:2022-02-27 22:24:25

            來源:

            添加時間:2022-02-27 22:24:25

            評分:

            防偽碼:CMSEASYc8F1WNG3uYwbjkb909

            “設計命中計數器”問題最近被包括 Dropbox 在內的許多公司提出,這個問題比看起來更難。它包括幾個主題,如基本數據結構設計、各種優化、并發和分布式計數器。


            它應該支持以下兩個操作:hit和getHits。


            hit(timestamp) – 顯示給定時間戳的命中。


            getHits(timestamp) – 返回過去 5 分鐘(300 秒)內收到的命中數(來自 currentTimestamp)。


            每個函數都接受一個時間戳參數(以秒為單位),您可以假設調用系統是按時間順序進行的(即時間戳是單調遞增的)。您可以假設最早的時間戳從 1 開始。


            例子:



            HitCounter 計數器 = new HitCounter();


            // 在時間戳 1 處命中。

            反擊(1);


            // 在時間戳 2 處命中。

            反擊(2);


            // 在時間戳 3 處命中。

            反擊(3);


            // 在時間戳 4 處獲得命中,應該返回 3。

            counter.getHits(4);


            // 在時間戳 300 處命中。

            反擊(300);


            // 在時間戳 300 處獲得命中,應返回 4。

            counter.getHits(300);


            // 在時間戳 301 處獲得命中,應返回 3。

            counter.getHits(301);


            問:微軟、亞馬遜、Dropbox 和更多公司。


            1.簡單的解決方案(蠻力方法):


            我們可以使用一個向量來存儲所有的命中。這兩個功能是自我解釋的。



            vector<int> v;

              

            /* Record a hit.

               @param timestamp - The current timestamp (in 

                                  seconds granularity).  */

              

            void hit(int timestamp)

            {

                v.push_back(timestamp);

            }

              

            // Time Complexity : O(1)

              

            /** Return the number of hits in the past 5 minutes.

                @param timestamp - The current timestamp (in

                seconds granularity). */

            int getHits(int timestamp)

            {

                int i, j;

                for (i = 0; i < v.size(); ++i) {

                    if (v[i] > timestamp - 300) {

                        break;

                    }

                }

                return v.size() - i;

            }

              

            // Time Complexity : O(n)

            2、空間優化方案:


            我們可以使用隊列來存儲命中并刪除隊列中無用的條目。它將節省我們的空間。

            我們正在從隊列中刪除多余的元素。



            queue<int> q;

              

            /** Record a hit.

                @param timestamp - The current timestamp 

                               (in seconds granularity). */

            void hit(int timestamp)

            {

                q.push(timestamp);

            }

              

            // Time Complexity : O(1)

              

            /** Return the number of hits in the past 5 minutes.

               @param timestamp - The current timestamp (in seconds

               granularity). */

            int getHits(int timestamp)

            {

                while (!q.empty() && timestamp - q.front() >= 300) {

                    q.pop();

                }

                return q.size();

            }

            // Time Complexity : O(n)

            3.最優化的解決方案:


            如果數據是無序的并且多個命中帶有相同的時間戳怎么辦。


            由于隊列方法在沒有有序數據的情況下無法工作,因此這次使用數組來存儲每個時間單位的命中計數。


            如果我們以 300 秒為單位跟蹤過去 5 分鐘內的命中,則創建 2 個大小為 300 的數組。

            int[] hits = new int[300];


            時間戳[] 次 = 新時間戳[300]; // 最后計數的命中

            的時間戳給定一個傳入,將其時間戳修改 300 以查看它在命中數組中的位置。


            int idx = 時間戳 % 300; => hits[idx] 保持命中計數發生在這一秒


            但在我們將 idx 的命中計數增加 1 之前,時間戳確實屬于 hits[idx] 正在跟蹤的第二個。

            timestamp[i] 存儲最后計數命中的時間戳。

            如果 timestamp[i] > timestamp,這個命中應該被丟棄,因為它在過去 5 分鐘內沒有發生。

            如果 timestamp[i] == timestamp,則 hits[i] 增加 1。

            如果 timestamp[i] currentTime – 300。



            vector<int> times, hits;

              

            times.resize(300);

            hits.resize(300);

              

            /** Record a hit.

               @param timestamp - The current timestamp

               (in seconds granularity). */

            void hit(int timestamp)

            {

                int idx = timestamp % 300;

                if (times[idx] != timestamp) {

                    times[idx] = timestamp;

                    hits[idx] = 1;

                }

                else {

                    ++hits[idx];

                }

            }

              

            // Time Complexity : O(1)

              

            /** Return the number of hits in the past 5 minutes.

                @param timestamp - The current timestamp (in 

                seconds granularity). */

            int getHits(int timestamp)

            {

                int res = 0;

                for (int i = 0; i < 300; ++i) {

                    if (timestamp - times[i] < 300) {

                        res += hits[i];

                    }

                }

                return res;

            }

            // Time Complexity : O(300) == O(1)

            如何處理并發請求?


            當兩個請求同時更新列表時,可能會出現競爭條件。最先更新列表的請求可能最終不會被包含在內。


            最常見的解決方案是使用鎖來保護列表。每當有人想要更新列表(通過添加新元素或刪除尾部)時,都會在容器上放置一個鎖。操作完成后,列表將被解鎖。


            當您沒有大量請求或性能不是問題時,這非常有效。有時放置鎖的成本可能很高,當并發請求過多時,鎖可能會阻塞系統并成為性能瓶頸。


            分發計數器


            當單臺機器獲得太多流量并且性能成為問題時,正是考慮分布式解決方案的最佳時機。分布式系統通過將系統擴展到多個節點,顯著減少了單臺機器的負擔,但同時增加了復雜性。


            假設我們將訪問請求平均分配給多臺機器。我想首先強調平等分配的重要性。如果特定機器比其他機器獲得更多的流量,則系統無法充分利用,在設計系統時考慮到這一點非常重要。在我們的例子中,我們可以獲得用戶電子郵件的哈希值并通過哈希值進行分發(直接使用電子郵件不是一個好主意,因為某些字母可能比其他字母出現得更頻繁)。


            為了計算數量,每臺機器獨立工作,從過去一分鐘開始計算自己的用戶。當我們請求全局編號時,我們只需要將所有計數器相加即可。


            上一篇
            下一篇
            用戶名 Name
            評論 Comment

            聯系我們

            / CONTACT US

            地 址:四川省成都市航空路豐德國際廣場

            郵政編碼:610000

            電 話:18215660330

            傳 真:18215660330

            手機:18215660330

            郵 箱:179001057@qq.com

            投訴郵 箱:179001057@qq.com

            姓名Name
            標題Title
            郵 箱Emali
            聯系電話Tel
            內容Content
            凤凰彩票