\voffset-10mm
\hoffset5mm
 
\documentstyle[a4wide,12pt,ite,polski]{article}
\pagestyle{empty}
\textwidth=16.5cm\textheight=24.5cm

%\date{14--04--95}
\date{}
\title {\bf Optymalizacja dzia`lania rozproszonej bazy danych na podstawie bada`n 
efektywno`sciowych X.500\thanks{Praca
 wykonana w ramach statutowej dzia`lalno`sci NASK}}
\author{{Maja G`orecka} \\ {\normalsize mgorecka@cc.uni.torun.pl} \and
{Tomasz Wolniewicz} \\ {\normalsize twoln@mat.uni.torun.pl}}

\begin{document}
\maketitle
\vspace{-5mm}
\centerline{\large Uniwersytet Miko`laja Kopernika w Toruniu}
\vspace{5mm}

%\vspace*{1cm}
\section{Wst`ep}
Celem niniejszego opracowania jest przedstawienie wniosk`ow z bada`n
efektywno`sciowych X.500 Directory, a dok`ladniej konkretnej implementacji
standardu --- oprogramowania QUIPU  wersja 12.0. 

Baz`a dla pracy by`l nasz wst`epny raport \cite{G-W-1}, w kt`orym
przedstawili`smy rozwa`xania teoretyczne nad czynnikami maj`acymi wp`lyw na
sprawno`s`c dzia`lania rozproszonej bazy danych, jak`a jest X.500. 
Zapoznanie si`e z 
tym raportem by`loby niew`atpliwie pomocne przy czytaniu przedstawianego
tutaj opracowania.

Obecnie chcemy podsumowa`c wyniki test`ow i skonfrontowa`c je z wcze`sniejszymi
przewidywaniami. Od razu mo`xemy nadmieni`c, `xe nie wszystkie 
testy da`ly oczekiwane wyniki. 
G`l`ebsza analiza tych rozbie`xno`sci wykaza`la, `xe niekt`ore
zaimplementowane w badanym oprogramowaniu metody
nie dzia`laj`a zgodne z ich opisem, w pewnych sytuacjach natomiast
wp`lyw niekt`orych czynnik`ow na dzia`lanie bazy jest tak silny, `xe 
uniemo`xliwia ocen`e znaczenia elementu badanego.

Nasz raport opisuje, cz`esto  do`s`c szczeg`o`lowo, mechanizmy
dzia`lania bazy X.500 w implementacji QUIPU. Wydaje si`e nam, `xe  taka 
g`l`ebsza wiedza
 mo`xe by`c bardzo przydatna administratorom serwisu X.500,
a nie spotkali`smy dotychczas opracowa`n, kt`ore przybli`xa`lyby rozwa`xane przez nas tematy
dostatecznie wyczerpuj`aco. 
\thispagestyle{empty}


Nie b`edziemy omawiali samego schematu bazy X.500. Powiemy tylko, `xe
analizujemy roz\-pro\-szo\-n`a baz`e danych opart`a na serwerach (DSA), do kt`orej
dost`ep zapewnia oprogramowanie klienta (DUA). Dok`ladny opis funkcjonowania
bazy i u`xywanej terminologii mo`xna znale`z`c mi`edzy innymi w naszych
raportach \cite{G-W-1}, \cite{G-W-2}, \cite{G-W-3}, 
a tak`xe w \cite {Rose} i \cite{X.500}, natomiast opis u`xytkowy oprogramowania
QUIPU zawarty jest w \cite {QUIPU}.

W raporcie zamieszczamy te`x wyniki pomiar`ow dzia`lania polskiej bazy X.500,
kt`ore zebrali`smy za pomoc`a specjalnie do tego celu napisanego
oprogramowania. Niekt`ore pomiary dokonywane by`ly r`ownie`x na testowo
uruchamianych instalacjach, robili`smy to w przypadkach, gdy
konieczne by`lo dok`ladne wydzielenie wp`lywu jednego badanego czynnika na zachowanie
serwera bazy.

\section{Obs`luga operacji rozproszonych}
System rozproszony (jakim jest X.500) przechowuje gromadzon`a informacj`e na
wielu serwerach (DSA). Dost`ep klienta (DUA) do bazy rozpoczyna si`e od
dowi`azania do wybranego DSA i zadania pierwszego zapytania. W zale`xno`sci od
tego, czy realizacja odpowiedzi mo`xe by`c dokonana lokalnie, czy te`x
niezb`edne jest odwo`lanie do innych serwer`ow b`edziemy mieli do czynienia z
wyst`epowaniem operacji rozproszonego dost`epu lub nie.
Do  wymiany informacji pomi`edzy DUA a DSA s`lu`xy protok`o`l DAP ({\it 
Directory Access Protocol}), serwery DSA komunikuj`a si`e w ramach
protoko`lu DSP ({\it Directory System Protocol}). 

W cz`e`sci tej opisujemy jak oprogramowanie QUIPU podejmuje decyzje o
nawi`azaniu kolejnych po`l`acze`n i jaki ma to wp`lyw na efektywno`s`c
dzia`lania ca`lej bazy.

\subsection{Wyb`or serwera}\label{dobor}

DSA obs`luguj`acy zlecenie nie daj`ace si`e zrealizowa`c lokalnie
mo`xe albo przekaza`c je kolejnemu serwerowi 
poprzez tworzenie `la`ncucha ({\it chaining}), 
albo zwr`oci`c DUA odes`lanie do innego serwera DSA ({\it referral}). 
Identyczny protok`o`l komunikacjny obowi`azuje
r`ownie`x w trakcie wymiany informacji po\-mi`e\-dzy serwerami.

Wyb`or w`la`sciwego DSA jest bardzo istotny z punktu widzenia
efektywno`sci pracy X.500. Na og`o`l istnieje kilka serwer`ow,
kt`ore prawdopodobnie s`a w stanie obs`lu`xy`c zlecenie.
QUIPU DSA w tej sytuacji dokonuje uporz`adkowania listy
serwer`ow wed`lug jako`sci operacyjnej i nast`epnie 
przekazuje `x`adanie do DSA uznanego  jako najlepsze, 
w przypadku niepowodzenia, wybiera kolejny serwer z listy itd.

Spos`ob post`epowania przy ocenie serwer`ow jest okre`slony 
w implementacji QUIPU 
w ramach algorytmu, kt`ory  bazuje na informacjach
o parametrach w`lasnych DSA oraz za\-pa\-mi`e\-ta\-nych  danych, dotycz`acych
aktywno`sci serwer`ow. Dodatkowo umo`xliwia si`e administracyjny
wp`lyw na wyb`or serwera docelowego poprzez podanie w zbiorze
konfiguracyjnym QUIPU warto`sci tzw. {\tt preferDSA}.

