Page 89 - 《软件学报》2021年第5期

尤勇 等:一种监控系统的链路跟踪型日志数据的存储设计 1313

Header[0]←−1 //赋初始值
for each Entry∈Header do: //顺序遍历一级索引中所有元素(entry)
if Entry is NULL then:
Header[L]←A //不存在则新建
end if
if Entry==A then:
L←i
break
end if
i←i+1
end for
Segment←array[L×4K:(L+1)×4K] //一级索引 Entry 对应的二级索引段
T←index%4K //取余的值为下标位置
Segment[T]←addressInfo //二级索引 Segment 段中第 T 个 Entry 存储 8byte 的位置信息
end function
• 索引查询过程
索引的查询与创建过程类似,即通过 id 信息定位到对应的二级索引段中对应的 Entry 空间,获取其中存储
的 8 字节的位置信息,最后根据位置信息读取数据文件即可.算法 3 为对应过程的算法代码.
算法 3. 索引查询.
Input:
索引文件读取为完整的字节数组,每个元素(entry)占 8byte:array;
LogView 的 id 标识:id.
Output:
日志数据.
function queryLogView(array,id)
Header←array[0:4K] //0~4K−1 的 Entry 为一级索引段
ip, index←id //解析 id 值
A←ip+index/4K //拼接 ip 与 index 的哈希值
i←1
for each Entry∈Header do: //顺序遍历
if Entry==A then:
L←i
break
end if
i←i+1
end for
Segment←array[L×4K:(L+1)×4K] //一级索引 Entry 对应的二级索引段
T←index%4K //取余的值为下标位置
addressInfo←Segment[T] //获取位置信息
headAddress, offset←addressInfo //解析 8byte 的地址信息
block←readFile(headAddress) //读取特定大小的块
data←getData(block,offset) //读取块中指定字节量