Project

General

Profile

InMemoryStorage » History » Version 26

Davide Pesavento, 03/10/2016 12:09 PM
Fix typo

1 1 Yingdi Yu
# Per-application in-memory storage
2
3 22 Yingdi Yu
Many NDN applications need to publish data packets. A data packet may have a FreshnessPeriod which guards producer from receiving too many interests for the same data packet.
4
However, producers may still receive interests for the same data packet after the FreshnessPeriod, 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.
5 4 Yingdi Yu
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.
6
Instead, it is better to provide the storage inside the app, i.e., in-memory storage.
7
8
We list several use cases of the in-memory storage.
9
10 1 Yingdi Yu
## Use cases
11
12
### Nack
13
14
When the producer want to explicitly tell consumer some data does not exist for now, it may use the nack data.
15
However, the producer may not know when the requested data will be generated. 
16
With the same logic, the producer can generate a nack data with short FreshnessPeriod,
17 4 Yingdi Yu
and put it into the in-memory storage to avoid repeatedly generating the same nack.
18
When the requested data has been generated, the producer can replace the nack with the new data in the in-memory storage.
19 1 Yingdi Yu
20
### ChronoChat
21 4 Yingdi Yu
22 1 Yingdi Yu
For chatroom discovery, each chatroom needs to publish the chatroom-info data. 
23
Chatroom-info must have finite FreshnessPeriod, so that after FreshnessPeriod, the chatroom-refresh interest will reach one of the chatroom participants.
24
If the chatroom-info has not changed yet, it is not necessary to generate a new chatroom-info data.
25
26
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.
27
An in-memory storage can help here as a guaranteed storage as long as the process is running.
28
29
### NLSR
30
31
NLSR LSA is the same as ChronoChat chat message.
32
33 22 Yingdi Yu
### PIB Service
34
35
PIB provides the public information about identities, keys, and certificates. 
36
For example, one may ask PIB for current certificate for a key.
37
And PIB's reply should be valid until the system default key is changed. 
38
Since PIB cannot predict when the system default key will be changed,
39
it is more reasonable to set a relatively short FreshnessPeriod for the reply. 
40
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.
41
42
In this case, PIB can benefit from the in-memory storage. 
43
By putting the reply into the in-memory storage, PIB can avoid repeatedly generating the same data packet.
44
45 1 Yingdi Yu
## Design Goal
46
47 22 Yingdi Yu
The goal of InMemoryStorage is to provide a common pattern for applications that need to keep a copy of valid data packets for a while in its own memory. 
48
Here is a diagram about how InMemoryStorage is used:
49 4 Yingdi Yu
50 22 Yingdi Yu
    +------------------------------------------------------------------------+    +---+
51
    | Application                                                            |    |   |
52
    |                                                                        |    |   |
53
    | +-----------+ A. Insert data  +-----------------+ C. OnInterest  +---+ |    |   |
54
    | |           |---------------->|                 |<---------------|   | |    |   |
55
    | |           |                 | InMemoryStorage |                |   | |    |   |
56
    | |           |---------------->|                 |--------------->|   | |    |   |
57
    | |           | B. Erase data   +-----------------+ D. If data     |   | |    |   |
58
    | |Processing |                       |                is found    | F | |    | N |
59
    | |Logic      |                       |                            | A | |/--\| F |
60
    | |           |                       | E. If data is not found    | C | |\--/| D |
61
    | |           |<----------------------+                            | E | |    |   |
62
    | |           |                       | F. OnInterest              |   | |    |   |
63
    | |           |                       +----------------------------|   | |    |   |
64
    | |           |                                                    |   | |    |   |
65
    | |           |--------------------------------------------------->|   | |    |   |
66
    | +-----------+      G. data is produced                           +---+ |    |   |
67
    +------------------------------------------------------------------------+    +---+
68 1 Yingdi Yu
69 22 Yingdi Yu
Typical processing could be:
70 4 Yingdi Yu
71 22 Yingdi Yu
1. app produces a data packet without incoming interest, then it could insert the data packet into the InMemoryStorage (Op. A). 
72
2. app may specify that some interests should be answered by InMemoryStorage first, in this case, 
73
   app can register the corresponding prefix with a OnInterest callback, when interest is received,
74
   app will lookup in the InMemoryStorage first (Op. C). If data is found, it will be returned directly (Op. D).
75
   If data is not found, the interest will be handled by the data producing logic of the app (Op. E).
76
   When app generates the data, app can insert the data in the InMemoryStorage (Op. A) and return it to face as well (Op. G).
77
3. app can also by-pass the InMemoryStorage for some interests. For this purpose, app can simply register a prefix with a callback
78
   that directly forward the interest to the data producing logic of the app (Op. F).
79
   And the generated response will be returned to face (Op. G).
