root/doc/devel_notes

1) Make a new bank account:

tycoon -o UserName=bank_admin bank create_account l.zhang@hp.com 1000 a __Bank

2) sync for debugging:
debugsync machine_name

*) Check all input from network.

*) Auctioneer handles XMLRPC, argument checking, transferring of money.

*) AuctioneerAllocator handles management of resources

*) VMM handles specifics of a virtualization technology

*) Use assertions to check things that should never happen

*) Throw exceptions for things that could happen, but shouldn't, e.g., 
   erroneous input from command line or network

*) Don't use multiple inheritance.

*) Avoid inheritance where convenient. 

*) Test all code using automated test harnesses.


2/21 Should minimum and contingency funds be kept separate?
     a) Separate pools: Can have very strong assurances to meet minimums
     b) Single pool: Can spend savings to get better expected performance

   Separate pools are better

2/21 Should have separate or shared contingency fund?
     Shared is better to spread risk, but disk is special case because of 
     importance of persistent data and ability to shutdown use of active 
     resources

     Shared, with pool bid over 1 time interval according to weights

2/24 What should the maximum memory of Xen VMs be?
  * Bid's maximum memory: too large. Other VMs may prevent this from
  being possible  
  * Actual available capacity based on bid, etc.
    * need to write config file before boot.

4/24 Magnitude of bids must be close to that of preferences and each
other.

5/2 Auctioneer API: return values are a dictionary. An "error" element
indicates an error with the value being a human readable
message indicating the type of the error. Additional machine readable
data can be in "error_value". 

5/2 Should probably avoid the use of exceptions in favor of explicit
return values. exceptions should be for unexpected situations, not
expected ones. 

6/6 Error handling is significantly complicated by using explicit
return values instead of Exceptions. Explicit return values have to be
processed all the way up the call stack even if only the top level
handles them. Exceptions only have to handled at the top level. The
new policy is to relax the old policy and use exceptions to signal
error conditions while still using return values to pass the expected
value of a function.

The actual exception used should be separate from the standard system
exceptions to distinguish anticipated error conditions from
unanticipated error conditions. Also, the name of exception should be
different for each module.

5/7 Resources have a name and type. A name specifies a specific
resource while a type specifies a class of resources.

5/24 Sample contingency bid: 

python tycoon host bid 67.164.68.18 0 "{'CPU': (1, 0.0, 1.0, 0.0)}"

"{('TCPv4Port', 30000): (1, 1.0, 1.0, 0.0)}"

6/9 There are several disk allocation quantities:
    bid_min and bid_max: specified by the account's bid
    usage: how much is actually being used by the account. Includes
           the file system size and all other files
    allocation: amount that the allocator gives to the account

6/9 The relative values of these quantities trigger different events:

    allocation < bid_min: delete the account. 
      This is the definition of bid_min
 
    allocation < usage: try to shrink file system, otherwise delete
      Ideally, the auctioneer would call an application specific
      handler to delete files.

6/13 Root must have a contingency ratio .9999999 instead of 1-epsilon 
so that resource prices are not zero. Zero prices causes
discontinuities in allocation like allocating more than 1.0
resources. This has been a problem for few users or when users all use
CR of 1.0 for a resource. 

6/20 What happens when the expiration time has arrived, but there are
still funds remaining? Here are the choices:
  1) Delete account and refund remaining funds. Harsh.
  2) Shutdown and reset with long interval. Much kinder. Account may
  still be garbage collected if outbid.
Decided to do 2), but not sure if this was the right decision.

6/27 Testing strategy: high level to low level. Group tests by
area. Each test should be completely independent. This takes more
time, but is easier to diagnose. Tests should verify results.

6/27 Problems with asynchronous error handling: 
  1) have to handle both exceptions and Failures because an exception
  may occur before the first "yield"
  2) have to handle failures at every level because twisted error loop 
  doesn't like failures propagated more than one level. May be able to 
  fix by fixing flow code.

6/27 Users are prevented from setting bids which cause their own
accounts to be deleted or shutdown. This includes changing of the
interval, refunding of currency, and asking for high minimums.

6/27 What happens if a setquota lowers the quota below the current
allocation? Users are marked in repquota and a grace period counts
down, but nothing happens when it expires.

9/20 command line return value = number of errors

10/24 Contingency Accounting: as per previous notes, the contingency
fund should be separate from the expected value fund, and a single
contingency fund should be shared by all resources. This provides
maximum predictability in resource allocation, but could allow a
malicious user to bid up one resource and drain the contingency fund,
causing unpredictability in another resource. This raises the related
question of how much the weighted resources bids with shared funding
pool model makes sense.

The question here is how the contingency fund should be managed. The
issues are idempotency of bids and simplicity of bidding. Some
possible solutions for when to reset the contingency fund:

1) with every bid. Simple to understand, difficult to manage.

2) with bids that change the duration or contingency ratio. Somewhat
   difficult to understand, but allows for simpler idempotency.

