源于公眾號Java藝術 ,
作者wujiuye
我先說下結果。我現在還不敢放線上去測,這是本地測的數據,我4g內存的電腦本地開redis,一次都沒寫完過全部數據,都是寫一半后不是redis掛就是測試程序掛。可以肯定的是總記錄數是以千萬為單位的。O(log(n千萬/range))的時間復雜度,本地測的結果我并不滿意,7ms的時間,太久了。這個數量級的數據,就算內存緩存也很花時間,因為并不是簡單的key-value,涉及到范圍查找。
使用Sorted Set實現范圍查找
最近系統需要更新IP庫,IP庫存儲的是IP所屬的國家和城市信息,廣告主投放廣告會有區域限制,所以需要根據點擊廣告的終端ip,獲取位置信息,并判斷是否滿足廣告投放區域的要求。
最頭疼的是,IP信息庫是按區間存儲的,拿到一個ip得要知道它所屬的范圍才能知道它對應哪條記錄。它的表結構是這樣的:
Ip_from,ip_to,ccountry_code,country,regin,city
Ip起始段,Ip結束段,國家編碼,國家,區域(比如中國的省),城市
而Ip_from和ip_to是一個數值,將ip通過公式轉化后的數值。
a.b.c.d
A*(256*256*256)+b*(256*256)+c*(256)+d
為了效率,程序中的轉換可以寫為
a*(1<<24)+b*(1<<16)+c*(1<<8)+d
在此之前我都沒注意以前是怎么實現查找的,以前是用內存緩存實現,但以前的數據比較少,而查找的方式用的遞歸,先不說遞歸查找算法的缺陷。而新的ip庫數據量很大,本地debug直接OOM,沒有足夠的內存撐起這么大的ip庫。
如果說,一個csv文件的大小是1g多,那么讀取到jvm中,就需要4g甚至更高的內存,因為一個對象占的內存是比一行逗號隔開的字符串耗更大的內存。要實現查找算法,創建對應的數據結構,這些也會占用很大的內存。
綜上所述,我們考慮用redis來緩存,當然,也可以用mongodb,如果是用mongodb緩存,那就簡單了。既然要用Redis,那么就不得不面對,Redis如何實現范圍查詢,還要支持高并發。這算是一道難題了。
插入一段內容,關于如果使用Sorted Set實現范圍查找,就是sql中的大于等于and小于等于。(下面是我參考的一篇博客,我覺得他的實現有些雞肋,完全可以用一條:
zadd myset 1015 1011-1015-v1 替代兩條記錄)。
服務端對于客戶端不同的版本區間會做些不同的配置,那么客戶端一個版本過來怎么快速的定位是屬于哪個版本區間呢?可以利用Sorted Sets的zrangebyscore命令。
zadd myset 1011 v1_start
zadd myset 1015 v1_end
zadd myset 1018 v2_start
zadd myset 1023 v2_end
如上我們像myset里插入了4條數據,代表的意思是版本區間v1是從1011-1015版本,版本區間v2是從1018-1023版本。
https://www.cnblogs.com/zhanjindong/p/3549994.html
那么我現在如何判斷1014版本屬于哪個區間呢,使用zrangebyscore如下操作:
zrangebyscore myset 1014 +inf LIMIT 0 1
1)v1_end
返回v1_end說明1014屬于版本區間1,上面的這個命令的意思是在myset中查找第一個score值大于等于1014的member,如果我們查找一個不在區間內的版本,比如1016:
zrangebyscore myset 1014 +inf LIMIT 0 1
1)v2_start
https://www.cnblogs.com/zhanjindong/p/3549994.html
首先,我想到的是利用Redis的有序集合Sorted Set,存儲每條記錄的ip區間,或者叫ip范圍。ip_to列作為有序集合的score。如:
zadd ip-country-city-locations-range 3756871679 3756871424~3756871679
這樣就可以查詢一個ip對應的score落在哪個區間,找出符合條件的第一個區間。如:
(1)將ip轉為number,假設得到的值為:3756871650 (2)使用zrangebyscore命令獲取所在區間 zrangebyscore ip-country-city-locations-range 3756871650 +inf 0 1
因為3756871650比3756871424~3756871679區間的end值3756871679小于等于,所以匹配到這條記錄。但拿到這條記錄后并不能說明3756871650在這個區間內,所以還要比較
3756871424<=3756871650<=3756871679
因為會存在這種情況,該區間與前一個區間并不是連續的,比如。
(1)3756870911=>3756870656~3756870911 (2)3756871679=>3756871424~3756871679
明顯,這兩個區間之間存在斷層。但可以肯定的是,如果不落在區間(2)中,也不會落在區間(1)。所以不滿足就可以直接返回null了。
Ip庫用hash類型存儲,field取ip_from或者ip_from&ip_to,value當然就是存完整的一行記錄了。最后就可以根據拿到的區間信息獲取到對應記錄的field,使用hget命令就能獲取到最終的一行ip信息記錄。
hget ip-country-city-locations 3756871424
這并不難實現,但是,耗時卻非常嚴重,可以看下官方文檔介紹的Sorted Set的zrangebyscore的時間復雜度。IP庫保守估計百萬條記錄,如果就這樣上線,百分百又是服務雪崩。
改進思路:區間+Sorted Set
由于Sorted Set有序集合的查詢時間復雜度是O(log(n)+m),其中n是總記錄數,m是此次查詢獲取的記錄數,在limit 0 1的情況下是O(log(n)),所以一個有序集合的元素個數越多,它的查詢時間耗時越長。對于一般的應用場景,如排行榜,都是只有極少數的幾百條記錄。而如果用于ip庫的區間查詢實現,記錄上百萬條,而且還是用于高并發場景,不把服務搞垮才怪了。
既然我們要用Sorted Set,但又不能讓集合的元素過大,那么我們可以分n/m個區間存儲啊。假設有一百萬條記錄,每個Sorted Set存儲1000條,那就用1000個Sorted Set集合來存儲。hash的查詢時間復雜度是接近O(1)的,增加1000個key在分槽位的分布式集群下根本不算什么。
按照上面的思路改進后,獲取一個ip的國家城市信息就變成如下步驟:
1、根據ip計算出一個number值
比如:3756871650
2、根據區間大小(這一步的區間指的是每個Sorted Set的最大大小),計算出該number所在的集合的key
比如:ip-country-city-locations-range-375
3、根據這個key,去Sorted Set查詢number所屬的區間。
比如:zrangebyscore ip-country-city-locations-range 3756871650 +inf 0 1
5、拿到區間信息后,從區間信息獲取ip范圍位置信息的 field(hash類型存儲)
比如查詢結果區間信息為:3756871424~3756871679拿到field就是:3756871424
6、根據key和field拿到目標記錄。
hget ip-country-city-locations 3756871424
編碼實現
我將實現封裝成一個組件,目的是對外提供更簡單的使用方式,封裝復雜的實現邏輯,同時,內部的改動對使用者無感知。通過SPI+分層設計,利用靜態代理模式等,使得組件具有極強的擴展性,如果某天想改成使用mongodb或者內存緩存,只需要實現幾個接口就可以了。
下面是README.MD的內容
關于數據源表的初始化
使用需要配置update啟動參數:
-Dip.database.table.update=true
如:
java -Xss256k-jar -Dip.database.table.update=true xxx-1.0.0.jar
true: 首次啟動就會從指定的url文件讀取解析記錄,插入數據表 false: 表示已經確認表存在記錄了,不需要再更新。(也不會去解析文件) 默認:false
解析記錄與插入表是異步的,后臺開啟一個線程執行。耗時根據文件大小決定,我測的是86s
配置使用表
使用了java的SPI
需要指定使用哪個文件解析器,也就對應使用哪種類型的表
配置redis操作實現類
使用了java的SPI
如果解析配置使用了
com.chestnut.ip.database.parser.RedisIP2LocationFileParser
則需要自己實現RedisOperation,并在
com.chestnut.ip.database.suppor.IP2LocationRedisOperation
文件中配置redis操作的實現類
緩存的key
如果使用redis存儲數據,則key固定為
ip-country-city-locations // 存儲真實記錄ip-country-city-locations-range-* // 存儲范圍與真實記錄的key的映射
其中ip-country-city-locations-range-后面的代表的分區索引
們查ip的時候都是利用ip138查詢的,不過那個有時候是不準確的,還不如自己引用淘寶的ip庫來查詢,這樣準確度還高一些。不多說了,介紹一下:
淘寶IP地址庫,淘寶公布了他們的IP庫http://ip.taobao.com/,還有REST API接口,不過每個用戶的訪問頻率需小于10qps,訪問方 式:http://ip.taobao.com/service/getIpInfo.PHP?ip=[ip地址字串],返回內容以json格式的。具有IP查詢,IP統計等功能。各大運營商擁有的IP數等信息。接下來介紹一下獲取ip的實例:
/**
* 通過淘寶IP接口獲取IP地理位置
* @param string $ip
* @return: string
**/
function getCity($ip)
{
$url="http://ip.taobao.com/service/getIpInfo.php?ip=".$ip;
$ipinfo=json_decode(file_get_contents($url));
if($ipinfo->code=='1'){
return false;
}
$city = $ipinfo->data->region.$ipinfo->data->city;
return $city;
}
header("Content-type:text/html;charset=utf-8");
// 這樣調用,顯示山東省臨沂市
var_dump(getCity("112.234.69.189"));
?>
調用的時候吧固定的ip替換成你想查詢的ip就可以了。
近在使用爬蟲爬取數據時,經常會返回403代碼,大致意思是該IP訪問過于頻繁,被限制訪問。限制IP訪問網站最常用的反爬手段了,其實破解也很容易,就是在爬取網站是使用代理即可,這個IP被限制了,就使用其他的IP。對于高大上的公司來說,他們基本都使用收費的代理,基本不會有什么問題,比較穩定。像我這樣的矮矬窮,肯定是用不起收費的代理。一般都是使用國內免費的代理,網上也有很多提供免費的代理。
很多人都是從網上爬取一批免費的代理IP,存放在存儲媒介中,例如excel文件或者數據庫。定時維護代理,保證代理可用。這個做法有個缺點,有些機器上并沒有裝有excel或者mysql、redis等數據庫,這就導致了的代理池無法正常使用。
我之前是做java開發的,經常會把一些常用的數據放在ArrayList中,使用起來非常方便,效率高,因此借鑒之前在java方面的經驗,將代理IP爬取下來存放在list列表中中,將list列表當做一個代理池,經常維護這個池里的代理。
我經常爬取免費代理的網站xicidaili
swei360等,這些免費的代理足夠我使用了,能夠應付大多數的爬蟲工作。爬取過程需要用到requests和pyquery庫,沒有安裝的同學自行安裝。
首先介紹下爬取xicidaili網站的過程,
要先定義一個方法用于抓取xicidaili網站的,參數有兩個,一個是url,另外一個是要爬取代理網頁的頁數,也就是要爬幾頁,方法如下:
def get_xicidaili_proxy(url,page): for i in range(1,page): headers = { "User-Agent": "Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 SE 2.X MetaSr 1.0"} response = requests.get(url + str(i), headers=headers) html = response.text doc = pq(html) ip_list = doc('#ip_list')('tr:gt(0)').items() for item in ip_list: ip = item.find('td:nth-child(2)').text() port = item.find('td:nth-child(3)').text() http_type = item.find('td:nth-child(6)').text() proxy_ip = http_type + "://" + ip + ":" + port if http_type == 'HTTP': http_proxy_pool.append(proxy_ip) elif http_type == 'HTTPS': https_proxy_pool.append(proxy_ip) # print(proxy_ip)
定義了http_proxy_pool和https_proxy_pool兩個list變量,用于存儲http類型和https類型的代理。 使用PyQuery根據css偽選擇器提取出ip,端口和http類型信息,并按照http:// + ip+port的方式組合成一個字符串,存儲在已經定義好的http_proxy_tool和https_proxy_pool變量中。
爬取swei360網站代理的方法就不貼出來了,原理和爬取xicidaili網站是一樣的。
一個代理在使用之前要判斷是否可用,我們使用request的get請求的返回代碼判斷代理是否可用,返回200,就說明代理可用,返回其他的代碼就表示代理不可用,代碼如下:
def detect_proxy(test_url,http_type,proxy): headers = { "User-Agent": "Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 SE 2.X MetaSr 1.0"} proxy={ http_type : proxy } try: response = requests.get(test_url,proxies=proxy,headers=headers) if response.status_code in [200]: print('代理可用',proxy) return True else: print('代理不可用', proxy); delete_proxy(http_type,proxy) return False except(requests.exceptions.ProxyError,RequestException): print('代理不可用', proxy) delete_proxy(http_type, proxy) return False
定義了detect_proxy方法用于檢測代理是否可用,有三個參數,分別是測試網址,代理類型(http和https)和代理IP。當requests的請求返回200代碼時,就表示該代理可用,返回True,否則就是不可用,返回False。當遇到request異常或者其他的錯誤也認為代理不可用,返回False。對于不可用的代理,要從代理池中刪除。
從代理池中獲取代理時,我們使用的是從代理池中隨機返回一個代理,這樣就避免經常使用一個代理,從而遭到拒絕訪問。代碼如下:
def get_https_proxy(): proxy_ip = random.choice(https_proxy_pool) return proxy_ip def get_http_proxy(): proxy_ip = random.choice(http_proxy_pool) return proxy_ip
為了保證代理的可用,當檢測到一個代理不可用時,要及時的清理掉。就是從http_proxy_pool和https_proxy_pool列表中刪除。
一個簡單的爬蟲代理池已經搭建好,總結下爬蟲代理池搭建的過程:
這個代理池其實相當的簡單,有一個弊端就是在檢測代理是否可用時,如果返回的不是200代碼就認為代理不可用,返回其他代碼的情況有很多,例如網絡不可用、測試網站不可訪問等。比較好的做法是給每個代理設置一個分值,例如10分,如果檢測到不可用就減1,當分數為0時,就確定該代理不可用,直接從代理池中移除。檢測到代理可用,就將分數設為10分。這種做法給每個檢測到不可用代理一個改邪歸正的機會,不至于一刀切的拋棄掉。
作者:Summer哥
出處:www.bigdata17.com
*請認真填寫需求信息,我們會在24小時內與您取得聯系。