proposal: allow lock-free updates?

[gaissmai]

Dear users,

I have implemented an InsertPersist method in the persist branch, and before I go to the trouble of writing the same for DeletePersist and UpdatePersist ModifyPersist, I'm asking for a thumbs up or down on whether this would be used.

Please consider that the lock-free persist methods are in the microsecond range as opposed to nanoseconds for normal insert/delete.

[gaissmai]

@tobez are you still using bart ? If so, could you please test the lock-free concurrency, see the new test example in the main branch. I need external testers with real life applications.

[LaurenceJJones]

Hey @gaissmai if its of any use I planned to migrate our naive approach of handling lots of IP's and Ranges to bart soon hopefully.

Would appreciate any feedback to my implementation of bart.Table via crowdsecurity/cs-haproxy-spoa-bouncer#66 the only issue I had was the usage of finding the item to update, maybe im being dumb as having to call delete just to reinsert it again was not the right approach.

Thank you if you find the time!

[gaissmai]

@LaurenceJJones please use ModifyPersist for this; perhaps I should add it to the example.

If you can't make progress with this, just get in touch again.

Currently, I don't have time to conduct a full code review, but I'm happy to help with specific problems, and I would also be interested in feedback on whether you run into any issues with bart Persist.

Please also run the tests for table.*Persist methods using the race detector.

[LaurenceJJones]

@LaurenceJJones please use ModifyPersist for this; perhaps I should add it to the example.

If you can't make progress with this, just get in touch again.

Currently, I don't have time to conduct a full code review, but I'm happy to help with specific problems, and I would also be interested in feedback on whether you run into any issues with bart Persist.

Please also run the tests for table.*Persist methods using the race detector.

Yes as soon as I posted I found the ModifyPersist, thank you for a response!

If I encounter any issues, I'll open a new one but so far it works flawlessly.

Thank you for your hard work.

[gaissmai]

@LaurenceJJones ups, I see my text in the issue description still listed the old UpdatePersist, so it's clear I misled you, sorry about that.

[gaissmai]

@LaurenceJJones Since I am a curious person, I browsed around a bit in your project. You write somewhere that you populate the trie during the init phase using a batch process. Question to you: Is there a clear init phase without any readers accessing the trie? If so, you would naturally fill the table much faster and more memory-efficiently using table.Insert during the init phase, and then use this initially filled table as a base table in the concurrent branch. Do you understand what I mean, and is there even a separate init phase?

[LaurenceJJones]

@LaurenceJJones Since I am a curious person, I browsed around a bit in your project. You write somewhere that you populate the trie during the init phase using a batch process. Question to you: Is there a clear init phase without any readers accessing the trie? If so, you would naturally fill the table much faster and more memory-efficiently using table.Insert during the init phase, and then use this initially filled table as a base table in the concurrent branch. Do you understand what I mean, and is there even a separate init phase?

Yeah kind off, using the phrase "init" is kinda right and wrong at the same time.

So without going into technical details, in short, when the component is spinning up it has to fetch the first list of Ip's and Ranges from a http endpoint to issue "decisions" (these can be ban, captcha etc etc), the first list may contain 15k to over 100k decisions depending on how many the user has active.

This is where the polling system fetches decisions and add / remove functions uses ModifyPersist to do an atomic swap on the trie.

Thinking now, I could set a initial boolean which gets set to false once the first list comes through and use Insert directly and then afterwards switch to modifypersist to do the swapping. The readers will come up in unison to this polling system so yeah there is a chance that readers could attempt to access before Insert run.

However, we can easily handle it by simply within the "checking" function check this boolean and return nothing because the initial data hasnt been populated, and since there is no data the check will ultimately return nothing anyways even if the readers have access.

sorry if I went too deep on anything, it useful getting your perspective and appreciate any time / curiosity you can afford

[gaissmai]

@LaurenceJJones Thank you for the explanation; no problem at all, as I was the one who inquired.
That's kind of what I thought. I can imagine that the startup phase with a pure Table.Insert is completed about a factor of 1000 faster (and less GC pressure) than with Table.InsertPersist. Of course, it depends on whether it is essential for the module if it's ready after microseconds or only after milliseconds (up to a second), depending on the size of the table. To decide that, you probably need a benchmark with your typical payload.

I am very interested in having a good tester who can test the concurrency code in a real-world scenario.

Thank you for flying with Bart

[gaissmai]

The readers will come up in unison to this polling system so yeah there is a chance that readers could attempt to access before Insert run.

There should be no nil pointer dereference (without a guarantee, to be fuzzy tested). If it doesn't cache the false answer and asks again on the next access, that would be the simplest solution without increasing code complexity too much.

[gaissmai]

There should be no nil pointer dereference (without a guarantee, to be fuzzy tested).

but a index out of range panic with unsynchronized Table.Delete

 83 // MustGet returns the value at index i without checking if it exists.
 84 //
 85 // Use only after ensuring i is set (via Test(i)); otherwise it may return
 86 // an incorrect value or panic. Intended only for tight, validated loops.
 87 func (a *Array256[T]) MustGet(i uint8) T {
 88   return a.Items[a.Rank(i)-1]                                                                                   
 89 }

this was a bad advice from me!

[LaurenceJJones]

There should be no nil pointer dereference (without a guarantee, to be fuzzy tested).

but a index out of range panic with unsynchronized Table.Delete

83 // MustGet returns the value at index i without checking if it exists.
84 //
85 // Use only after ensuring i is set (via Test(i)); otherwise it may return
86 // an incorrect value or panic. Intended only for tight, validated loops.
87 func (a *Array256[T]) MustGet(i uint8) T {
88 return a.Items[a.Rank(i)-1]
89 }

this was a bad advice from me!

appreciate the feedback loop, helping me progress the implementation. I am only using insert for initial table load, removals or modifications use modifypersist methods (cause underlying data type may hold multiple items). To which already increases performance, tested 100k initial load took 3 seconds with modifypersist but sub 1 seconds with insert only operations. 👍🏻