• sdong's avatar
    HashLinkList memtable switches a bucket to a skip list to reduce performance outliers · 9c332aa1
    sdong authored
    In this patch, we enhance HashLinkList memtable to reduce performance outliers when a bucket contains too many entries. We switch to skip list for this case to enable binary search.
    Add threshold_use_skiplist parameter to determine when a bucket needs to switch to skip list.
    The new data structure is documented in comments in the codes.
    Test Plan:
    make all check
    set threshold_use_skiplist in several tests
    Reviewers: yhchiang, haobo, ljin
    Reviewed By: yhchiang, ljin
    Subscribers: nkg-, xjin, dhruba, yhchiang, leveldb
    Differential Revision: https://reviews.facebook.net/D19299