Topic: An optimal engine for UTXO db (Read 3171 times)

Because the title of this thread is about DBMS a.k.a. DB engines.

Because of the fact that the data stored is actually about money.

You just have zero experience dealing with financial data processing, and actually less-than-zero as far as legally-responsible fiduciary-duty-bound handling of money for other people.

Therefore what you are doing are just educational toys. I have nothing against you designing and playing with those toys. But if you thinking that you are making something that will become a real financial product you set yourself for a CIYAM-level disappointment.

https://bitcointalksearch.org/topic/m.13995422

To answer the OP, it is difficult to decide what makes an optimal engine for the UTXO set because as usual one has to make design trade offs.

1. If you are interested in super fast import, i.e. processing the block chain in shortest time, you are dealing with a large amount of insert/delete of key value pairs where the key contains a crypto hash. They are essentially random values and will fall all over the place. However, the net amount fits in an average development machine so you can work entirely in RAM. However, bitcoin core can't assume that you have several GB of RAM available!

Here, the main problem of leveldb is that its engine uses skip lists. Their average search complexity is ln(N). You'd be better off with a hash table which is O(1). For the record, skip lists and B-Trees are used when we need to retrieve the keys in order and it's not the case here.

Because blocks depend on previous blocks, processing them in parallel isn't easy. I'm not sure it helps even. (Block validation excluded)

2. If you are building a browser, then you can precalculate the hell out of your data set. The usual database tricks apply: lineralize the key space, compress values, use bloom filters, partition your data, etc. You are working with data than changes only every 10 mn, so very quite static. If you need the unconfirmed tx, add them on top. This case isn't what a db is really used for anyway. A lot of effort is put into concurrency and durability. When they are not crucial, faster implementations exist - especially if you can choose the hardware.

3. If it's for checking transactions in a full node, there are relatively few of them. Once you have extracted the UTXO, we are talking about a few million records which is peanuts in today's standards.

In conclusion, leveldb is fine for its usage it bitcoin core. The choice of a skip list vs hash table engine is questionable, but I don't think that makes a big difference for most of the users.

Maybe, you could describe your usage?

1) of course on fast hardware it is ok to have slow software. but slow software on slow hardware is not acceptable. And if you have to write fast software for the slow system, there is no point to write slow software is there?

2) initial sync and re-sync are very important. continuous operation will be running out of RAM directly, combining data from the readonly dataset. And it is not so easy to test things before they are running. I am assuming that chain reorgs wont go past 100 blocks very often. In the event it does, you would have a few minutes of downtime to regenerate the most recent block.

If it has nothing to do with DBMS, then why did you keep doing the database class thing?

As far as performance of iguana when it is complete, it will be fast for things that typically are very slow, ie. importprivkey.

You are making 2 unrelated mistakes:

1) mixing hardware speed with software speed. On fast hardware it is OK to have slow software.

2) your tests are only including sync speed (both initial and re-sync after getting temporary offline). You don't test continuous operation nor chain reorganization.

This has nothing to do with using or not using a DBMS. It is a more fundamental question what your system will be capable of when finished.
 

If you think I am ignoring overall system speed, then you are not really reading my posts.
I also like kokoto's requirements and my dataset is designed to get good overall system performance for those, and also to be able to do blockexplorer level queries from the same dataset for lower level blockchain queries.

Not sure what your point is? Maybe you can try to run a DB system written in JS? I dont know of any that is anywhere fast enough.

It is not a choice between DB vs no DB, but rather no-DB vs nothing, as my requirement is for a system that works from a chrome app

James

This is a self-refuting argument.

Hardware gets faster therefore people are willing to put up with slower software.

Do not confuse hardware speed and software speed when discussing speed of the whole system.

Edit: A good example of clear thinking from somebody who isn't professionally doing software development:

please be specific

What part of bitcoin makes it not able to scale?

I have solved the "takes too long to sync" issue. I think with interleaving, a much greater tx capacity is possible. Using BTC as the universal clock for all the other cryptos will let smaller chains deal with lower value transactions. And now a way to use GPU for blockchain operations.

James

me. and I am ready to repeat it again

if you want really fast speed, you can make a CUDA/OpenSSL version and use a dedicated core per bundle, among other optimizations.

With most all the data being read only, the biggest challenge of GPU coding (out of sync data between cores) is already solved.

It might take a few GPU cards to store all the dataset, but then all RPC to scan the entire blockchain happens in milliseconds

using the CPU for the latest bundle can create a system that keeps up with new blocks.

Who said there was a scaling problem with bitcoin?

James

thanks. i like it.

do you mean reprocessing all the raw data from scratch? With 8 cores that would take 30 minutes or less depending on if you validate all sigs from block0 or not, maybe a bit longer.

