c - 计算某个IP范围和时间范围内的访问次数的有效方法

Question

假设有一个流行的Web服务器，这个Web服务器一小时内的访问量可以达到数万次，为了分析这些访问的统计特性，我们想要知道特定时间内的请求数时间范围和IP范围。

例如，我们有 10¹² 个请求，格式如下:

(IP地址、访问时间)

假设我们想知道下午 2 点和下午 4 点期间有多少次访问来自 IP 范围 [10.12.72.0 , 10.12.72.255]。

我能想到的唯一候选想法是:

(1)使用B-TREE对这个大数据集进行一维索引，比如在参数IP上建立一个B-TREE。使用这个B-TREE，我们可以快速获取来自任何特定IP范围的请求数量，但是我们如何知道其中有多少访问是在下午2点到4点之间呢？

(2)使用BITMAP，但与B-TREE类似，由于空间要求，BITMAP只能建立在一维上，例如IP地址，我们不知道2p之间发出了多少个这样的请求。上午和下午 4 点。

有什么高效的算法吗，谢谢？查询数量可能相当大

Answer 1

您的第一步是找出您需要的精度...

时间:

• 您是否需要精确到毫秒的时间戳，或者精确到小时的时间戳就足够了吗？
• • 自 1970 年以来的小时数可以容纳在 100 万以内，3 个字节 ~ 整数
• • 毫秒数，您需要 8 个字节 ~long

IP:

• 您的所有 IP 都是 v4(4 字节)还是 v6(16 字节)？
• 您会按特定 IP 进行搜索还是仅使用 IP 范围？
• • 如果是后者，您可以为每个 IP 123.123.123.X(3 字节)使用 C 类

假设:

• 1小时的时间精度已经足够了
• 3 字节 IP Class C 就足够了

重新组织数据(2 种可能的结构，选其一):

数据库:

• 您可以使用关系数据库
• • 表格:点击次数
• • • IPClassC INT 非聚集索引
• • • TimeHrsUnix INT 非聚集索引
• • • 计算 BIGINT 默认值 (1)

平面文件:

• 您可以使用更多平面文件
• • 为日志中出现的每个 C 类 IP 准备 1 个平面文件(最多 2^24)
• • • 每个文件大小为 8B(大整数)* 1MB(自 1970 年到 2070 年的时间)= 8MB

如何加载新的数据结构:

数据库:

• 解析您的日志(一次在内存中读取一行)
• 将记录转换为 3 字节 IP 和 3 字节时间
• 将您的 IP 类别 C 转换为整数，将您的时间转换为整数
• IF EXISTS(SELECT * FROM Hits WHERE IPClassC = @IP AND TimeHrsUnix = @Time)
• • 更新命中 SET Count = Count + 1，其中 IPClassC = @IP AND TimeHrsUnix = @Time
• 否则
• • 插入命中值(@IP、@Time)

平面文件:

• 解析您的日志(一次在内存中读取一行)
• 将记录转换为 3 字节 IP 和 3 字节时间
• 将您的 IP 转换为字符串，将时间转换为整数
• 如果 File.Exist(IP) = False
• • 文件.创建(IP)
• • File.SetSize(IP, 8 * 1000000)
• CountBytes = File.Read(IP, 8 * 时间, 8)
• NewCount = Convert.ToLong(CountBytes) + 1
• CountBytes = Convert.ToBytes(NewCount)
• File.Write(IP, CountBytes, 8 * 时间, 8)

查询您的新数据结构:

数据库:

• 从命中中选择 SUM(Count)，其中 IPClassC 介于 @IPFrom 和 @IPTo 之间，并且 TimeHrsUnix 介于 @TimeFrom 和 @TimeTo 之间

平面文件:

• 总计 = 0
• 偏移量 = 8 * 时间
• Len = (8 * TimeTo) - 偏移量
• 对于 IP = IPFrom 到 IPTo
• • 如果 File.Exist(IP.ToString())
• • • CountBytes = File.Read(IP.ToString(), Offset, Len)
• • • LongArray = Convert.ToLongArray(CountBytes)
• • • 总计 = 总计 + Math.Sum(LongArray)
• 下一个IP

一些额外的提示:

• 如果您选择数据库路线，您可能必须为数据库文件使用多个分区
• 如果您采用平面文件路线，您可能希望将查询分解为线程(假设您的 SAS 能够处理带宽)。每个线程将处理该范围内的 IP/文件的子集。一旦所有线程完成，每个线程的总数就会被求和。