數(shù)據(jù)庫(kù)大概存儲(chǔ)幾十萬(wàn)條IP記錄，記錄集如下：


+----------+----------+------------+---------+---------+--------+--------+ 
| ip_begin | ip_end   | country_id | prov_id | city_id | isp_id | netbar | 
+----------+----------+------------+---------+---------+--------+--------+ 
|        0 | 16777215 |          2 |       0 |       0 |      0 |      0 | 
| 16777216 | 33554431 |          2 |       0 |       0 |      0 |      0 | 
| 33554432 | 50331647 |          2 |       0 |       0 |      0 |      0 | 
| 50331648 | 67108863 |          3 |       0 |       0 |      0 |      0 | 
| 67108864 | 67829759 |          3 |       0 |       0 |      0 |      0 | 
+----------+----------+------------+---------+---------+--------+--------+ 
　　這樣做查詢需要用到如下SQL：
<?php
$sql = 'SELECT * FROM i_m_ip WHERE ip_begin <= $client_ip AND ip_end >= $client_ip';
?>
　　這樣的檢索顯然用不到索引，即使用到，MySQL查詢效率也不大可能達(dá)到每秒500次以上，我做了很多并發(fā)優(yōu)化，最終平均查詢效率也只有每秒200次左右，實(shí)在是頭痛。一開(kāi)始我也有想到借鑒純真IP庫(kù)的檢索方法，但是我一直對(duì)算法有抵觸，也以為二分法很難，所以就沒(méi)有嘗試使用，直到最后沒(méi)有辦法了，才最終實(shí)現(xiàn)了二分法的IP地址檢索。
　　從上表可以看到IP庫(kù)是從0到4294967295的一個(gè)連續(xù)數(shù)值，這個(gè)數(shù)值要是拆開(kāi)存儲(chǔ)，會(huì)有幾百G的數(shù)據(jù)，所以沒(méi)辦法使用索引也沒(méi)辦法哈希。最終我使用PHP將這些東東轉(zhuǎn)為二進(jìn)制存儲(chǔ)，拋棄了數(shù)據(jù)庫(kù)的檢索?？梢钥吹絀P起止長(zhǎng)度為一個(gè)4字節(jié)的長(zhǎng)整型，后面的國(guó)家ID、省份ID等，可以使用2個(gè)字節(jié)的短整型來(lái)存儲(chǔ)，總共一行數(shù)據(jù)就有18個(gè)字節(jié)，總共31萬(wàn)條數(shù)據(jù)，算起來(lái)也就5M的樣子。具體IP庫(kù)生成代碼如下：
<?php
/*
IP文件格式：
3741319168    3758096383    182    0    0    0    0
3758096384    3774873599    3    0    0    0    0
3774873600    4026531839    182    0    0    0    0
4026531840    4278190079    182    0    0    0    0
4294967040    4294967295    312    0    0    0    0
*/
set_time_limit(0);
$handle = fopen('./ip.txt', 'rb');
$fp = fopen("./ip.dat", 'ab');
if ($handle) {
    while (!feof($handle)) {
        $buffer = fgets($handle);
        $buffer = trim($buffer);
        $buffer = explode("\t", $buffer);
        foreach ($buffer as $key => $value) {
            $buffer[$key] = (float) trim($value);
        }
        $str = pack('L', $buffer[0]);
        $str .= pack('L', $buffer[1]);
        $str .= pack('S', $buffer[2]);
        $str .= pack('S', $buffer[3]);
        $str .= pack('S', $buffer[4]);
        $str .= pack('S', $buffer[5]);
        $str .= pack('S', $buffer[6]);
        fwrite($fp, $str);
    }
}
?>

　　這樣IP就按照順序每18字節(jié)一個(gè)單位排列了，所以很容易就使用二分法來(lái)檢索出IP信息：
function getip($ip, $fp) {
    fseek($fp, 0);
    $begin = 0;
    $end   = filesize('./ip.dat');
    $begin_ip = implode('', unpack('L', fread($fp, 4)));
    fseek($fp, $end - 14);
    $end_ip   = implode('', unpack('L', fread($fp, 4)));
    $begin_ip = sprintf('%u', $begin_ip);
    $end_ip   = sprintf('%u', $end_ip);

    do {
        if ($end - $begin <= 18) {
            fseek($fp, $begin + 8);
            $info = array();
            $info[0] = implode('', unpack('S', fread($fp, 2)));
            $info[1] = implode('', unpack('S', fread($fp, 2)));
            $info[2] = implode('', unpack('S', fread($fp, 2)));
            $info[3] = implode('', unpack('S', fread($fp, 2)));
            $info[4] = implode('', unpack('S', fread($fp, 2)));
            return $info;
        }

        $middle_seek = ceil((($end - $begin) / 18) / 2) * 18 + $begin;

        fseek($fp, $middle_seek);
        $middle_ip = implode('', unpack('L', fread($fp, 4)));
        $middle_ip = sprintf('%u', $middle_ip);

        if ($ip >= $middle_ip) {
            $begin = $middle_seek;
        } else {
            $end = $middle_seek;
        }
    } while (true);
}

　　以上$fp為打開(kāi)ip.dat的文件句柄，由于是循環(huán)檢索，所以寫(xiě)在函數(shù)外面，免得每次檢索都要打開(kāi)一次文件，30W行數(shù)據(jù)二分法最多也只需要循環(huán)7次(2^7)左右即可找到準(zhǔn)確的IP信息。之后本來(lái)還想將ip.dat放在內(nèi)存中加快檢索速度，后來(lái)發(fā)現(xiàn)，字符串定位函數(shù)的效率，根本和文件指針的偏移定位不是在一個(gè)數(shù)量級(jí)的，所以還是放棄使用內(nèi)存來(lái)存放IP庫(kù)。
　　這個(gè)實(shí)現(xiàn)，使IP檢索效率提高了近百倍，只是一個(gè)簡(jiǎn)單的二分法的應(yīng)用，從此算法在WEB應(yīng)用中不重要的觀念徹底打消了。其實(shí)要實(shí)現(xiàn)這個(gè)，我還請(qǐng)教了金狐，我一開(kāi)始是請(qǐng)他幫我生成一個(gè)純真格式的IP庫(kù)，然后用Discuz的IP查詢函數(shù)來(lái)檢索，不過(guò)他不肯幫我，最后造就了我的這個(gè)實(shí)踐和學(xué)習(xí)。有時(shí)候，求人不如求己。

最新評(píng)論