Intelligente suggesties, deel 4: Aantallen, caching en Protocol Buffers nl

Door creator1988 op donderdag 30 december 2010 15:57 - Reacties (2)
Categorie: Algoritmes, Views: 3.322

Dit is deel 4 in een serie over de techniek uit een 'intelligente' zoekbox.We kunnen hierarchisch zoeken, spel- en typfouten verhelpen en zelfs vrij goed gokken wat een gebruiker bedoelt als we de zoekterm niet helemaal begrijpen; waardoor alleen nog de grijze getallen met aantallen openstaan.

Aantallen
Op funda worden verschillende soorten aanbod gefaciliteerd. Op funda.nl zijn dit er 5: koop, huur, recreatie, nieuwbouw en europe; en op fundainbusiness.nl zijn dit er zelfs acht! Omdat deze aantallen redelijk vaak veranderen willen we dit waarschijnlijk minder lang cachen dan alle gebieden en de trees. Daarom willen we de aantallen in een los object opslaan.

Allereerst heb ik in de database een view gebakken die de data gegroepeerd ophaalt. Hierin staat bijvoorbeeld:

code:
1
2
Id      | Type  | Straat    | Buurt         | Plaats    | Gemeente  | etc.  | Aantal
1       | koop  | Griftland | Ermelo-West   | Ermelo    | Ermelo    | ...   | 2


Ja, dit zijn flink wat records (max. het aantal straten in Nederland * (8 + 5)), maar in de praktijk is dit aantal records over de lijn trekken secondenwerk.

Model
In het model willen we geen referentie naar het GebiedId hebben, omdat deze in een andere cachegroep kan leven:

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
public class AantallenWrapper
    {
        private static List<ObjectAantalType> _legeObjectAantallen = Enum.GetValues(typeof (ObjectAantalType)).Cast<ObjectAantalType>().ToList();
        public Dictionary<ObjectAantalType, int> ObjectAantallen { get; set; }

        public AantallenWrapper()
        {
            // voeg alle 'objectaantaltypes' toe, met initiele waarde '0'
            ObjectAantallen = _legeObjectAantallen.ToDictionary(t => t, t => 0);
        }
    }
    
    // ObjectAantalType is een enumeration met daarin 'Koop', 'Huur', etc.


We cachen deze in een:

C#:
1
public Dictionary<int, AantallenWrapper> IxGebiedAantallen { get; set; }


En vullen hem door door alle records in de tabel heen te lopen en de aantallen stuk voor stuk toe te voegen. We kunnen nu snel het aantal objecten opvragen voor gebied 1234 voor 'koop' via:

C#:
1
var cnt = cache.IxGebiedAantallen[1234].ObjectAantallen[ObjectAantalType.Koop];



Caching dan?
De zoekbox die we maken gebruikt zo 200 MB aan geheugen, inclusief aantallen. Niet iets dat je voor elke website op je server in geheugen wil houden (zeker niet op een 32-bits machine). Daarom cachen we de data in ASP.NET cache, voordeel hierover ten opzichte van memcached is dat het benaderen van data in de ASP.NET cache bijna net zo snel is als het object opvragen vanuit een static. Bij memcached zou elke keer de volledige tree naar de machine moeten worden getrokken.

Daarnaast is het ook mogelijk om een cachegroep in een ander AppDomain te hosten dan de website zelf. Wanneer elke website dat AppDomain gebruikt om de data op te halen kunnen we de gecachete data delen over verschillende websites. Scheelt flink wat memory, daar we zowel funda, als funda in business, als onze backend van deze data gebruik willen laten maken!

Hoelang cachen?
We maken gebruik van Enyim als client-side component voor caching. Deze kan op basis van config bepaalde cachegroepen in memcached en ASP.NET draaien. Bovendien ondersteunt deze ook het na een bepaalde tijd laten expiren van je items in cache. Voor zaken die lang in cache moeten blijven gebruiken we typisch 4 uur. Na deze vier uur zijn dus al onze gebruikers de klos! Ze moeten dan minuut of twee wachten tot alle trees weer zijn opgebouwd. Daarom gebruik ik binnen mijn gecachte object een 'LastUpdated' veld: wanneer de 'LastUpdated' 3:50 uur geleden is starten we een async thread die alvast de data opnieuw gaat ophalen. Hierdoor hebben gebruikers geen last van een expirerende cache!

