User:The8472/Tech Stuff

From AzureusWiki

Here some random ideas which popped into my mind or i've read about:

Contents 1 DHT/Distributed tracker 1.1 making Magnet links more useful 1.2 Bloomfilter RPCs 1.3 collapsing PUT and/or GET 1.4 keyword search 1.5 parallel lookup speedup 1.6 Hold Lookup handlers 1.7 DHT key pointers/forwards 2 Bittorrent Core 2.1 Enhanced Messaging & new messages 2.2 Tracker Auth 2.3 Anti-leeching 2.3.1 keeping IP stats 2.3.1.1 non-cheatability of kept stats 2.3.2 trust metrics 2.4 request queue/measuring connection latency 2.5 Info dictionary 2.0 3 Other stuff to optimize 3.1 Crash safety 3.2 Improve use of ByteBuffers 3.3 Concurrency/Atomic 3.4 Generalized Bloom Filters

DHT/Distributed tracker

interesting dht bugs: http://cohesion.rice.edu/engineering/computerscience/tr/TR_Download.cfm?SDID=231

making Magnet links more useful

To make sure that every (none-private) torrent is downloadable via magnet link a node should check how many (recent) entries the key which is normally used to retrieve .torrent information has. If the # of storage entries (use the DHT key statistics query) is lower than a specific value N then the client should publish itself under that key to ensure magnet links work even when the torrent is healthy

[Parg - this has been supported for a while - check the tracker log for "presence queries", this is where clients look to see how well represented a torrent is in the DHT and publish if < 8 (if I recall correctly) values]

Bloomfilter RPCs

The Bloomfiltered Get RPC is capable of a returning a subset of values that are stored under a specific key that match a bloomfilter sent by the requestee.

The Fetch Bloomfilter Index RPC returns a bloomfilter of all values under a specific key. This can be used to intersect with other bloomfilters to narrow down the result list and return a limited set of interesting values from a crowded key.

collapsing PUT and/or GET

Often many nodes store identical values multiple times and then other nodes retrieve exhaustive lists of stored values. When the originator of a value doesn't matter for the retrieving nodes then it should be possible to omit redundant values and use a frequency multiplier instead. E.g. the value X under key Y has been put there by N different originators, value Z under key Y only by 1 originator instead of transmitting X N times and Z once.

Of course the storing node would still have to verify each store to prevent attacks but collapsing PUTs would reduce the amount storage needed and reduce the traffic caused by GETs automatgically. Collapsing GETs would preserve the originator information but at least allow the retrieving nodes to choose low-traffic variants.

keyword search

iff keyword search would be implemented in azureus that should be done in the most traffic-efficient way.

M is an arbitrary value used as redundancy limit from here on.

register a torrent for searching:

1. to register any torrent for keyword search the torrent metadata (e.g. the name, file number, size, infohash etc. etc.) should be stored under a single DHT key K1 (derived from the infohash). A client should verify that there aren't more than M instances of that specific torrent registered under that key
2. then the client dissects the torrent name into words, ommitting all special chars (just look at the silly scene naming rules) and words shorter than 4 latin letters, named W1...Wn

   Note: Special chars means all kind of brackets, dashes, underscores etc. so non-latin characters are valid word chars, e.g. for japanese or other complex charsets.

3. the client fetches statistics for each W1...Wn (translated to DHT keys KW1...KWn) in the torrent name and checks (via a bloomfiltered get) if the torrent's infohash is already stored under those keys, and if it is, how often.
4. if the K1 isn't stored M times under each KW1...KWn then the client publishes K1 to each KW1...KWn that hasn' reached sufficient redundancy.

search for a torrent:

1. dissect the search query into words W1...Wn (as above) and derive KW1...KWn
2. fetch statistics for each KW1...KWn
3. fetch bloomfilter indices for each KW1...KWn and intersect them as required by the search terms.
4. perform bloomfiltered Gets on some of the KW1...KWn with the intersected bloomfilter(s) to retrieve DHT key pointers to K1 to retrieve the torrent metadata in a second step.

parallel lookup speedup

sort all lookups/puts/gets by their hash and reuse traversed subbranches. If 2 destination keys are in similar buckets than a part of the lookup path is redundant

Hold Lookup handlers

If something interfaces with the DHT and puts/gets/lookups (etc.) something from a specific key it should be possible to create a handle for that specific key that can be kept alive. This way the entire lookup path can/should be cached within that handle, seperate from the Contacts in the DHT implementation itself. This handle can be used to perform multiple operations on a single key more efficiently, esp. if they're time-delayed and the path would fall out of the cache otherwise.

