У меня зазвонил телефон. Кто говорит?.. Поможет «слон»

    Автоматическое определение клиента и его региона по входящему телефонному звонку стало неотъемлемой частью любой развитой HelpDesk или CRM-системы. Только надо уметь делать это быстро — тогда появляется масса возможностей.

    Например, можно менеджеру сразу показать из какого города идет звонок, подтянуть актуальный прайс и условия доставки, вывести карточку звонящего клиента, последние сделки с ним, конкретное контактное лицо,… — да много чего полезного, как это умеет наш СБИС CRM!


    А как этот функционал реализовать самостоятельно? Оказывается, не так уж сложно. Собрать и опробовать работающую модель можно, буквально, «на коленке» — нужна только связка из Node.js и PostgreSQL.

    Определяем регион по номеру


    Давайте предположим, что АТС присылает нам уже нормализованный и отформатированный до 10 цифр (будем рассматривать только звонки внутри России) входящий телефонный номер. Как наиболее эффективно понять, откуда пришел звонок?

    Собираем телефонные коды


    Сначала нам понадобится база телефонных кодов России в привязке к регионам. Для этого можно воспользоваться официальным источником — актуальной выпиской из плана нумерации на сайте Федерального агентства связи.

    Но найти — мало, надо эти данные скачать и извлечь. В этом нам поможет небольшой скрипт для Node.js, использующий библиотеку request:

    const async = require('async')
      , request = require('request');
    
    const fs = require('fs');
    
    let queue = [
      'ABC-3xx'
    , 'ABC-4xx'
    , 'ABC-8xx'
    , 'DEF-9xx'
    ]
      .map(key => (
        {
          base : 'https://rossvyaz.gov.ru'
        , path : `/data/${key}.csv`
        }
      ));
    
    let ranges = [];
    
    async.doWhilst(
      cb => {
        // берем из очереди и загружаем очередную страницу
        let task = queue.shift();
        request(
          {
            url  : task.base + task.path
          , pool : false
          }
        , (err, res, body) => {
            // примитивный разбор CSV
            body.split('\n').forEach(line => {
              let tds = line.split(';');
              let place = tds[5].split('|');
              ranges.push([
                tds[0]
              , tds[1]
              , tds[2]
              , tds[4]
              , place[place.length - 1]
              , place[place.length - 2] && place[place.length - 2].startsWith('р-н') ? place[place.length - 2] : ''
              , place.length > 1
                ? place[0].startsWith('р-н')
                  ? ''
                  : place[0]
                : ''
              ]);
            });
            return cb(err);
          }
        );
      }
      // итерируем, пока очередь заданий непуста
    , cb => {
        return cb(null, queue.length);
      }
      // когда все распарсили - подчищаем данные и формируем файл для загрузки в БД
    , err => {
        // чистим коды и диапазоны
        ranges.forEach(row => {
          // убираем пересечение цифр кода и диапазона
          let ln = row[0].length + row[1].length - 10;
          if (ln > 0) {
            let sfx = row[0].slice(-ln);
            if (row[1].startsWith(sfx) && row[2].startsWith(sfx)) {
              row[1] = row[1].slice(ln);
              row[2] = row[2].slice(ln);
            }
          }
    
          // пересобираем общий префикс
          let pfx;
          for (let i = 1; i < row[1].length; i++) {
            if (row[2].startsWith(row[1].slice(0, i))) {
              pfx = row[1].slice(0, i);
            }
            else {
              break;
            }
          }
          if (pfx) {
            row[0] = row[0] + pfx;
            row[1] = row[1].slice(pfx.length);
            row[2] = row[2].slice(pfx.length);
          }
        });
    
        let sql = `
    SET client_encoding = 'UTF-8';
    CREATE TABLE phonecodes(
      code
        varchar
    , numb
        varchar
    , nume
        varchar
    , oper
        varchar
    , region
        varchar
    , district
        varchar
    , city
        varchar
    );
    COPY phonecodes FROM STDIN;
    `;
        // собираем COPY-формат
        let copy = ranges.map(row => row.join('\t')).join('\n') + '\n\\.\n';
    
        fs.writeFileSync('phonecodes.sql', sql + copy);
      }
    );
    

    Теперь загрузим его в нашу тестовую базу, и можно работать:

    psql -f phonecodes.sql -U postgres tst

    Если все сработало как надо, в нашу таблицу будет загружено почти 378 тысяч диапазонов:

    SET
    CREATE TABLE
    COPY 377937

    Замечу, что в нашем примере и код, и граничные номера диапазона представлены строками. Да, их можно превратить в integer/bigint, но мы пока не будем этим заниматься. Тем более, что входящий номер телефона не всегда состоит только из цифр — например, некоторые таксофоны могут сообщать свой номер с «цифрой A».

    «Ищут пожарные, ищет милиция...»


    Сначала попробуем наивный запрос:

    WITH src AS (
      SELECT '4852262000' num -- входящий номер
    )
    SELECT
      *
    FROM
      src
    , phonecodes
    WHERE
      num LIKE (code || '%') AND -- проверяем совпадение кода
      num BETWEEN (code || numb) AND (code || nume) -- проверяем вхождение в диапазон
    LIMIT 1;


    [посмотреть на explain.tensor.ru]

    Вычитали почти 70 тысяч строк (и это еще повезло, что не все 380!), почти 10MB данных перелопатили… не слишком эффективно, но результат достигнут:

    num        | code   | numb | nume | oper | region           | district | city
    -----------------------------------------------------------------------------------
    4852262000 | 485226 | 0000 | 9999 | МТС  | Ярославская обл. |          | Ярославль

    Но давайте как-то избавимся от Seq Scan! Для этого нам всего-то нужен индекс, который поможет искать по LIKE, так ведь?..

    Увы, нет. Если нам надо искать column LIKE (val || '%'), то нам помогут префиксные индексы с varchar_pattern_ops, но у нас-то все наоборот — val LIKE (column || '%'). И мы получаем ситуацию близкую к той, что я описывал в статье «Классифицируем ошибки из PostgreSQL-логов».

    Используем знания о прикладной области


    Близкую, но, к счастью, все-таки существенно проще — данные у нас фиксированы и их относительно немного. Причем по кодам записи распределены достаточно разреженно:

    SELECT -- сколько кодов с таким кол-вом диапазонов
      ranges
    , count(*)
    FROM
      (
        SELECT -- сколько диапазонов по каждому коду
          code
        , count(*) ranges
        FROM
          phonecodes
        GROUP BY
          1
      ) T
    GROUP BY
      1
    ORDER BY
      1 DESC;

    Только лишь около сотни кодов имеют по 10 диапазонов, а почти четверть — вообще ровно один:

    ranges | count
    --------------
        10 |   121
         9 |   577
         8 |  1705
         7 |  3556
         6 |  6667
         5 | 10496
         4 | 12491
         3 | 20283
         2 | 22627
         1 | 84453

    Поэтому давайте проиндексируем пока только код. А раз все диапазоны одного кода нам понадобятся все вместе — упорядочим нашу таблицу с помощью CLUSTER, чтобы записи лежали физически рядом:

    CREATE INDEX ON phonecodes(code);
    CLUSTER phonecodes USING phonecodes_code_idx;

    А теперь вспомним, что телефонный номер у нас состоит ровно (всего!) из 10 цифр, среди которых нам надо вычленить префиксный код. То есть наша задача спокойно решается простым перебором не более чем 10 вариантов:

    WITH RECURSIVE src AS (
      SELECT '4852262000' num
    )
    , T AS (
      SELECT
        num pfx -- в качестве исходного "префикса" задаем весь номер
      , NULL::phonecodes pc
      FROM
        src
    UNION ALL
      SELECT
        substr(pfx, 1, length(pfx) - 1) -- "отщипываем" последнюю цифру
      , (
          SELECT
            X
          FROM
            phonecodes X
          WHERE
            code = T.pfx AND -- проверяем полное совпадение префикса
            (TABLE src) BETWEEN (code || numb) AND (code || nume) -- проверяем вхождение в диапазон
          LIMIT 1
        ) pc
      FROM
        T
      WHERE
        pc IS NOT DISTINCT FROM NULL AND -- ищем, пока ничего не нашли
        length(pfx) > 2 -- ... и префикс еще может оказаться кодом
    )
    SELECT
      (pc).* -- "разворачиваем" найденную запись диапазона в поля
    FROM
      T
    WHERE
      pc IS DISTINCT FROM NULL;
    


    [посмотреть на explain.tensor.ru]

    Нам потребовалось всего 5 обращений к индексу, чтобы найти искомый код. Выигрыш кажется микроскопическим в абсолютных цифрах, но мы получили снижение нагрузки в 150 раз относительно наивного варианта! Если вашей системе приходится обрабатывать десятки и сотни тысяч таких запросов в час — экономия становится весьма солидной!
    А можно делать еще меньше итераций по индексу — если все коды заранее привести к классическому виду «от 3 до 5 цифр». Правда, тогда возрастет количество диапазонов в каждом коде, и их фильтрация может добавить проблем.

    int8range + GiST


    Как правильно заметил в комментариях miksir, раз у нас все пары «код + диапазон» и входящий номер имеют строго одинаковую размерность в 10 цифр, то задачу можно свести к интервальному поиску среди числовых значений.

    Для этого создадим индекс, который будет рассматривать наши записи как диапазонный тип int8range:

    CREATE INDEX ON phonecodes USING gist(
      int8range(
        (code || numb)::bigint -- левая граница отрезка
      , (code || nume)::bigint -- правая граница отрезка
      , '[]' -- включая крайние точки
      )
    );

    После этого мы сможем использовать его в запросе:

    WITH src AS (
      SELECT '4852262000'::bigint num
    )
    SELECT
      *
    FROM
      phonecodes
    WHERE
      int8range((code || numb)::bigint, (code || nume)::bigint, '[]') @> ( -- вхождение интервала
        SELECT
          int8range(num, num, '[]') -- "интервал" из единственной точки
        FROM
          src
      )
    LIMIT 1;


    [посмотреть на explain.tensor.ru]

    Непересекающиеся интервалы + btree


    Сначала убедимся, что наши диапазоны номеров действительно не пересекаются:

    SELECT
      *
    FROM
      phonecodes X
    , phonecodes Y
    WHERE
      int8range((X.code || X.numb)::bigint, (X.code || X.nume)::bigint, '[]') &&
      int8range((Y.code || Y.numb)::bigint, (Y.code || Y.nume)::bigint, '[]') AND
      X.ctid <> Y.ctid;

    Если получили «ничего» — все хорошо, и можно применить следующую оптимизацию: номер может входить только в тот из диапазонов, к концу (или началу) которого находится ближе всего.

    Для поиска ближайшего «начала» нам достаточно обычного btree-индекса:

    CREATE INDEX ON phonecodes((code || numb));

    WITH src AS (
      SELECT '4852262000' num
    )
    SELECT
      *
    FROM
      src
    , LATERAL (
        SELECT
          *
        FROM
          ( -- находим тот единственный ближайший диапазон
            SELECT
              *
            FROM
              phonecodes
            WHERE
              (code || numb) <= src.num
            ORDER BY
              (code || numb) DESC
            LIMIT 1
          ) T
        WHERE
          src.num BETWEEN (code || numb) AND (code || nume) -- перепроверяем попадание
      ) T;
    

    Несмотря на кажущуюся простоту, этот вариант дает производительность хуже предыдущего:


    [посмотреть на explain.tensor.ru]

    Определяем клиента по номеру


    Теперь давайте представим, что у нас уже есть таблица с клиентами, где записан «подчищенный» номер телефона — убраны все скобки, дефисы, и т.п.

    Но вот неприятность, далеко не все и них имеют код города — то ли менеджеры ленятся забивать, то ли АТС так настроена, что присылает не полные, а «внутригородские» номера… Как тогда найти клиента — ведь поиск по полному соответствию уже не сработает?

    АТС дает полный номер


    В этом случае воспользуемся тем же «переборным» алгоритмом. Только «отщипывать» цифры будем не с конца номера, а с начала.

    Если номер в карточке клиента был указан полностью, мы на первой же итерации на него наткнемся. Если не полностью — когда «отрежем» какой-то из подходящих кодов.

    Безусловно, нам потребуется какая-то перекрестная проверка по другим реквизитам (адрес, ИНН, ...), чтобы не получилось ситуации, что из входящего номера мы «отрезали» код Москвы, а по оставшемуся 7-значному номеру нашли клиента из Санкт-Петербурга.

    АТС дает «городской» номер


    пришло от АТС      :     262000
    указано в карточке : 4852262000

    Тут ситуация интереснее. «Приращивать» каждый возможный код к короткому номеру и пробовать искать мы не можем — их слишком много. Взглянем на ситуацию с другой стороны — буквально:

        reverse(262000) -> 000262
    reverse(4852262000) -> 0002622584

    Оказывается, если развернуть строки с номерами, то задача превращается в обычный префиксный поиск, который легко решается с помощью индекса с varchar_pattern_ops и LIKE!

    CREATE INDEX ON client(reverse(phone) varchar_pattern_ops);

    SELECT
      *
    FROM
      client
    WHERE
      reverse(phone) LIKE (reverse($1) || '%');

    А дальше, опять-таки перепроверяем дополнительную информацию — из какого региона АТС нам прислала номер, к какому региону относится клиент.
    Тензор
    Разработчик системы СБИС

    Комментарии 38

      0

      Почему нельзя задать диапазоны в базе 10-значным числом и просто делать поиск по диапазону?

        0
        И такой метод имеет право на жизнь:

        CREATE INDEX ON phonecodes USING gist(int8range((code || numb)::bigint, (code || nume)::bigint, '[]'));
        
        SELECT
          *
        FROM
          phonecodes
        WHERE
          int8range((code || numb)::bigint, (code || nume)::bigint, '[]') @> '[4852262000, 4852262000]'::int8range;

        Правда, с теми же номерами с «цифрой A» обломится.
          0

          У вас АТС прямо в базу ходит? Отрезать что-то не проблема, думаю.
          Опять же, зачем все так сложно?
          Вы все-равно парсите номера скриптом, можно же склеить префикс и диапазон в одно число в момент загрузки данных в базу. В итоге будет два числа границ диапазона и обычный поиск по дереву where phone >= numb and phone <= nume.

            0
            Какой «обычный поиск по дереву» позволяет сделать val BETWEEN col1 AND col2, если имеется в виду btree?
              0

              Да, тут я ступил. Ну сразу делать колонку int8range.
              Или, с учетом того, что диапазоны у нас не пересекаются, просто nume >= phone order by nume limit 1 и потом уже проверить на numb эту одну строку.

                0
                А вот не факт, что они не пересекаются. Тут надо проверять конкретную выгрузку, а то бывало.

                Правда, с обратной задачей так уже не получится.
                  0

                  Не должны пересекаться, иначе не понятно, что делать, если номер попадает в два диапазона. Накосячить могут, но эту проверку не сложно запихнуть в скрипт загрузики.

                    0
                    Добавил в статью, спасибо за идеи.
        0
        Зачем так сложно? Берем любой kv и заливаем все коды в него.
        378 тысяч ключей это ерунда.
          0
          Допустим, залили — а дальше что? Искать-то какими алгоритмами?
            0
            Запрос от всего номера, запрос от номера минус последняя цифра и так далее пока не найдется. Номер предварительно приведен к стандартному виду.
            10 запросов на звонок в худшем случае. Ерунда.
            Если нужны миллисекунды паралелим. Тут чуть сложнее, но тоже тривиально все.

            В качестве бонуса в тот же kv кладем всех клиентов. Если у вас их сколь либо адекватное количество работать отлично будет.
              0
              Так чем это отличается от описанного в статье, кроме использования kv вместо sql?
                –3

                Сложностью. Мое решение описывается двумя предложениями, реализуется джуном за день. Ваше даже в словах сложное.

                  0
                  Вы точно посмотрели приведенный SQL-запрос?
                  substr(pfx, 1, length(pfx) - 1) -- "отщипываем" последнюю цифру

                  Это же ровно тот же алгоритм:
                  запрос от номера минус последняя цифра и так далее пока не найдется
                    –2

                    Сложность это не только конечный код. Сложность это все от тикета с задачей до готового кода.


                    В моем варианте негде ошибаться, понятно как писать тесты, понятно что с производительностью, производительность не надо оптимизировать, да и сама задача джуну на день написать код, и мне 10 минут на написать тикет.
                    У вас все гораздо сложнее.

                      +1
                      Что сложнее написать — один SQL-запрос или кусок кода на бизнес-логике, который сделает то же самое? Зависит от навыков исполнителя.

                      Точно ли не надо оптимизировать производительность? Поставим какой-нибудь Redis на площадке в Мск и будем делать к нему последовательно те самые 10 запросов из Владивостока, получая на каждом задержку до 150мс… Делать параллельно? Так это же уже оптимизация, и не для всякого джуна.

                      Это не имеет никакого отношения к теме статьи, а исключительно холивар SQL vs NoSQL. Есть задачи, где выигрывает NoSQL, есть — где SQL, есть где они равноприменимы, как тут.
                        0

                        У вас абстракции протекли.


                        Возможность без спец ухищрений сделать базу в 150мс от бека это ошибка другого уровня. Ее тоже надо исправлять, но к этой задаче это не имеет отношения.

                          0
                          Странно, что не имеет — мне казалось, что мы обсуждаем…
                          Мое решение описывается двумя предложениями, реализуется джуном за день.
                          В моем варианте негде ошибаться, понятно как писать тесты, понятно что с производительностью, производительность не надо оптимизировать, да и сама задача джуну на день написать код, и мне 10 минут на написать тикет.

                          А оказывается, что именно решение, как цельный законченный функционал — не работает!
                          150мс от бека это ошибка другого уровня. Ее тоже надо исправлять
                          Ну так и где оно «проще», если там нужно еще дополнительную кучу граничных условий учитывать? То есть это заведомо не «постановка за 10 минут».
                            0

                            За 10. Исходим из разумных предположений. Предположить что небольшая kv база рядом с бекендом разумно. Предполагать что она через океан неразумно.


                            Исправление ошибок архитектуры, а kv база в 150мс от бекенда это ошибка архитектуры, никак не связано с разработкой бизнес логики. Тут же чистая разработка бизнес логики.
                            Смешивать такие вещи это и есть протекающие абстракции.

                              0
                              Продолжу мысль:
                              — делать 10 запросов к БД вместо 1 — ошибка архитектуры приложения, поскольку увеличивает нагрузку на нее, плюс лишний трафик, плюс задержки
                              — делать запросы последовательно — тоже ошибка архитектуры
                              — взять KV без поддержки префиксного поиска — туда же

                              Ими мы не занимаемся. Поэтому к концу дня приходит гордый джун: "Смотри, я сделал ничего. Оно идеально [не] работает — все тесты это показывают. Но у меня нет ни одной ошибки! Зато вот в архитектуре — сплошные..."

                              И таки он прав — это не его ошибки, а того, кто его отправил неправильной дорогой за те самые 10 минут — если под «джуном» мы понимаем обычного простого кодера, а не того, кто стремится вырасти до «сеньора».
                                0

                                10, да и любое другое разумное фиксированное число обращений к kv это правильно и хорошо. Kv созданы для такой нагрузки и хорошо умеют ее обрабатывать. Это типовой паттерн использования.


                                За все фичи, в том числе префиксные поиски, надо платить. Как правило это не имеет смысла. У нас типичный О(1) с разумной константой. Смысл что-то там городить?


                                Если джун нашел ошибки архитектуры на уровне планирования ДЦ баз и бекендов то надо что-то в консерватории менять. И это что-то никак не связано с реализацией бизнес логики.

                                  0
                                  У нас типичный О(1) с разумной константой. Смысл что-то там городить?
                                  Вы вторую часть статьи про префиксный поиск по reverse точно прочитали?

                                  Если джун не смог нормально решить поставленную задачу указанными инструментами, то не факт, что проблема в нем или в архитектуре. Возможно, она в том, кто ему указал решать эту задачу именно этими инструментами.
                                    0

                                    Я это и называю жутким переусложнением.
                                    Задача решается однострочником. С нормальным и предсказуемым быстродействием. При этом не делается ни одного неразумного предположения о проекте или инфраструктуре.
                                    Ну что еще надо?


                                    IntStream.range(0, str.length()).mapToObj(i -> str.substring(0, str.length() - i)).parallel().map(this::redisReq).filter(Objects::nonNull).findFirst();
                                      0
                                      А теперь давайте посмотрим, во что вырождается попытка таким же способом реализовать префиксный поиск на том же Redis:
                                      oldblog.antirez.com/post/autocomplete-with-redis.html

                                      И сравните с краткостью и выразительностью CREATE INDEX (varchar_pattern_ops) / SELECT ... LIKE.
                                        0
                                        Именно поэтому так делать не надо.
                                        Творить из хорошей kv плохую «любую другую» базу не надо.
                                        Надо пользоваться преимущесвами kv. Она держит безумный рпс на смешном железе. И при этом очень быстро работает. Надо этим пользоваться.
                                          0
                                          Если «так делать не надо» (от самого автора Redis), но «мое решение… реализуется джуном за день» — есть какой-то магический способ «как надо»?

                                          Или все-таки все зависит от задачи?
                                          Это не имеет никакого отношения к теме статьи, а исключительно холивар SQL vs NoSQL. Есть задачи, где выигрывает NoSQL, есть — где SQL, есть где они равноприменимы
                                            0
                                            Я чуть выше написал однострочник. Который используя плюсы kv делает что надо.
                                            День на перекладывание джейсонов, тесты и прочий бойлерплейт.

                                            Конечно зависит. sql великолепен. Но тут он не нужен.
                                            Равноприменимы — не верю. Слишком оно разное. Использование не того что нужно для конкретной задачи вызывает как минимум усложнение кода. Где код и проектирование получаются проще, то и надо использовать.

                                            Ваш пример это отлично иллюстрирует. Варианты реализации, профайлеры, планы запросов. Море всего. У меня же одна строка. Понятно как она работает, понятно быстродействие, понятны ограничения. Не надо вообще ничего больше делать.

                                            Общие ограничения любой БД знать полезно. Чтобы случайно ужаса не сделать.
                                              0

                                              Изивините, но ваше решение выглядит сложнее в коде, чем простой sql заропс с поиском по специально предназначенному для таких целей индексу. Редис тут имеет смысл использовать только если для нас важно время ответа. Про rps я бы не был столь уверен, было бы интересно потестировать… равно как и потребление памяти.

                                    0
                                    За все фичи, в том числе префиксные поиски, надо платить. Как правило это не имеет смысла. У нас типичный О(1) с разумной константой. Смысл что-то там городить?

                                    Если чо, то вы просто сделали префиксный поиск на редисе со сложностью O(n).

                          0

                          Ну да, а потом условный джун внезапно узнает, что ключи в данной kv по префиксу не ищутся, ибо там хешмап.

                            0

                            У него тесты не сработают. Он пойдет почитает доку и все сделает правильно.
                            Для того и пишем интеграционные тесты.

                              +1

                              Ага, и сделает поиск по маске в редисе, например ;)

                                0

                                Код ревью для кого придумали?


                                Если и ревьюер не в курсе и считает такой код ок, то пора нанимать людей подороже. С кадрами серьезные проблемы.

                                  0

                                  И что ревьювер в данном кейсе предложит сделать?

                                    0

                                    Предложит переписать код так чтобы не искать по маске? Можно приложить ссылочку где описано что так не оптимально делать.

                                      0

                                      Потом окажется, что искать на редисе по префиксу не так и просто, что нужно или сложную структуру придумывать или дублировать ключи, что увеличит объем данных раз 10. Что нужно искать другое nosql решение, которое хотя бы умеет btree, что бы искать по префиксу… и внезапно придете к тем же запросам, что и в статье, только может не на sql. Вы все еще считаете, что nosql решение сильно "элементарнее", чем написать один sql запрос на постгресе, который давно работает, проверен, по нему хорошая экспертиза?

              0
              Все бы хорошо, только исходные данные у вас не актуальные!
              Актуальные данные мобильных операторов нужно брать здесь: zniis.ru/bdpn/check
                0
                Я так понимаю, это только по перенесенным мобильным номерам? С точки зрения определения региона, это ничего не меняет, но за ссылку спасибо.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое