Хеш-фильтры.

12.4. Хеш-фильтры.

Если у вас возникла потребность в большом количестве правил, например, когда у вас много клиентов, причем все имеют различные спецификации QoS (от англ. Quality of Service -- Качество Обслуживания), то может сложиться ситуация, когда ядро будет тратить недопустимо большое количество времени на поиск подходящего правила в наборе.

По-умолчанию, все фильтры находятся в одной большой цепочке, и располагаются в порядке убывания приоритетов. Если набор содержит 1000 правил, то для некоторых пакетов может потребоваться выполнить 1000 проверок, чтобы решить, что с ними делать дальше.

Поиск шел бы гораздо быстрее, если бы было 256 цепочек, по четыре правила в каждой, при условии, что вы сможете направить пакет в нужную цепочку.

В этом случае вам поможет хеширование. Представим, что у нас имеется сеть из 1024 компьютеров, с IP-адресами от 1.2.0.0 до 1.2.3.255, причем каждый компьютер может быть отнесен к одному из 3-х предопределенных классов качества обслуживания, например 'lite', 'regular' и 'premium'. Решение "в лоб" дает 1024 правила:

# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.1 classid 1:1
...
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.3.254 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.3.255 classid 1:2      
      
Чтобы уменьшить число проверок, можно использовать последний байт IP-адреса в качестве хеш-ключа. В результате получается 256 таблиц, первая из которых:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.1.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.2.0 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.3.0 classid 1:2      
      
Следующая:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.1 classid 1:1
...      
      
Таким образом каждый пакет должен пройти не более 4-х проверок.

Реальная конфигурация намного сложнее, но она стоит того. Первым создается корневой фильтр, а затем -- таблица на 256 записей:

# tc filter add dev eth1 parent 1:0 prio 5 protocol ip u32
# tc filter add dev eth1 parent 1:0 prio 5 handle 2: protocol ip u32 divisor 256      
      
После этого добавляются правила в созданные таблицы:
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
        match ip src 1.2.0.123 flowid 1:1
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
        match ip src 1.2.1.123 flowid 1:2
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
        match ip src 1.2.3.123 flowid 1:3
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
        match ip src 1.2.4.123 flowid 1:2      
      
Это записи в таблице с номером 123, которые выполняют проверку на принадлежность адресам 1.2.0.123, 1.2.1.123, 1.2.2.123, 1.2.3.123, и в случае совпадения передают пакеты в классы 1:1, 1:2, 1:3 и 1:2 соответственно. Обратите внимание на то, как задается номер таблицы, шестнадцатеричное число 0x7b соответствует числу 123, в десятичном представлении.

И наконец создается хеш-фильтр, который перенаправит трафик в нужную таблицу:

# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 800:: \
        match ip src 1.2.0.0/16 \
        hashkey mask 0x000000ff at 12 \
        link 2:      
      
А теперь поясним некоторые моменты. Заданной по-умолчанию хеш-таблице присвоен идентификатор 800:: и вся фильтрация начинается отсюда. Затем выбирается IP-адрес отправителя, который находится в 12, 13, 14 и 15 байтах в IP-заголовке и указывается, что нас интересует только последний байт. После чего трафик передается в хеш-таблицу 2:, которая была создана ранее.

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