DHT key pointers/forwards

if a value A stored on the DHT under key K1 is likely to be associated with another lookup to K2 to retrieve the final value B then the originator of value A should be able to store a IP/Port hint to the nodes associated with K2 to speed up the secondary lookup.

Bittorrent Core

Enhanced Messaging & new messages

general requirements:

• forward compatibility: a peer should offer a list of all supported protocols so that the other side can choose a supported protocol
• stacked haves -> reduce message overhead
• stacked requests (not important)
• hash requests/replies for the #Info dictionary 2.0
• short zero/full bitfield (slightly less overhead when connecting)
• flexible message negotiation (versioned packages that include multiple implicit messages) + freeform metadata header

  This must support mostly collision-free, uncoordinated extension-design. Possibly via vendor-specific namespaces (e.g. one for joint developments, one for mainline, one for azureus etc.)

• compact per-message headers, the meaning of a message id should be derived from the negotiation
• possibly message interleaving to allow larger messages to be sliced into smaller ones transparently

see random scribblings @ Talk:Enhanced_messaging_protocol#modular_layered_protocol

possible packages:

• bittorrent baseline: v1 (classic bittorrent messages) v2 (classic + fast extensions + pex (including capability flags!) + hash requests for the new info dictionary + stacked haves)
• tex (iff anybody cares)
• tracker authentication

freeform header entries:

• full client name
• listening port (improves pex)
• dht port
• crypto support

Tracker Auth

1. tracker has an asymmetric keypair. On each (start?) announce it provides its public key and a certificate for the peer, containing the infohash, IP and an expiration date.
2. peers provide the certificates to each other when they connect, that certificate can be checked against the public key of the tracker

Anti-leeching

keeping IP stats

the optimistic unchoker and superseeding already rely on long-term stats, so should the optimistic disconnect. To prevent other peers (like BC) from cheating by reconnecting stats should be kept with a most-frequently used statistic. If a peer has 0 up / 0 down stats those don't have to be kept.

a peer can be re-recognized by: a) IP b) Port (if outgoing) c) Client type (unreliable) d) random part of the peer id (even less reliable)

i think a) and b) (if possible) should be sufficient to recombine recorded stats with a reconnected peer.

data to store (in addition to the tracking data):

• connection time
• uploaded data
• downloaded data

If a peer is recognized those stats should be integrated seamlessly as if he never disconnected.

non-cheatability of kept stats

Since Azureus can't/shouldn't keep all stats in memory it is important to harden the stats removal against possible reconnection-behavior patterns that would make azureus forget the stats of cheating peers.

A simple method to achieve that is dropping peer stats which have the smallest score calculated by: timeSinceDisconnect/abs(uplodaded-downloaded). This way a peer will be remembered longer the more harm or good he did.

Note: This is not optimal since the relation between abs(uplodaded-downloaded) and the optimistic unchokes aren't correlated in a linear fashion. Thus a peer still might get a net gain from disconnecting, waiting for azureus to forget his stats and then reconnecting. But a linear approximation should be sufficient to make this possible gain small.

The advantage is that good peers are remembered too and thus a disconnect won't harm an established relation between 2 cooperating peers.

trust metrics

nice concept, no specific ideas yet

request queue/measuring connection latency

current request message scheduling algorithms simply ramp up the number of outstanding requests based on the transfer speed of the peer. That works pretty well under most conditions but can lead to some trouble in edge cases. A way around that would be to factor the RTT into the equation.

Since not all bittorrent interactions happen are responded to in realtime it's not always straight-forward to measure the RTT. But the following exchanges should yield a pretty good estimate:

• the delay between us unchoking the peer and the 1st incoming request
• the delay between us sending the 1st request after an incoming unchoke and the piece message
• the delay between us sending the bitfield and the peer signaling an interested-flag (initial stat)

To rule out peers that are simply choking their uplink and suffer from congestion latency instead of a high baseline latency one can also measure the peak transfer rate, which should be normal in a high latency high bandwidth case.

Info dictionary 2.0

The purpose of the new torrent file format is to produce only one info hash for identical content, regardless of variable factors like file names, file order or piece size.

the new info dictionary must be stored in the key info2 under the root dictionary.

root dictionary:

• key (string): "info2" => dictionary:

• key (string): "sha1" => dictionary:

