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之间发出了多少这样的请求。下午 3 点和下午 4 点

有没有什么高效的算法，thx？查询数量可以相当大

Answer 1

您的第一步是弄清楚您需要的精度...

时间:

• 您需要精确到毫秒的时间戳还是精确到小时的时间戳？
• • 自 1970 年以来的小时数不到一百万，3 个字节~整数
• • 毫秒数，你需要 8 个字节 ~long

知识产权:

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

假设:

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

重新组织您的数据(从 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)
• • UPDATE Hits SET Count = Count + 1 WHERE IPClassC = @IP AND TimeHrsUnix = @Time
• 其他
• • INSERT INTO Hits VALUES(@IP, @Time)

平面文件:

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

查询您的新数据结构:

数据库:

• 从@IPFrom 和@IPTo 之间的IPClassC 和@TimeFrom 和@TimeTo 之间的TimeHrsUnix 中选择总和(计数)

平面文件:

• 总计 = 0
• 偏移量 = 8 * TimeFrom
• 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/文件子集。一旦所有线程完成，每个线程的总数将被加总。