Upstream: undo feature id sharding

[yhahn]

Transferring braindump notes to here. This issue affects both carmen-cache and carmen, but the problem originates mostly from the grid cache outward so capturing here for now.

Why the problem exists at????!!!

Feature storage is sharded right now not just for historical reasons but because the grid storage in our PBF format currently limits us 20-bit feature IDs.

• https://github.com/mapbox/carmen-cache/blob/master/src/binding.cpp#L1136

Even with a larger feature ID space (e.g. if we went from 53 bits => 64 bits) we would probably encounter feature ID collisions at which point we'd need to store them in a nested fashion with some kind of secondary factor (like cover zxy) to disambiguate where possible.

Example:

feature A 120951912 \
                     +----> store together, distinguish by id + zxy
feature B 120951912 /

Rough braindump of how to untangle

• We'd want unlimited feature ID storage space
• We'd want enforcement of feature ID uniqueness (per index) at indexing time
• We'd want to undo "sharded" feature storage
• We'd want to stop using uint-64 as a way to transfer cover data into and out of carmen-cache -- we'd probably define a new PBF message format (variable length, allowing for any size feature IDs) for encoding this information

I think these would all be very positive changes, just a pretty solid, invasive refactor

cc @mapbox/geocoding-gang

[springmeyer]

This looks very old and perhaps stale. /cc @miccolis - can this be closed?

[ingalls]

cc/ @apendleton

[apendleton]

Hm, old, but not really stale? Feature IDs are still truncated to 20 bits, we still don't enforce uniqueness, we still clumsily handle collisions, and assuming the API boundary between carmen-cache and carmen stays the same, we'd need to move to a new way of communicating grid data back and forth (that is, not integers anymore) in order to work around it. I think there are probably even bigger grand-vision questions around carmen-cache now than there were then, but at least some potential avenues forward would involve executing on the plan proposed here.