• key (string): "files" => dictionary:

• <N> keys (byte arrays): <sha1 file hashes> => dictionaries:

• key (string): "length" => integer value: file length in bytes
• key (string, optional): "tree" => byte array: <file tree root key>

• key (string, optional): "private" => boolean: <info hash modificator>
• key (string): "tree" => byte array: <torrent tree root key>
• key (string, optional): "pieces" => byte array: piece list <optional tree level>
• key (string, optional): "pieces_depth" => integer: <optional tree level depth>

• key (string): "fullname" => string: <full torrent name>
• key (string): "fileMap" => list of <file mapping type>

• entries => dictionary (is <file mapping type>)

• keys (string) <file/dirname> => integer <file indices> || dictionary <file mapping type>

The new info hash is calculated by calculating: SHA1(<torrent tree root key> + <ordered SHA1 key set> + is_private_flag_set ? "private" : "" )

<N>

number of files in the torrent

<sha1 file hashes>

the SHA1 of each (entire) file. No pieces, no trees... just the plain hash.

<ordered SHA1 key set>

The ordered set of the SHA1 hashes (i.e. the "files" dictionary keys in the same order as they are in the dictionary). The 1st element is indexed as 0.

<file tree root key>

root key of a SHA1 binary hash tree built from 16KiB-chunks of the file. Missing branches/leaves must be omitted when building the tree.

<torrent tree root key>

root key of a SHA1 binary hash tree built from 16KiB-chunks of all files in the torrent. The files are ordered by their raw (not base 32 encoded) SHA1 key ordering in the "files" dictionary (ordering is important, see bencoding specification). Missing branches/leaves must be omitted when building the tree.

<optional tree level>

This is a not classical piece list but a level of the tree. It's piece granularity is indicated by the next value.

<optional tree level depth>

This indicates how far away we are from the leaf level. 0 indicates raw 16KiB piece hashes. 1 indicates the hash of 2 piece hashes. 2 indicates the hash of 2 hashes of 2 hashes etc.

<info hash modificator>

If set to 1 it will enable the Secure torrents behavior and alter the info hash, if set to 0 it will be ignored.

<full torrent name>

Contains the full torrent name, which can be more verbose than the the root directory name or (if it is a single-file torrent) the file name itself.

<file mapping type>

This is a special dictionary, it can contain <file/dirname> keys mapping to numerical <file indices> values - referencing to indices of SHA1 hashes in the <ordered SHA1 key set> - or further <file mapping type> structures, indicating subdirectories. A published torrent should only contain a single root <file mapping type> entry in the "fileMap" list.

Note: For local storage multiple root entries can be used to retarget files to different directories

Note2: Multiple file names can map to the same SHA1 key, this means that files which have the same content have to be transfered once and can be replicated later.

<file/dirname>

1. In a single-file torrent it's just the filename
2. In a multi-file torrent the <file/dirname> value in the root <file mapping type> entry should be a user-friendly directory name.
3. In a multi-file torrent the <file/dirname> value in deeper nested entries must be relative paths to the parent directory
4. For local storage the root entry path(s) can be converted to absolute paths, otherwise (when loading an external torrent) they must be relative

• Since key collisions are unlikely the tracker protocol itself can be reused.
• This extended .torrent file uses a new hashing system, thus extensions to the peer-peer protocol will be necessary, namely hash-request and -reply messages to fetch missing hashes.

  Peer-peer protocol backward compatibility can be achieved by including the optional <optional tree level> and ;<optional tree level depth> values.

• To ensure compatibility with non-torrentv2-aware peers the old info dictionary can be included and the client can announce to 2 infohashes (new and old) and handshake peers separately (i.e. handshake a different hash), depending on the peer source.

====Bencoding 2.0==== (scrapped, due to criticism)

The purpose of these extensions is to make bencoding easier to parse for strictly typed programming languages by differentiating between different data types and thus eliminating the need for for error-prone type checks and conversions.

Original spec:

• Strings are length-prefixed base ten followed by a colon and the string. For example 4:spam corresponds to 'spam'.
• Integers are represented by an 'i' followed by the number in base 10 followed by an 'e'. For example i3e corresponds to 3 and i-3e corresponds to -3. Integers have no size limitation. i-0e is invalid. All encodings with a leading zero, such as i03e, are invalid, other than i0e, which of course corresponds to 0.
• Lists are encoded as an 'l' followed by their elements (also bencoded) followed by an 'e'. For example l4:spam4:eggse corresponds to ['spam', 'eggs'].
• Dictionaries are encoded as a 'd' followed by a list of alternating keys and their corresponding values followed by an 'e'. For example, d3:cow3:moo4:spam4:eggse corresponds to {'cow': 'moo', 'spam': 'eggs'} and d4:spaml1:a1:bee corresponds to {'spam': ['a', 'b']}. Keys must be strings and appear in sorted order (sorted as raw strings, not alphanumerics).

