Distributed search engines using BitTorrent and SQLite
github.com
github.com
[0]: https://github.com/mikeal/IPSQL
[1]: https://0fps.net/2020/12/19/peer-to-peer-ordered-search-inde...
[1]: https://github.com/attic-labs/noms/blob/master/doc/intro.md#... [2]: https://www.dolthub.com/blog/2020-04-01-how-dolt-stores-tabl...
Whereas Noms Prolly-Trees are like B+Trees, since all values are stored in the leaves.
Merkel Search Trees use the prefix of the hash of inserted keyvalues (number of leading zeros) to determine which layer will contain that keyvalue. This provides a deterministic tree structure for any given set of keyvalues, when you arrange them by key order.
Noms Prolly-Trees use a rolling hash across the sequence of keyvalues to determine split points, similarly when the number of leading zeros exceeds a threshold. Then those leaves are assigned as children to keyvalues on the next highest layer, which is again split in the same way, until a single root node is left.
Given that i've been using Prolly-Trees for a content addressed store, a lot of the descriptions of Merkel sound similar in properties to how Prolly-Trees behave. I struggle to think of a use case where Prolly would excel over Merkel, or where Merkel would excel over Prolly.
For a tree built on an immutable log, it makes sense to buffer some writes at each level of the tree. When you write a new record, you make a copy of the root node with your latest key-value pair appended to the root node's buffer. If this fills up the cache space in the root node, then you determine which child node corresponds to the most buffered key-value, and flush those corresponding key-value pairs down to that child node, recursively until none of the buffers in nodes are over-full. This means that often only a small number of nodes near the root need to be updated, instead of having to write lots of updated intermediate nodes like you'd need with a normal B-tree. The worst-case behavior is all of the caches being full, resulting in O(log N) nodes being written. Also, frequently written keys remain near the root, so if your read pattern resembles your write pattern, frequently read keys will remain near the root node. For TokuDB Fractal Index Trees, my understanding is that these buffered records can also represent schema changes, so that schema changes can be incrementally and lazily applied.
Of course, if one cached write being flushed down the tree catches up to an older cached write for the same key, the older value is just discarded. Presumably, there's also a periodic incremental operation to save space by removing older cached values. Even for something like a blockchain where you want to keep infinite history, you'd probably still want incremental compaction so that clients wanting to download the entire current state don't need to download the entire history.
Interesting. How does the system know where the result of the query might appear in the file?
SQLite knows where to look for when you open a SQLite database and you run a query, right? It just asks the underlying filesystem to provide N bytes starting from an offset using a C function, then it repeats the same operation on different portions of the file, it does its computation and everybody is happy.
The software relies on sqltorrent, which is a custom VFS for SQLite. That means that SQLite function to read data from a file stored in the filesystem is replaced by a custom function. Such custom code computes which Torrent block(s) should have the highest priority, by dividing the offset and the number of bytes that SQLite wants to read by the size of the torrent blocks. It is just a division.
See: https://github.com/bittorrent/sqltorrent/blob/master/sqltorr...
For future reference: "APSW has the following enhancements/differences over pysqlite 2 (wrapping SQLite 3): - APSW stays up to date with SQLite. As features are added and functionality changed in SQLite, APSW tracks them. - APSW gives all functionality of SQLite including virtual tables, Virtual File System (VFS), BLOB I/O, backups and file control. [...]" -- https://rogerbinns.github.io/apsw/pysqlite.html#pysqlitediff...
https://rogerbinns.github.io/apsw/download.html#easy-install...
Basically, if you install it from pip (without following the directions to install from git directly), then you end up with some ancient version, which rather defeats the point of APSW.
If you only implement the filesystem shims, you will receive everything already figure it out, and the btree engine(storage) will ask you for the given chunk of data where you can resolve to the right torrent chunk, download it and just care about delivering the bytes that were asked.
I deliver sqlite dbs over torrent and the torrent chunks are optimized for the sqlite page sizes which are 64K.
In my case i dont stream the database, but through filesystem VFS it can be done if i had a need for it.
The beauty here lies in the SQLite architecture and the abstraction over pages.
The content itself is distributed, which creates privacy challenges of its own, but control over that content is centralized. If we want automatic updates of the index, we're still relying on a single party to provide them. That single party might respond to DMCAs, remove/censor content etc.
edit: attracted->abstracted
Distributed search engines are not new, many companies tried to make them [1].
I think the main challenges of distributed search engines are not technical. I don't think there isn't much financial incentive to create/maintain/seed them.
There isn't much advantage to using them either (if a alternative is available). I think the only viable use case for them is for indexing pirated torrents.
Maybe a foundation could use this type of technology to lower their expenses. Like a charity version of Google
(But of course, if its over torrent and public the other party would have access to this data..)
But lets not forget, it would only reach the data over torrent if its not local, and as it would do it only once for each block, someone that would be spying over torrent would not have access to further queries after the first hit over that particular piece.
Also, as far as i know, you would only know about the pieces, if its asking it from you, so you would need to seed from as many peers as you can, to have access to all the pieces requests from the party you are interested in..
So even assuming a sophisticated party that could reverse engineer over piece offset access, (and let not forget that if the block size is big, this gets even harder), still, i don't think it would be possible to rebuild the query.
That is already a sign that this project is not going to go anywhere. Anyone who wants to build a server or make this part of their seedbox is going to use Linux or one of the BSDs.
The bigger reasonis, unless im missing something, this is not distributed in the sense most people use the term "distributed" in the context of search engines, so its not as interesting as everyone is making it out to be.
What sense is that? I'm not familiar with "distributed" having some protected/special meaning for search engines.