Algorytm ustala nast`epuj`ace uporz`adkowanie element`ow decyduj`acych
o wyborze DSA:

\begin {enumerate}
\item Istnienie nawi`azanego po`l`aczenia z odpowiednim serwerem.

\item Docelowe DSA jest QUIPU DSA, czyli  w {\tt objectClass}
znaleziono warto`s`c {\tt quipuDSA}.
Dodatkowo sprawdzany jest atrybut specyfikuj`acy
akceptowane typy protoko`l`ow, zwane kontekstem aplikacji 
({\tt SupportedApplicationContext}),
tzn.\ te wszystkie elementy warstwy aplikacji (ASE --- Application
Service Element), kt`ore serwer implementuje.
Pierwsze`nstwo otrzymuje DSA z kontekstem QUIPU, nast`epnie DSA
wed`lug protoko`lu Internet, wszystkie pozosta`le traktowane s`a
jednakowo, z wyj`atkiem serwera DSA, kt`ory 
podtrzymuje wy`l`acznie protok`o`l DAP.

\item Docelowe DSA zosta`lo uznane jako bardziej niezawodne. Ocena
ta bazuje na `sledzeniu informacji o czasie ostatniej pr`oby dost`epu
do DSA oraz jej efekcie, tzn.\ czy po`l`aczenie zako`nczy`lo
si`e sukcesem oraz czy wyst`api`ly b`l`edy.
W ten spos`ob preferowany jest np.\ ten serwer, kt`ory nie by`l
ostatnio aktywny w sytuacji, gdy konkurencyjny mia`l nawi`azane
po\-`l`a\-cze\-nie, ale w trakcie dost`epu zawi`od`l. Z kolei w przypadku,
gdy dwa serwery by`ly aktywne, zwyci`e`xa ten, kt`ory nie zawi`od`l,
a je`xeli oba  mia`ly b`l`edy --- serwer, dla kt`orego nie min`a`l
czas mi`edzy kolejnymi pr`obami nawi`azania po`l`aczenia ({\it retrytime}).
Wiele przypadk`ow traktowanych jest jako nierozstrzygalnych, m.in.\
gdy oba serwery nie by`ly aktywne, gdy oba by`ly, jeden zawi`od`l,
ale dla obu up`lyn`a`l czas {\it retrytime}, gdy jeden by`l aktywny, ale
zawi`od`l i up`lyn`a`l czas ponowienia pr`oby po`l`aczenia.

\item DSA dost`epne jest we w`la`sciwej kategorii protoko`lu sieciowego
({\it community}), a w przypadku, gdy dwa DSA znajduj`a si`e w tej samej
kategorii, wybierany jest serwer uznany za lokalny na bazie analizy
wyr`o`xnionej nazwy DSA ({\it Distinguished Name}).\label{community}

\item DSA jest uprzywilejowany na podstawie listy {\tt preferDSA}.
\end {enumerate}

Jak wida`c algorytm wyboru DSA nie jest rozbudowany. 
W minimalnym stopniu wykorzystuje `"histori`e" po`lacze`n, ogranicza
si`e wy`l`acznie do sprawdzania, czy DSA by`l aktywny i czy wyst`api`ly
b`l`edy w trakcie pracy. Nie jest zapami`etywany czas 
niezb`edny do nawi`azania `l`aczno`sci, czy `sredni czas po`l`aczenia. 
Oczywi`scie mo`xe to prowadzi`c
do cz`estego korzystania z serwer`ow, kt`ore spe`lniaj`a warunki
kwalifikacyjne, natomiast kontakt z nimi jest czasoch`lonny.

%Analiza oprogramowania IC R2.0v3, na bazie kt`orego przeprowadzamy
%prace testowe wykazuje, `xe 
%realizacja pewnych funkcji w ramach algorytmu abstrahuje od umiejscowienia
%lokalnego serwera X.500. Np. w fazie opisanej w punkcie \ref{community}
%nast`epuje por`ownanie adres`ow prezentacyjnych dw`och
%DSA i na ich podstawie dokonuje si`e przyporz`adkowania serwer`ow
%do okre`slonej kategorii sieci. Dopuszczalne pi`e`c kategorii {\it community} 
%jest umieszczonych na li`scie w kolejno`sci:
%realNS, nt-X25, Internet, Janet, localTCP, IXI.

%Poniewa`x przypisuje si`e wy`xszy priorytet pierwszemu DSA, kt`orego numer 
%{\it community} zgodzi si`e z kolejno pobieranymi z listy dopuszczalnych
%warto`sci, w ten spos`ob DSA znajduj`ace si`e w tej samej sieci
%i po`lo`xone bli`xej mo`xe zosta`c  uznane za `"gorsze" w sytuacji,
%gdy konkurencyjne DSA ma w swoim adresie sk`ladow`a wskazuj`ac`a na
%kategori`e sieciow`a umiejscowion`a na wy`xszej pozycji.

%???????????????????????????????
%Bardziej sensowne wydaje si`e wykorzystanie adresu prezentacyjnego
%lokalnego DSA do uporz`adkowania listy kategorii
%sieciowych, traktuj`ac uszeregowanie sk`ladowych adresu jako wzorzec do 
%przypisania priorytet`ow poszczeg`olnych sieci.
%Planujemy przetestowanie oprogramowania serwera pracuj`acego w oparciu
%o tak zmodyfikowany algorytm. 


