Lorsqu’on développe une application web et qu’on souhaite une audience qui, sans forcément être mondiale, dépasse quand même les frontière de son pays, on est forcément amené à traiter de géolocalisation, même un peu. Connaître le pays d’où viennent vos visiteurs vous permet de mieux localiser l’interface, adapter l’offre ou encore respecter des contraintes légales éventuelles.

Comme on l’a vu précédemment, si vous n’avez pas besoin de plus précis que le pays, vous pouvez obtenir vos données directement auprès des Registres Internet Régionaux via leurs fichiers de délégation qui contiennent tout ce dont vous avez besoin. C’est librement accessible et mis à jours quotidiennement.

Après avoir surtout vu le côté théorique, nous allons aujourd’hui mettre les mains dans le cambouis et construire notre propre base de géolocalisation, utilisable dans nos applications.

La base de donnée

Pour rester simple et relativement universel, je vais utiliser du PHP pour effectuer les opérations et une base sqlite pour organiser et stocker les données. Sur une Debian ou dérivée, vous pouvez installer tout le nécessaire avec le gestionnaire de paquets comme suit :

sudo apt-get install php-cli php-sqlite3

Si vous êtes dans une autre situation ou avez des contraintes particulières, vous pouvez toujours utiliser d’autres systèmes, langages et structures de stockage, il faudra simplement traduire au fur et à mesure…

Maintenant que l’environnement est prêt, on va enfin pouvoir coder. Et comme je préfère les choses propres, je vais encapsuler la base de donnée dans une classe et je vais la compléter petit à petit. L’intérêt, c’est aussi de pouvoir suivre le patron RAII en initialisant tout dans le constructeur.

class Database {
    
    private $pdo ;

    public function __construct($filename) {
        $this->pdo = new PDO("sqlite:$filename") ;
        
        // Parce que je préfère les exceptions :
        $this->pdo->setAttribute(
            \PDO::ATTR_ERRMODE,
            \PDO::ERRMODE_EXCEPTION
        ) ;

        // Définies plus loin
        $this->initIPv4() ;
        $this->initIPv6() ;
    }
    
    // ...
}

Réseaux IP version 4

Je vais commencer par traiter les adresses IP version 4 car elles sont plus simples et nous permettront de poser les bases pour la suite.

Le table SQL

