KAFKA-6432: Make index lookup more cache friendly (#5346)
KAFKA-6432: Make index lookup more cache friendly (#5346)

 KAFKA-6432: Make index lookup more cache friendly

For each topic-partition, Kafka broker maintains two indices: one for message offset, one for message timestamp. By default, a new index entry is appended to each index for every 4KB messages. The lookup of the indices is a simple binary search. The indices are mmaped files, and cached by Linux page cache.

Both consumer fetch and follower fetch have to do an offset lookup, before accessing the actual message data. The simple binary search algorithm used for looking up the index is not cache friendly, and may cause page faults even on high QPS topic-partitions.

In a normal Kafka broker, all the follower fetch requests, and most consumer fetch requests should only look up the last few entries of the index. We can make the index lookup more cache friendly, by searching in the last one or two pages of the index first. 

Reviewers: Colin Patrick McCabe <342564bc1ab1e55103f85104b5e013adfdf828cb@cmccabe.xyz>, Guozhang Wang <wangguoz@gmail.com>, Ted Yu <yuzhihong@gmail.com>,  Ismael Juma <github@juma.me.uk>, Sriharsha Chintalapani <sriharsha@apache.org>
TiVo/kafka,Esquive/kafka,noslowerdna/kafka,KevinLiLu/kafka,apache/kafka,mihbor/kafka,lindong28/kafka,Chasego/kafka,guozhangwang/kafka,noslowerdna/kafka,TiVo/kafka,Esquive/kafka,lindong28/kafka,apache/kafka,Chasego/kafka,sslavic/kafka,gf53520/kafka,Esquive/kafka,richhaase/kafka,guozhangwang/kafka,apache/kafka,lindong28/kafka,gf53520/kafka,mihbor/kafka,lindong28/kafka,TiVo/kafka,richhaase/kafka,Esquive/kafka,gf53520/kafka,richhaase/kafka,sslavic/kafka,TiVo/kafka,gf53520/kafka,mihbor/kafka,KevinLiLu/kafka,sslavic/kafka,Chasego/kafka,guozhangwang/kafka,ollie314/kafka,sslavic/kafka,noslowerdna/kafka,ollie314/kafka,richhaase/kafka,KevinLiLu/kafka,ollie314/kafka,noslowerdna/kafka,guozhangwang/kafka,apache/kafka,ollie314/kafka,Chasego/kafka,mihbor/kafka,KevinLiLu/kafka