%W`atpliwo`sci budzi r`ownie`x okre`slona kolejno`s`c czynnik`ow decyduj`acych
W`atpliwo`sci budzi okre`slona kolejno`s`c czynnik`ow decyduj`acych
o doborze DSA. Ma`l`a rol`e 
odgrywa administracyjne ustalenie listy uprzywilejowanych serwer`ow;
jedynie w przypadku nie\-mo`x\-li\-wo\-`sci rozstrzygni`ecia na podstawie 
niezawodno`sci i lokalizacji DSA wybierany jest serwer wskazany
przez administratora. W przypadku zapyta`n pochodz`acych  np.\ z 
polskich serwer`ow regionalnych zapewnienie wysokiego
priorytetu wyborowi DSA wed`lug listy wskazanej przez {\tt preferDSA},
na kt`orej znajdowa`lby si`e serwer krajowy,
mia`loby zdecydowanie korzystny wp`lyw na obs`lug`e zapyta`n dotycz`acych
danych replikowanych przez DSA Polski.
Typowym rozwi`azaniem maj`acym na celu  usprawnienie dzia`lania bazy jest
replikowanie fragment`ow drzewa geograficznie odleg`lych. Na przyk`lad lista
instytucji polskich jest replikowana przez krajowy serwer australijski. Fakt
ten oznacza jednak, `xe serwer australijski mo`xe by`c wybierany jako `zr`od`lo
informacji o Polsce przez inne serwery europejskie (a nawet polskie (!)).

QUIPU daje najwy`xszy priorytet DSA, do kt`orego jest ju`x aktualnie nawi`azane
po\-`l`a\-cze\-nie. Intencja autor`ow oprogramowania
jest `latwo zrozumia`la, gdy u`swiadomimy sobie,
`xe na\-wi`a\-za\-nie nowego kontaktu jest zawsze kosztowne czasowo (potwierdzaj`a to wyra`znie wyniki wykonanych przez nas test`ow).
Rozumiej`ac
to zauwa`xamy jednocze`snie negatywny wp`lyw takiego rozwi`azania.
Mo`xe si`e zda`xy`c, `xe nawi`azane po`laczenie z odleg`lym
serwerem w celu uzyskania od niego
informacji dla niego lokalnej przes`adzi o pobieraniu z tego miejsca
danych, kt`ore, gdyby nie otwarte po`l`aczenie, mog`lyby zosta`c
udost`epnione z bli`xszego, a nawet lokalnego serwera.



\subsection {Obs`luga zlecania --- tworzenie `la`ncucha lub przekazywanie
ode\-s`la\-nia do serwera}

QUIPU DSA realizuj`ac zlecenie musi podj`a`c decyzj`e, w jaki spos`ob
ma ono zosta`c obs`lu`xone. Je`xeli polecenie otrzymane od DUA lub
innego DSA  nie mo`xe
by`c rozstrzygni`ete lokalnie jest ono albo przekazywane innemu serwerowi
poprzez formowanie `la`ncucha zlece`n ({\it  chaining}), albo DSA zwraca
DUA ode\-s\-`la\-nie do innego serwera ({\it referral}) i DUA samodzielnie
kontynuuje zapytania.

Wyb`or metody mo`xe mie`c istotny wp`lyw na efektywno`s`c pracy X.500.
Decyzja {\it  chaining} lub {\it referral} jest podejmowana 
po ustaleniu listy mo`xliwych serwer`ow oraz uporz`adkowaniu jej zgodnie
z algorytmem opisanym w rozdziale \ref{dobor} i odbywa si`e w 
nast`epuj`acych krokach:

\begin {itemize}
\item W przypadku, gdy zg`laszaj`aca si`e do DSA aplikacja 
legitymuje si`e jako proces u`xy\-wa\-j`a\-cy protoko`lu DAP 
--- s`lu`x`acy do wymiany informacji po\-mi`e\-dzy DUA i
DSA) zak`lada si`e, `xe stosowana b`edzie obs`luga poprzez tworzenie
`la`n\-cu\-cha zlece`n, druga forma --- zwrot ode\-s`la\-nia
pozostaje r`ownie`x w mocy. 
Uporz`adkowanie listy serwer`ow nie ulega zmianie.
Na bazie tej listy tworzone s`a odpowiednie parametry dla operacji,
 tzw.\ {\it continuation references}, czyli wskazania
dok`ad kierowa`c zlecenie po wyst`apieniu b`led`ow.
Nast`epnie sprawdzane s`a argumenty zwi`azane z obs`lug`a operacji
({\it service control}). Je`xeli proces zg`losi`l si`e z zaleceniem,
by nie przekazywa`c zadania do wykonania innym serwerom
({\it chainingprohibited}), lub by ograniczy`c 
przeszukiwania do bazy lokalnej ({\it localscope}), zostaje wybrana
metoda zwrotu ode\-s`la\-nia do DUA, w przeciwnym razie stosowana
jest metoda tworzenia `la`ncuch`ow zlece`n.

\item Je`xeli do DSA zwraca si`e proces o protokole DSP,
w`owczas nast`epuje wyb`or serwera DSA priorytetowego
przy wskazywaniu ode\-s`la\-nia. Odbywa si`e to przez 
okre`slenie czy proces wysy`laj`acy zlecenie i docelowy serwer
nale`x`a do tej samej kategorii sieciowej --- {\it community}.
Oczy\-wi\-`s\-cie jest to mo`xliwe jedynie w sytuacji, gdy lokalnie
mo`xna zdoby`c informacj`e, jaki adres prezentacyjny posiada 
zlecaj`acy. Pierwszy serwer z listy dopuszczalnych DSA o
{\it community} zgodnej  z aplikacj`a zlecaj`ac`a jest 
wybierany jako najlepszy. Je`xeli `xaden serwer nie znajduje
si`e w tej samej sieci, blokowana jest mo`xliwo`s`c zwracania
ode\-s`la\-nia.
W przypadku, gdy DSA nie jest w stanie ustali`c adresu zg`laszaj`acego,
pierwszy serwer z listy delegowany jest jako adres ewentualnego
ode\-s`la\-nia.

Po ustaleniu listy DSA  sprawdzana jest mo`xliwo`s`c wykonywania operacji
{\it chaining} w ramach obs`lugi zlecenia wed`lug protoko`lu
DSP. 
Je`xeli wyst`api`l jeden z nast`epuj`acych przypadk`ow:
\begin {itemize}
\item {\it chaining} zosta`l zakazany administracyjnie 
przez ustawienie parametru
konfiguracyjnego {\tt dspchaining} jako {\tt off} lub {\tt WhenNeeded},
\item proces zg`laszaj`acy wymusza obs`lug`e bez `la`ncuchowania
({\it chainingprohibited} lub {\it localscope})
\end {itemize}

