假设有一个热门的web服务器，在一小时内访问该web服务器的次数可以达到数万次，为了分析这些访问的统计属性，我们想知道特定时间范围和IP范围内的请求数量。
例如，我们有10个12个请求，格式如下:(IP地址，访问时间)
假设我们想知道IP范围[10.12.72.0,10.12.72.255]在2p期间有多少次访问。上午和下午4点。
我能想到的唯一的备选方案是:
(1)使用B-TREE对这个大数据集进行一维索引，例如在参数IP上建立B-TREE。使用这个B-TREE，我们可以快速获得来自任何特定IP范围的请求数量，但是我们如何知道这些访问中有多少是在2p和2p之间。上午和下午4点?
(2)使用BITMAP，但与B-TREE类似，由于空间要求，BITMAP只能建立在一维上，例如IP地址，我们不知道在2p之间发出了多少这些请求。上午和下午4点
有没有有效的算法?查询的数量可能相当大
你的第一步是计算出你需要的精度…
:
- 你需要毫秒级的时间戳还是小时级的时间戳，足够好吗?
-
- 自1970年以来的小时数可以容纳在一百万个，3字节~整数
-
- 毫秒数，你需要8字节~长
- 你所有的ip是v4(4字节)还是v6(16字节)?
- 您是否会按特定IP进行搜索，还是只使用IP范围?
- 如果是后者，你可以为每个IP 123.123.123使用C类。X(3字节)
假设:
- 1小时时间精度足够好
- 3字节IP C类足够好
重新组织你的数据(2种可能的结构选择一个):
数据库:- 可以使用关系数据库
- 表:点击
- IPClassC INT非聚类索引
- TimeHrsUnix INT NON-CLUSTERED INDEX
- Count BIGINT默认值(1)
平面文件:
- 可以使用更多平面文件
- 有一个平面文件为每个类C IP出现在你的日志(最大2^24)
- 每个文件大小为8B(大int) * 1MB (Hrs从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转换为字符串，将您的时间转换为整数 if File.Exist(IP) = False
- File.Create (IP)
- 文件。SetSize(IP, 8 * 1000000)
- CountBytes = File。Read(IP, 8 * Time, 8) NewCount = Convert.ToLong(CountBytes) + 1
- CountBytes = Convert.ToBytes(NewCount)
- 文件。Write(IP, CountBytes, 8 * Time, 8)
查询新的数据结构:
数据库:- SELECT SUM(Count) FROM Hits WHERE IPClassC BETWEEN @IPFrom AND @IPTo AND TimeHrsUnix BETWEEN @TimeFrom AND @TimeTo
平面文件:
- Total = 0
- Offset = 8 * TimeFrom
- Len = (8 * TimeTo) - Offset
- For IPFrom To IPTo
- 如果File.Exist (IP.ToString ())
- CountBytes = File.Read(IP.ToString()， Offset, Len)
- LongArray = Convert.ToLongArray(CountBytes)
- Total = Total + Math.Sum(LongArray)
下IP
一些额外提示:
- 如果你选择数据库路径，你可能需要为数据库文件使用多个分区
- 如果您选择平面文件路由，您可能希望将查询分解为线程(假设您的SAS将处理带宽)。每个线程将处理范围内IP/文件的一个子集。一旦所有线程完成，每个线程的总数将被求和。
您需要一个支持正交范围计数的数据结构。
10^12是一个很大的数字(TERA)——对于内存处理来说肯定太大了。我会使用星型模式将其存储在关系数据库中，使用时间维度，并按一天中的时间(例如小时带)、IP子网和其他您感兴趣的标准进行预聚合。