ACL nad velkým množstvím dat v DB

Hryzo

ACL nad velkým množstvím dat v DB
« kdy: 09. 11. 2017, 18:13:28 »
Mam klasicky ACL pattern [user / group, document, permission] a potrebujem priamo v DB pomocou  SELECT zobrazit len tie dokumenty, na ktore ma user  READ opravnenie.

select * from document
left join ACL on  (ACL.document = document.id)
where (user = {0} and permission = {1}

Problemom je, ze aj tento JOIN je vcelku pomaly a prave kvoli 1:N vztahu medzi dokumentom a ACL nemozem mat permission na documente (a teda mat flat strukturu, co by zase nieco urychlilo)
Ako vo vseobecnosti riesit problem, kedy mi nestaci vyhodnotit ACL on demand pri pristupe k dokumentu (to je velmi rychle), ale ked potrebujem vratit z 60 miliona dokumentov tie, na ktore mam pravo READ - a to moze byt kludne len 10.

Uviedol som jednoduchy priklad, moje ACL moze mat bud userID alebo rovno groupID, ci sa to este mierne komplikuje, pretoze je nutne riesit aj join na grupy podla a matchnut, ci sa userID nachadza v joine na groupu, a nakoniec kvoli kartezskemu sucinu spravit DISTINC podla PK dokumentu. Pre urychlenie vypoctu zoznamu moznych ACL som este pouzil funkciu, ktora vytvara TEMP tabulku a cachovala vysledky, ale nebolo to o moc rychlejsie.
« Poslední změna: 10. 11. 2017, 10:15:10 od Petr Krčmář »


Hryzo

Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #1 kdy: 09. 11. 2017, 18:15:48 »
Este doplnim, ze sa jedna o MS SQL a uvazoval som aj o indexe (elasticsearch), ale potrebujem mat ACID, a aj keby som  kvoli rychlosti vyhladavania preklapal a vytvoril  flat strukturu v indexe z DOCUMENT -> ACL, nakoniec by  som to musel stale updatovat pri kazdej zmene ACL prejst vsetky dokumenty, ktorych sa zmena tyka a spravit znovu flat index.

Toto mi pride az prilis.

dustin

Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #2 kdy: 09. 11. 2017, 19:11:07 »
Máme podobnou situaci (objekty uložené v relační DB s hlídáním práv přes ACL). Všechny autorizační entity (typicky user, group) mají jedinečné ID (authEntityID), generované databází a uložené v pomocných mapovacích tabulkách. V našem případě (původně ACL práva na souborech/adresářích) se kombinace read práv na objektech (adresáře, soubory, pomocné objetky) velice často opakují. Opakují se proto, že jejich vznik je defacto ruční práce změny práv, tudíž tak rychle nepřibývají.

Proto ukládáme rovnou kombinaci auth entit do tabulky read_perms s klíčem id_read_perm. Rozpad kombinací read_perm je v mapovací tabulce read_perm_members(id_read_perm, id_auth_entity). U každého objektu je pak uloženo id příslušné  kombinace entit id_read_perm.

Při hledání se najde seznam id_read_perm kombinací, ve kterých se vyskytuje uživatel (má user ID a několik groupIDs, namapované na jednu množinu jedinečných authEntityIDs) a joinuje se to s tabulkou objects. Pro cca 3 mil. objektů a 40 tis. uživatelů+skupin máme aktuálně 20 tis. kombinací read_perms (tabulka read_perms) obsahujících celkem 25tis. různých authorizačních entit (tabulka read_perm_members). Máme jich tak málo, protože hodně objektů má read pro everyone, které je uložené jak flag přímo u objektu - pro read everyone není potřeba vytvářet kombinaci autorizačních entit.

Pro nepřihlášeného uživatele (everyone) se hledá jednokolově s omezením na flag objects.is_public, pro přihlášeného se do databázové temporary tabulky vygenerované hledáním public připojují výsledky hledání s joinem přes read_perms. Query generujeme záměrně aplikačně, šlo by ale využít i stored procedure.

Tomas2

  • ****
  • 310
    • Zobrazit profil
    • E-mail
Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #3 kdy: 09. 11. 2017, 19:21:37 »
a subselect to nevyřeší?

select * from document
where document.id in (select distinct ACL.document from ACL where user = {} and permission = {1})

Šlo by poté dokonce v subselectu stránkovat, abys nemusel pokaždé tahat desítky tisíc dokumentů.

Hryzo

Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #4 kdy: 09. 11. 2017, 19:57:50 »
a subselect to nevyřeší?

select * from document
where document.id in (select distinct ACL.document from ACL where user = {} and permission = {1})

Šlo by poté dokonce v subselectu stránkovat, abys nemusel pokaždé tahat desítky tisíc dokumentů.

Vyskusam, problemom je, ze pocet ACL s tym istym dokumentom moze byt desiatky tisic (userovia z grupy), co distinct vyriesi, pozrem exekucne plany zajtra v praci a popripade sa ozvem a poskytnem aj screenshot.


Hryzo

Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #5 kdy: 09. 11. 2017, 20:13:54 »
Máme podobnou situaci (objekty uložené v relační DB s hlídáním práv přes ACL). Všechny autorizační entity (typicky user, group) mají jedinečné ID (authEntityID), generované databází a uložené v pomocných mapovacích tabulkách. V našem případě (původně ACL práva na souborech/adresářích) se kombinace read práv na objektech (adresáře, soubory, pomocné objetky) velice často opakují. Opakují se proto, že jejich vznik je defacto ruční práce změny práv, tudíž tak rychle nepřibývají.

Proto ukládáme rovnou kombinaci auth entit do tabulky read_perms s klíčem id_read_perm. Rozpad kombinací read_perm je v mapovací tabulce read_perm_members(id_read_perm, id_auth_entity). U každého objektu je pak uloženo id příslušné  kombinace entit id_read_perm.

Podobne mam implementovany aktualny stav:

Kód: [Vybrat]
OBJEKT (fk_acl_id) --1------1--> ACL (acl_id, name) --1------N--> ACL item (acl_id, user, group, permission)
Vy pouzivate reusovanie, ja ratam s najhorsim scenarom, ze aj rovnake "pristupy" maju nove ACL so zoznamom ACL items aj za cenu "duplikacie" rovnakych kombinacii user,group,permission (aby zmena jedneho nezmenila ostatne)

K performance problemom sa dostavam uz ked existuje viac ako 100 000 ACL namapovanych na dokumenty 1:1 a kazdy ACL ma 4 permission (C,R,U,D).

Preto som sa snazil optimalizovat a odstranil som vazobnu tabulku ACL:

Kód: [Vybrat]
OBJEKT (obj_id PK) --1------*--> ACL item (obj_id, user, group, permission)
Citace
Při hledání se najde seznam id_read_perm kombinací, ve kterých se vyskytuje uživatel (má user ID a několik groupIDs, namapované na jednu množinu jedinečných authEntityIDs) a joinuje se to s tabulkou objects. Pro cca 3 mil. objektů a 40 tis. uživatelů+skupin máme aktuálně 20 tis. kombinací read_perms (tabulka read_perms) obsahujících celkem 25tis. různých authorizačních entit (tabulka read_perm_members). Máme jich tak málo, protože hodně objektů má read pro everyone, které je uložené jak flag přímo u objektu - pro read everyone není potřeba vytvářet kombinaci autorizačních entit.

Vyskusam, flag read_everyone je celkom dobry tip.

Citace
Pro nepřihlášeného uživatele (everyone) se hledá jednokolově s omezením na flag objects.is_public, pro přihlášeného se do databázové temporary tabulky vygenerované hledáním public připojují výsledky hledání s joinem přes read_perms. Query generujeme záměrně aplikačně, šlo by ale využít i stored procedure.


Kazdopadne vyskusam vsetky tipy, ktore ste spomenul vratane "reusovania" rovnakych permission, to by mohlo pomoct.


Hryzo

Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #6 kdy: 09. 11. 2017, 20:18:31 »
A co napr. noSQL databazy - neriesil niekto nieco podobne napr. nad MongoDB ?

dustin

Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #7 kdy: 09. 11. 2017, 22:49:42 »
V mongodb máme přístupové statistiky webů, nějakých 100 mil. dokumentů. Když se tomu nastaví správně indexy, jede výborně. Naštěstí umí indexy buildovat za plného provozu na pozadí, výroba indexu jede ve více vláknech. Pořád mě překvapuje úspornost uložení (engine WiredTiger). Rovněž mi vyhovuje, jak snadné je zprovoznit replikaci (třeba kvůli zálohování a/nebo pro dalsí stroje HA clusteru), funguje zcela spolehlivě.

Pokud by ti stačila ACID na úrovni uložení dokumentu, pak bys mohl vyzkoušet. Řekl bych, že v poli (seznam read entit ids u dokumentu), na kterém má index, vyhledává docela svižně. Ale není to na vyhledávání joinem mezi dokumenty, spíš jen dle hodnot atributů (což je přesně naše využití pro prohledávání logů). Možnost libovolně rozšiřovat dokumenty novými atributy (a ke stávajícím dokumentům je zpětně přidat) je samozřejmě obrovská výhoda.

Tomas2

  • ****
  • 310
    • Zobrazit profil
    • E-mail
Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #8 kdy: 09. 11. 2017, 23:02:09 »
nemyslím si, že je vhodné řešení doporučovat použít jinou databázi, tvůj původní návrh na denormalizovanou (či vazební) tabulku byl mnohem vhodnější.

Mongodb není všespásné a má dost různých problémů, asi bych ho nedával do ruky lidem, kteří ho moc neznají, to si pak takhle uloží nové permission, v zápěti si je chtějí načíst a ouha, oni nikde :). Holt asynchronní indexování má své nevýhody, stejně tak, že třeba není možné ho distribuovat na více serverů.