Extensions (partially backwards compatible):

• Parsing should be done in a fail-fast manner, anything violating the given specification must result in errors, this ensures that applications not adhering to the standard won't work with others.
• Dictionary ordering is mandatory (fail-fast behavior)
• Dictionaries can take byte arrays, strings and integers as keys. Ordering first sorts all integers, unicode strings and byte arrays separately then inserts them into the dictionary in the integer, string, array order.
• Forward compatibility is achieved by ignoring all unknown keys/values/entries matching the follwing patterns: /[a-zA-Z]([0-9]+):.{\1}/ and /[a-zA-Z][^e]*e/. Warnings should be given when such patterns occur. Any other unknown patterns must lead to parsing errors (fail-fast behavior)
• All length-prefixed strings are expected to be UTF-8 encoded by default. Other formats can be specified by prefixing the string with a BOM. These 3-4 bytes, if discovered, are NOT part of the string since the BOM is not a valid unicode character as of Unicode 3.2 and thus must be stripped before decoding the string in the appropriate format. If the BOM is used both little- and big-endian encodings of UTF-16 and UTF-32 are possible.
• Floating point values can be stored in the format /f(((-|+)?[0-9]\.[0-9]*(-|+)?E[0-9]+)|NaN|+INFIN|-INFIN)e/ (case-sensitive regular expression). NaN, +INFIN and -INFIN denote the real number extensions Not a Number, positive Infinity, negative Infinity as specified by the standard IEEE 754. The numbers used shouldn't exceed the double precision ranges as specified by IEEE 754, if they do it is at the interpreting clients discretion to round them to the nearest matching value and thus should be avoided. Double precision values must not be truncated to single precision.

  Important: Since a small 'e' terminates the number it is important to use a capital 'E' for the exponent.

  Examples:

  valid: f1.5034E-20e, f+1.5034E-20e, f1.E+20e, fNaNe, f+INFINe

  invalid: f15.034E-20e, f1,5034E-20e, fINFINe, f+NaNe, f1.5034e-20e

• Booleans can be stored in the format /b(1|0)e/ (case-sensitive regular expression)

  Example: b1e or b0e

• Byte arrays can be stored in the format /a([0-9]+):.{\1}/ (case-sensitive regular expression). I.e. it is identical to the string format, just that the base ten size is prefixed with an 'a' (for array).

  Example: a20:�Iò1¶tÈã§C�>‘¤¨y?·

Other stuff to optimize

Crash safety

• when the downloads.config and downloads.config.bak files are lost/not readable then azureus might/should offer to rescan the <azureus-config>/active/ directory and recover lost torrents, or rather, it should be offered somewhere in the options and the user should be informed about that option when the configuration is lost.
• The config file backup scheme could be changed to make a backup once a start was successful w/o any errors (esp. w/o indications of corrupted config files) and then sync/flush/close/release the filehandle to avoid any corruption that might occur during azureus' normal operation.

Improve use of ByteBuffers

currently byte buffers are often repackaged (and thus copied into a newer, larger one) to accommodate the header of a lower protocol layer. There are 2 ways to fix that:

• Use some sort of Byte-Buffer-Builder which can chain multiple bytebuffers together (and preferrably provide the same interface as a bytebuffers but allows dynamic growth)
• ask lower protocol layers how much additional overhead they need (bubble the size request down)

Concurrency/Atomic

• make piece availability counting, have messages etc. access an atomic integer array and event-driven (this would reduce tons looping checks)
• same for the pieces-done counts, pieces-written flags etc. (they're currently all synchronized)

...

Generalized Bloom Filters

Azureus is currently using bloom filters to implement matching for some stuff, e.g. the DHT. The problem is that these filters have to be flushed and rotated from time to time since their false positive ratio approaches infinity the longer they're filled with values. A generalized bloom filter can fix this if false negatives are acceptable since they have a bounded false positive and false negative rate.

Note: These can't be used for the bloom filter RPCs since they're not easily intersectable