Question posted in
The official documentation can be found here.

Redis | Best data structure to store IPs and networks

My goal is to store in Redis:

  • Plain IP addresses like 228.228.228.228
  • IP networks like 228.228.228.0/24

in order to check in request/response cycle whether or not
current IP xxx.yyy.xxx.vvv is inside( contained by):

  • Plain ips

or

  • Ip network ( for example 228.228.228.228 inside 228.228.228.0/24)

Overall amount of ips and networks – few 1000 items.

Question is – what is the best way (best structure) to store both plain ips and networks in Redis and make aforementioned check without fetching data from Redis?

Thanks.

P.S. Current IP is already known.

UPDATE

Ok, lets simplify it a bit with example.

I have 2 ips and 2 networks in where I want to check if certain ip is contained.

# 2 plain ip
202.76.250.29
37.252.145.1

# 2 networks
16.223.132.0/24
9.76.202.0/24

There are 2 possible ways where exact ip might be contained:

1)Just in plain ips. For example 202.76.250.29 contained in the structure above and 215.08.11.23 is not contained simply by definition.

2)Ip might be contained inside network. For example 9.76.202.100 contained inside networks 9.76.202.0/24 but not contained inside list of plain ips as there are no any exact ip = 9.76.202.100.

Little bit of of explanation about ip networks. Very simplified.

Ip network represents range of ips. For example ipv4 network "192.4.2.0/24" represents 256 ip addresses:

IPv4Address('192.4.2.1'), IPv4Address('192.4.2.2'),
…
…
…
IPv4Address('192.4.2.253'), IPv4Address('192.4.2.254')

In another words ip network is a range of ip addresses

from '192.4.2.1' up to '192.4.2.254'

In our example 9.76.202.100 contained inside networks 9.76.202.0/24 as one of this addresses inside the range.

My idea is like this:

Any ip address can be represented as integer. One of our ip addresses
202.76.250.29 converted to integer is 3394042397.

As ip network is a range of ips, so that it is possible to convert it in a range of integers by converting first and last ip in range in integers.
For example one of our networks 16.223.132.0/24 represents range between IPv4Address('16.223.132.1') and IPv4Address('16.223.132.254'). Or integers range from 283083777 up to 283083781 with step 1.

Individual ip can be represented as range between it’s integer and it’s integer + 1 (lower bound included, upper bound excluded).

Obviously search in plain ips can be done by putting them to SET and then using SISMEMBER. But what about searching inside networks. Can we do some trick with ranges maybe?

Tags:

2

Answers


  1. 0

    "Best" is subjective(in memory, in speed etc) but you may use two sets/hash to store them. Since they are unique both hashes and sets would be fine. If you prefer you can use a single set/hash to save both ip and network ip addresses but i would prefer separate since they are two different type of data sets(just like database tables).

    Then you can use either of those

    • SISMEMBER with O(1) time complexity
    • HEXISTS with O(1) time complexity.

    It can be handled on application level with multiple commands or lua script(in a single transaction).

    Depending on your choice add to your keys with SADD and HSET(the field value would be 1).

    —
    Edit: (hope i get it right)

    For the range of network addresses create sets from the integers surrounding two dots such as 12.345.67.1-12.345.67.254 range will be represented as 12.345.67 and you will add this to the set. When you want to search for 12.345.67.x it will be parsed into 12.345.67 in your application level and you will check with SISMEMBER. Same can be done with hash with HEXISTS.

    Since ip addresses contain four different numbers with three dots, you will discard last dot and last number and the rest will be representing(i assume) the network range.

    Login or Signup to reply.
  2. 0

    For IPs you can use Set and query by certain IP within O(1) time.

    For IP range, I think you can use List with Lua Script for query. List will have O(n) time for searching, but since you only have 1000 items, O(N) and O(1) will not have a huge difference for Redis in memory query.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search