U 100M dokumentů je skoro jedno co se za databázi použije, všechny s nějakou formou indexů to zvládají.

dustin

Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #9 kdy: 09. 11. 2017, 23:36:19 »
Ať hledám, kde hledám, nikde jsem nenašel nic o asynchronním přidávání dokumentů do již existujících indexů. Mohu poprosit nějaký odkaz? Našel jsem jenom nějakou studii asynchronní indexace, kde to právě porovnávají s neupravenou mongodb. Díky moc.

Tomas2

  • ****
  • 310
    • Zobrazit profil
    • E-mail
Re:ACL nad velkym mnozstvom dat v DB
« Odpověď #10 kdy: 10. 11. 2017, 08:49:32 »
myšleno to bylo tak, že přidání nového dokumentu či úprava existujícího a vygenerování indexu není atomická operace jako u relačních databází. Pošleš dokument, dostane ho storage engine (whitetiger třeba), ten ho uloží a catalog si zjistí, jestli je dopad na index, ten poté nechá ve vlastním threadu dopočítat a invalidovat cache, ale to už RPC request nečeká a clientovi pošle info, že dokument je vložený. Pokud chviličku poté chceš dokument vyhledat, ještě není v indexu, trvá to pár ms (u nezatížené db) až klidně minuty (u hodně zatížené), nedá se to ale skoro vůbec nebugovat, mongo-tools na tohle je slabé.

Nevím, jestli jsou nějaké články, vychází to ze zdrojového kódu, mrkni na github, jak se v catalogu řeší thready a posílají data do storage enginu. Klidně napiš, můžeme se o tom pobavit více. Nechci mongo pomlouvat, ale technologie chce používat tak, jak jsou navržené. Mongo nepoužívá žádný wal, nemá updaty uložené v btree struktuře jako leveldb, díky tomu má neskutečný paralelismus při ukládání, ale hledání vložených dokumentů je hodně lazy, což zrovna u acl vidím jako kritické.