DSA b`edzie obs`lugiwa`lo zlecenia przez zwrot odes`lania, chyba `xe
wcze`sniej  zablokowano stosowanie tej metody --- w tym przypadku 
operacja zako`nczy si`e niepomy`slnie z powodu zakazu tworzenia 
`la`ncucha do innych DSA i niemo`xliwo`sci wys`lania wskazania innego serwera.

W pozosta`lych sytuacjach stosowane jest przekazywanie niezrealizowanych
`x`ada`n do kolejnych DSA.

\end{itemize}

Jak wynika z opisu, decyzja o metodzie obs`lugi zlecenia zale`xy
od takich czynnik`ow jak:  
\begin {itemize}
\item `srodowisko pracy serwera i mo`xliwo`s`c wsp`o`lpracy z innymi DSA,
\item parametry konfiguracyjne serwera,
\item  otrzymane razem ze zleceniem argumenty operacji. 
\end{itemize}

Dla zapyta`n od DUA typowo stosowana jest metoda budowania `la`ncucha, 
jednak interfejs u`xytkowy mo`xe wymusi`c obs`lug`e poprzez wskazania
za pomoc`a odpowiednich argument`ow.


Je`xeli DSA po`sredniczy w realizacji zlecenia, {\it chaining}
dokonywany jest do kolejnych DSA z listy, st`ad wi`eksze prawdopodobie`nstwo
sukcesu. Dodatkowo DSA jest w posiadaniu informacji statystycznej, na
podstawie kt`orej b`edzie w stanie podejmowa`c kolejne akcje w imieniu DUA,
samo DUA skazane jest na `scis`le pod`a`xanie za podawanymi mu odes`laniami.
Wida`c z tego, `xe tworzenia `la`ncucha ma szereg zalet. Niew`atpliwie jest to
najw`la`sciwsz`a metod`a dla obs`lugi po`l`aczenia realizowanego w protokole DAP
(inicjowanego przez DUA), a operacje wed`lug protoko`lu DSP (pomi`edzy DSA) powinny mie`c 
zablokowanie `la`ncuchowanie zg`losze`n.
Aby to uzasadni`c przyjmijmy najbardziej typow`a sytuacj`e, w
kt`orej DUA `l`aczy si`e z bliskim sobie (w sensie geograficznym) DSA. DSA to
posiada lokaln`a wiedz`e o mo`xliwo`sci nawi`azywania sprawnych po`l`acze`n z
innymi DSA, kt`ore poprzednio wykorzystywa`lo, mo`xe te`x preferowa`c pewne DSA
zgodnie z ustawieniami administracyjnymi. Pytania zadawane przez DUA
obs`lugiwane s`a zatem zawsze w optymalny dla tego DUA spos`ob. Przekazanie
DUA odes`lania spowoduje, `xe nast`api dowi`azanie do obcego (by`c mo`xe odleg`lego)
DSA, kt`ory b`edzie stosowa`l swoje mechanizmy doboru najw`la`sciwszych DSA, sam
b`edzie podejmowa`l decyzje o tym, czy tworzy`c `la`ncuchy czy nie i w efekcie
mo`xe doprowadzi`c do tego, ze DUA b`edzie korzysta`lo z niego do ko`nca
nawi`azanej sesji. Utworzenie `la`ncucha zawieraj`acego wi`ecej ni`x jedno DSA
powoduje, `xe kolejne DSA nie maj`a w`la`sciwej informacji o tym sk`ad pochodzi
zapytanie i mog`a przekazywa`c nieoptymalne adresy kolejnych DSA. Towarzyszy
temu oczywi`scie niepotrzebny transfer danych przez kilka serwer`ow.

Oczywi`scie tworzenie `la`ncuch`ow protoko`lu DSP daje wi`eksze
prawdopodobie`nstwo powodzenia operacji, ale r`ownocze`snie obni`xa sprawno`s`c
ca`lej bazy i dlatego, naszym zdaniem, nie powinno mie`c miejsca.
 Z tego powodu wydaje si`e korzystne
wymuszanie administracynego zakazu tworzenia `la`ncuch`ow dla protoko`lu DSP.
W sytuacji pod`laczenia DSA tylko do jednego {\em community}, ca`lkowicie zb`edna
jest funkcja `la`ncuchowania protoko`lu DSP, funkcja ta ma sens, gdy serwer
jest pod`l`aczony do kilku {\em communities} i mo`xe dzia`la`c jako most ({\em
relay DSA}). W takiej sytuacji w`l`aczenie lub wy`l`aczenie opcji zezwalaj`acej
na `la`ncuch`owanie mo`xe by`c podyktowane np.\ argumentami finansowymi
(routowanie obcego ruchu). 

Wydaje si`e nam, `xe najw`la`sciwsze w sytuacji polskiego X.500 by`loby
zmodyfikowanie algorytmu generowania odes`la`n, tak aby polskie DSA
zwraca`ly si`e do polskiego serwera krajowego, zawsze wtedy gdy serwer ten posiada
poszukiwan`a przez nie informacj`e, z kolei serwer krajowy powinien blokowa`c
`la`ncuchowanie protoko`lu DSP, tak aby promowa`c obs`lugiwanie lokalnych DUA,
przez ich lokalne DSA.



\section{Wp`lyw wielko`sci bazy na prac`e serwera}

