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