etcd-io
Exploratory test for freepages allocator
Free pages allocation is extremely sensitive piece of bbolt logic. Double releasing a page has catastrophic consequences for bbolt file consistency and data durability.
Current code with 2 implementations (array & map) using the same struct is very hard to follow and justifies bigger refactor. But I would be afraid to touch this code without investing in extensive unit/exploratory tests for this data structure.
I think we should have a test that uses just free-pages allocator:
It randomly keep performing one of the following action.
-
performs a RW TX that: - releases some of the nodes present at the beginning of transaction. - allocates random number of nodes. Some of this nodes are multi-page. The closer to DB size limit, the less should get allocated. - sometimes parforms a rollback after such changes.
-
start a RO transaction. Copy the list of 'available' pages to per-tx data.
-
closes one of the RO transactions [and verifies all the nodes present at the beginning of the transactions are still available]
I think this could be based on 2 data structures:
map [pageId] -> (txId, allocated) - a map that stores for each page, the last RW transaction that 'wrote' (allocated) the page
list[ (pageid, size) ] - list of pages that are 'in-use' at the current RW transaction
Freelist is not locked - so the test should be executed from a single thread.
@ptabor Sorry if I misunderstand something. How to performs a RW transaction when there is open RO transaction? Or do you mean performs a RW transaction only after all RO transactions have been closed?
You can have mulitiple read only transactions in bbolt parallel to the RW transaction. The RO transaction should see the state of the system as it was at the time the transaction started.
go db.View({
func() { ... }
expect(get(foo) == 'old')
sleep(10 sec)
expect(get(foo) == 'old')
});
db.Update( func (tx) { tx->Set('foo', new' });
db.View({ func() { ... }
expect(get(foo) == 'new')
Freepages allocator is here a crucial part to provide the semantic. It deallocates pages only when the last transaction potentially accessing them has be closed.