Serwer DSA w implementacji QUIPU w swojej podstawowej konfiguracji
`laduje do pami`eci operacyjnej ca`l`a lokaln`a baz`e danych, `l`acznie
z wszystkimi replikacjami. Przy du`xej ilo`sci hase`l prowadzi to
do tworzenia bardzo pami`ecioch`lonnego procesu.

Rozmiar bazy danych w pami`eci zale`xy od ilo`sci i wielko`sci
hase`l. `Srednio okre`sla si`e, `xe jedno has`lo potrzebuje oko`lo
2KB pami`eci.

Przeprowadzone testy wykaza`ly m.in., `xe:
\begin {itemize}
\item Baza o ilo`sci hase`l 3500, wi`ekszo`s`c hase`l rozbudowana ---
wymaga ok.\ 6.5MB pami`eci operacyjnej (na dysku zajmuje ok.\ 14MB), 
czyli `srednio na jedno has`lo przypada 1.8MB. 
\item Baza o ilo`sci hase`l ok.\ 30000, has`la o ma`lej ilo`sci
atrybut`ow ---
wymaga ok.\ 33MB pami`eci operacyjnej (na dysku --- 27MB), 
czyli `srednio jedno has`lo zajmuje 1.1MB.
\item Baza o 20000 ma`lych hase`l zajmuje 24MB pami`eci operacyjnej
(ok.\ 1.2MB na has`lo),
po rozbudowanu hase`l --- 34MB (ok.\ 1.7MB na has`lo).
\end {itemize}

Pami`e`c zajmowana przez serwer, to suma wielko`sci samego procesu
DSA i rozmiaru bazy danych powi`ekszana przez bie`x`ac`a alokacj`e
dla potrzeb buforowania, czy wykonywania operacji replikacji danych.
Zarz`adzanie pami`eci`a nie jest mocn`a stron`a oprogramowania QUIPU.
Wszystkie wersje, na bazie kt`orych pracujemy ju`x od 3 lat m.in.\
nie wykonuj`a prawid`lowo zwalniania pami`eci, co powoduje, `xe
rozmiar d`lugo pracuj`acego serwera znacznie wzrasta.

Je`xeli proces serwera nie mie`sci si`e w ca`lo`sci w wolnej
pami`eci komputera stosowana jest metoda tworzenia pami`eci wirtualnej poprzez 
przenoszenie cz`e`sci
procesu na dysk (stronicowanie pami`eci).
 W tej sytuacji istotnie obni`xa si`e efektywno`s`c
pracy serwera, gdy`x wi`ekszo`s`c operacji wi`a`xe si`e z konieczno`sci`a
kontaktu z dyskiem w celu pobrania w`la`sciwego fragmentu procesu.

Z powy`xszych ustale`n wynika, `xe
serwery QUIPU obs`luguj`ace du`xe bazy lokalne, dla zapewnienia sprawno`sci 
dzia`lania wymagaj`a odpowiedniej wielko`sci pami`eci operacyjnej,
tak by ca`ly proces m`og`l rezydowa`c w pami`eci.
W przeciwnym razie doprowadza si`e do bardzo du`xych op`o`znie`n czasowych
w realizacji zapyta`n. Testy wykaza`ly, `xe operacja
przeszukiwania lokalnej bazy zawieraj`acej  20000 hase`l, obs`lugiwana przez 
serwer o pami`eci operacyjnej 64MB jest wykonywana w przeci`agu 1-2 sekundy,
podczas gdy w przypadku uruchomienia tego serwera na tym samym komputerze, ale
przy rozmiarze pami`eci 32MB oczekiwanie na rezultat trwa ok.\ 1.5 minuty.

\vskip 3mm
W pakiecie oprogramowania Isode Consortium pocz`awszy od wersji IC R2.0 
istnieje mo`xliwo`s`c przechowywania cz`e`sci bazy X.500 na dysku w trakcie
pracy serwera. Wydzielony fragment drzewa informacji DIT jest 
zarz`adzany przez specjalny proces zwany {\it delegate DSA}. 
Baza dyskowa posiada szereg dodatkowych zbior`ow indeksowych, pomocnych
przy operacjach przeszukiwania i listowania.

Stosowanie bazy dyskowej jest zalecane przy przechowywaniu du`xych
poddrzew, autorzy oprogramowania zapewniaj`a sprawne dzia`lanie
przy ilo`sci hase`l do jednego miliona. Korzystanie z dysku zacznie 
skraca czas `ladowania procesu i istotnie ogranicza wymagania
odno`snie pami`eci operacyjnej.
Usprawnienie to odbywa si`e jednak kosztem zwi`ekszenia zapotrzebowania
na pami`e`c dyskow`a.  
Bardzo czasoch`lonny jest te`x proces budowania baz indeksowych.


Testowanie wersji serwera z obs`lug`a dyskow`a
dla bazy gromadz`acej w `"delegowanym" poddrzewie ok.\ 3500 hase`l
wykaza`lo blisko dwukrotne powi`ekszenie zu`xycia obszaru dyskowego,
zapotrzebowanie na pami`e`c spad`lo o ok.\ 3MB, przy czym w trakcie
pracy rozmiar serwera w pami`eci r`os`l stosunkowo szybko (buforowanie
wynik`ow).
Sprawno`s`c reakcji przy realizacji zlece`n dotycz`acych
lokalnych  zasob`ow w spos`ob zauwa`xalny maleje, w por`ownaniu
z sytuacj`a, gdy ca`la baza rezyduje w pami`eci (op`o`znienie rz`edu
3-5 sekund). 

W przypadku, gdy serwer ma obs`lugiwa`c rozbudowane poddrzewo danych
i wiadomo, `xe proces serwera nie b`edzie dysponowa`l wystarczaj`ac`a
pami`eci`a operacyjn`a,
podej`scie dyskowe powinno znacznie podnie`s`c efektywno`s`c.




\section {Indeksowanie a wielko`s`c bazy i sprawno`s`c 
jej dzia\-`la\-nia}

