#573 assigned enhancement

Allow client to control which storage servers receive shares

Reported by: swillden Owned by: daira
Priority: normal Milestone: 1.13.0
Component: code-peerselection Version: 1.2.0
Keywords: extensibility usability review-needed Cc:
Launchpad Bug:

Description (last modified by nejucomo)

Although in general the peer list permutation method is great, there are some situations in which clients may want to choose which specific peers get their shares.

One example is clients performing backup operations. If the client machine is also running a storage server, the client will often place a share there, but in the most important backup recovery scenarios the local storage server's data will be gone, too. By choosing to place a share locally, the client is more or less "pre-failing" that share. Similarly, if a single site has multiple systems participating in a network, it's probably not advisable to store shares on any of the co-located machines, if part of the backup goal is the ability to survive catastrophe (excepting data centers that provide other disaster recovery solutions, of course).

So, backup clients should be able to specify that machine-local and site-local storage is not allowed.

Another example is a client that wants to provide fast local access to specific caps (mutable or immutable) to certain peer clients. By choosing to place k shares with a specified storage server, the client can ensure that a client on that machine can access those caps without reaching out over the network.

Of course, deliberately placing k shares with a single storage server somewhat reduces reliability, assuming the remaining n-k shares are distributed normally. This is mitigated to a large degree if the k-share server is known to be highly available (e.g. if I want to back up my digital photos to the network, but put k shares of each on my Mom's computer so that she has fast access to the photos, I can take steps to make sure that the data on her storage server is available). However, to further mitigate this risk, a client that is storing k shares with a single storage server should probably distribute more than n-k shares to other storage servers.

There are probably other scenarios where clients should be able to exercise greater control over share targeting as well.

I think share targeting should not be a tahoe-level configuration option. Instead, I think tahoe should provide an API to allow applications using tahoe to specify target selection parameters.

One issue created by targeted peer selection is the breaking of the share recovery search process. It's not an issue for a backup client's refusal to store a share locally, essentially we're just simulating a full storage peer and otherwise we can walk the permuted peer list. Where it becomes a problem is when clients wish to choose the peers that receive shares, potentially completely ignoring the permuted list and completely breaking the recovery search. This could result in requiring the recovery process to search the entire network.

One solution is to simply ignore the issue and accept that recovery of targeted shares is harder. In small networks that would be fine, since you're probably retrieving from almost every peer anyway. In larger networks, searching the entire peer set might be unacceptable. If applications can request specific targeting for storage, perhaps they should also be able to suggest specific peers for recovery. Then they could store the targeted peer list as another file, and place that file normally. The only problem I see with making this a purely application-level issue is that a generic Repairer will have a hard time finding the shares, unless it is also told where they are, or knows about the pointer file.

As for the nature of the targeting APIs, I can think of a lot of sophisticated ways to specify selection criteria, but we should probably start simple and then see if something more is required. The simplest solution I can thing of is to allow the application to specify a list of (peer ID, share count) tuples. The client would traverse this list and deliver the specified number of shares to each peer. Any remaining shares (assuming sum(share_counts) < n) would be delivered normally, except that peers with a specified count of 0 would not receive any shares, even if they're at the top of the peer list.

Change History (24)

comment:1 Changed at 2009-01-08T18:42:06Z by zooko

+1

I really like this idea.

Another motivating example is a commercial storage company like allmydata.com. Suppose allmydata.com rented space in three different co-lo's, each separated from the other in geography, network topology, business ownership, legal jurisdiction, etc. Suppose a single SATA hard drive in one of those locations fails, or even a cluster of hard drives such as when a power supply goes haywire and fries all the drives that it is powering (something like this happened to us!).

Now we would need to repair all the files which had shares on the lost drives. We can already do this, by acquiring shares and reconstructing the missing shares in this co-lo. But inter-co-lo bandwidth is expensive compared to intra-co-lo bandwidth (which is more or less free). Wouldn't it be nice if we could recreate the missing shares using only bandwidth from within the damaged co-lo? Well, if there are 3 (i.e. K) shares of each file available inside the co-lo then you can! If you used K=3, M=12, and if your share-placement algorithm had chosen to put 4 shares in each co-lo, then you're all set.

(In general if Q is the number of co-los, then you need M = (K+1)*Q in order to do this trick and spend no inter-co-lo bandwidth when repairing from the loss of a single share.)

My intuition strongly agrees with swillden's that this sort of thing ought to be an API and not a configuration option. It is potentially hard to understand where the shares will go in what circumstances, and the answer is probably application-specific. I would really like for the tahoe core to get dumber, or at least not smarter, about share placement and make it someone else's problem to decide the best share-placement strategy for their particular goals.

comment:2 Changed at 2009-06-22T06:50:49Z by warner

I had a thought.. one scaling problem we've anticipated is the practical requirement of maintaining a connection to all known servers. Because each file will put shares on a pseudorandomly-selected set of servers, reading A files will obligate you to talk to something like max(A*k,NUMSERVERS) hosts. You can make peer-selection more clever and have it prefer to use hosts that it already has connections to, but if you're grabbing a significant number of files, you're going to wind up with a full mesh of connections.

But, what if we assume that most of the time, people are downloading their own files? Or files that were mostly uploaded by the same person? We could set it up such that Alice's files all tend to wind up on the same N servers (except for overspill due to full/faulty ones). Then, if we make the network layer only bring up connections on demand, and prefer connected servers to not-yet-connected servers, this use case would see fewer connections being made.

We've talked about splitting out a new "peer selection index" from the existing storage-index. To achieve useful load-balancing across the grid in this scheme I'm thinking about, we could have each node choose a random peer-selection-index at create-client time, and use it for each upload (of course, it could be overridden per-upload). Now, and this is the important part, the peer-selection-index gets written into the filecap. Everything Alice uploads will have the same PSI, and anyone who sees the filecap will have enough information to create the right serverlist and ask the right servers. But Alice's files will all tend to be concentrated on the first N machines in her own personal list.

You could imagine changing the way this PSI is implemented to reference some other ordering, perhaps an explicitly-defined one (which is perhaps stored in some distributed fashion, and retrievable with the PSI? imagine if the PSI is a random string that can somehow be turned into a mutable readcap, and you publish a list of storage server ids/furls in that slot, and you give it a DNS-style TTL so readers are allowed to cache it for a long time). I think that might accomplish the goals of this ticket while still making the filecap sufficient to retrieve any file.

On the other hand, maybe Alice doesn't want all of her files to be concentrated on the same N servers. If she loses N-k-1 of those, she's lost everything. She might prefer a distribute-over-all-servers mode which gives a slightly higher chance of losing a small number of files, over the slightly-lower chance of losing everything. For her, she'll just duplicate or hash the storage-index to generate the PSI for each upload, giving the exact same behavior that we have now.

comment:3 Changed at 2009-07-03T03:29:40Z by zooko

Brian has implemented much of this, but it isn't commented-in, documented, etc. in the current trunk. The next step (after the Tahoe v1.5.0 release) is to experiment with use cases and UI. Anybody out there want to actually use this for something? Shawn Willden has mentioned that he wants to make sure his mom's PC gets K shares. Jake Appelbaum has mentioned that he wants to make sure non-Tor-hidden-server nodes get N-K shares. Some corporations have mentioned that they would like to send approximately the same number of shares to each of Q different geographically distributed data centers.

I think we need some brave user like Shawn or Jake to try this feature out and complain about how it doesn't do what he wants.

comment:4 follow-up: Changed at 2009-07-03T04:57:21Z by swillden

Even before the ability to ensure that specific servers get k shares, I want to be able to specify that the local node get no shares. For backup purposes, you're probably going to use a local (often on the machine being backed up!) Tahoe node as the interface to the grid, and it makes little sense to store a share there, at least if the primary purpose of your backups is disaster recovery.

comment:5 in reply to: ↑ 4 Changed at 2009-07-03T22:18:26Z by midnightmagic

My use-case is to specify which servers receive the lion's share of the blocks, for two reasons:

  1. To ensure that known-reliable machines receive the most blocks.
  1. To ensure that the space is used in a way I want to control manually.

For example, even though one of my machines in my home storage grid has multiple TB of relatively reliable storage space on it, I would prefer to use that as sparingly as possible and instead dump most of them on machines that are allocated specifically to the task of being a Tahoe storage node.

Also, out of those Tahoe nodes that are participating, I happen to know that machines X, Y, and Z are extremely reliable, whereas others have had flakey drive bus issues in the past. I want X, Y, and Z to definitely get blocks.. and the rest of them, maybe.

So I'll be using this feature for sure. :-)

comment:6 Changed at 2009-08-10T15:29:36Z by zooko

The following clump of tickets might be of interest to people who are interested in this ticket: #711 (repair to different levels of M), #699 (optionally rebalance during repair or upload), #543 ('rebalancing manager'), #232 (Peer selection doesn't rebalance shares on overwrite of mutable file.), #678 (converge same file, same K, different M), #610 (upload should take better advantage of existing shares), #573 (Allow client to control which storage servers receive shares).

comment:7 Changed at 2009-08-10T15:45:56Z by zooko

Also related: #778 ("shares of happiness" is the wrong measure; "servers of happiness" is better).

comment:8 follow-up: Changed at 2009-08-10T18:33:53Z by warner

Please take a look at #467, which is about a tahoe.cfg language for defining storage servers (instead of or in addition to using the Introducer), and attributes like how many shares should be sent to such servers.

As Shawn pointed out, an important feature of this language is to say "do not send shares to myself, even if I'm running a storage server".

I currently feel that #467 (specify the servers in tahoe.cfg) will be more useful to more people than (this) #573 (specify the servers in the webapi call), and easier to implement, if only because to take advantage of #573, people have to write an application which:

  1. uses an as-yet-unwritten API to learn about a list of servers, or has such a list hard-coded into it
  2. speaks the tahoe webapi to pass the additional arguments, rather than using the existing CLI tools like 'tahoe backup'

Whereas folks that are on a static friendnet (with perhaps some servers that are larger than others) can all use the same tahoe.cfg server-specification text and then use all their existing tahoe-enabled tools without change.

comment:9 Changed at 2009-08-10T19:42:49Z by zooko

When I've been repeatedly saying "fixing #573 would be really valuable", I wasn't distinguishing between #573 and #467. Now that I've looked at #467, the thing that I want from #573 would also be provided by #467. I just hadn't really been aware of that ticket as being relevant to this one.

comment:10 Changed at 2009-12-08T19:00:01Z by zooko

There is a wiki page about this and related tickets: ServerSelection.

comment:11 Changed at 2010-02-16T03:44:43Z by joe

I had an idea that is related to this problem, which may or may not be useful, but I'll throw it out there in case it may be.

My application for this is a situation like the Volunteer Grid, where I would run a storage node X, but if I put files on the grid, I would prefer to put them somewhere other than X, since my files already share fate (network connectivity, physical location, power, spindles, etc.) with shares located on X.

In this scenario, X would have some publically-advertised attribute Y composed of an arbitrary string. (I don't have a good name for this yet.) A client Z could specify a similar string; the semantics of doing so would be that Z would avoid placing shares on storage nodes advertising the same string. One could also imagine more complicated things like using some calculation of distance between strings as a weight for influencing placement.

The advantage of this scheme is that it is fairly simple, at least to explain, and that, as far as I can see, the worst that someone interested in interfering with it could do would be to advertise the same string you are using, which would cause you not to use that someone's storage node. It doesn't generally solve the problem of controlling where shares are located, however.

This is sort of a slightly more generalized version of having a storage node blacklist; one can set multiple nodes to advertise the same string, and clients will do the right thing without reconfiguration.

comment:12 Changed at 2010-02-20T04:01:56Z by zooko

  • Resolution set to duplicate
  • Status changed from new to closed

As far as I can tell almost all or perhaps all of the use cases so far would be satisfied by #467 (configure which servers will receive which shares statically, in a configuration file, which is read by the gateway process at startup and used for all uploads during the life of that process) without this ticket, #573 (configure which servers will receive which shares dynamically, so that different uploads can implement different policies during the life of the gateway process).

I'm going to go ahead and close this ticket as "duplicate" for now in order to concentrate all of these use cases into #467, but if you have a use case which specifically needs dynamic share-placement strategies then please re-open this ticket and explain your use case in detail. Thanks!

comment:13 Changed at 2013-06-28T04:28:00Z by nejucomo

  • Description modified (diff)

This is one possible stepping stone feature to the "universal caps" use case I just created a ticket for here: #2009

Ticket #2009 would not be satisfied by a static config file of servers for placement.

Last edited at 2013-06-28T04:29:06Z by nejucomo (previous) (diff)

comment:14 in reply to: ↑ 8 Changed at 2013-06-28T05:32:45Z by nejucomo

Replying to warner:

[...] to take advantage of #573, people have to write an application which:

  1. uses an as-yet-unwritten API to learn about a list of servers, or has such a list hard-coded into it

If we were to revive this ticket, we should also have a ticket for just such an API!

Here are some proposals:

  • get_known_nodes(type="storage") -> [conn_info]
  • suggest_nodes(cap) -> [conn_info]

I'm actually not sure if this is useful since for the client to have a cap, a file was already uploaded. Maybe it should be called if_you_had_chosen_where_would_you_have_put_this(cap). ;-)

Then if we were exposing the introducer-interaction layer like this, we of course might want:

  • introduce_peer(introduction)

A related intriguing potential of #467 is that those configurations can be distributed through tahoe itself, so a friend-net application might have a mapping of some_context_such_as_friend_name → CAP_OF_SERVER_PREFERENCES. It could then use that list for the proposed share-placement API, assuming CAP_OF_SERVER_PREFERENCES has shares placed by the "default" method.

Of course, now that app and/or its users have the problem of maintaining that mapping, so this is an incomplete solution. And since it relies on default share placement anyway, the reliability gains of manual share placement are thwarted. Hrm.

It suggests a sort of layer-confused API:

  • upload(data, server_selection_read_cap) -> cap_of_data
  • get(cap_of_data, server_selection_read_cap) -> data

All of these suggestions still have the "discoverability" problem swillden described: how does a reader learn the server selection preferences in the first place?

  1. speaks the tahoe webapi to pass the additional arguments, rather than using the existing CLI tools like 'tahoe backup'

The commandline tools could also be extended. It does seem clunky, but I'm a proponent of cmdline / webapi parity, where the "ugly details" can be behind verbose options which may be hidden from "normal" --help output and only shown with --help-plumbing-yes-I-really-want-enough-rope or somesuch.

Last edited at 2013-06-28T06:03:51Z by nejucomo (previous) (diff)

comment:15 Changed at 2014-12-30T20:04:24Z by daira

  • Resolution duplicate deleted
  • Status changed from closed to reopened

Shu Lin wrote on tahoe-dev:

From current implementation, it seems Tahoe picks up servers based on k, n and happiness parameters. I am wondering if Tahoe can provide an interface or framework to hook up a 3rd party server distribution algorithm, which might allow 3rd party to hook up some other determinate server distribute algorithms, such as server location or network bandwidth as preference?

prabahy replied:

Currently there is not, but this has been discussed and it appears that there is a general agreement that enhancing storage node selection is a good idea.

Related tickets: #467, #573, #1838, #2059

Shu Lin answered:

Thanks a lot for the information! The feature we are looking for is exact ticket #573.

Actually, if I have a team can build such an application mentioned in ticket #573, which is maintaining a server capability mapping and able to submit per upload server preference. Can Tahoe team do define the interface mentioned in #573?

If Tahoe team has no bandwidth on this, we are willing to help out on this issue. Just looking for a good way to coordinate the effort. :-)

We have little bandwidth available, but I'm happy to review any proposals for such an interface. Please post on this ticket.

comment:16 Changed at 2014-12-30T20:05:25Z by daira

  • Keywords extensibility usability added
  • Priority changed from minor to normal

comment:17 follow-up: Changed at 2014-12-31T03:42:27Z by linshu

Daira,

Thanks for reopening the ticket.

Basically, my idea is continuing using the PSI framework implemented by Warner. But, instead of using a fix algorithm inside Tahoe, we can use a callback to hook up an outside server selection function.

The input of the callback will be online servers got from storage_client.get_connected_servers() call, the return will be a sorted set of active servers.

In the server data structure or announcement, we can extend an external extension dictionary for 3rd party announcing their own parameters matrix, then the 3rd party sorting callback can use these extension to do the real sorting.

In this way, Tahoe framework will be total topology and server preference un-aware. Giving the both neutral Tahoe framework and extensible friendly interface to 3rd party and future server selection capability.

Last edited at 2014-12-31T03:44:27Z by linshu (previous) (diff)

comment:18 in reply to: ↑ 17 ; follow-up: Changed at 2015-01-07T16:03:51Z by zooko

Dear linshu:

That sounds like a good strategy to me. Let's do it! Also, I am very interested to see what server-selection strategies you need for your purposes…

comment:19 in reply to: ↑ 18 Changed at 2015-02-05T05:23:43Z by linshu

Zooko,

Yes. I just sent out the github pull request with my proposal change. Please review it. Any comment and suggestion is appreciated.

Here is the link: https://github.com/tahoe-lafs/tahoe-lafs/pull/140

comment:20 Changed at 2015-02-09T01:30:31Z by daira

  • Keywords review-needed added
  • Owner set to daira
  • Status changed from reopened to new

linshu wrote:

I fixed the build. Please review it. :-)

comment:21 Changed at 2015-02-09T01:30:38Z by daira

  • Status changed from new to assigned

comment:22 Changed at 2015-02-20T18:28:46Z by daira

  • Milestone changed from undecided to 1.11.0

comment:23 Changed at 2016-03-22T05:02:52Z by warner

  • Milestone changed from 1.11.0 to 1.12.0

Milestone renamed

comment:24 Changed at 2016-06-28T18:20:37Z by warner

  • Milestone changed from 1.12.0 to 1.13.0

moving most tickets from 1.12 to 1.13 so we can release 1.12 with magic-folders

Note: See TracTickets for help on using tickets.