80
4. If app want to delete some data packets from the InMemoryStorage or replace some obsolete data, it can erase the data packets from the InMemoryStorage (Op. B).
81
82
83
84 9 Yingdi Yu
Data packets in an InMemoryStorage is explicitly managed by the app. 
85
A data packet can be either inserted into or erased from the InMemoryStorage. 
86
In other words, the only way to change a data packet in an InMemoryStorage is to erase the data packet from the InMemoryStorage.
87
88 23 Yingdi Yu
InMemoryStorage provides two types of data look up interfaces: one is by-name while the other one is by-interest.
89
The by-name method will return the data packet that can match the name (or prefix).
90 1 Yingdi Yu
If there are more than one matched data packet, the lower bound (the first one in canonical order) will be returned.
91 23 Yingdi Yu
92
The by-interest method will start from the first data packet that matches the incoming interest and apply the selectors one-by-one,
93 1 Yingdi Yu
therefore it is not very efficient if application did not maintain the content in the InMemoryStorage very well.
94 23 Yingdi Yu
Note that not all the selectors are meaningful to the data producer.
95
For example, the variety of data packets at the producer side is much less than the one in the cache intermediate routers,
96 26 Davide Pesavento
so that processing on some selectors (e.g., ChildSelector, Min/MaxSuffixComponents, PublisherPublicKeyLocator) may not be necessary.
97 1 Yingdi Yu
98 23 Yingdi Yu
One particular selector deserves special processing: MustBeFresh.
99
Ideally, InMemoryStorage does not need to process MustBeFresh selector,
100
because interests with MustBeFresh intend to retrieve the latest version of data from the producer, and the InMemoryStorage is already at the producer side, thus a producer can always keep the latest version of data in the InMemoryStorage. 
101 25 Yingdi Yu
However, in some special cases, a producer may also want to serve obsolete data in InMemoryStorage (See [[example|http://redmine.named-data.net/issues/2200#note-95]]).
102 23 Yingdi Yu
Therefore, InMemoryStorage must be able to process MustBeFresh selector when the producer has such a need.
103
For this purpose, InMemoryStorage allows a producer to specify a processing window for MustBeFresh selector when a data packet is inserted.
104
The processing window provides a semantic that "this data may satisfy Interests with MustBeFresh selector for the next T duration; after that it may only satisfy Interests without MustBeFresh selector".
105
A negative processing window means "infinity", indicating that MustBeFresh will not be processed.
106
107
108 1 Yingdi Yu
Note that an InMemoryStorage instance is created within an application instance, and is destroyed when the application instance ends. 
109
Therefore, the lifetime of the InMemoryStorage instance is no longer than the lifetime of the application instance. 
110 22 Yingdi Yu
The data packets stored in the InMemoryStorage will also be eliminated if the data packets in it are not serialized in some persistent storage (e.g., hard disk, repo, etc.) before the InMemoryStorage is destroyed.
111 1 Yingdi Yu
112
Also note that data in the InMemoryStorage cannot be modified unless erased.
113
This implies that a data packet is uniquely identified by its name and implicit digest,
114
so that a data packet in InMemoryStorage cannot be overwritten by another data packet with the same name.
115
116
## Interface
117
118
The interfaces of InMemoryStorage is defined as:
119
120
    class InMemoryStorage 
121
    {
122
      ...
123
124
      // required methods
125
      void 
126 24 Yingdi Yu
      insert(const Data& data, time::milliseconds mustBeFreshProcessingWindow);
127 6 Yingdi Yu
128 9 Yingdi Yu
      void 
129 1 Yingdi Yu
      erase(const Name& prefix);
130
131 11 Yingdi Yu
      shared_ptr<const Data> 
132 1 Yingdi Yu
      find(const Name& name);
133 6 Yingdi Yu
134
      shared_ptr<const Data> 
135 24 Yingdi Yu
      find(const Interest& interest);
136 6 Yingdi Yu
137
      // optional methods
138 22 Yingdi Yu
      const_iterator
139
      begin() const;
140 9 Yingdi Yu
141 22 Yingdi Yu
      const_iterator
142
      end() const; 
143 5 Yingdi Yu
      ...
144
    };
145
146 22 Yingdi Yu
147 1 Yingdi Yu
## NFD support
148
149
Since an application has already kept a copy of data packet, it should be able to inform the local daemon not to keep a copy in the content store. 
150 6 Yingdi Yu
This can be done through extending NFD local control header, but specific design is still TBD.
151 22 Yingdi Yu
152
## Discussion about FreshnessPeriod
153
154
As stated in NDN-TLV spec: 
155
156
> Note that the stale data is still valid data; the expiration of FreshnessPeriod only means that the producer may have produced newer data.
157
158
The inconsistency between the actually validity of a data packet and its FreshnessPeriod comes from the unpredictability of the future.
159
In some cases, the data producer cannot predict when a data packet will be replaced by a new version of data packet. 
160
One extreme solution is to set FreshnessPeriod of the unpredictable data packet to 0, 
161
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.
162
163
Fortunately, some data packets are relatively static (i.e., it occasionally changes) and can benefit from network caching.
164
The FreshnessPeriod becomes a tradeoff between network caching and data freshness.
165
As a result, during the FreshnessPeriod, the producer will not be bothered by interests for the same data packet.
166
However, after the FreshnessPeriod, when all the cached copies become stale, the producer should be prepared to receive the interests again.
167
If, at that time, the data is still valid, the producer should return the same data packet to refresh the cached copies.
168 4 Yingdi Yu
169
## Reference
170
171 1 Yingdi Yu
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)