Index Cache: Change fetchMulti interface to return slice rather than map

[yeya24]

Is your proposal related to a problem?

IndexCache interface has two FetchMulti methods FetchMultiPostings and FetchMultiSeries.

For example, FetchMultiPostings looks like below:

FetchMultiPostings(ctx context.Context, blockID ulid.ULID, keys []labels.Label, tenant string) (hits map[labels.Label][]byte, misses []labels.Label)

The hits map is kind of unnecessary. It can be replaced by a slice [][]byte where the index maps to the input keys. This should save some memory when fetching data from caches.

Describe the solution you'd like

Change FetchMultiPostings to this method below. We can even change misses to []int and see if it is something easy to do.

FetchMultiPostings(ctx context.Context, blockID ulid.ULID, keys []labels.Label, tenant string) (hits [][]byte, misses []labels.Label)

[Zyyeric]

To convert 'Label' to an int probably requires some forms of hash function, but it will always compromise to the possibility (despite very low) of collision which would result a missing cache hit.

Would this be acceptable? or there is a better implementation you have in mind?

[yeya24]

@Zyyeric The return result slice can use the index as of keys []labels.Label by maintaining the same order. But the downside is that we have to allocate the slice even though nothing is cached.

[Zyyeric]

@yeya24 Ahh I see, this sounds valid. Despite the allocating for miss hits for the slice, its memory overhead shall still be lower than that of a map. This shall not be hard to do. I'll give it a shot.