Elke vier uur; verandert die data dan wel echt?
Ja en nee. De aantallen willen we wel graag elke 4 uur opnieuw ophalen, maar de geografische data verandert hoogstens elke paar maanden (wanneer we nieuwe data aangeleverd krijgen). Zonde dus dat we die BK-trees elke keer opnieuw moeten opbouwen! Vandaar dat we een extra laag caching gebruiken: het filesystem! Normaal gesproken heel eenvoudig: schrijf de cache weg door middel van Binary Serialization naar schijf, en als de cache expiret lees je de file weer uit. Bij een nieuwe update verwijder je gewoon de file, en na een tijdje genereert het systeem zelf een nieuwe file op basis van de nieuwste data. Alleen jammer dat er zo'n gigantische overhead in CPU, memory en HDD space is bij deze vorm van serialisatie!

Tijd voor...
Protocol Buffers! Een gestructureerd bestandsformaat van Google; juist gemaakt voor het opslaan en verzenden van grote bomen aan data. Er is ook een goede .NET wrapper gemaakt door Marc Gravell, die werkt door attributes te gebruiken.

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    [ProtoContract]
    public class GeoGebied
    {
        public GeoGebied()
        {
        }

        [ProtoMember(1)]
        public Niveau Niveau { get; set; }
        [ProtoMember(2)]
        public string Naam { get; set; }
        [ProtoMember(3)]
        public string[] Keys { get; set; }
        [ProtoMember(4)]
        public int Id { get; set; }
        [ProtoMember(5)]
        public int Parent { get; set; }
    }
    
    // en dit is de magic!
    using(var fs = File.Create(@"C:\ergensopschijf.jan"))   
    {
        Serializer.Serialize(fs, obj);
    }


In ons geval scheelde dit 60% aan HDD ruimte (op de gehele cache), was dit met serializen ruwweg 2 keer zo snel, en memory Infinite times omdat .NET de tree niet terug kon serializen zonder OutOfMemory te raken. Awesomeness (om met E.B. te spreken)!

Lijsten serializen

C#:
1
2
[ProtoMember(1)]
public List<GeoGebied> EenLijst { get;set;}


Bij het serializen van bovenstaande code wordt élk item in die lijst ook geserialized. Wanneer je vijf lijsten hebt met steeds dezelfde objecten scheelt dat veel ruimte op HDD en (na deserializen) veel memory! Daarom wilde ik alleen de ID's van de gebieden opslaan. Die kan ik dan runtime weer terugzoeken. Dit is niet triviaal, maar met een kleine hack vrij snel te fixen:


C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// dit is de definitie van de BkTreeNode uit de vorige post

    [ProtoContract]
    public class BkTreeNode<T>
        where T : class, IZoekboxItem
    {
        [ProtoMember(1)]
        public string Key { get; set; }
        
        [ProtoMember(2)]
        public Dictionary<int, BkTreeNode<T>> Nodes { get; set; }

        [ProtoMember(4)]
        // bij de eerste aanroep moet deze NULL teruggeven anders lukt deserialisatie niet!
        internal List<int> ProtoItems
        {
            get { return Items.Count == 0 ? null : Items.Select(i => i.Id).ToList(); }
            set { _protoList = value; }
        }
        private List<int> _protoList;

        private List<IZoekboxItem> _items;
        private List<IZoekboxItem> Items
        {
            get
            {
                if (_items.Count == 0 && _protoList != null)
                {
                    // hier terugmappen. Je eigen implementatie zal er anders uitzien
                    _items = _protoList
                        .Select(i => 
                            ZoekboxController.LongCache.IxGebiedId.ContainsKey(i) 
                            ? (IZoekboxItem)ZoekboxController.LongCache.IxGebiedId[i].First()
                            : null)
                        .Where(i=> i != null)
                        .ToList();
                    _protoList = null;
                }

                return _items;
            }
            set
            {
                _items = value;
            }
        }

        /// <summary>
        /// Don't use, needed for serialization
        /// </summary>
        public BkTreeNode()
        {
            Nodes = new Dictionary<int, BkTreeNode<T>>();
            ProtoItems = new List<int>();
            Items = new List<IZoekboxItem>();
        }

        public BkTreeNode(string s, T item)
        {
            /* default ctor */
        }

        public void Add(string s, T item)
        {
            /* ... */
        }

        public List<T> Query(string searchTerm, int maxDistance, ref int hits)
        {
            /* ... */
        }
    }



Werking is dus hetzelfde gebleven, maar tijdens (de)serializen wordt alleen het ID opgeslagen :) .

Morgen
Oud-en-nieuw. Serie is afgelopen. In het volgende jaar weer met goede moed helemaal los op een nieuw project! Als ik een publiek beschikbare demo heb zal ik de link posten.

Volgende: 2010: Nu eens échte cijfers over browsers en besturingssystemen 01-'11 2010: Nu eens échte cijfers over browsers en besturingssystemen
Volgende: Intelligente suggesties, deel 3: Uitspraak en hierarchie 12-'10 Intelligente suggesties, deel 3: Uitspraak en hierarchie

