Facebook has released F14, one of the tools it uses to manage the enormous amount of data that the social network moves daily. It is a hash table developed in C + + programming language, which is already available in Folly, the Open Source component library of the social network.
Hash tables are associative arrays or containers that are used to store and search for data quickly. They are able to perform these tasks optimally even if the volume of data increases dramatically.
F14 is a 14-way probing hash table, it uses a hybrid storage called F14Fast, which chooses the most efficient approach to store data based on the types of value. "Its core algorithm leverages vector instructions to increase the load factor while reducing collisions, because it supports multiple memory layouts for different scenarios, delivering a CPU and RAM efficiency that is robust across a wide variety of use cases”, explain Facebook software engineers Xiao Shi and Nathan Bronson in a blog post.
The operation of this tool is based on a strategy called chunking to reduce the likelihood of collisions. Performance is significantly improved by reducing CPU and memory overhead by managing empty slots in the hash table, which is quite useful in cases where many insertion and deletion workloads are handled.
Other aspects that improve performance are the use of less code and the fact that F14 reduces the need to create objects and copies within the hash tables and the surrounding code.
F14 is available for download at GitHub.
See all the technical details at Facebook official blog.
You must authenticate to review this post