3) with funding operations. Too complex; introduces a third kind of
   bid operation (others are bid and fund).

11/14 Error handling revisited 3: there are several kinds of rpc error
mechanisms without a clear policy on how they should be used:

1) a TyException passed in the "result" field of the result.
2) a Fault that is raised
3) an unexpected Exception that occurs

#2 and #3 should be retired because they cannot be authenticated

12/18 Bid semantics are confusing because of the ability to use
default values and the precedence of different values. Here are the
rules:

1) Any value can be "None". This means that the existing value is used.
2) However, the min_resource and min_resource_amount cannot both be
specified (the same goes for max_resource and max_resource_amount), so
when one is specified, it takes precedence over the earlier value.

1/17 Long standing auctioneer bugs:
     1) balance and contingency balance need to take effect on
     immediate account_and_allocate. They were waiting for next
     accounting cycle
     2) balance, contingency_balance, and allocation need to be
     undone on failed bid, fund, and refund
     3) allocation needs to be undone on failed create_account

     Solutions:
     *) For 2 and 3: rerun allocation cycle after undoing operation
     *) For 1: Save balance, contingency balance information, restore
     on failure. This opens a window when the balance is altered and 
     an RPC call could alter it. Need to preclude race conditions
     anyway.

1/17 Revisiting the question of when the contingency fund should be
recalculated, the previous solution of only doing it when duration or
contingency ratios change seems to allow incorrect values when the
weights change. As a result, we should recompute the contingency fund
with every bid change. Also, the contingency accounting counters
should be reset. As a special case, if the bid does not change at all,
we will keep all contingency information unchanged. This is useful if
the client sends multiple identical bids to increase reliability.

1/25 Account and allocate problem: solutions to simplify handling of
failed bids:
    1) Make all state ephemeral and write it back after checking for
       errors
    2) Run another allocation pass after undoing error
    3) Hybrid: commit accounting immediately, make allocation ephmeral,
       only re-run allocation on error, only commit allocation late.

2/7 Should a failure to get a unique resource cause a
bid/creation/fund/refund to fail? No, putting in a failed bid for
unique resources is useful to raise the price of that resource.

2/9 Resource model: There should be a more unified model of resources
that encompasses both non-unique and unique resources. This should make
it easier to think about and write code. Here is a new model:

Resource Type: memory, IPv4Address, etc.
{ identifier: 
  { 'capacity': c, 'price': p, 'time': t, 'price_statistics': ps, 
    'misc': m}
  ...
}

identifier can be any scalar or a tuple (l, r) indicating a range.

The issues:

1) When to combine identifiers into a range?

2) When to split them?

3) How to express preferences?

Possibilities:
capacity                id              example
min, max                any one         disk
1.0, 1.0                specific one    port 80
1.0, 1.0                any one         any IP address
min, max                all             

Use the existing interface and defer this issue.

4) How to allocate based on preferences?

Use the existing allocation algorithm and defer this issue.

5/2/2007 Unique resource states:

1) Allocated. These have individual entries in the status data
   structure for keeping price statistics
2) Recently Unallocated. These are the same as the allocated.
3) Unallocated and old. These are coalesced with adjacent instances
   and do not have price statistics.

5/23/2007 Unique resource pricing

The current second price auction for unique resources has problems:

1) It is difficult to gauge demand. The price is zero most of the
   time and only surges when someone else tries to acquire the
   resource. In many cases, the other person will not even try to
   acquire it because he can see that he will not meet the highest
   bid. The inability to gauge demand prevents users from making
   rational bids for the resource.

2) A users who tries to outbid another user may not pay anything for
   the attempt. This will happen if there are only two users. Bidding
   should cost something to limit the damage that a malicious user can
   cause. In this case, the damage is denying a user the use of a
   unique resource.

3) Paying zero most of the time for unique resources is unfair to the
   provider.  

Solutions:

1a) Use the top bid to record current and historical prices. This will
   give a better sense of demand. Unfortunately, this also allows an
   attacker to easily outbid the top bidder. Publishing the top price
   removes the sealed bid property.

1b) The top bidder pays the maximum of his minimum bid, the second
    highest bid, and the provider's minimum bid. This is the reported
    price. Users who want to advertise a high bid must pay for that
    privilege. The problem with this is that it is unclear what a
    late-arriving bidder should do since he does not know what bid
    will be required to outbid the existing bidder. He will probably
    bid when his valuation is much greater than the advertised price.

2) Failed bids always pay their bid instead of zero. This will limit
   the damage that malicious attackers can do without overly charging
   legitimate users.

5/31/2007

Bank bid:

tycoon -u bank host bid tycoon-ext-02.hpl.hp.com 3y \
  memory:1,256MiB,1GiB,10000.9 CPU:1,0.10,1,10000.9 \
  disk:1,100GB,100GB,10000 NetworkInterfaceIncoming:1,0.5,1.0,10000.9 \
  NetworkInterfaceOutgoing:1,0.5,1.0,10000.9 \
  IPv4Address,204.123.34.92:1,10000