If you have all the processed bundle files, then in the time it takes to memory map 200 files, the data set is accessible to the CPU. So that would be up to the OS/HDD, but I am seeing it map all the files in a few seconds on a lowend laptop and less than a second on a VPS server.

Once the bundle files are mapped, then a block explorer (not blockchain) level data is available for all addresses, blocks, tx

James

so say, @james you only have the blocks data - from 1 to 400000. stored close, on ssd disk or whatever. say ramdisk
how long does it "load" for you to have all the database content of the block 400000?

this is my preferred expression.
thank you.

i think its nice and I will look into it more.

to encode the tx data in the following format:


struct iguana_txid { bits256 txid; uint32_t txidind,firstvout,firstvin,locktime,version,timestamp,extraoffset; uint16_t numvouts,numvins; } __attribute__((packed));

struct iguana_unspent { uint64_t value; uint32_t txidind,pkind,prevunspentind,scriptoffset; uint16_t hdrsi:14,type:4,vout:14; } __attribute__((packed));

struct iguana_spend { uint32_t spendtxidind,scriptoffset:31,coinbase:1; int16_t prevout; uint16_t numsigs:4,numpubkeys:4,p2sh:1,sighash:4,external:1,sequenceid:2; } __attribute__((packed));

struct iguana_pkhash { uint8_t rmd160[20]; uint32_t pkind,pubkeyoffset; } __attribute__((packed));

I describe this in the iguana child board in a lot more detail

Since I am not you, I do not know what expression requirements exist to allow proper parsing and semantic understanding by you.

Maybe you can ask the specific questions after reading the iguana threads?

James

Sounds good, but can you express it in a way that I could understand, what does it actually mean to do for the software?

You would need a high end CPU to fit it all in L caches and not all the "DB" would fit into CPU cache, unless you partitioned queries for the different datasets to different cores and strongly influenced the content of each CPU's cache

iguana_ramchain.c has most of what is needed, but right now it is a construction zone as I just change the data structures to support lossless encoding/decoding and quite tricky doing that with all the constraints.

Assuming you have already the blockchain internally, it might be easier to just directly generate the bundle files. The key is the encoding and if interop is not a constraint, then you can just use a similar model without making it exactly compatible. Of course, having an independent implementation would be a fantastic cross check, so if you are up for that we can work out a strict memory layout. Then you will know you made things bugfree if it makes the identical file and debugging is quite the chore without this...

I am starting to describe in some detail the internal data formats: https://bitco.in/forum/forums/iguana.23/

The codebase is highly tuned and optimized to do the parallel sync and due to this, I have each peer's thread create the first pass file(s). Then helper threads aggregate a bundle and generate the bundle file. the ramchain_iterate handles both the raw and expanded forms, so maybe a port of iguana_ramchain.c is a good way to port it.

The functions ending with PT indicate it is running in a peer's thread and not all functions are needed. the bundlesaveHT function runs from a helper thread and it is the one doing the combining

James

James, can you please describe how you actually implemented your db?
I'm especially interested in the index part, that (according to you) fits into the CPU's cache.

I've been trying to read through your code, but its shit loads and I don't have that much patience.
I once implemented sipa's secp256k functions in Go, so I do have some patience... but it has its limits

Say, I'd like to implement the read-only database you made, in another language - what does it take?

If you just want an embeddable DB, http://sophia.systems/ is pretty good. I see they released a version 2 with hybrid in-memory, which is good as my feedback to them was having everything HDD made it too slow.

The sophia 1.2 was 10x smaller than BDB and much faster, so 2.0 version should be that much better.

but nothing would have the performance/footprint profile of the read-only memory mapped bundles. I just cant double the size of the code just to add a DB, especially as I could just use a deterministic reverse hash chain for a wallet's keypairs. Loss of the wallet passphrase would compromise the privkeys, but it seems the same result as storing independent privkeys in a DB encrypted with the same passphrase.

Making slow but steady progress with the debugging and documenting it here: https://bitco.in/forum/threads/debugging-status.950/

James

this looks like a right way to go, but..

1) I failed to install the software on my linux, following the docs. Or to build the sources....

2) I don't think TCP based API is suitable for the needs of a DB we're discussing here

how do you imagine browsing trough a content of the current 35M+ UTXO records whit this TCP based API?

http://www.extremetech.com/extreme/188776-how-l1-and-l2-cpu-caches-work-and-why-theyre-an-essential-part-of-modern-chips

https://forums.aida64.com/topic/2864-i7-5775c-l4-cache-performance/

The 10x to 40x speed improvements creates very nonlinear performance boosts when the dataset is small enough

James