Oprogramowanie QUIPU dopuszcza indeksowanie bazy X.500 wed`lug zadanych
atrybut`ow \\
{\tt optimized\_attr} w ramach wskazanych obszar`ow drzewa danych
(poddrzewo --- {\it subtree} lub jeden poziom --- {\it siblings}).
Tworzenie indeksu odbywa si`e w pami`eci operacyjnej, podczas `ladowania 
bazy danych serwera. Indeks zawiera dla ka`xdego optymalizowanego 
atrybutu wskazania miejsc rezydowania w pami`eci hase`l  maj`acych
przypisane tym atrybutom warto`sci.

W celu przyspieszenia realizacji zapyta`n QUIPU u`xywa do
zapami`etywania hase`l w pa\-mi`e\-ci
struktur wywa`xonego drzewa binarnego, zwany\ AVL\footnote 
{ Adelson-Velskii i Landis zdefiniowali t`e struktur`e jako takie
drzewo, w kt`orym dla ka`xdego w`ez`la wysoko`sci dw`och jego poddrzew 
r`o`xni`a si`e co najwy`xej o 1.}.
 Obs`luga takiej
struktury jest optymalna --- przy {\it N} has`lach `srednio potrzeba nie wi`ecej
ni`x {\it logN} operacji, by odnale`z`c has`lo szukane. Odpowiednie 
algorytmy dokonuj`a wyr`ownania drzewa po dodaniu lub usuni`eciu w`ez`l`ow.
R`ownie`x indeksy budowane s`a na bazie struktur AVL.

Wprowadzenie indeksowania w bazie prowadzi do dodatkowego
zapotrzebowania na pa\-mi`e`c operacyjn`a. Nie jest to wprawdzie
drastyczny wzrost (np.\ dla indeksacji wed`lug dw`och atrybut`ow,
wzgl`edem jednego poddrzewa przy ilo`sci hase`l 3500 zaobserwowano przyrost 
ok.\ 500KB, przy zwi`ekszeniu ilo`sci atrybut`ow do 6 --- ok.\ 1.8MB),
jednak w niekt`orych sytuacjach mo`xna indeksuj`ac przekroczy`c
barier`e dost`epnej pami`eci i w efekcie spowodowa`c znaczne pogorszenie
efektywno`sci.

Wykonane testy wykaza`ly, `xe wprowadzenie indeksu nie wp`lywa zauwa`xalnie
na przyspieszenie operacji na bazie lokalnej. Krytycznym elementem
pozostaje pami`e`c, jak`a dysponuje serwer. Je`xeli proces serwera nie musi
korzysta`c z technik stronicowania i {\it swapowania}, jego reakcja,
jest zadawalaj`aca, nawet przy przegl`adaniu du`xego poddrzewa i
stosowaniu rozbudowanych filtr`ow przeszukania. Niewystarczaj`aca pami`e`c
wprowadza  d`lugi czas odpowiedzi, a dodanie metody indeksacji nie wnosi
istotnych zmian.

Przeprowadzone pr`oby z nowym mechanizmem bazy opartej na dysku pokazuj`a,
`xe stosowanie jego  wydaje si`e bardzo ogranicza`c mo`xliwo`sci
przeszuka`n ca`lych ga`l`ezi bazy. Serwer nie zezwala na dokonywanie przeszuka`n
ze wzgl`edu na atrybuty nieindeksowane. Mechamizm dzia`lania serwera z t`a
dodatkow`a opcj`a nie jest dostatecznie dobrze opisany w dokumentacji i
prawid`lowe zrozumienie algorytm`ow mo`xliwe b`edzie dopiero po analizie kodu
`zr`od`lowego.



\section {Wp`lyw na efektywno`s`c poprzez stosowanie techniki buforowania
resultat`ow operacji}

QUIPU DSA pozwala utrzymywa`c w `"podr`ecznej pami`eci" typu {\it cache}
otrzymane dane z innych serwer`ow DSA. Technika {\it `"cachowania"} jest
stosowana zar`owno po stronie DSA jak i DUA. 
W trakcie pracy serwera w pami`eci {\it cache} gromadzone s`a 
przeczytane has`la, tj.\ nazwa (DN --- {\it Distinguished Name})
oraz warto`sci tych atrybut`ow, kt`ore zosta`ly przekazane pytaj`acemu.
DSA implementuje,
niezb`edne dla wiarygodnej pracy serwera, algorytmy przedawniania
danych w pami`eci podr`ecznej oraz decydowania, czy informacja ta
mo`xe zadowoli`c odbiorc`e. W tym celu wprowadzane s`a odpowiednie
interwa`ly czasowe, w ramach kt`orych zak`ladana jest poprawno`s`c
danych z pami`eci typu {\it cache}. 
Dodatkowo zlecaj`acy razem z typem wykonywanej operacji mo`xe 
ustali`c warunki obs`lugi ({\it service control}) i m.in.\
za`x`ada`c nie u`xywania kopii przy przekazywaniu wynik`ow.

Stosowanie techniki buforowania znacznie przyspiesza wszelkie
operacje zwi`azane z ponownym odczytem informacji z bazy X.500.
Z punktu widzenia serwera wprowadza jednak dodatkowe zapotrzebowanie
na pami`e`c operacyjn`a i wymaga poprawnych algorytm`ow przedawniania
informacji oraz prawid`lowego administracyjnego ustalenia interwa`l`ow
czasowych dotycz`acych czasu `xycia danych.

Nale`xy podkre`sli`c, `xe niezb`edne jest r`ownie`x korzystanie
z dobrze przygotowanych interfejs`ow u`xytkowych --- DUA.
DSA implementuje utrzymywanie kopii rezultatu operacji listowania tylko 
dla polece`n wed`lug protoko`lu DSP (czyli pomi`edzy serwerami), poza tym 
w pami`eci podr`ecznej umieszczane s`a odczytane has`la.
Uzyskane wyniki listingu powinny wi`ec by`c {\it cachowane} 
w ramach DUA. Dzi`eki temu
mo`xna np.\  dodatkowo, przed zapami`etaniem w pami`eci podr`ecznej 
przeprowadzi`c uporz`adkowanie. DUA dzia`laj`ace w oparciu o prawid`lowo
zrealizowan`a technik`e korzystania z pami`eci {\it cache} mog`a
znacznie podnie`s`c efektywno`s`c pracy serwisu postrzegan`a przez
u`xytkownik`ow. Jednocze`snie, w przypadku interfejs`ow DUA, b`ed`acych
procesami kr`otkotrwa`lymi, niebezpiecze`nstwo przekazywania odbiorcy
nieaktualnej informacji, wnoszone przez buforowanie danych
jest niewielkie.

Nasze dotychczasowe do`swiadczenia zwi`azane z realizacj`a program`ow
u`xytkowych opie\-ra\-j`a si`e na pracach nad modyfikacjami w celu
dostosowania do korzystania z zapami`etanych w bazie X.500 poprawnych 
polskich danych. Przy obs`ludze zlecenia odczytu uzyskiwana jest
wyr`o`xniona nazwa konkretnego obiektu  w przeszukiwanym drzewie. Nazwa
ta sk`lada si`e z szeregu relatywnych nazw wyr`o`xnionych, kt`ore
pozbawione s`a polskich znak`ow narodowych. Aby uzyska`c pe`ln`a, poprawn`a
polsk`a nazw`e nale`xy odczyta`c odpowiednie atrybuty  ka`xdego obiektu
wyst`epuj`acego w ga`l`ezi prowadz`acej do otrzymanego wyniku.
Oczywi`scie, tego typu dzia`lania mog`a powodowa`c istotne op`o`znienia
w odbiorze rezultatu. Technika buforowania polskich nazw wyr`o`xnionych  
mo`xe w opisanym przypadku istotnie poprawi`c efektywno`s`c.

W ramach opisywanych prac dokonali`smy modyfikacji atrakcyjnego
 interfejsu POD poprzez wprowadzenie funkcji buforowania wynik`ow
 i popraw`e algorytmu  sortowania list. Zmiana sposobu sortowania
przyspieszy`la dzia`lanie tego interfejsu o ok.\ 100 razy. Zwracamy na to
uwag`e, aby podkre`sli`c jak zupe`lnie prosty b`l`ad w realizacji ko`ncowego
interfejsu mo`xe os`labi`c dzia`lanie ca`lego systemu.



\section{Wyniki pomiar`ow sprawno`sci polskiej bazy X.500}

W ramach badania efektywno`sci bazy X.500 przeprowadzilismy szereg pomiar`ow
funkcjonowania polskiej bazy. W tym celu napisane zosta`lo oprogramowanie
monitoruj`ace baz`e o nast`epuj`acych funkcjach:

\begin{enumerate}
\item sprawdzenie `srednigo czasu dost`epu do komputera, na kt`orym dzia`la
DSA (za pomoc`a internetowego {\tt ping}),
\item dowi`azanie do DSA (bind),
\item dokonanie kilku wyszuka`n lokalnych dla serwera, z kt`orym si`e
po`l`aczyli`smy,
\item dokonanie kilku wyszuka`n nielokalnych,
\item wy`swietlenie warto`sci odszukanych hase`l lokalnych,
\item wy`swietlenie warto`sci wyszukanych hase`l nielokalnych.
%\item kompleksowa opreacja bind+search+show.
\end{enumerate}

Oprogramowanie monitoruj`ace oparte jest na wersji DUA o nazwie {\tt dish},
kt`ore pozwala na wydawanie dowolnych komend DUA bezpo`srednio z linii komend
systemu operacyjnego. Interfejs ten jest bardzo wygodny do oprogramowania,
obarczony jednak pewnym op`o`znieniem uruchomienia ka`xdej komendy (oceniamy
j`a na ok.~0.5s). Pomiary czas`ow prowadzone by`ly z dok`ladno`sci`a ok.\ 0.1~s.
Trzeba podkre`sli`c, `xe toru`nski serwer centralny ma jeszcze obecnie
po`laczenie satelitarne z Warszaw`a, co wprowadza op`o`znienia sieciowe.
Sytuacja ta jest w zasadzie sprzyjaj`aca pomiarom efektywno`sci, gdy`x pozwala
`latwiej mierzy`c wp`lyw op`o`znie`n sieciowych na zachowanie si`e bazy.


Pomiar by`l dokonywany wed`lug nast`epuj`acego algorytmu:
\begin{enumerate}
\item dowi`azanie do mierzonego serwera,
\item wydanie komendy przeszukania (typowo dwa do trzech przeszuka`n
zwracaj`acych niekiedy pojedyncze, a niekiedy wielokrotne trafienia),
czasy przeszuka`n by`ly dodawane, a nast`epnie u`sredniane,
\item wydanie komendy wypisania wybranych atrybut`ow znalezionych hase`l
poprzez wielokrotne wydanie rozkazu {\tt showentry} odpowiadaj`acemu
protoko`lowemu {\tt read}, czasy by`ly dodawane, a nast`epnie u`sredniane;
poniewa`x wynik`ow operacji przeszukania by`lo z regu`ly wi`ecej ni`x samych
operacji przeszukania, dla operacji czytania mieli`smy wi`eksz`a pr`obk`e
statystyczn`a,
\item wydanie komendy przeszukania w zakresie organizacji ob`lugiwanej przez
inny serwer (dla wszystkich przypadk`ow by`ly to te same dwa has`la znajduj`ace
si`e na serwerze warszawskim),
\item wydanie komendy wypisania atrybut`ow tych hase`l.
\end{enumerate}
Operacja ta wykonywana jest 7 razy. Z ka`xdego ci`agu wynik`ow odrzucany jest
wynik najlepszy i najgorszy, pozosta`le s`a u`sredniane. Dodatkowo odnotowywane
s`a r`ownie`x wyniki skrajne, jak te`x czas pierwszego dowi`azania do serwera.

Dowi`azanie do serwera prowadzone by`lo zar`owno w trybie anonimowym jak i ze
sprawdzeniem to`xsmo`sci. Ta druga sytuacja zmusza serwery do dokonania
po`swiadczania ({\it authentication}), 
a zatem przes`lania dodatkowej informacji (co oczywi`scie musi
op`o`zni`c operacj`e dowi`azania).
 

Poza mo`xliwo`scia przeprowadzenia pojedynczego cyklu pr`ob, napisane przez
nas oprogramowanie (po ewentualnym rozbudowaniu) b`edzie s`lu`xy`lo jako system
ci`ag`lego monitorowania polskiego projektu X.500.


Wyniki przeprowadzonych pomiar`ow wykazuj`a generalnie dobre zachowanie si`e
bazy. Spodziewali`smy si`e uzyskania odpowiedzi na nast`epuj`ace pytania:
\begin{enumerate}
\item Jaki jest czas startu bazy (czy pierwsze dowiazanie jest wolniejsze od
nast`epnych)?

\item Jaka jest r`o`xnica pomi`edzy wykonaniem dowi`azania anonimowego i
autoryzowanego?

\item Jaka jest r`oznica pomi`edzy otrzymaniem wyniku przeszukania
instytucji, kt`orej dane s`a dost`epne lokalnie od tych, kt`orych pozyskanie
wymaga nawi`azania dodatkowego po`l`aczenia?

\item Jakie sk`ladowe typowego zapytania maj`a szczeg`olny wp`lyw na czas
trwania operacji? 

\item Czy rozpraszanie bazy na wiele serwer`ow jest korzystne i w jakich
warunkach?
\end{enumerate}

\newpage
W wyniku test`ow otrzymali`smy:
\begin{itemize}
\item[ad.\ 1] W przypadku polskiego systemu serwer`ow regionalnych czas
pierwszego dowi`azania nie jest zauwa`xalnie d`lu`xszy od nast`epnych. Z
do`swiadcze`n lokalnych wiemy, `xe serwer bardzo rzadko eksploatowany ma
d`lu`xszy czas rozruchu (konieczno`s`c za`ladowania do pami`eci operacyjnej
znacznej ilo`sci danych z dysku). Serwery regionalme s`a jednak eksploatowane
stosunkowo intensywnie.

\item[ad.\ 2] Op`o`znienie powodowane po`swiadczaniem jest sum`a operacji
dowi`azania do DSA prze\-cho\-wu\-j`a\-ce\-go dane dowi`azuj`acego si`e, 
przes`lania podanego has`la i wykonanie po\-r`ow\-na\-nia z przechowywanym w
bazie, przes`lania wyniku operacji. Na wszystko to nak`ladaj`a si`e oczywi`scie
op`o`znienia sieciowe. W niekorzystnych sytuacjach mo`xe to oczywi`scie
prowadzi`c do zauwa`xalnego pogorszenia dzia`lania bazy, typowo jednak
po`swiadczanie dokonywane jest przez DSA bliskie DUA, a nast`epne operacje
rozproszone oparte s`a na wzajemnym zaufaniu DSA (ta ewidentna luka w
bezpiecze`nstwie mo`xe by`c usuwana przy stosowaniu wy`xszych poziomom`ow
zabezpiecze`n). Przy okazji warto wspomnie`c, `xe istnieje mo`xliwo`s`c
dowi`azania
z podaniem nazwy, ale bez po`swiadczania. Takie dowi`azanie ma charakter
jedynie informacyjny. Serwer dokonuje jedynie bardzo pobie`xnej
weryfikacji, je`xeli dowi`azuj`acy si`e powinien wyst`epowa`c w bazie lokalnej
danego serwera, to sprawdzane jest istnienie takiego obiektu i w przypadku
stwierdzenia fa`lszu po`l`aczenie jest blokowane, nie sprawdza sie jednak
danych nielokalnych, aby nie przed`lu`xa`c operacji. Ten rodzaj dowi`azania nie
pozwala oczywi`scie na dokonywanie `xadnych modyfikacji bazy, ani na czytanie
zastrze`xonych danych.

\item[ad.\ 3] Zgodnie z przewidywaniami, dost`ep do danych lokalnych jest na
og`o`l szybszy, chocia`x w przypadku serwera krakowskiego, w pewnych okresach
dane nielokalne by`ly dost`epne znacznie szybciej. Musi to by`c zwi`azane z
obci`a`xeniem maszyny. Dost`ep do danych nielokalnych by`l jednak w sumie
bardzo szybki (`srednio przeszukanie lokalne trwa 2--3 sekund, nielokane o 1
do 2 sekund d`lu`xej).

\item[ad.\ 4] Jak wynika z za`l`aczonych wynik`ow test`ow, najd`lu`xsz`a operacj`a
jest dokonanie po\-cz`at\-kow\-ego dowi`azania do serwera (zw`laszcza autoryzowanego
na znaczn`a odleg`lo`s`c). Operacje przeszukania s`a stosunko sprawne. Nale`xy
przyj`a`c kryterium, `xe operacja przeszukania bazy nie powinna
przekracza`c 3~sekund. D`lu`xszy czas wskazuje na nadmierne obci`a`xenie
serwera, b`ad`z t`a sam`a baz`a X.500, b`ad`z innymi procesami. Najszybsza
(zgodnie z przewidywaniem) jest operacja czytania. Przy konstrukcji DUA
nale`xy zwraca`c uwag`e na to, aby prosi`c o przes`lanie jedynie tych atrybut`ow,
kt`ore nasze DUA jest w stanie obrabia`c, w szczeg`olno`sci nie ma sensu robi`c
transferu obrazu dla DUA tekstowego. Jednocze`snie prawid`lowo realizowane
buforowanie tego typu danych mo`xe bardzo znacznie przyspieszy`c
funkcjonowanie systemu.

\item[ad.\ 5] Stosunkowo szybki dost`ep do danych nielokalnych wydaje si`e
wskazywa`c na  celowo`s`c rozpraszania bazy. Jednocze`snie jednak rozpraszanie 
pojedynczych instytucji, w ramach kt`orych dokonywane jest przeszukiwanie,
wyra`znie os`labia funkcjonowanie systemu i nale`xy go unika`c. Wydaje si`e
zatem, `xe w`la`sciwym modelem jest rozproszone zarz`adzanie danymi skupionymi
na jednym serwerze. Zarz`adzanie takie polega na powierzeniu pieczy nad
wybranymi domenami okre`slonym zarz`adcom. Mog`a oni dokonywa`c modyfikacji
danych po autoryzowanym dowi`azaniu do bazy. Zarz`adzanie takie mo`xe by`c
dokonywane jedynie w czasie pracy serwera i nie mo`xe dotyczy`c modyfikacji
danych bezpo`srednio na dysku. 
\end{itemize}


\begin{thebibliography}{99}
\bibitem{X.500}Data Communication Networks: Directory, Recommendations X500-X.521,
CCITT, Fascile VIII.8 of Blue Book
\bibitem {Rose} Marshall T. Rose (1992) {\it The Little Black Book: Mail
Bounding with OSI Directory Services}
\bibitem {QUIPU} C.J. Robbins, S.E. Kille (1992) {\it The ISO Development Environment:
User's Manual, Volume 5: QUIPU}
\bibitem{G-W-1}M. G`orecka, T. Wolniewicz (1994) {\it Ocena efektywno`sci rozproszonej
bazy danych na podstawie X.500 Directory}, Raport NASK
\bibitem{G-W-2} M. G`orecka, T. Wolniewicz (1994) {\it Stosowanie znak`ow diakrytycznych
w systemach baz danych X.500}, Raport NASK
\bibitem{G-W-3} M. G`orecka, T. Wolniewicz (1995) {\it X.500 --- 
standard i us`lugi katalogowe}, Materia`ly konferencyjne, POLMAN '95

\end{thebibliography}

\end{document}