sls bid:

tycoon -u sls host bid tycoon-ext-03.hpl.hp.com 3y \
  memory:1,256MiB,1GiB,10000.9 CPU:1,0.10,1,10000.9 \
  NetworkInterfaceIncoming:1,0.5,1.0,10000.9 \
  NetworkInterfaceOutgoing:1,0.5,1.0,10000.9 disk:1,1GiB,1GiB,10000 \
  IPv4Address,204.123.34.101:1,10000

6/15/2007

Replay defense system: replay prevention is important in any system
that does not have real time bi-directional communication. Previous
work has used three basic techniques for replay prevention: 1)
timestamps, and 2) random nonces with history buffers, and 3)
incrementing nonces.

With timestamps, the sender includes a timestamp in a message and the
source verifies that the timestamp is after an offset from its own
time. The disadvantages are that the clocks must be relatively
synchronized and timestamped messages can still be replayed within the
offset time.

With random nones and history buffers, the sender includes a
randomly-generated identifier in a message and the receiver compares
it to entries in a buffer of received nonces. If the identifier is not
in the buffer, then it is accepted. Otherwise, it is rejected. The
disadvantage is that it requires unbounded state.

With incrementing nonces, the sender simply keeps a counter that it
increments after every communication. The receiver compares this
counter to its largest seen counter and verifies that the new counter
is larger than any previously received counter. The disadvantage is
that the sender and receiver's state must be synchronized, which is
difficult when sender use multiple machines or the sender's machines
fails.

Our solution is to combine the best properties of timestamps and
history buffers. The sender sends a timestamp with each message. The
receiver keeps a buffer of recently seen timestamps. If the
transmitted timestamp is after the oldest timestamp in the buffer and
is not in the buffer, then it is not a replay. Otherwise, it is either
too old, or a duplicate of timestamp in the buffer. Both are
suspicious, so the timestamp is rejected. As with a timestamp-only
approach, this technique uses a constant amount of state. As with the
history buffer approach, this technique can detect duplicates that are
within the clock skew horizon.

In Tycoon, this system is used for RPCs and bank receipts.

9/12/2007

Service location service authentication. The SLS needs to authenticate
clients to prevent clients from hijacking other clients' addresses.

This is complicated by web proxies and NATing. For example, the
simplest solution is to require that operations on an IP address be
from that IP address. This works for normal hosts and NAT-ed hosts,
but not for hosts behind web proxies. Another solution is to use the
address contained within the registration message. This works for
normal and proxied hosts, but NAT-ed hosts usually do not know their
externally routable address. In addition, this solution allows clients
to "squat" on the addresses of others, preventing them from being
registered by the real owner.

There are variety of cases that the solution must handle:

   A. Well-behaved, non-proxied, non-nat-ed clients.
   B. Well-behaved, nat-ed clients. They can be contacted externally.
   C. Well-behaved, proxied clients. They cannot be contacted externally.
   D. Squatting clients.


Here is a more robust (and complex) registration solution that allows
NAT-ed and proxied clients to co-exist: 

   1. The client contacts the SLS with its self-known address and the
      externally known address used at the network layer.

   2. The SLS tries to connect back to both the self-known address and
      externally known address to verify the hash. 

external              self-known
conn, hash verified   conn, hash verified   if ex==self-known, accept ex
conn, hash verified   conn, hash failed     accept ex, NAT w/external
conn, hash verified   no conn               accept ex, NAT w/external
conn, hash failed     conn, hash verified   accept self, proxy?
conn, hash failed     conn, hash failed     reject
conn, hash failed     no conn               accept self, NAT
no conn               conn, hash verified   accept self, proxy?
no conn               conn, hash failed     reject
no conn               no conn               accept self, proxy

In any case where a registration was accepted without callback hash
verification, a new registration that passes callback hash
verification supercedes it.

4/1/2008 Migration

Automatic VM migration is important for maintaining high reliability
and reducing admin overhead. The basic design is for clients to
request a migration.

4/1/2008 Uploading a file system

This is challenging because python's XML-RPC implementation is not
designed to for streaming. More specifically, it assumes that all the
call arguments can be held in memory. Since file system images are in
the range of 300MB-2GB, this could cause paging and slow the entire
system down. Some alternatives:

1) Split the upload into multiple XML-RPC calls

2) Do the upload as a separate scp operation. The process would be:
   a) Create_account with a dummy file system name
   b) Upload using scp, overwriting the dummy file system
   c) Configure the file system 

5/30/2008 XML Parsing Benchmarks
1.87 GHz laptop, 500,000 elements
               Serialize Unserialize
Unpatched         1.9878     10.8072
cElemenTree       1.9327      7.0276
lxml 2.0.5        1.9271      9.7098

Local Variables:
mode:text
End: