|
Size: 2605
Comment:
|
← Revision 15 as of 2013-04-18 18:37:27 ⇥
Size: 3444
Comment: mark for cleanup
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| '''[http://29kj.com >>>> 香港六合彩曾道人白小姐提供六合彩资料和六合彩开奖结果]''' | <<Include(A:dated)>> <<Include(A:style)>> |
| Line 3: | Line 4: |
| '''[http://29kj.com >>>> 香港六合彩专业网站,香港赛马会连结,提供香港六合彩特]''' | ## page was renamed from WireProtocolNG |
| Line 5: | Line 6: |
| '''[http://29kj.com >>>> 香港六合彩官方网站曾道人内幕玄香港六合 彩大公开]''' | Status: Draft/Experiment |
| Line 7: | Line 8: |
| '''[http://1878.cc >>>> 香港六合彩天线宝宝公开内幕玄香港六合 彩]''' | == Proposed new discovery/changegroup protocol == |
| Line 9: | Line 10: |
| '''[http://29kj.com >>>> 香港六合彩曾道人特码主论坛六合彩图库白小姐liuhecai]''' | The wire protocol has several flaws: * it uses the roots of the new branches, this is susceptible to a race (see issue1320) . * if the client is missing a lot of nodes but doesn't have any local changes, it will still have to do a lot of round trips to discover the base nodes. |
| Line 11: | Line 14: |
| '''[http://1878.cc >>>> 香港六合彩内幕玄香港六合 彩大公开]''' | See WireProtocol for the current protocol. |
| Line 13: | Line 16: |
| '''[http://29kj.com >>>> 香港六合彩开奖结果预测、特码、图库、单双、大小、头数、尾数、平码、特围等开奖综合信息]''' | === Overview === |
| Line 15: | Line 18: |
| '''[http://1878.cc >>>> 香港六合彩特码白小姐网站:六合彩开奖结果最快现场直播网站]''' | |
| Line 17: | Line 19: |
| '''[http://1878.cc >>>> 香港六合彩开奖现场 香港六合彩官方网 香港六合彩开奖记录 香港六合彩开奖结果 香港六合彩图库]''' | |
| Line 19: | Line 20: |
| '''[http://1878.cc >>>> 香港六合彩公司 香港六合彩开奖 香港六合彩网站 香港六合彩总公司 香港六合彩特码 ]''' | === The Protocol === |
| Line 21: | Line 22: |
| '''[http://29kj.com >>>> 香港六合彩开奖现场 香港六合彩官方网 香港六合彩开奖记录 香港六合彩 六合彩开奖结果]''' | ==== Discovery ==== |
| Line 23: | Line 24: |
| '''[http://29kj.com >>>> 香港六合彩-六合彩图库/六合彩网站/偷偷暗示每期内幕特码资料]''' | Instead of exploring the missing remote nodes like the current protocol, this proposal explores the local nodes, exploiting more local knowledge and having a stateful approach (which can't be done on the server). |
| Line 25: | Line 26: |
| '''[http://29kj.com >>>> 香港六合彩开奖结果:香港六合彩图库-六合彩曾道人特码-六合彩开奖结果]''' | It only needs one new server call: |
| Line 27: | Line 28: |
| '''[http://29kj.com >>>> 香港六合彩曾道人公开内幕资料— 香港六合彩-特码搜索]''' | {{{discover(nodes)}}} * list of local nodes {{{ return a boolean array, value is True if the server has the node, False otherwise. (TODO: investigate what is cheaper, between list and boolean array / to avoid races, should we pass the head as argument?) }}} |
| Line 29: | Line 34: |
| '''[http://29kj.com >>>> 六合彩|香港六合彩|六合彩公司|曾道人六合彩|六合彩最快开奖结果]''' | The client keeps all it's nodes between three states: unknown, missing and common. At each iteration, it builds a sample of the nodes in unknown state, send it to discover and update the sets accordingly. The sample size should obviously be bounded. |
| Line 31: | Line 38: |
| '''[http://29kj.com >>>> 香港六合彩/曾道人特码主论坛/六合彩特码主论坛/黄大仙老牌主论坛..]''' | Proposed sample construction: first breadth first search, starting from the nodes at {{{headsof(unknown)}}}, keep nodes at a distance 0, 1, 2, 4, 8, 16, ... from the heads. Second breadth first search starting at {{{rootsof(unknown)}}}, keep the nodes at a distance 0, 1, 2, 4, 8, 16, ... from the roots. If the sample is bigger than MAX_SAMPLE_SIZE, take a random sample from it, but make sure it includes the heads. If the number of unknown nodes is smaller than MAX_SAMPLE_SIZE, send all the unknown nodes to discover. |
| Line 33: | Line 41: |
| '''[http://29kj.com >>>> 香港六合彩图库，特码，平码，六合彩开奖结果，六合彩开奖历史记录]''' | During testing in largish repository (NetBeans, Linux Kernel), the number of iteration was almost always lower than 5. |
| Line 35: | Line 43: |
| '''[http://29kj.com >>>> 香港六合彩资料|香港六合彩:香港六合彩曾道人特码|香港六合彩开奖结果...]''' | Proposed tweak: the server can compute it's own unknown set and return a sample on it's own. Testing showed that it didn't make a big difference in the number of iterations (it usually removes at most one round trip) |
| Line 37: | Line 45: |
| '''[http://29kj.com >>>> 六合彩香港六合彩香港六合彩总公司六合彩官方网六合彩图库美香港六合 彩六肖图]''' | ==== Changegroup ==== |
| Line 39: | Line 47: |
| '''[http://29kj.com >>>> 香港六合彩公司|六合彩网|香港六合彩网|一字解特码|六合彩518222总公司]''' | The current changegroup() uses base nodes, it should instead use common nodes. |
| Line 41: | Line 49: |
| '''[http://29kj.com >>>> 香港六合彩网站,香港赛马会资料,香港六合彩玄香港六合 彩at 今天最新资料]''' | {{{changegroup(roots, heads)}}} * roots = list of nodes, that the server can assume the client knows (as well as all their ancestors). {{{ find all changesets ancestors from heads and not descended from roots and return them as a single changegroup }}} A changegroup is a single stream containing: * a changelog group * a manifest group * a list of * filename length * filename * file group (terminated by a zero length filename) A group is a list of chunks: * chunk length * self hash, p1 hash, p2 hash, link hash * uncompressed delta to p1 (or optionally to the previous node) * (terminated by a zero length chunk) * where should lightweight copies be put? === Prototypes === Prototypes can be found here: * http://bitbucket.org/parren/dag-discovery/ * http://bitbucket.org/bboissin/dag-discovery/ (fork) === Wishlist === * Estimate early how much data or items have to be transfered and communicate this to the other side, so a progress indicator could be more useful. -- ThomasArendsenHein <<DateTime(2008-10-24T14:23:01Z)>> ---- CategoryInternals |
Note:
This page appears to contain material that is no longer relevant. Please help improve this page by updating its content.
|
This page does not meet our Status: Draft/Experiment
Proposed new discovery/changegroup protocol
The wire protocol has several flaws:
- it uses the roots of the new branches, this is susceptible to a race (see issue1320) .
- if the client is missing a lot of nodes but doesn't have any local changes, it will still have to do a lot of round trips to discover the base nodes.
See WireProtocol for the current protocol.
Overview
The Protocol
Discovery
Instead of exploring the missing remote nodes like the current protocol, this proposal explores the local nodes, exploiting more local knowledge and having a stateful approach (which can't be done on the server).
It only needs one new server call:
discover(nodes)
- list of local nodes
return a boolean array, value is True if the server has the node, False otherwise. (TODO: investigate what is cheaper, between list and boolean array / to avoid races, should we pass the head as argument?)
The client keeps all it's nodes between three states: unknown, missing and common. At each iteration, it builds a sample of the nodes in unknown state, send it to discover and update the sets accordingly. The sample size should obviously be bounded.
Proposed sample construction: first breadth first search, starting from the nodes at headsof(unknown), keep nodes at a distance 0, 1, 2, 4, 8, 16, ... from the heads. Second breadth first search starting at rootsof(unknown), keep the nodes at a distance 0, 1, 2, 4, 8, 16, ... from the roots. If the sample is bigger than MAX_SAMPLE_SIZE, take a random sample from it, but make sure it includes the heads. If the number of unknown nodes is smaller than MAX_SAMPLE_SIZE, send all the unknown nodes to discover.
During testing in largish repository (NetBeans, Linux Kernel), the number of iteration was almost always lower than 5.
Proposed tweak: the server can compute it's own unknown set and return a sample on it's own. Testing showed that it didn't make a big difference in the number of iterations (it usually removes at most one round trip)
Changegroup
The current changegroup() uses base nodes, it should instead use common nodes.
changegroup(roots, heads)
- roots = list of nodes, that the server can assume the client knows (as well as all their ancestors).
find all changesets ancestors from heads and not descended from roots and return them as a single changegroup
A changegroup is a single stream containing:
- a changelog group
- a manifest group
- a list of
- filename length
- filename
- file group (terminated by a zero length filename)
A group is a list of chunks:
- chunk length
- self hash, p1 hash, p2 hash, link hash
- uncompressed delta to p1 (or optionally to the previous node)
- (terminated by a zero length chunk)
- where should lightweight copies be put?
Prototypes
Prototypes can be found here:
Wishlist
- Estimate early how much data or items have to be transfered and communicate this to the other side, so a progress indicator could be more useful.
-- ThomasArendsenHein 2008-10-24 14:23:01