Bitmap&hyperloglog&GEO

面試問

1. 記錄對集合中的數據進行統計
2. 在移動應用中，需要統計每天的新增用戶數和第2天的留存用戶數；
3. 在電商網站的商品評論中，需要統計評論列表中的最新評論：
4. 在簽到打卡中，需要統計一個月內連續打卡的用戶數：
5. 在網頁訪問記錄中，需要統計獨立訪客(Unique Visitor,UV)量。

痛點：

類似今日頭條、抖音、淘寶這樣的額用戶訪問級別都是億級的，請問如何處理？

需求痛點

1. 億級數據的收集、清洗、統計、展現
2. 需要：存的進、取得快、多維度

一、統計的類型有哪些

1. 聚合統計

   統計多個集合元素的聚合結果，就是set里面的交差并等集合統計

   

   交并差集和聚合函數的應用

2. 排序統計

   抖音短視頻最新評論留言的場景，請你涉及一個展現列表。考察數據結構和設計思路。

   

   使用zset實現

   

   在面對需要展示最新列表、排行榜等場景時，如果數據更新頻繁或者需要分頁顯示，建議使用zset

3. 二值統計

   集合元素的取值就只有0和1兩種。在釘釘上班簽到打卡的場景中，我們只需要記錄簽到（1）和沒簽到（0）

   一般使用bitmap實現

4. 基數統計

   指統計一個集合中不重復的元素

   一般使用hyperloglog

二、hyperloglog

1. 名詞

   1. UV

      Unique Visitor，獨立訪客，一般理解為客戶端IP

      需要考慮去重

   2. PV

      Page View，頁面瀏覽量

      不用去重

   3. DAU

      Daily Active User，日活躍用戶量，登錄或使用某個產品的用戶數（去掉重復登錄的用戶）

      常用于反映網站、互聯網應用或網絡游戲的運營情況

   4. MAU

      Monthly Active User，月活躍用戶量

2. 需求

   很多計數類場景，比如每日注冊IP數、每日訪問IP數、頁面實時訪問數PV、訪問用戶數UV等。

   因為主要的目標高效、巨量地進行計數，所以對存儲的數據的內容并不太關心。

   也就是說它只能用于統計巨量數量，不太涉及具體的統計對象的內容和精準性。

   統計單日一個頁面的訪問量(PV),單次訪問就算一次。

   統計單日一個頁面的用戶訪問量(UV),即按照用戶為維度計算，單個用戶一天內多次訪問也只算一次。

   多個ky的合并統計，某個門戶網站的所有模塊的PV聚合統計就是整個網站的總PV。

3. 是什么

   1. 基數

      是一種數據集，去重復后的真實個數

      

   2. 去重復統計功能的基數估計算法，就是hyperloglog

      

   3. 基數統計

      用于統計一個集合中不重復的元素個數，就是對集合去重復后剩余元素的計算

   4. 基本命令

      

4. hyperloglog如何實現的，如何演化的

   1. 去重的幾種方法

      • hashset

      • bitmap

        

      • hyperloglog概率算法

        通過犧牲準確率來換取空間，對于不要求絕對準確率的場景下可以使用，因為概率算法不直接存儲數據本身，

        通過一定的概率統計方法預估基數值，同時保證誤差在一定范圍內，由于又不儲存數據故此可以大大節約內存。

   2. 如何做到的？如何演化來的

      只是進行不重復的基數統計，不是集合也不保存數據，只記錄數量而不是具體的內容。

      有誤差：

      ? hyperloglog提供不精確的去重計數方案，犧牲準確率來換取空間，誤差在0.81%左右

      論文和出處：http://antirez.com/news/75

      

   3. 淘寶網站首頁億級UV的Redis統計方案

      1. 需求

         1. UV的統計需要去重，一個用戶一天內的多次訪問只能算一次
         2. 淘寶、天貓首頁的UV，平均每天是1~1.5個億左右
         3. 每天存1.5個億的IP，訪問者來了后先去查是否存在，不存在加入

      2. 方案

         1. 使用redis hash存儲詳細數據

         2. 使用hyperloglog

            

      3. hyperloglog service

      4. hyperloglog controller

三、GEO

面試題說明：

移動互聯網時代LBS應越來越多，交友軟件中附近的小姐姐、外賣軟件中附近的美食店鋪、打車軟件附近的車輛等等。

那這種附近各種形形色色的XXX地址位置選擇是如何實現的？

會有什么問題呢？

1. 查詢性能問題，如果并發高，數據量大這種查詢是要搞垮mysq數據庫的
2. 一般mysql查詢的是一個平面矩形訪問，而叫車服務要以我為中心N公里為半徑的圓形覆蓋。
3. 精準度的問題，我們知道地球不是平面坐標系，而是一個圓球，這種矩形計算在長距離計算時會有很大誤差，mysql不合適

3.1 redis之GEO

經緯度：

如何獲取某個地址的經緯度：使用百度地圖等系統

命令復習：

1. GEOADD:添加經緯度坐標

2. GEOPOS:返回經緯度

3. GEOHASH：返回坐標的geohash，geohash算法生成的base32編碼值

   

4. GEODIST：兩個位置之間距離

5. GEORADIUS：查找距離中心位置小于XX距離的地點

6. GEORADIUSBYMEMBER

四、bitmap

1. 命令復習

   

2. 需求和解決方案

   

3. bitmap解決方法