CMU课程15-721数据库系统设计(第二个项目)

CMU课程15-721最新一期开课啦!

课程安排

Project #2 - Concurrent Index

实现一个支持无锁并发的BW树作为索引底层数据结构

  • PID到指针的映射表
  • 改动链
  • split/merge
  • 动态垃圾回收

论文中几个奇怪概念:

  • install CAS 即使用CAS操作来替换映射表中的项目
  • epoch机制 即使用版本号保证没有其他操作正在进行(可以执行物理删除)

实现要求:

  • 支持重复key且可以配置,如果配置为不允许则InsertEntry插入重复key的索引条目时返回false,且DeleteEntry只删除完全匹配的索引条目
  • 支持consolidation,需要考虑阈值
  • 支持split与merge,特别是并发插入与删除的情况
  • 应该有工具函数帮助测试结构完整性并可以修复,类似fsck
  • 支持动态垃圾回收,调用Cleanup函数进行物理释放,会使用GetMemoryFootprint统计内存情况
  • 支持reverse iterators并保证concurrent mutators正常工作

Profile方法

profile工具使用valgrind或perf

  1. valgrind

使用memcheck或callgrind动态检查:valgrind --tool=callgrind --trace-children=yes ./build/src/peloton -D data &> /dev/null&

  1. perf

通过收集linux的cpu周期计数实现,也支持收集其他事件
perf record -e cycles:u -c 2000

本站总访问量