タイル画像ファイルおよびOSMバイナリレコードファイルは階層ディレクトリで管理するのが一番簡単であるが、 ファイル数が膨大になると、Android スマホでは負担が重くなってくる。
そこで、zipファイルとしてみた。現在、OSM地図のタイル画像ファイルは 10万程度であり、 以前の階層ディレクトリに比べて、総合的なパフォーマンスに大きな違いはない。
国土地理院標準地図ではレンダリングはないが、ガーベージコレクションが頻発する。 この原因は タイル画像数が膨大なため、管理部が相当大きくなり、エントリ(タイル画像)読み込みごとに、 大きなメモリが使われることにあるようだ。
zipファイル構造に似ているが、管理部をシンプルにしたファイル構造にした。 管理部はメモリに読み込んで個々のエントリを読みだすようにした。
こうした場合、国土地理院標準地図ではアプリ全体のメモリ使用量は 70MB 未満で変動は少なく、ガーベージコレクションは起きない。 メモリの大半はタイルキャッシュであろう。
レンダリングにはそれなりの時間がかかるため、今後、保存するタイル画像は更に増えるため、zip をやめ、 独自アーカイブ方式に変える。
現在は、更新/新規タイルは階層ディレクトリに置いている。 この二重構造より、アーカイブファイルに更新/新規タイルを含める方がいいであろう。 更新の場合、古いタイル画像はそのまま残し、後ろに新しいタイルを追加して、管理部はこの新しいタイルを指すように 修正する。
追加するたびに管理部を移動するには時間がかかるため、管理部の前に、適当な空きを作っておき、ここに追加する。 空きが足りなくなったときだけ、管理部全体を後ろに移動させる。
更新により、使われなくなった領域がだんだん増えてくるので、この無駄が全体の１，２割になったとき、 この空きを詰めて再構築する。
新規タイルの追加があるため、管理部上の並びは zoom, x, y の昇順は維持できない。 メモリ上の管理部は zoom, x, y の昇順に並び替え、バイナリ検索を使えるようにする。
メモリ上の並び替えはエントリ追加ごとに行う。
ファイル構造は、先頭からエントリを続け、次にエントリ管理部、最後に全体の管理部とする。
初期のエントリ管理部は zoom, x, y の昇順とする。エントリ追加がおきると昇順が維持されない。
全体の管理部はエントリ数(これにより、エントリ管理部の長さが分かり、エントリ管理部の先頭オフセットが分かる)、 最終エントリからエントリ管理部までの空き領域のサイズ（エントリ管理部の先頭オフセットからこのサイズを引いたところが空き領域の先頭オフセット） とする。
OSMバイナリレコードの場合、更新/新規による追加は起きないため、空き領域はない。
管理部はエントリ毎に id (zoom, x, y) および offset（エントリを指す）とする。 各エントリヘッダは length、lastModified（最終更新日時）とする。
offset は 4バイトでは不足する。アーカイブファイルが 数十GBを超えるようになった場合、 zoom 別に分けることにより、一つのアーカイブファイルのサイズを抑える。
36(4*8+4)ビット（＝4.5バイト）あれば十分である。
エントリの最大サイズはOSMバイナリレコードの方が大きいが、128MB未満である。
128x1024x1024＝27ｘ210ｘ210＝227であるから、28ビット（＝3.5バイト）あれば十分である。
したがって offsetとlengthを合わせて long（8バイト）で表せる。
エントリの length は管理部に必須ではないが、管理部にあると、エントリ読み込みがほんの少し楽になる。 また、管理部をスキャンすると、更新によって無効になったエリアの合計サイズを算出できる。
無効エリアの合計サイズは全体管理部に置き、エントリを更新するとき、合計サイズを更新する案もある。
ビット割り当てはプログラム的には簡単であるが、やや分かりにくいので、できれば避けたい。 また、エントリ管理部はメモリに読み込むため、このサイズを大きくすることも避けたい。
正確な無効エリアの合計サイズは必ずしも必要なわけではない。 エントリ管理部をスキャンすれば、無効エントリがいくつあるかは分かる。 「無効エントリ数÷全エントリ数」で無効エリア合計サイズは推測できるので、 これで再構築(無効エリア除去)のタイミングは決められる。
やはり、「管理部はエントリ毎に id (zoom, x, y) および offset（エントリを指す）とする。 各エントリヘッダは length、lastModified（最終更新日時）とする。」としよう。
全体管理部に無効エリアの合計サイズを置くこともしない。
ファイル構造はできるだけシンプルなものとしたい。
Updater でのアーカイブファイルの修正には当然、排他制御が必要となる。時間がかかると快適性が損なわれる。 あらかじめ、追加を考慮してエントリ部に空きエリアがあり、エントリ管理部にも予備エントリがあれば、エントリの追加には さほど時間はかからないであろう。この場合、アーカイブファイルのサイズは変わらず、空きエリアにエントリ本体を書き込み、 エントリ管理部の予備エントリにオフセット、長さ、id(zoom, x, y) を書き込むだけである。
空きエリアがたりないか、予備エントリがなくなったときが課題である。エントリ管理部全体および全体の管理部をメモリに退避して 空きエリアを拡張して、エントリ管理部の予備エリアを増やして、ファイルに書き込み、最後に、全体管理部を書き込む必要がある。 数十万、数百万エントリとなれば、エントリ管理部のサイズは、数十MBを超えるので、ファイル更新に秒単位の時間がかかる可能性がある。
予備エリア、予備エントリがいくら残っているかは全体管理部で分かるようにしておけば、地図アプリ起動時に、 チェックして、残り少ないときには、拡張する。
マルチスレッドのタイル更新スレッド(Updater)では、アーカイブファイル拡張は行わない。 更新時点で空きエリア、予備エントリが不足するときは、警告メッセージを出すだけで、エントリ(タイル画像)の追加は行わない。
タイル更新では古いタイルはそのまま残り、新しいタイルが追加される。月日がたてば無効エリアが増えてくる。 無効エントリエリアの合計サイズは全体管理部に置く案もあるが、
ReadWriteLockを使えば、書き込みは一つのスレッドであるが、読み込みは同時に複数スレッドで可能になるようである。
タイル更新は確率で決めるので、書き込みスレッドは少ないが、新規は一斉に起こるため、シリアル処理になる。 しかし、ダウンロードやレンダリング時間に比較して短いため、排他制御によるロスは小さいと思われる。
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class DataCache {
private final Map<String, String> cache = new HashMap<>();
private final ReadWriteLock lock = new ReentrantReadWriteLock();
public String getData(String key) {
lock.readLock().lock(); // 読み込みロック
try {
return cache.get(key);
} finally {
lock.readLock().unlock();
}
}
public void putData(String key, String value) {
lock.writeLock().lock(); // 書き込みロック
try {
cache.put(key, value);
} finally {
lock.writeLock().unlock();
}
}
}
国土地理院標準地図タイルは 65,481ファイルで 1.10 GB (1,188,000,998 バイト)であるから 平均値は約18KBである。
1万タイル分として 180MB（18KBx10000）の空きエリア、エントリ管理部に10000エントリ分の予備エントリ を持たせておく。
各エントリの先頭にはヘッダとして ４バイトの length(ヘッダを含む)、８バイトの lastModified（単位 mSec）を 置く。このエントリ部の後ろに空きエリアをおく。次にエントリ毎に id(8バイト)、offset(8バイト)のエントリ管理部を 置く。最後に、空きエリアの先頭オフセット(8バイト)、使用エントリ数(4バイト)、予備を含めた全エントリ数(4バイト) を置く。エントリ管理部の先頭は ファイルサイズ－16(全体管理部)－全エントリ数×16 で算出される。
更新/新規による追加は、空きエリアの先頭か length、lastmodified、エントリデータを書き込み、 全体管理部の空きエリアオフセットを更新する。
次に、エントリ管理部の有効エントリの末尾すなわち予備エントリの先頭に追加したエントリの id (zoom, x, y)、先頭オフセット を登録する。全体管理部の使用エントリ数を更新する。
エントリ管理部では更新により、同じ id を持つエントリが二つ以上になる。時刻を比較するまでもなく、 一番最後にあるものが最新で有効なタイルである。
このような重複をさけ、既にあるもののオフセットを変更するだけでもよい。メモリ上のエントリ管理部は id 順にして いるので、バイナリサーチにより、該当エントリの位置は迅速に分かる。 メモリに読み込んだエントリ管理部を使うことに抵抗感があるが、エントリ管理部に古いエントリも残っている場合、 エントリ管理部読み込み時にそれを除去する必要がある。
どうすればよいかもう少し時間をかけて検討したい。
更新のないアーカイブファイルはシンプルであるが、更新を考えると、途端に難しくなる。 じっくり考えてできるだけシンプルなものにしたい。
答えが見つかるまで、現在のように、更新/新規タイルは階層ディレクトリに置いてもよい。
いずれにしても、時折、再構築が必須であるから、再構築も含めて最良の方法を考える必要がある。
zipの場合、再構築では、一旦、zip を解凍することを考えていたが、エントリ数が膨大になると、解凍は好ましくない。
エントリ管理部に古いエントリも残っている場合、エントリ管理部の末尾から先頭に向けてスキャンして、 無効なエントリを消してから、改めて先頭から有効なタイルを抜き出して、新しいアーカイブファイルを作ることになろう。 この場合、エントリ本体の並びとエントリ管理部の並びは順序が一致しているので、 新しいアーカイブファイルを作らず、エントリ部、エントリ管理部とも無効エントリを除いて、前に詰めるだけでよい。 最後に、全データ管理部の後ろを切り捨てればよい。
エントリ管理部に古いエントリを残さず、ここに新しいオフセットを書き込んだ場合、オフセットは昇順ではなくなる。 エントリ本体の順番とエントリ管理部の順番が異なるのが少し分かりにくい。
エントリ管理部の読み込み頻度は少なく、メモリ上の処理時間は短い。
古いエントリ本体はそのまま残すのでエントリ管理部の古いエントリもそのまま残す方がいいだろう。 そうすれば、古いエントリと新エントリを並べて表示することも可能である。この方がエントリ更新時のアーカイブファイルへの 操作は簡単である。
メモリ上のエントリ管理部に対する処理はファイルに対する処理とは異なる。 更新の場合、バイナリサーチで位置を求め、そのオフセットを更新する必要がある。新規タイルの場合、 予備エントリに idとoffsetを登録して、並び替えを行う。
更新ではメモリ上の予備エントリは消費されないため、予備エントリ数はファイルよりもメモリの方が多くなる。 何ら支障はないが、すこし分かりにくいと言えよう。
アーカイブファイルの全体管理部の有効タイル数には古いタイル分も含まれる。一方、メモリ上の有効タイル数は古いタイル分は含まない。 このため、両者の差が古いタイル数である。
この数値は管理には使わない。空きエリアまたは予備エントリ数が残り少なくなったら、再構築する必要がある。 古いエントリは除去するが十分な空きエリアと予備エントリを確保するため、再構築ではファイルサイズが縮小されるとは限らず、 拡大する可能性の方が大きいであろう。