LKRhash is a hashtable that scales to multiple processors and to millions of items. LKRhash was invented at Microsoft in 1997 by Per-Åke (Paul) Larson of Microsoft Research and Murali Krishnan and George Reilly of Internet Information Services. LKRhash has been used in many Microsoft products. The techniques that give LKRhash its performance include linear hashing, cache-friendly data structures, and fine-grained locking.
- Northwest C++ Users’ Group talk, June 2012. Speaker Deck Slides.
- Unpublished paper submitted to Software: Practice & Experience (Oct 1999).
- US 6,578,131 patent. Associated PDF contains some of the SP&E paper.
If Microsoft had had 20% time, LKRhash would have been my main project. I put a lot of effort into making it a polished, well-tuned library that was used in multiple products across the company. I even ported the C++ code to kernel mode, though it never ended up in a production driver, as far as I know. Several years ago, after I left Microsoft, I attempted to get it open-sourced. However, despite some help on the inside, we were never able to surmount the legal barriers.