InMemoryStorage » History » Version 9
Yingdi Yu, 09/13/2014 10:54 PM
1 | 1 | Yingdi Yu | # Per-application in-memory storage |
---|---|---|---|
2 | |||
3 | 4 | Yingdi Yu | Many NDN applications need to publish data packets. A data packet may have a FreshnessPeriod which indicates how long a node (local fowarders and routers) should wait after the arrival of this data before marking it as stale. As stated in NDN-TLV spec: |
4 | 1 | Yingdi Yu | |
5 | 4 | Yingdi Yu | > Note that the stale data is still valid data; the expiration of FreshnessPeriod only means that the producer may have produced newer data. |
6 | |||
7 | The inconsistency between the actually validity of a data packet and its FreshnessPeriod comes from the unpredictability of the future. |
||
8 | In some cases, the data producer cannot predict when a data packet will be replaced by a new version of data packet. |
||
9 | One extreme solution is to set FreshnessPeriod of the unpredictable data packet to 0, |
||
10 | so that whenever the data is request, the interest will be forwarded to the original producer to check whether a new version of data packet has been generated or not. |
||
11 | |||
12 | Fortunately, some data packets are relatively static (i.e., it occasionally changes) and can benefit from network caching. |
||
13 | The FreshnessPeriod becomes a tradeoff between network caching and data freshness. |
||
14 | As a result, during the FreshnessPeriod, the producer will not be bothered by interests for the same data packet. |
||
15 | However, after the FreshnessPeriod, when all the cached copies become stale, the producer should be prepared to receive the interests again. |
||
16 | If, at that time, the data is still valid, the producer should return the same data packet to refresh the cached copies. |
||
17 | |||
18 | It seems that it is beneficial to keep a copy of the valid data packet at the producer side, otherwise the producer has to generate/sign the data packet again and again. |
||
19 | The copy of the valid data packet cannot be stored in the ContentStore of local nfd, because current ContentStore can only tell fresh or stale data, but cannot tell valid or invalid data. |
||
20 | Instead, it is better to provide the storage inside the app, i.e., in-memory storage. |
||
21 | |||
22 | We list several use cases of the in-memory storage. |
||
23 | |||
24 | 1 | Yingdi Yu | ## Use cases |
25 | |||
26 | ### PIB Service |
||
27 | |||
28 | 4 | Yingdi Yu | PIB provides the public information about identities, keys, and certificates. |
29 | For example, one may ask PIB for the system default key. |
||
30 | And PIB's reply should be valid until the system default key is changed. |
||
31 | Since PIB cannot predict when the system default key will be changed, |
||
32 | it is more reasonable to set a relatively short FreshnessPeriod for the reply. |
||
33 | As a result, after every FreshnessPeriod, PIB may receive an interest for the system default key, because the cached copy in ContentStore is marked as stale. |
||
34 | 1 | Yingdi Yu | |
35 | 4 | Yingdi Yu | In this case, PIB can benefit from the in-memory storage. |
36 | By putting the reply into the in-memory storage, PIB can avoid repeatedly generating the same data packet. |
||
37 | |||
38 | ### Nack |
||
39 | |||
40 | When the producer want to explicitly tell consumer some data does not exist for now, it may use the nack data. |
||
41 | However, the producer may not know when the requested data will be generated. |
||
42 | With the same logic, the producer can generate a nack data with short FreshnessPeriod, |
||
43 | and put it into the in-memory storage to avoid repeatedly generating the same nack. |
||
44 | When the requested data has been generated, the producer can replace the nack with the new data in the in-memory storage. |
||
45 | |||
46 | 1 | Yingdi Yu | ### ChronoChat |
47 | |||
48 | 4 | Yingdi Yu | For chatroom discovery, each chatroom needs to publish the chatroom-info data. |
49 | Chatroom-info must have finite FreshnessPeriod, so that after FreshnessPeriod, the chatroom-refresh interest will reach one of the chatroom participants. |
||
50 | If the chatroom-info has not changed yet, it is not necessary to generate a new chatroom-info data. |
||
51 | |||
52 | The FreshnessPeriod of a chat message can be set to infinite. However, ContentStore may not guarantee to keep all the chat messages even if they are fresh. |
||
53 | An in-memory storage can help here as a guaranteed storage as long as the process is running. |
||
54 | |||
55 | 1 | Yingdi Yu | ### NLSR |
56 | |||
57 | 4 | Yingdi Yu | NLSR LSA is the same as ChronoChat chat message. |
58 | |||
59 | 6 | Yingdi Yu | ## Design Goal |
60 | 1 | Yingdi Yu | |
61 | 6 | Yingdi Yu | The goal of InMemoryStorage is to allow an application instance to keep a copy of valid data packets in its own memory. |
62 | The InMemoryStorage is useful in two general cases: |
||
63 | 1 | Yingdi Yu | |
64 | 6 | Yingdi Yu | * when data packets have been generated without incoming interest; |
65 | * when the lifetime of a data packet is longer than the FreshnessPeriod of the data packet. |
||
66 | |||
67 | For an application that may run into either of the two cases, it can create an InMemoryStorage instance within itself |
||
68 | and insert the data packets into the InMemoryStorage. |
||
69 | When the app receives an incoming interest, the app may first look up matched data packet in the InMemoryStorage to avoid generating the same data packet again. |
||
70 | |||
71 | Data packets in an InMemoryStorage is explicitly managed by the app. |
||
72 | A data packet can be either inserted into or erased from the InMemoryStorage. |
||
73 | In other words, the only way to change a data packet in an InMemoryStorage is to erase the data packet from the InMemoryStorage. |
||
74 | |||
75 | 9 | Yingdi Yu | Ideally, the InMemoryStorage should find a data packet that can match the incoming interest, |
76 | that is, besides longest name prefix matching, the InMemoryStorage should also process selectors. |
||
77 | However, some selectors are not meaningful to the data producer (e.g., MustBeFresh). |
||
78 | Moreover, the variety of data packets at the producer side is much less than the one in the cache intermediate routers, |
||
79 | so that some selectors (e.g., ChilderSelector, Min/MaxSuffixComponents, PublisherPublicKeyLocator) may not be necessary. |
||
80 | Therefore, longest name prefix matching alone should be sufficient for InMemoryStorage in most cases. |
||
81 | And InMemoryStorage provides two types of data look up interfaces: one is by-name while the other one is by-interest. |
||
82 | The by-name method will return the data packet that can match the interest name. |
||
83 | If there are more than one matched data packet, the lower bound (the first one in canonical order) will be returned. |
||
84 | 1 | Yingdi Yu | |
85 | 9 | Yingdi Yu | Note that an InMemoryStorage instance is created within an application instance, and is destroyed when the application instance ends. |
86 | 1 | Yingdi Yu | Therefore, the lifetime of the InMemoryStorage instance is no longer than the lifetime of the application instance. |
87 | The data packets stored in the InMemoryStorage will also be eliminated if the data packets are not backed up in some persistent storage (e.g., hard disk, repo, etc.) before the InMemoryStorage is destroyed. |
||
88 | 6 | Yingdi Yu | |
89 | 9 | Yingdi Yu | Also note that data in the InMemoryStorage cannot be modified unless erased. |
90 | 1 | Yingdi Yu | This implies that a data packet is uniquely identified by its name and implicit digest, |
91 | so that a data packet in InMemoryStorage cannot be overwritten by another data packet with the same name. |
||
92 | |||
93 | 6 | Yingdi Yu | ## Interface |
94 | |||
95 | 9 | Yingdi Yu | The interfaces of InMemoryStorage is defined as: |
96 | 6 | Yingdi Yu | |
97 | class InMemoryStorage |
||
98 | 5 | Yingdi Yu | { |
99 | 9 | Yingdi Yu | ... |
100 | |||
101 | // required methods |
||
102 | 5 | Yingdi Yu | void |
103 | insert(const Data& data); |
||
104 | |||
105 | void |
||
106 | 1 | Yingdi Yu | erase(const Name& prefix); |
107 | |||
108 | shared_ptr<const Data> |
||
109 | find(const Name& name); |
||
110 | 6 | Yingdi Yu | |
111 | 9 | Yingdi Yu | shared_ptr<const Data> |
112 | find(const Interest& interest); |
||
113 | 1 | Yingdi Yu | |
114 | 9 | Yingdi Yu | // optional methods |
115 | void |
||
116 | save(const std::string& filename); // save data packets to a file in default format |
||
117 | 6 | Yingdi Yu | |
118 | 9 | Yingdi Yu | void |
119 | load(const std::string& filename); // load data packets from a file in default format |
||
120 | ... |
||
121 | }; |
||
122 | 4 | Yingdi Yu | |
123 | ## Reference |
||
124 | |||
125 | There is another type of local storage, which is different from in-memory storage, called [Managed ContentStore](http://redmine.named-data.net/projects/nfd/wiki/ManagedContentStore) |