Opened 9 months ago

Closed 6 months ago

#27359 closed defect (implemented)

Store family lists more efficiently

Reported by: nickm Owned by: nickm
Priority: Medium Milestone: Tor: 0.4.0.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: 035-roadmap-master, 035-triaged-in-20180711
Cc: Actual Points: 3
Parent ID: #27243 Points:
Reviewer: teor Sponsor: Sponsor8-can

Description

Looking at the analysis, our storage for family lists accounted for 1.3MB out of 24.9MB total allocation. That's around 5% of our total allocation, not counting malloc overhead.

Fortunately, this will be pretty easy to fix.

Child Tickets

Change History (18)

comment:1 Changed 9 months ago by nickm

I've got an untested, undocumented, unintegrated sketch design in a branch called ticket27359. It needs to get tested, documented, and integrated with microdesc. (maybe someday it could get integrated with routerdesc -- but that wouldn't work for authorities yet.)

comment:2 Changed 8 months ago by nickm

Milestone: Tor: 0.3.5.x-finalTor: 0.3.6.x-final

comment:3 Changed 8 months ago by nickm

Sponsor: Sponsor8-can

comment:4 Changed 7 months ago by nickm

Owner: set to nickm
Status: newaccepted

comment:5 Changed 7 months ago by nickm

So the idea of the scheme here is to encode families in a more compact representation: roughly, as a sorted array of 21-byte elements, where each element is a one byte tag, and 20 bytes of either a sha1 ID or a nickname. These objects are reference-counted, so that they can be shared by relays with the same family members.

To optimize the number of family objects that are shared by multiple relays, I want to add each relay's hex ID to its own family -- doing this will make all the relays in the same family have the same encoded family. (It's harmless to consider a relay a member of its own family.)

I've run into a few issues with this, and I'm not sure which of them need to be solved pre-merge, and how.

1) A small number of relays specify invalid hex IDs in their family lines -- typically, with the wrong number of hex digits.

2) A small number of relays use the $hexid=nickname syntax, which can't be encoded in the manner above, and which is probably not what they want anyway.

3) Authorities need to process family lines exactly as they are received, and rely on a lossless encoding of their inputs.

4) When parsing a microdescriptor, we do not know which relay it is associated with, so we can't easily add its own ID to its family when parsing it. (Further, it is in theory possible for two misconfigured relays to wind up with the same microdescriptor, I think.)

I'm not sure quite what to do about each of these issues.

comment:6 Changed 7 months ago by nickm

After conversation with teor, here's what we're thinking:

  1. Ignore any malformed family entries
  2. Treat $hexid=nickname as if it just said $hexid.
  3. Don't use this trick outside of parsed microdescriptors, since that's what clients need.
  4. Add a new consensus method to canonicalize family lists by adding each node's own identity and sorting the entries.

comment:7 Changed 7 months ago by nickm

For future work (TODO, make tickets)

  1. Also do the same canonicalization in ns consensus documents
  2. Deprecate $foo=bar and $foo~bar
  3. Relays should warn if they are about to publish an invalid hexid in their family line.
  4. Relays should canonicalize their own family lines

comment:8 in reply to:  6 Changed 7 months ago by teor

Replying to nickm:

...

  1. Add a new consensus method to canonicalize family lists by adding each node's own identity and sorting the entries.

Looking at the available microdescs, we should also:

  • uppercase the hex ids

It's also worth noting;:

  • chutney doesn't set MyFamily, so we'll need to test carefully
  • this change likely causes:
    • a slight increase in the size of descriptors on disk (from the extra ids), offset by removing =nick and malformed hex id, and
    • a slight decrease of compressed descriptor size, because the sorted lines are identical

comment:9 Changed 7 months ago by nickm

  1. Also do the same canonicalization in ns consensus documents

fwiw, I don't think ns consensus documents include family lines?

comment:10 Changed 7 months ago by nickm

Actual Points: 2
Status: acceptedneeds_review

See branch ticket27359_v2, with PR at https://github.com/torproject/tor/pull/463

comment:11 in reply to:  9 Changed 7 months ago by teor

Replying to nickm:

  1. Also do the same canonicalization in ns consensus documents

fwiw, I don't think ns consensus documents include family lines?

Yes, you're right, family only appears in descriptors.

comment:12 Changed 7 months ago by dgoulet

Reviewer: teor

comment:13 Changed 7 months ago by teor

Status: needs_reviewneeds_revision

I did a review, looks good, except for a case-comparison bug.

comment:14 Changed 7 months ago by nickm

Milestone: Tor: 0.3.6.x-finalTor: 0.4.0.x-final

Tor 0.3.6.x has been renamed to 0.4.0.x.

comment:15 Changed 6 months ago by nickm

Status: needs_revisionneeds_review

I've resolved the bug, and added a bunch of tests. Do you like the test coverage now?

comment:16 Changed 6 months ago by teor

Status: needs_reviewmerge_ready

Looks good to me.

Let's defer the routerinfo / microdesc decision until later.

comment:17 Changed 6 months ago by nickm

Thanks! Squashed and merged!

comment:18 Changed 6 months ago by nickm

Actual Points: 23
Resolution: implemented
Status: merge_readyclosed
Note: See TracTickets for help on using tickets.