Reacties


Door Tweakers user ACM, donderdag 30 december 2010 16:26

Ik begrijp je cachingverhaal eigenlijk niet zo goed, althans, vooral de nu gemaakte keuzes niet. Dat je je tellertjes en BK-tree (los?) in een gedeeld geheugen plaatst is uiteraard logisch.

Maar waarom zou die BK-tree naar disk opgeslagen moeten worden? Dat opbouwen doe je toch niet zo vaak? Ik mag toch hopen dat je die BK-tree in (gedeeld) ram-geheugen houdt, of niet? En dan blijft het opstarten over, daarvan boeit het toch niet dat het wat langer duurt?

Om onze eigen productomgeving er maar bij te pakken; het is compleet onafhankelijk van de disk. Zodra het gestart wordt wordt alle productdata ingelezen en in diverse structuren in het ram-geheugen opgeslagen (kost zo'n 40 seconden) en vanaf dan wordt de boel adhv berichten op een publish/subscribe messaging systeem (een jms topic) on-demand bijgewerkt. Voor de zekerheid gebeurt het opbouwen ook compleet opnieuw elke paar uur (afhankelijk van de precieze dataset tussen de 6 en de 24 bij mij), maar aangezien dat herladen allemaal op de achtergrond gebeurt merkt niemand dat.
Zelfs als de data minder vaak zou veranderen en ik elk uur de applicatie zou herstarten zou ik niet gauw de boel naar disk proberen te schrijven om zo de opstarttijd te halveren.

Daarbij moet wel gezegd worden dat ik hier het voordeel heb dat het losse omgevingen zijn, waardoor de webservers uit kunnen wijken naar een niet-lokale versie als die even niet (snel genoeg) reageert :)

[Reactie gewijzigd op donderdag 30 december 2010 16:28]


Door Tweakers user creator1988, maandag 3 januari 2011 09:07

ACM schreef op donderdag 30 december 2010 @ 16:26:
Maar waarom zou die BK-tree naar disk opgeslagen moeten worden? Dat opbouwen doe je toch niet zo vaak? Ik mag toch hopen dat je die BK-tree in (gedeeld) ram-geheugen houdt, of niet? En dan blijft het opstarten over, daarvan boeit het toch niet dat het wat langer duurt?
Dat boeit in dit geval wel; opnieuw opbouwen kost me zo'n drie minuten; en van disk laden zo'n 15 seconden. Na elke release is er een AppPool reset en dus duurt het opnieuw in de loadbalancer brengen van de server 3 minuten langer. Bovendien trekt het opbouwen van de cache een server makkelijk voor 2 cores vol; ook niet iets wat je zo vaak wil hebben op productie.
Om onze eigen productomgeving er maar bij te pakken; het is compleet onafhankelijk van de disk. Zodra het gestart wordt wordt alle productdata ingelezen en in diverse structuren in het ram-geheugen opgeslagen (kost zo'n 40 seconden) en vanaf dan wordt de boel adhv berichten op een publish/subscribe messaging systeem (een jms topic) on-demand bijgewerkt. Voor de zekerheid gebeurt het opbouwen ook compleet opnieuw elke paar uur (afhankelijk van de precieze dataset tussen de 6 en de 24 bij mij), maar aangezien dat herladen allemaal op de achtergrond gebeurt merkt niemand dat.
Zelfs als de data minder vaak zou veranderen en ik elk uur de applicatie zou herstarten zou ik niet gauw de boel naar disk proberen te schrijven om zo de opstarttijd te halveren.

Daarbij moet wel gezegd worden dat ik hier het voordeel heb dat het losse omgevingen zijn, waardoor de webservers uit kunnen wijken naar een niet-lokale versie als die even niet (snel genoeg) reageert :)
Dit is voor ons een nieuwe situatie: normale data is altijd snel genoeg om op te bouwen wanneer de gebruiker dit vraagt en wordt daarna opgeslagen in memcached of ASP.NET Cache. Voor grotere sets die we willen aggregeren etc. verwerken we dit via een ESB naar een gewone database. De data uit deze database wordt vervolgens opgeslagen in memcached wanneer iemand erom vraagt. Nooit de gehele set maar altijd het resultaat van de query. In principe hetzelfde model als jullie gebruiken alleen met MSSQL als persistant datastore ertussen. De dataset die we nu hebben is alleen niet efficiënt genoeg op te slaan in een relationele database, dus vandaar deze tussenweg. Zie het filesystem dus eigenlijk als een vervanging van onze database. We zouden hem daar evt. als blob in kunnen opslaan, dan is de werking helemaal gelijk.

Reageren is niet meer mogelijk