Filename: 226-bridgedb-database-improvements.txt Title: "Scalability and Stability Improvements to BridgeDB: Switching to a Distributed Database System and RDBMS" Author: Isis Agora Lovecruft Created: 12 Oct 2013 Related Proposals: XXX-social-bridge-distribution.txt Status: Reserve * I. Overview BridgeDB is Tor's Bridge Distribution system, which currently has two major Bridge Distribution mechanisms: the HTTPS Distributor and an Email Distributor. [0] BridgeDB is written largely in Twisted Python, and uses Python2's builtin sqlite3 as its database backend. Unfortunately, this backend system is already showing strain through increased times for queries, and sqlite's memory usage is not up-to-par with modern, more efficient, NoSQL databases. In order to better facilitate the implementation of newer, more complex Bridge Distribution mechanisms, several improvements should be made to the underlying database system of BridgeDB. Additionally, I propose that a clear distinction in terms, as well as a modularisation of the codebase, be drawn between the mechanisms for Bridge Distribution versus the backend Bridge Database (BridgeDB) storage system. This proposal covers the design and implementation of a scalable NoSQL ― Document-Based and Key-Value Relational ― database backend for storing data on Tor Bridge relays, in an efficient manner that is ammenable to interfacing with the Twisted Python asynchronous networking code of current and future Bridge Distribution mechanisms. * II. Terminology BridgeDistributor := A program which decides when and how to hand out information on a Tor Bridge relay, and to whom. BridgeDB := The backend system of databases and object-relational mapping servers, which interfaces with the BridgeDistributor in order to hand out bridges to clients, and to obtain and process new, incoming ``@type bridge-server-descriptors``, ``@type bridge-networkstatus`` documents, and ``@type bridge-extrainfo`` descriptors. [3] BridgeFinder := A client-side program for an Onion Proxy (OP) which handles interfacing with a BridgeDistributor in order to obtain new Bridge relays for a client. A BridgeFinder also interfaces with a local Tor Controller (such as TorButton or ARM) to handle automatic, transparent Bridge configuration (no more copy+pasting into a torrc) without being given any additional privileges over the Tor process, [1] and relies on the Tor Controller to interface with the user for control input and displaying up-to-date information regarding available Bridges, Pluggable Transport methods, and potentially Invite Tickets and Credits (a cryptographic currency without fiat value which is generated automatically by clients whose Bridges remain largely uncensored, and is used to purchase new Bridges), should a Social Bridge Distributor be implemented. [2] * III. Databases ** III.A. Scalability Requirements Databases SHOULD be implemented in a manner which is ammenable to using a distributed storage system; this is necessary because many potential datatypes required by future BridgeDistributors MUST be stored permanently. For example, in the designs for the Social Bridge Distributor, the list of hash digests of spent Credits, and the list of hash digests of redeemed Invite Tickets MUST be stored forever to prevent either from being replayed ― or double-spent ― by a malicious user who wishes to block bridges faster. Designing the BridgeDB backend system such that additional nodes may be added in the future will allow the system to freely scale in relation to the storage requirements of future BridgeDistributors. Additionally, requiring that the implementation allow for distributed database backends promotes modularisation the components of BridgeDB, such that BridgeDistributors can be separated from the backend storage system, BridgeDB, as all queries will be issued through a simplified, common API, regardless of the number of nodes system, or the design of future BridgeDistributors. *** 1. Distributed Database System A distributed database system SHOULD be used for BridgeDB, in order to scale resources as the number of Tor bridge users grows. This database system, hereafter referred to as DDBS. The DDBS MUST be capable of working within Twisted's asynchronous framework. If possible, a Object-Relational Mapper (ORM) SHOULD be used to abstract the database backend's structure and query syntax from the Twisted Python classes which interact with it, so that the type of database may be swapped out for another with less code refactoring. The DDBM SHALL be used for persistent storage of complex data structures such as the bridges, which MAY include additional information from both the `@type bridge-server-descriptor`s and the `@type bridge-extra-info` descriptors. [3] **** 1.a. Choice of DDBS CouchDB is chosen for its simple HTTP API, ease of use, speed, and official support for Twisted Python applications. [4] Additionally, its document-based data model is very similar to the current archetecture of tor's Directory Server/Mirror system, in that an HTTP API is used to retrieve data stored within virtual directories. Internally, it uses JSON to store data and JavaScript as its query language, both of which are likely friendlier to various other components of the Tor Metrics infrastructure which sanitise and analyse portions of the Bridge descriptors. At the very least, friendlier than hardcoding raw SQL queries as Python strings. **** 1.b. Data Structures which should be stored in a DDBS: - RedactedDB - The Database of Blocked Bridges The RedactedDB will hold entries of bridges which have been discovered to be unreachable from BridgeDB network vantage point, or have been reported unreachable by clients. - BridgeDB - The Database of Bridges BridgeDB holds information on available Bridges, obtained via bridge descriptors and networkstatus documents from the BridgeAuthority. Because a Bridge may have multiple `ORPort`s and multiple `ServerTransportListenAddress`es, attaching additional data to each of these addresses which MAY include the following information on a blocking event: - Geolocational country code of the reported blocking event - Timestamp for when the blocking event was first reported - The method used for discovery of the block - an the believed mechanism which is causing the block would quickly become unwieldy, the RedactedDB and BridgeDB SHOULD be kept separate. - User Credentials For the Social BridgeDistributor, these are rather complex, increasingly-growing, concatenations (or tuples) of several datatypes, including Non-Interactive Proofs-of-Knowledge (NIPK) of Commitments to k-TAA Blind Signatures, and NIPK of Commitments to a User's current number of Credits and timestamps of requests for Invite Tickets. *** 2. Key-Value Relational Database Mapping Server For simpler data structures which must be persistently stored, such as the list of hashes of previously seen Invite Tickets, or the list of previously spent Tokens, a Relational Database Mapping Server (RDBMS) SHALL be used for optimisation of queries. Redis and Memcached are two examples of RDBMS which are well tested and are known to work well with Twisted. The major difference between the two is that Memcaches are stored only within volatile memory, while Redis additionally supports commands for transferring objects into persistent, on-disk storage. There are several support modules for interfacing with both Memcached and Redis from Twisted Python, see Twisted's MemCacheProtocol class [5] [6] or txyam [7] for Memcached, and txredis [8] or txredisapi [9] for Redis. Additionally, numerous big name projects both use Redis as part of their backend systems, and also provide helpful documentation on their own experience of the process of switching over to the new systems. [17] For non-Twisted Python Redis APIs, there is redis-py, which provides a connection pool that could likely be interfaced with from Twisted Python without too much difficultly. [10] [11] **** 2.a. Data Structures which should be stored in a RDBMS Simple, mostly-flat datatypes, and data which must be frequently indexed should be stored in a RDBMS, such as large lists of hashes, or arbitrary strings with assigned point-values (i.e. the "Uniform Mapping" for the current HTTPS BridgeDistributor). For the Social BridgeDistributor, hash digests of the following datatypes SHOULD be stored in the RDBMS, in order to prevent double-spending and replay attacks: - Invite Tickets These are anonymous, unlinkable, unforgeable, and verifiable tokens which are occasionally handed out to well-behaved Users by the Social BridgeDistributor to permit new Users to be invited into the system. When they are redeemed, the Social BridgeDistributor MUST store a hash digest of their contents to prevent replayed Invite Tickets. - Spent Credits These are Credits which have already been redeemed for new Bridges. The Social BridgeDistributor MUST also store a hash digest of Spent Credits to prevent double-spending. *** 3. Bloom Filters and Other Database Optimisations In order to further decrease the need for lookups in the backend databases, Bloom Filters can used to eliminate extraneous queries. However, this optimization would only be beneficial for string lookups, i.e. querying for a User's Credential, and SHOULD NOT be used for queries within any of the hash lists, i.e. the list of hashes of previously seen Invite Tickets. [14] **** 3.a. Bloom Filters within Redis It might be possible to use Redis' GETBIT and SETBIT commands to store a Bloom Filter within a Redis cache system; [15] doing so would offload the severe memory requirements of loading the Bloom Filter into memory in Python when inserting new entries, reducing the time complexity from some polynomial time complexity that is proportional to the integral of the number of bridge users over the rate of change of bridge users over time, to a time complexity of order O(1). **** 3.b. Expiration of Stale Data Some types of data SHOULD be safe to expire, such as User Credentials which have not been updated within a certain timeframe. This idea should be further explored to assess the safety and potential drawbacks to removing old data. If there is data which SHOULD expire, the PEXPIREAT command provided by Redis for the key datatype would allow the RDBMS itself to handle cleanup of stale data automatically. [16] **** 4. Other potential uses of the improved Bridge database system Redis provides mechanisms for evaluations to be made on data by calling the sha1 for a serverside Lua script. [15] While not required in the slightest, it is a rather neat feature, as it would allow Tor's Metrics infrastructure to offload some of the computational overhead of gathering data on Bridge usage to BridgeDB (as well as diminish the security implications of storing Bridge descriptors). Also, if Twisted's IProducer and IConsumer interfaces do not provide needed interface functionality, or it is desired that other components of the Tor software ecosystem be capable of scheduling jobs for BridgeDB, there are well-tested mechanisms for using Redis as a message queue/scheduling system. [16] * References [0]: https://bridges.torproject.org mailto:bridges@bridges.torproject.org [1]: See proposals 199-bridgefinder-integration.txt at https://gitweb.torproject.org/torspec.git/blob/HEAD:/proposals/199-bridgefinder-integration.txt [2]: See XXX-social-bridge-distribution.txt at https://gitweb.torproject.org/user/isis/bridgedb.git/blob/refs/heads/feature/7520-social-dist-design:/doc/proposals/XXX-bridgedb-social-distribution.txt [3]: https://metrics.torproject.org/formats.html#descriptortypes [4]: https://github.com/couchbase/couchbase-python-client#twisted-api [5]: https://twistedmatrix.com/documents/current/api/twisted.protocols.memcache.MemCacheProtocol.html [6]: http://stackoverflow.com/a/5162203 [7]: http://findingscience.com/twisted/python/memcache/2012/06/09/txyam:-yet-another-memcached-twisted-client.html [8]: https://pypi.python.org/pypi/txredis [9]: https://github.com/fiorix/txredisapi [10]: https://github.com/andymccurdy/redis-py/ [11]: http://degizmo.com/2010/03/22/getting-started-redis-and-python/ [12]: http://www.dr-josiah.com/2012/03/why-we-didnt-use-bloom-filter.html [13]: http://redis.io/topics/data-types §"Strings" [14]: http://redis.io/commands/pexpireat [15]: http://redis.io/commands/evalsha [16]: http://www.restmq.com/ [17]: https://www.mediawiki.org/wiki/Redis