Artifact 0986b41ddddc3cdff48f295d76c5d9cad9d919cc:

• File wiki/distributed-data.wiki — part of check-in [44ebdb258a] at 2015-05-01 22:49:12 on branch trunk — More conversion to in-source wiki (user: bernd size: 1668)

0000: 3c 68 31 3e 44 69 73 74 72 69 62 75 74 65 64 20  <h1>Distributed 
0010: 44 61 74 61 3c 2f 68 31 3e 0a 0a 3c 64 69 76 3e  Data</h1>..<div>
0020: 3c 69 3e 54 68 69 73 20 69 73 20 73 74 69 6c 6c  <i>This is still
0030: 20 71 75 69 74 65 20 69 6e 63 6f 6d 70 6c 65 74   quite incomplet
0040: 65 3c 2f 69 3e 3c 2f 64 69 76 3e 0a 0a 3c 64 69  e</i></div>..<di
0050: 76 3e 46 6f 6c 6c 6f 77 69 6e 67 20 74 68 65 20  v>Following the 
0060: 22 65 76 65 72 79 74 68 69 6e 67 20 69 73 20 61  "everything is a
0070: 20 66 69 6c 65 22 20 70 68 69 6c 6f 73 6f 70 68   file" philosoph
0080: 79 20 6f 66 20 55 6e 69 78 2c 20 65 76 65 72 79  y of Unix, every
0090: 20 64 61 74 61 20 6f 62 6a 65 63 74 0a 69 73 20   data object.is 
00a0: 61 20 66 69 6c 65 2e 20 26 6e 62 73 70 3b 49 74  a file. &nbsp;It
00b0: 27 73 20 75 6e 69 71 75 65 6c 79 20 72 65 66 65  's uniquely refe
00c0: 72 65 6e 63 65 64 20 62 79 20 69 74 73 20 68 61  renced by its ha
00d0: 73 68 2e 20 26 6e 62 73 70 3b 46 75 72 74 68 65  sh. &nbsp;Furthe
00e0: 72 20 6d 65 74 61 64 61 74 61 0a 61 72 65 20 63  r metadata.are c
00f0: 61 6c 6c 65 64 20 22 74 61 67 73 22 2c 20 61 6e  alled "tags", an
0100: 64 20 6f 72 67 61 6e 69 7a 65 64 20 69 6e 20 61  d organized in a
0110: 20 64 69 73 74 72 69 62 75 74 65 64 20 70 72 65   distributed pre
0120: 66 69 78 20 68 61 73 68 20 74 72 65 65 2e 20 26  fix hash tree. &
0130: 6e 62 73 70 3b 54 68 65 72 65 0a 61 72 65 20 61  nbsp;There.are a
0140: 6c 73 6f 20 22 73 75 62 6a 65 63 74 73 22 20 28  lso "subjects" (
0150: 70 65 72 73 6f 6e 73 2c 20 63 6f 6d 70 75 74 65  persons, compute
0160: 72 73 29 2c 20 77 68 69 63 68 20 61 72 65 20 72  rs), which are r
0170: 65 66 65 72 65 6e 63 65 64 20 62 79 20 74 68 65  eferenced by the
0180: 69 72 20 70 75 62 6c 69 63 0a 6b 65 79 73 3b 20  ir public.keys; 
0190: 6e 65 63 65 73 73 61 72 79 20 6d 65 74 61 64 61  necessary metada
01a0: 74 61 20 66 6f 72 20 74 68 6f 73 65 20 73 75 62  ta for those sub
01b0: 6a 65 63 74 73 20 69 73 20 61 6c 73 6f 20 66 6f  jects is also fo
01c0: 75 6e 64 20 69 6e 20 74 68 65 20 44 50 48 54 2e  und in the DPHT.
01d0: 3c 2f 64 69 76 3e 0a 0a 3c 64 69 76 3e 41 73 20  </div>..<div>As 
01e0: 74 68 65 20 44 50 48 54 20 63 6f 6e 74 61 69 6e  the DPHT contain
01f0: 73 20 61 6c 6c 20 74 68 65 20 6d 65 74 61 64 61  s all the metada
0200: 74 61 2c 20 6f 62 6a 65 63 74 73 20 77 68 69 63  ta, objects whic
0210: 68 20 61 72 65 20 6e 6f 74 20 73 68 61 72 65 64  h are not shared
0220: 20 70 75 62 6c 69 63 0a 73 68 6f 75 6c 64 20 61   public.should a
0230: 6c 73 6f 20 6e 6f 74 20 62 65 20 76 69 73 69 62  lso not be visib
0240: 6c 65 20 69 6e 20 61 20 70 75 62 6c 69 63 20 68  le in a public h
0250: 61 73 68 20 74 72 65 65 3b 20 74 68 65 72 65 66  ash tree; theref
0260: 6f 72 65 2c 20 74 68 65 72 65 20 61 72 65 20 70  ore, there are p
0270: 72 69 76 61 74 65 0a 6f 72 20 67 72 6f 75 70 2d  rivate.or group-
0280: 72 65 6c 61 74 65 64 20 68 61 73 68 20 74 72 65  related hash tre
0290: 65 73 2c 20 61 73 20 77 65 6c 6c 2e 3c 2f 64 69  es, as well.</di
02a0: 76 3e 0a 0a 3c 68 32 3e 45 66 66 69 63 69 65 6e  v>..<h2>Efficien
02b0: 74 20 64 69 73 74 72 69 62 75 74 69 6f 6e 20 6f  t distribution o
02c0: 66 20 64 61 74 61 20 74 6f 20 6c 61 72 67 65 20  f data to large 
02d0: 6e 75 6d 62 65 72 73 20 6f 66 20 70 65 65 72 73  numbers of peers
02e0: 3c 2f 68 32 3e 0a 0a 3c 64 69 76 3e 46 6f 72 20  </h2>..<div>For 
02f0: 64 69 73 74 72 69 62 75 74 69 6e 67 20 64 61 74  distributing dat
0300: 61 20 74 6f 20 6d 61 6e 79 20 70 65 65 72 73 2c  a to many peers,
0310: 20 74 68 65 73 65 20 70 65 65 72 73 20 61 72 65   these peers are
0320: 20 61 72 72 61 6e 67 65 64 20 69 6e 20 61 20 63   arranged in a c
0330: 6f 6c 6f 72 65 64 0a 74 72 65 65 2e 20 26 6e 62  olored.tree. &nb
0340: 73 70 3b 44 61 74 61 20 28 65 2e 67 2e 20 76 69  sp;Data (e.g. vi
0350: 64 65 6f 20 73 74 72 65 61 6d 73 29 20 61 72 65  deo streams) are
0360: 20 64 69 76 69 64 65 64 20 69 6e 74 6f 20 64 69   divided into di
0370: 66 66 65 72 65 6e 74 20 63 68 75 6e 6b 73 2c 20  fferent chunks, 
0380: 61 6e 64 0a 73 65 6e 74 20 64 6f 77 6e 20 64 69  and.sent down di
0390: 66 66 65 72 65 6e 74 20 63 6f 6c 6f 72 65 64 20  fferent colored 
03a0: 62 72 61 6e 63 68 65 73 20 6f 66 20 74 68 65 20  branches of the 
03b0: 74 72 65 65 2e 20 26 6e 62 73 70 3b 54 68 65 20  tree. &nbsp;The 
03c0: 6c 65 61 66 20 6e 6f 64 65 73 20 6f 66 20 65 61  leaf nodes of ea
03d0: 63 68 0a 63 6f 6c 6f 72 65 64 20 62 72 61 6e 63  ch.colored branc
03e0: 68 20 74 68 65 6e 20 64 69 73 74 72 69 62 75 74  h then distribut
03f0: 65 20 74 68 65 20 64 61 74 61 20 74 6f 20 74 68  e the data to th
0400: 65 20 6f 74 68 65 72 20 62 72 61 6e 63 68 65 73  e other branches
0410: 2e 20 26 6e 62 73 70 3b 49 74 20 63 61 6e 20 62  . &nbsp;It can b
0420: 65 0a 73 68 6f 77 6e 20 74 68 61 74 20 65 61 63  e.shown that eac
0430: 68 20 6e 6f 64 65 20 72 65 63 65 69 76 65 73 20  h node receives 
0440: 61 73 20 6d 75 63 68 20 64 61 74 61 20 61 73 20  as much data as 
0450: 69 74 20 73 65 6e 64 73 20 28 77 68 65 6e 20 74  it sends (when t
0460: 68 65 20 74 72 65 65 20 69 73 0a 62 61 6c 61 6e  he tree is.balan
0470: 63 65 64 29 2e 20 26 6e 62 73 70 3b 54 68 65 20  ced). &nbsp;The 
0480: 6c 61 74 65 6e 63 79 20 6f 66 20 74 68 65 20 74  latency of the t
0490: 72 65 65 20 69 73 20 4f 28 6c 6f 67 20 6e 29 3b  ree is O(log n);
04a0: 20 74 68 65 20 61 63 74 75 61 6c 20 62 61 73 65   the actual base
04b0: 20 69 73 20 61 0a 74 72 61 64 65 6f 66 66 20 6f   is a.tradeoff o
04c0: 66 20 62 61 6e 64 77 69 64 74 68 20 61 6e 64 20  f bandwidth and 
04d0: 73 65 6e 64 69 6e 67 20 6c 61 74 65 6e 63 79 2e  sending latency.
04e0: 20 26 6e 62 73 70 3b 54 68 65 20 72 75 6c 65 20   &nbsp;The rule 
04f0: 6f 66 20 74 68 75 6d 62 20 69 73 20 74 6f 20 75  of thumb is to u
0500: 73 65 0a 74 68 65 20 68 6f 70 2d 74 6f 2d 68 6f  se.the hop-to-ho
0510: 70 20 6c 61 74 65 6e 63 79 20 74 69 6d 65 20 74  p latency time t
0520: 6f 20 73 65 6e 64 20 6f 75 74 20 70 61 63 6b 65  o send out packe
0530: 74 73 2c 20 73 6f 20 68 69 67 68 65 72 20 6c 61  ts, so higher la
0540: 74 65 6e 63 79 20 6d 65 61 6e 73 20 68 69 67 68  tency means high
0550: 65 72 0a 66 61 6e 6f 75 74 20 6f 66 20 74 68 65  er.fanout of the
0560: 20 74 72 65 65 2e 3c 2f 64 69 76 3e 0a 0a 3c 64   tree.</div>..<d
0570: 69 76 3e 54 72 65 65 73 20 61 72 65 20 66 6f 72  iv>Trees are for
0580: 6d 65 64 20 61 64 20 68 6f 63 2c 20 61 6e 64 20  med ad hoc, and 
0590: 73 69 6e 63 65 20 6e 6f 64 65 73 20 63 61 6e 20  since nodes can 
05a0: 63 6f 6d 65 20 61 6e 64 20 67 6f 20 61 73 20 74  come and go as t
05b0: 68 65 79 20 6c 69 6b 65 2c 0a 74 68 65 72 65 20  hey like,.there 
05c0: 6e 65 65 64 73 20 74 6f 20 62 65 20 73 65 6c 66  needs to be self
05d0: 2d 68 65 61 6c 69 6e 67 20 63 61 70 61 62 69 6c  -healing capabil
05e0: 69 74 69 65 73 2e 20 26 6e 62 73 70 3b 4e 6f 64  ities. &nbsp;Nod
05f0: 65 73 20 6b 6e 6f 77 20 32 6e 20 6e 65 69 67 68  es know 2n neigh
0600: 62 6f 72 73 20 66 6f 72 0a 61 20 74 72 65 65 20  bors for.a tree 
0610: 62 61 73 65 20 6e 2e 20 26 6e 62 73 70 3b 54 68  base n. &nbsp;Th
0620: 65 73 65 20 74 72 65 65 73 20 61 72 65 20 75 73  ese trees are us
0630: 65 64 20 66 6f 72 20 66 69 6c 65 2d 73 68 61 72  ed for file-shar
0640: 69 6e 67 2c 20 66 6f 72 20 67 72 6f 75 70 20 6d  ing, for group m
0650: 65 73 73 61 67 65 0a 64 65 6c 69 76 65 72 79 2c  essage.delivery,
0660: 20 61 6e 64 20 74 6f 20 6b 65 65 70 20 74 68 65   and to keep the
0670: 20 44 50 48 54 20 69 6e 20 73 79 6e 63 2e 3c 2f   DPHT in sync.</
0680: 64 69 76 3e                                      div>