Youqi Li (黎有琦)

Youqi Li (黎有琦)

Assistant Professor at Beijing Institute of Technology

学生论文读后感分享

less than 1 minute read

Published:

2024年的第一天，分享本科毕设罗嘉宇同学阅读两篇关于CDN cache的论文读后感，为新的一年开个好兆头。

12.12-12.18周报

1. 上周工作总结

1.1 论文研读：Darwin: Flexible Learning-based CDN Caching

Darwin的目标是实现在CDN服务器中最大化HOC命中率的准入策略，其方法是用机器学习去“检测”并从一些“已知的优秀expert”选择（expert被设计为一个元组（f,s），f代表频率阈值，s代表尺寸阈值，所有多于f次、小于s的物体都会被传输到HOC中）。Darwin最终学习将到达工作负载中的流量模式和表现最好的expert相联系，Darwin可以轻松扩展为包括其他不同于f和s的knob。

Darwin大致分为离线学习和在线选择两个步骤。

离线学习：

  1. 离线聚类和专家集关联：收集CDN服务器运行的历史流量轨迹，每个轨迹包括大量请求；从轨迹中提取feature（平均请求物体大小、到达间隔时间的向量和堆栈距离的向量）；根据feature将轨迹聚类；将一个命中率在表现最好的expert的θ%以内的expert与轨迹相关联；遍历每个聚类中的每个轨迹，得到一个feature到对应专家集的映射

  2. 离线跨专家预测器：映射到一个聚类的多个expert是相关联的，表明可以根据给定expert的表现预测其他expert的表现；为每对有序的expert训练神经网络，input：轨迹，output：给定另一个expert的命中/未命中次数时一个expert的命中次数的概率；预测器将被用于在线阶段

在线学习：以Ne个请求为周期，包括特征估计、最佳专家识别和部署

  1. 特征估计：前Nwarm-up个请求用来将当前流量和一个专家集相关联

  2. 最佳专家识别和部署：根据跨专家预测器提供的侧面信息，从这个专家集中用最佳臂识别算法选择一个最佳专家；最佳专家被部署

2. 下周任务

  1. 继续学习本篇论文的数学推导

  2. 继续自学与内容分发网络、多臂老虎机相关的文献和知识

12.12-12.28周报

1. 上周工作总结

1.1 论文研读：Learning Cache Replacement with CACHEUS

机器学习的发展为解决计算机科学中的问题开辟了一条新的途径，在存储领域，缓存替换策略就是之一。

现有的缓存替换策略存在以下两个问题：

1) 不同的工作负载、乃至同一个工作负载在不同的时间段会表现出不同的访存特性，对于特定工作负载缓存替换策略不一定适合另一些。 2) 缓存块的大小会影响缓存替换策略的效果。

本篇论文使用机器学习算法改进缓存替换策略，主要内容如下：

1.1.1 定义了四种工作负载原语类型，任何工作负载均有这四种原语组合而成。

1) LFU-friendly：由访问序列定义，该序列由最近使用的最少的（LRU）缓存算法处理最优。 2) LRU-friendly：由访问序列定义，该序列由最不经常使用（LFU）缓存算法处理最优。 3) scan：由访问序列定义，每个项只被访问一次。 4) churn：定义为对存储项子集的重复访问，每个项被访问的概率相等。

1.1.2 改进了LeCaR，提出CACHEUS。

1.1.2.1 将LeCaR中的 LRU 替换为 SR-LRU，将LeCaR中的 LFU 替换为 CR-LFU

1) 通过历史预测信息更新 LRU 和 LFU 的权重，控制对 SR-LRU 和 CR-LFU 的动态使用

2) SR-LRU:

1) **LRU Problem**：scan型负载会替换掉cache中被访问多次的page

2) 它将缓存分为两部分：一部分仅包含具有多个访问权限的项（R），另一部分用于单访问项以及具有多个访问权限的旧项（SR）。SR分区允许SR-LRU具有抗扫描性；一个用于容纳新项目的分区，以便它们不会影响R中的重要项目。SR-LRU仅从SR分区逐出-当缓存已满时，它在缓存未命中时逐出SR的LRU项目。R中较旧的项被降级为SR，以便只保留在R中重用的重要项。此外，SR-LRU维护的历史列表的大小与包含最近逐出的项的缓存的大小相同。

3) 当缓存遗漏时，x不在历史列表中，x会被插入到SR的MRU位置，如果缓存满了，SR的LRU项会被驱逐到HLU。如果缓存满了，SR的LRU项会被驱逐到H，如果H满了，算法会删除H的LRU项以腾出空间。缓存遗漏时，x在H中，x被移到R的MRU位置；缓存命中时，x在SR中，x被移到R的MRU位置；缓存命中时，x在R中，x被移到R的MRU位置。

