Adaptive Radix Tree for Indexes

[absolutelightning]

Description

Using Adaptive Radix Tree for Indexes in new V2 controller architecture instead of Immutable Radix Tree.

It should reduce the memory usage.

Reference - https://db.in.tum.de/~leis/papers/ART.pdf https://github.com/armon/libart/

Testing & Reproduction steps

CI

Benchmarking - For 10000 inserts and lookup

BenchmarkInsertSearchRadix-12    2655649	       450.2 ns/op	    1664 B/op	      15 allocs/op
BenchmarkInsertSearchART-12    	 2736802	       439.5 ns/op	    1666 B/op	       4 allocs/op

First is from main and second is from this branch with ART. Second one is better in terms of memory.

Code used

func BenchmarkInsertSearchRadix(b *testing.B) {
	r := iradix.New[int]()
	for i := 0; i < 10000; i++ {
		uuid1, _ := uuid.GenerateUUID()
		for j := 0; j < 10; j++ {
			uuidx, _ := uuid.GenerateUUID()
			uuid1 += uuidx
		}
		r.Insert([]byte(uuid1), i)
	}
	keys := make([]string, 10000)
	for i := 0; i < 10000; i++ {
		uuid1, _ := uuid.GenerateUUID()
		for j := 0; j < 10; j++ {
			uuidx, _ := uuid.GenerateUUID()
			uuid1 += uuidx
		}
		keys[i] = uuid1
	}
	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		uuid1 := keys[n%10000]
		r.Insert([]byte(uuid1), n)
		r.Get([]byte(uuid1))
	}
}

func BenchmarkInsertSearchART(b *testing.B) {
	r := adaptive.NewAdaptiveRadixTree[int]()
	for i := 0; i < 10000; i++ {
		uuid1, _ := uuid.GenerateUUID()
		for j := 0; j < 10; j++ {
			uuidx, _ := uuid.GenerateUUID()
			uuid1 += uuidx
		}
		r.Insert([]byte(uuid1), i)
	}
	keys := make([]string, 10000)
	for i := 0; i < 10000; i++ {
		uuid1, _ := uuid.GenerateUUID()
		for j := 0; j < 10; j++ {
			uuidx, _ := uuid.GenerateUUID()
			uuid1 += uuidx
		}
		keys[i] = uuid1
	}
	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		uuid1 := keys[n%10000]
		r.Insert([]byte(uuid1), n)
		r.Search([]byte(uuid1))
	}

PR Checklist

• [x] updated test coverage
• [x] external facing docs updated
• [x] appropriate backport labels added
• [x] not a security concern

[github-actions[bot]]

This pull request has been automatically flagged for inactivity because it has not been acted upon in the last 60 days. It will be closed if no new activity occurs in the next 30 days. Please feel free to re-open to resurrect the change if you feel this has happened by mistake. Thank you for your contributions.

[absolutelightning]

Closing since priorities changed.

[hc-github-team-consul-core]

This PR has diffs in agent/uiserver/dist. If the changes are intentional, add the label pr/update-ui-assets. Otherwise, revert changes to agent/uiserver/dist.

[hc-github-team-consul-core]

This PR has diffs in agent/uiserver/dist. If the changes are intentional, add the label pr/update-ui-assets. Otherwise, revert changes to agent/uiserver/dist.

[absolutelightning]

Removed locks. Closing the PR since it is not a priority now.