聊聊CDN与高性能流媒体服务器的关键技术设计( 三 )


聊聊CDN与高性能流媒体服务器的关键技术设计

文章插图
 
2.4 Cache 模块的主要接口设计
Cache 模块的主要接口设计如下:
(5) Cache_open()
文件打开接口,主要功能如下:
(a) 查看文件状态 。
(b) 在文件 hash 表中查找文件是否已经被打开,如果已经被打开,则刷新引用计数(ref),并直接返回;如果未被打开,则在 hash 表里增加一个表项,并使用 dump_file()接口打开该文件 。
(6) Cache_read()
读文件接口,主要功能如下:
(a) 增加文件引用数 。
(b) 在 cache_file 的 block_list 中查找块是否存在,如果存在则直接返回给调用者;如果未找到,则向空闲块列表中申请一个新的块 。
(c) 调用 dump_file()接口进行文件读取 。
【聊聊CDN与高性能流媒体服务器的关键技术设计】(d) 将块加入到 used_list 和 cache_file 中 。
(3) File_closed()
文件关闭接口,主要功能如下:
(a) 减少引用计数,一旦引用计数为 0,则执行文件关闭流程 。
(b) 同步调用 dump_file()接口来关闭文件 。
(c) 同步和异步销毁 cache_file 文件,其中需要清空 cache_file 文件所拥有的 block_list 。
 
(4) Io_read() 文件预读接口,主要功能如下:
(a) 检查 block 是否已经在 cache 中存在,如果存在则无需进行预读 。
(b) 向预读线程提交预读任务,预读从线程中增加文件的引用计数,防止预读过程中,文件被关闭 。
(c) 调用 cache_read()接口,同时回滚文件的引用计数 。
 
(5) Block_aging()
块老化接口,主要功能如下:
(a) 遍历 used_list,将引用数为 0 的 block 块加入老化列表,并按照时间排序 。
(b) 遍历老化列表,将排名靠前的 N 个块从 used_list 中摘除,放入 free_list,一旦空闲块数量达到要求(阈值的两倍),则停止老化 。
 
2.5 Cache 模块的功能设计与实现
Cache_file 用来存储一个个的缓存数据块,数据块包括两种,cache_block_list 和 uncached_block_list 。在对这两个模块进行数据存储时,可供选择的数据结构有链表、二叉树、哈希结构等
(1) 链表(含单向链表、双向链表)链表的特点是便于元素的增加与删除,开销较小,但在对元素的查找时效率很低 。因此其多用在数据量较小,且不需要排序的场景 。
(2) 二叉树(含红黑树、平衡二叉树)
二叉树的特点是在插入任意元素时都可以自动进行排序,使元素保持有一定的特性 。由于二叉树的空间占用与输入的数据保持一致,所以不需要为二叉树预先分配固定的空间 。因此,二叉树多是用在频繁对数据进行增删和查询操作的场景下,在增删改查的同时需要时刻保证数据的有序排列,且无需预先知道数据量的大小 。二叉树的时间复杂度是 O(log(n)) 。
(3) 哈希(hash) 哈希结构使用链表和数组来管理元素,在理想的哈希算法的支持下可以达到接近数组的随机访问效率,因此其使用场景为无需保证元素的有序性且频繁对数据进行操作的场景 。流媒体服务器应用在多用户直播或点播场景中,此场景的数据特点是数据量大且保存媒体文件时无需排序 。当一个用户请求某一路直播(比如 CCTV2),哈希结构可以快速根据 CCTV2 的 hash 值很快找到对应的缓存块,从中读取数据,时间复杂度可以近似达到 O(1) 。若使用链表或二叉树,需对缓存中的每项内容进行遍历,时间复杂度较高 。其次,媒体文件本身并无排序需求,不符合二叉树的使用场景 。另外,哈希结构的代码开发简便且可维护性较强 。综上选择使用哈希数据结构对流媒体服务器的 Cache 模块进行设计开发 。
在数据量较大时,哈希结构会产生冲突 。解决哈希冲突采用的方案有两种:第一种是线性探索,相当于在冲突之后建立一个单链表,这种情况下,插入和查找以及删除操作消耗的时间会达到 O(n);第二种方法是开放寻址,这种方法不需要更多的空间,在最坏的情况下,时间复杂度也只会达到 O(n) 。
Cache_file 的哈希结构在 Cache 模块中的实现方式 。哈希表的 key 值是由点播或者直播的媒体文件名通过哈希表达式计算得来 。每一个 file 文件后又以链表的形式存有若干block,当需要查找资源时,只需按照哈希表达式来进行查找即可,这样的数据查找方式在一定程度上提高了查找效率 。Cache_file 的哈希实现方式如下所示:


推荐阅读