3) CR-LFU:

1) **LFU Problem**：如果要访问的项目数大于缓存的大小，则LRU风格的算法将导致缓存内容的搅动，从而重复地将项目插入缓存并从缓存中逐出

2) 抗搅扰LFU（CR-LFU）修改了纯LFU中的替换机制，当多个缓存项的访问频率最低时，选择MRU（Most Recently Used）项来打破束缚。通过选择MRU项，CR-LFU有效地将频率最低的项目子集 “锁定 “到缓存中，使 缓存算法产生命中。
1.1.2.2 采用自适应的动态学习速率

对于每一轮迭代，采取如下操作：

1) 若学习速率改变 1) 性能改变 1) 变优，强化变化趋势 2) 变差，反转变化趋势 2) 若学习速率未改变 1) 性能改变 1) 变优，不更新 2) 变差，随机条约 3) 如果学习速率不变，并且连续10个窗口大小性能持续下降或变为零，将学习速率重置为初始值

2. 下周任务

  1. 准备写开题报告

  2. 继续了解相关内容

You May Also Enjoy

毕业学长学习分享本科毕设经验

less than 1 minute read

Published:

今天荣庆邀请到张问宗、蒙思洁、吴一凡同学回来给今年带的本科毕设学生分享了宝贵经验，以免同学们踩雷。以下是蒙思洁和吴一凡做的分享经验文档。

毕设分享

1. 2023年整体时间线

1.1 实验阶段 - 前中期

1月中旬-2月中旬  |  寒假 + 开题报告（3000字 or 6页）
2月中旬-4月上旬  |  详细了解毕设内容 + 实验开端（配环境之类的） + 翻译（中文6000字）+ 应对中期（有阶段性成果） 
4月中           |  中期报告（3000字 or 6页）（抽到的人做ppt汇报，没抽到的提交文档即可） 
4月中旬 — 4月底  |  实验后期（赶代码）
每周要写指导记录（答辩前不少于16次，每周一次）（最好就1次/周，要不然后期补起来很费劲，不好编x）
  • 建议趁早做计划，因为实际进度很有可能比计划慢，做计划的时候一定要给自己预留好缓冲时间。
    • msj：当时拟的计划是 - 4月底结束实验，五一假期开始写论文，写半个月，结果果然晚了，五一假期结束才开始写的论文。

1.2 论文阶段 - 后期

  • msj：进入论文阶段的时候，代码实际上还有问题，需要边调整边写论文。（时间无敌紧张）

（👇当时的安排表和实际完成情况）

（msj的计划表）
√ 5.4 - 18:00~24:00  |  算法的数据分析  |  提前开始绘图、绘表
√ 5.5                |  C1 绪论 
√ 5.6                |  C2 数据准备 
√ 5.7 ~ 5.8          |  C3 主体
x 5.9 ~ 5.10         |  C4 测试 
x 5.11               |  摘要、C5、结论、检查排版、检查文章通顺度
（后续时间节点的补充↓）
※ 5.17 盲审，要提交盲审版论文（20000字 or 40页正文）
※ 5.24 正式答辩，打印答辩材料+提交答辩版论文+做答辩ppt+排练答辩ppt
※ 6.4  提交所有留档材料（交了17个），提交最终存档版论文
  • 时间安排：
    • 写论文：一周的时间写论文真的很紧张！！！所以时间安排一定要往前提！！
    • 审论文：要考虑给导师留足帮忙审核论文+提意见的时间！！（至少得留半周吧！）
  • 去年毕设答辩的时候整体的时间节点连接都很紧，所以盲审开始之后，基本上就没有太多的精力能再回头进行实验+大改论文了。
    • 盲审前：把毕设的实验部分做完！
    • 盲审后：专注于论文的修改（参考导师意见）+ 准备答辩！
      • 后期要提交的材料很多，可以考虑列表整理，以及和实验室同学互相对一下提交进度。
    • 正式答辩前：针对盲审版论文给出的修改意见，和导师讨论后再修改一版论文。
    • 正式答辩后：基本能进入缓冲休息阶段。接下来基本上是根据学院的要求修改自己的各种材料，提交。

2.分享

2.1 自觉性

  • 可以把毕设看成一个项目，靠自己的自觉来push自己完成。
    • 要有自己的想法：自己要逐渐开始考虑“下一步要怎么做”的问题，不能光等着导师安排。
    • 摆烂不可行！！！

2.2 有计划

  • 提前列个大计划出来，给出一些大的关键时间点，按计划完成毕设。
    • 列计划的时候可以尽可能的给出一些“能可视化”的判断标准，这样方便自己按节点检查计划完成效果。
    • 盲审开始后，要提交的东西非常多，列一个“有轻重缓急”的计划表能方便自己及时检查是否漏交什么东西。
  • 减少拖延症，计划尽量往前赶。
    • 如果牵扯到复试，那3月份还需要分精力准备复试，毕设的进度势必会更慢，所以考虑在3月份之前尽量多做点东西出来。