Plutôt que de stocker le réseau avec la longueur du préfixe, on va le stocker sous sa forme d’intervalle ouvert $[debut,fin[$ avec la première et dernière adresse du réseau. Ça nous évitera des calculs de préfixes pour comparer les réseaux et les adresses.

Même si on les écrits avec 4 nombres décimaux, fondamentalement, les adresses IP version 4 ne sont que des entiers 32 bits (non signés pour être précis). En SQL, on peut donc les stocker dans un int unsigned, ce qui sera bien pratique, entre autre pour les futures comparaisons.

Tourisme… petite particularité de sqlite, tous les entiers sont en fait manipulés comme des INTEGER (entiers 64 bits) puis tronqués lors de l’écriture à la précision idoine.

create table if not exists IPv4 (
    start   int unsigned,
    end     int unsigned,
    country varchar(2)
);

Dernière optimisation, vu qu’on va utiliser cette table pour faire des recherches, on va ajouter des indexes aux colonnes start et end. L’intérêt c’est qu’on passera d’une complexité en $O(n)$ à un complexité en $O(\log n)$ pour les recherches. Vous verrez plus loin que ça n’est pas que théorique…

create index if not exists index_ipv4_start on IPv4(start);
create index if not exists index_ipv4_end   on IPv4(end)  ;

Avec ça, on a tout ce qu’il faut pour initialiser la table IPv4 via la méthode suivante :

private function initIPv4() {
    $this->pdo->query("
            create table if not exists IPv4 (
                start   int unsigned,
                end     int unsigned,
                country varchar(2)
            )") ;
    $this->pdo->query("
            create index if not exists index_ipv4_start on IPv4(start)
            ") ;
    $this->pdo->query("
            create index if not exists index_ipv4_end on IPv4(end)
            ") ;
}

Ajouter un réseau

Pour ajouter un réseau, on va convertir l’adresse IP en entier grâce à la fonction ip2long() faite justement pour ça. Comme les RIR fournissent le nombre d’adresses pour les IPv4 (et pas un préfixe), on va donc l’ajouter à cette valeur pour avoir la dernière du réseau.

Défense en profondeur : même si je sais que cette fonction sera appelée avec des adresses IP, j’ai l’habitude de toujours préparer mes requêtes pour ensuite leur lier leurs paramètres et éviter ainsi les injections SQL quoi qu’il arrive.

public function addIPv4($addr, $count, $country) {
    $start = ip2long($addr) ;
    $st = $this->pdo->prepare(
        "insert into IPv4 (start, end, country)"
        . " values (:start, :end, :country)"
    ) ;
    $st->execute([
        "start"   => $start,
        "end"     => $start + $count,
        "country" => $country
    ]) ;
}

Chercher une adresse

Pour trouver le pays d’une adresse, vu qu’on utilise des intervalles, on peut simplement chercher la ligne dont les bornes encadrent la valeur.

Tourisme… Pour gérer le cas où aucun réseau n’existe, j’utilise l’opérateur NULL coalescent ?? (qui me retourne son deuxième argument si le premier est NULL ou n’existe pas), une nouveauté de PHP7. L’avantage sur l’opérateur ternaire simplifié ?:, c’est qu’il n’y a pas de warning si le premier argument n’existe pas.

public function getIPv4($ip) {
    $value = ip2long($ip) ;
    $st = $this->pdo->prepare("
            select * from IPv4
            where
                start  <= :value and
                :value <  end
            ") ;
    $st->execute(["value" => $value]) ;
    $row = $st->fetch() ;
    return $row["country"] ?? "ZZ" ;
}

On peut aussi profiter que les réseaux soient disjoints pour éviter des comparaisons inutiles. Dans ce cas, on va chercher les intervalles dont le début est plus petit que notre adresse, puis garder le plus grand d’entre eux.

Comme certains réseaux sont réservés et n’apparaissent pas dans la base (i.e. 192.168.0.0/16), il y a des trous. Pour une adresse réservée, la requête retournera un intervalle mais qui ne la couvrira pas. Il faut donc, en PHP, vérifier que le réseau fourni est bon.

public function getIPv4($ip) {
    $value = ip2long($ip) ;
    $st = $this->pdo->prepare("
            select * from IPv4
            where start <= :value
            order by start desc
            limit 1
            ") ;
    $st->execute(["value" => $value]) ;
    $row = $st->fetch() ;
    if ($row === false || $row["end"] < $value) {
        return "ZZ" ;
    }
    return $row["country"] ;
}

Comparaisons

L’intérêt de faire des variantes, c’est de les comparer. J’ai donc généré 2500 adresses aléatoires pour lesquelles j’ai demandé une recherche en base avec l’un ou l’autre des algorithmes. Et pour les petits malins qui se disent qu’on pourrait bénéficier des deux versions en gardant le test sur les deux bornes et chercher le début de réseau le plus grand, j’ai aussi utilisé cette variante (que j’ai appelé hybride mais que je n’ai pas ajouté ici).

Et pour être vraiment exhaustif, j’ai fait ces tests avec et sans indexes sur les bornes des intervalles. Pour vous montrer à quel point un indexe, ça change la vie.

Pour les mesures, j’ai réutilisé mon profiler PHP qui me permet de mesurer l’exécution d’une fonction particulière tout en restant très simple.

Voici les résultats bruts, les durées sont exprimées en secondes (avec les millisecondes après la virgule). Les tests sont fait avec une Ubuntu 18.04.4 utilisant deux processeurs Intel® Xeon® X5670. Notez que le script n’utilise qu’un cœur à la fois :

Sans surprise, la théorie est conforme a la réalité : les indexes accélèrent vraiment les requêtes (on divise le temps par 1000). Deuxième lapalissade ; plus la requête est simple, plus elle est performante (la version hybride ne tire pas autant de bénéfice des indexes).

Réseaux IP version 6

Pour les adresses IP en version 6, on va devoir adapter légèrement les structures et algorithmes précédents. Rien de bien méchant mais ça mérite une section à part.

La table SQL

Comme précédemment, on va stocker les intervalles sous la forme $[debut, fin[$. Ce sera bien plus pratique que de devoir comparer des préfixes IPv6 et gérer ses particularités d’écritures (i.e. RFC 4291). Par contre, comme ces adresses font 128 bits, ça ne rentre plus directement dans un entier et il va falloir choisir une modélisation adaptée.

Une chaîne hexadécimale. On peut directement traduire les 128 bits dans une chaîne hexadécimale de 32 caractères et la stocker dans un varchar(32). Pour ça, je vais utiliser la fonction inet_pton() pour obtenir ces 128 bits puis hex2bin() pour avoir les 32 caractères.

public static function ip6toString($ip) {
    $bin = inet_pton($ip) ;
    $hex = bin2hex($bin) ;
    return $hex ;
}

La notion d’intervalles reste possible et on peut utiliser des indexes mais comme il s’agit de chaînes de caractères, je trouve leur manipulation moins pratique qu’avec des entiers.

Deux entiers 64 bits. Pour accélérer les comparaisons, plutôt que 32 caractères (des entiers entre 0 et 255 en fait), on peut les regrouper en deux entiers 64 bits non signés. Cette fois, on va utiliser la fonction unpack() pour transformer les 128 bits en un tableau de 2 entiers 64 bits.

Tourisme… la fonction unpack(), retourne un tableau associatif. Lorsque vous demandez plusieurs éléments du même type, la numérotation débute à 1 (et non 0).

public static function ip6toInts($ip) {
    $bin  = inet_pton($ip) ;
    $ints = unpack("J2", $bin) ;
    return [$ints[1], $ints[2]] ;
}

La comparaison sera plus rapide mais il va falloir la coder nous même en comparant d’abord les entiers de poids forts puis, s’ils sont égaux, ceux de poids faible. En PHP, on aurait quelque chose de ce genre :

public static function isLessThan($lhs, $rhs) {
    return $lhs[0] < $rhs[0] || ($lsh[0] == $rhs[0] && $lsh[1] < $rhs[1]) ;
}

C’est déjà pas super pratique en PHP alors vous imaginez s’il faut écrire ce genre de chose dans toutes les requêtes SQL  ? Ça marchera, mais c’est pas franchement pratique.

Un entier 64 bits. Le truc, c’est que les Registres Internet Régionaux n’allouent pas de préfixe plus grand que 48 bits (RFC 2450) Il est donc inutile de garder les 64 derniers bits des adresses puisqu’ils n’auront aucune influence sur les calculs.

Suivant cette norme, il est aussi inutile de garder les 16 bits au delà du 48^ème mais on va les garder pour deux raisons : 1. Il n’y a pas de format de stockage d’entiers sur 3 octets (48 bits), 2. Les RIR ont quand même découpé des réseaux dont le préfixe fait entre 59 et 64 bits…

public static function ip6toBigInt($ip) {
    $bin = inet_pton($ip) ;
    $ints = unpack("J2", $bin) ;
    return $ints[1] ;
}

Pour le stockage, on va donc utiliser un seul bigint unsigned pour les bornes et, comme précédemment, ajouter un indexe sur chacune d’entre elle.

private function initIPv6() {
    $this->pdo->query("
            create table if not exists IPv6 (
                start   bigint unsigned,
                end     bigint unsigned,
                country varchar(2)
            )") ;
    $this->pdo->query("
            create index if not exists index_ipv6_start on IPv6(start)
            ") ;
    $this->pdo->query("
            create index if not exists index_ipv6_end on IPv6(end)
            ") ;
}

Ajouter un réseau

Cette fois, la particularité vient des fichiers de délégations qui, pour les adresses IP version 6 ne fournissent pas le nombre d’adresses dans le réseau mais son préfixe. Il faut donc, à partir du préfixe, calculer le nombre à ajouter pour obtenir la borne de fin de l’intervalle.

public function addIPv6($addr, $prefix_length, $country) {
    $start = self::ip6toBigInt($addr) ;
    $count = 1 << (64 - $prefix_length) ;
    $st = $this->pdo->prepare(
        "insert into IPv6 (start, end, country)"
        . " values (:start, :end, :country)"
    ) ;
    $st->execute([
        "start"   => $start,
        "end"     => $start + $count,
        "country" => $country
    ]) ;
}

Chercher une adresse

Avec nos conventions précédentes, l’algorithme de recherche ne changera pas. On utilise simplement notre fonction ip6toBigInt() pour la conversion avant la recherche.

public function getIPv6($ip) {
    $value = static::ip6toBigInt($ip) ;
    $st = $this->pdo->prepare("
            select * from IPv6
            where start <= :value
            order by start desc
            limit 1
            ") ;
    $st->execute(["value" => $value]) ;
    $row = $st->fetch() ;
    if ($row === false || $row["end"] < $value) {
        return "ZZ" ;
    }
    return $row["country"] ;
}

Comparaisons

Cette fois, ce sont les variantes de modélisation que nous allons comparer : l’entier 64 bits que j’ai choisi de vous montrer versus la chaîne de 32 caractères hexadécimaux. La version à deux entiers n’ajoutant rien d‘utile, je n’ai pas pris la peine de l’ajouter.

Les tests sont les mêmes que précédemment : trouver le pays pour 2500 adresses générées aléatoirement. C’est toujours la même machine et les temps sont en secondes :

On voit, encore une fois, l’intérêt d’ajouter des indexes ; le temps est divisé par 300. Par contre, les variantes sont sensiblement équivalentes, c’est normal car le temps dépend surtout du parcours de l’index qui, dans notre cas, est équivalent pour ces deux données.

Tourisme… Même s’il y a 4 fois plus de réseaux IPv4 que de réseaux IPv6, les temps de recherches sont aussi équivalents. C’est normal et, encore une fois, dû aux indexes et surtout à leur complexité de recherche logarithmique en $O(\log n)$ :

Multiplier la taille de l’ensemble va donc ajouter un temps constant et pas le multiplier.

$$\begin{split} \log(20000) & = \log(50000 \times 4) \\ & = \log(50000) + \log(4) \\ & = 4,6990 + 0,6021 \\ & = 5,3031 \\ \end{split}$$

Dans notre cas, multiplier la taille de l’ensemble par 4 ajoute 14% de temps. Un temps d’exécution de 0,121 secondes pour la recherche des adresses IPv4 devrait nous donner théoriquement 0,137 secondes pour IPv6, très proche de nos mesures.

Mise à jour

Maintenant que notre classe peut répondre aux requêtes et est prête à accueillir des données, on peut s’attaquer aux fichiers mis à disposition des Registres Internet Régionaux.

Comme on est parti pour faire les choses propres, je vais continuer en scindant la mise à jours en plusieurs fonctions qui n’ont qu’une responsabilité chacune.

Purge

Comme on ne met pas la base à jours très souvent (une fois par jour), on peut se permettre de faire un code plus simple qui vide la base avant de tout y réintégrer. L’alternative serait plus complexe car il faudrait, pour chaque réseau, traiter les cas où des réseaux ont été regroupés ou divisés, et donc toute une logique qui n’est finalement, pas utile.

private function purge() {
    $this->pdo->query("delete from ipv4") ;
    $this->pdo->query("delete from ipv6") ;
}

Un fichier

On peut maintenant ajouter un fichier de délégation fourni (via son URL). Il faut d’abord récupérer son contenu, via file_get_contents() qui, ça tombe bien, peut récupérer des fichiers fia FTP. On pourra ensuite filtrer les lignes de commentaires (commençant par #), séparer en colonnes (séparées par |) et traiter les enregistrements ipv4 et ipv6.

Tourisme… Par défaut, sqlite va enregistrer toutes les modifications de la base dans le fichier à chaque fois, ce qui peut générer autant d’entrées/sorties et donc ralentir le programme. Pour l’éviter, on va regrouper toutes les opérations dans une transactions. Les modifications seront écrites ensemble lors du commit.

private function addDelegationFile($url) {
    $this->pdo->beginTransaction() ;

    $content = file_get_contents($url) ;
    foreach (explode("\n", $content) as $line) {
        // Commentaires dans le fichier
        if (strpos($line, "#") === 0) {
            continue ;
        }

        $row = explode("|", $line) ;
        // lignes à ignorer : vides ou en-tête ou résumés
        if (count($row) == 1 || is_numeric($row[0]) || $row[1] == "*") {
            continue ;
        }
        
        // enregistrements non utilisés
        if ($row[1] == "" || $row[5] == "" || $row[6] == "available") {
            continue ;
        }
        
        // Les enregistrements utiles
        switch($row[2]) {
            case "ipv4" :
                $this->addIPv4($row[3], $row[4], $row[1]) ;
                break ;
            case "ipv6" :
                $this->addIPv6($row[3], $row[4], $row[1]) ;
                break ;
        }

    }
    $this->pdo->commit() ;
}

Globale

Ne reste donc plus qu’à organiser la logique de mise à jours : vider la table puis ajouter les fichiers un par un.

public function update() {
    $this->purge() ;

    $urls = [
        "ftp://ftp.afrinic.net/pub/stats/afrinic/delegated-afrinic-extended-latest",
        "ftp://ftp.apnic.net/pub/stats/apnic/delegated-apnic-extended-latest",
        "ftp://ftp.arin.net/pub/stats/arin/delegated-arin-extended-latest",
        "ftp://ftp.lacnic.net/pub/stats/lacnic/delegated-lacnic-extended-latest",
        "ftp://ftp.ripe.net/pub/stats/ripencc/delegated-ripencc-extended-latest",
    ] ;

    foreach ($urls as $url) {
        $this->addDelegationFile($url) ;
    }
}

Comparaisons

Pour cette dernière partie, j’ai fait une comparaison du temps de mise à jours avec et sans transactions. J’avais initialement prévu de faire plein de mises à jours pour que ça moyenne un peu mais lorsque j’ai vu le temps d’une seule mise à jours sans transaction, j’ai renoncé.

Pour éviter les délais du à FTP, les fichiers ont été rapatriés avant le test et sont ensuite lus en local à chaque fois.

Voici les résultats bruts. Les tests sont faits sur la même machine que précédemment, notez qu’elle dispose d’un disque SSD qui réduit beaucoup les latences lors des entrées/sorties, les résultats seraient encore pire sur un disque mécanique à l’ancienne…

C’est ce que j’appelle une optimisation 😉, passer de 52 minutes à moins de 11 secondes, ça vaut la peine 😄.

Pour finir

Pour que la classe soit vraiment utilisable, il nous manque un helper pour rediriger les recherches de pays vers la bonne méthode suivant la version de l’adresse…

public function getIP($ip) {
    if (strpos($ip, ".") !== false) {
        return $this->getIPv4($ip) ;
    } else if (strpos($ip, ":") !== false) {
        return $this->getIPv6($ip) ;
    }
    
    throw new Exception("Not a valid IP Address") ;
}

Avec tout ça, il est maintenant très facile de mettre à jours une base et d’y faire des recherches :

$db = new Database("db.sqlite") ;
$db->update() ;

echo $db->getIP("192.168.1.1")              . "\n" ; // ZZ
// www.arsouyes.org :
echo $db->getIP("188.165.53.185")           . "\n" ; // FR
echo $db->getIP("2001:41d0:301::21")        . "\n" ; // FR
// www.google.com :
echo $db->getIP("216.58.201.228")           . "\n" ; // US
echo $db->getIP("2a00:1450:4007:816::2004") . "\n" ; // IE

Et après ?

Dans cet article, je vous ai montré comment parcourir vraiment les fichiers de délégations et organiser les données dans une base sqlite que vous pourriez utiliser dans n’importe quelle autre applications.

Pour les curieux, voici d’autres articles qui peuvent vous intéresser.

Géolocalisation, connaître le pays de vos utilisateurs

5 Février 2020 Développeur ou utilisateur d’application, vous avez forcément été confronté au problème de géolocalisation. Avant de rentrer dans des précisions insensée, on va aujourd’hui voir comment obtenir le Pays à l’aide des bases de données publiques.

Profiler en PHP

25 Juin 2017 - tbowan. Lorsque vous avez besoin de mesurer les ressources prises par certaines parties de vos scripts, plutôt que de sortir la grosse artilerie avec xDebug, je vous proposes une petite classe bien pratique.

Complexité algorithmique

4 Juin 2018 - tbowan. Quelques explications sur la complexité des algorithmes. Différente mais non moins importante lorsqu’il s’agit d’avoir des applications efficaces.