2.3 勤交流

  • 勤找导师交流：
    • 不要因为害怕老师就刻意不找导师交流。
    • 讨论计划合不合理、讨论毕设思路合不合理、讨论论文写作的框架合不合理…
      • （在完成细节之前跟导师讨论大方向，至少能保证大方向不偏）
  • 勤找同学交流。

2.4 多检查

  • 实验结果，自己多检查。

  • 论文初稿，自己多检查：

    • 写论文阶段，写完之后自己先多读两遍，先改掉一些显眼的错误（错字、病句、图文不匹配、排版）等等。
      • 可以写完一章改一章，也可以全写完之后整体回头看，但一定要回头检查！

北理邮箱客户端设置

less than 1 minute read

Published:

北理工邮箱客户端设置，几经波折，记录一下过程，以便后续使用。

客户端邮箱，需要设置协议参数，包括IMAP、POP3和SMTP。其中收件服务器协议有两个：IMAP和POP3。发现服务器协议只有SMTP。

协议参数的来源有两个，官网底部和QA，都不一样，很容易设置错误。以下是设置Outlook 2016、Win 10/11自带邮件和苹果手机邮件客户端的过程细节：

  1. Outlook 2016 1）选择POP3 2）接收服务器：mail.bit.edu.cn 3）发送邮件服务器：smtp.bit.edu.cn 4）登录信息，用户名（邮件地址@前面）

  2. Win 10/11自带邮件 1）添加账户 2）高级设置 3）Internet电子邮件 4）填写表单：电子邮件地址、用户名、密码、账户名、使用此名称发送你的邮件、传入邮件服务器、账户类型、传出（SMTP）电子邮件服务器。需要说明的是，用户名填写同电子邮件地址、账户名填写电子邮件地址@前面，账户类型选择POP3。传入邮件服务器：mail.bit.edu.cn，传出（SMTP）电子邮件服务器：smtp.bit.edu.cn。需要用于传出电子邮件的SSL，不勾选。 5）填写完毕点击登录，即可同步邮箱，也可以发送。

  3. 苹果手机邮件客户端 1）添加其他POP、IMAP 2）填写全名、电子邮件 3）收件服务器，主机名（mail.bit.edu.cn）、用户名（邮件地址@前面）、密码 4）发件服务器，主机名（smtp.bit.edu.cn）、用户名（邮件地址@前面）、密码、不使用SSL 5）选择IMAP 6）确定等待验证。

对pthread_create未定义的引用

less than 1 minute read

Published:

本篇博客记录编译CSAPP课本code/ecf/waitpid1.c的错误调试过程

在Linux编译，出现错误：

/tmp/ccYURWPy.o: In function `main':
waitpid1.c:(.text+0x12): undefined reference to `Fork'
waitpid1.c:(.text+0xb6): undefined reference to `unix_error'
collect2: error: ld returned 1 exit status
(base) [root@instance-3kolm650 ecf]# gcc -I. -o waitpid1 waitpid1.c csapp.c
/tmp/ccnEDu7P.o: In function `Pthread_create':
csapp.c:(.text+0x1049): undefined reference to `pthread_create'
/tmp/ccnEDu7P.o: In function `Pthread_cancel':
csapp.c:(.text+0x107b): undefined reference to `pthread_cancel'
/tmp/ccnEDu7P.o: In function `Pthread_join':
csapp.c:(.text+0x10b8): undefined reference to `pthread_join'
/tmp/ccnEDu7P.o: In function `Pthread_detach':
csapp.c:(.text+0x10ea): undefined reference to `pthread_detach'
/tmp/ccnEDu7P.o: In function `Pthread_once':
csapp.c:(.text+0x114a): undefined reference to `pthread_once'
/tmp/ccnEDu7P.o: In function `Sem_init':
csapp.c:(.text+0x1172): undefined reference to `sem_init'
/tmp/ccnEDu7P.o: In function `P':
csapp.c:(.text+0x119a): undefined reference to `sem_wait'
/tmp/ccnEDu7P.o: In function `V':
csapp.c:(.text+0x11c2): undefined reference to `sem_post'
collect2: error: ld returned 1 exit status

出现原因，由于csapp.h引用了pthread库，不是linux系统默认库，链接时候需要使用库libpthread.a，所以在使用pthread_create创建线程时候，要在编译中加-lpthread参数选项

gcc -I. -lpthread -o xxx

-I. 表示在本目录寻找头文件

学生论文读后感分享

less than 1 minute read

Published:

本篇博客记录硕士生马越同学阅读4篇Sigcomm论文的读后感。