Wyszukanie brakujacych ID

0

Krotko i na temat. Szukam optymalizacji pod katem redukcji zuzycia pamieci i przyblizonym utrzymaniu czasu procesu/zapytania. Przy prawie pelnej tabeli dla zakresu np. 501000000-500000000 pozera w granicach ~50MB (zalezy od konfiguracji serwera) jednak chcialbym to zredukowac, bo... tych procesow bedzie nie mniej niz 25 wiec... 1,25GB co jest dla mnie zbyt duza wartoscia. Zalozenia podstawowe. Na poczatku zliczamy ilosc rekordow dla zakresu. Jezeli mniej niz 50% to pobieramy aktualne i w petli uzupelniamy braki. Jezeli jest na odwrot to potrzebuje wszystkie brakujace ID do petli aby je uzupelnic. Ma to na celu redukcje pozartej pamieci. Prosze sie nie przejmowac syfem w metodzie some_operation() - wklejone na szybko. Odsylanie do Google... to nie rozwiazanie, bo... np. takie rozwiazania (http://stackoverflow.com/questions/12325132/mysql-get-missing-ids-from-table) trwaja za dlugo. Tworzenie tymczasowej tabeli dla miliona rekordow tez mija sie z celem jezeli przemnozy sie przez ilosc procesow (nie bede ich opozniac celowo). Zastanawialem sie nad procedura aby pobrac wszystkie i wylapac brakujace. Moze jest jakies zapytanie, ktore jest optymalne i wykona cel?

index.php

<?php
$config['mysql']['host'] = 'localhost';
$config['mysql']['database'] = 'test2';
$config['mysql']['login'] = 'root';
$config['mysql']['password'] = '';
// Jezeli nie masz ustawionego to... juz masz :D
set_time_limit(0);

$range = '501000000-500000000';

require './debug.class.php';
require './test.class.php';

$test = new test($config);
// $test -> add_records($range);
// $test -> create_random_holes();
$test -> some_operation($range);
?>

debug.class.php

<?php
class debug
{
 static private $units = array('B','kB','MB','GB');

 static public function get_memory_usage()
 {
  return debug::convert(memory_get_usage()).'/'.debug::convert(memory_get_usage(true));
 }

 static private function convert($size)
 {
  $unit = floor(log($size, 1024));

  return round($size / pow(1024, $unit), 2).' '.debug::$units[$unit];
 }
}
?>

test.class.php

<?php
class test
{
 private $db;

 public function test($config)
 {
  $this -> db = new mysqli($config['mysql']['host'], $config['mysql']['login'], $config['mysql']['password'], $config['mysql']['database']);

  if($this -> db -> connect_errno !== 0)
  {
   throw new Exception('Could not connect to database');
  }
  else
  {
   // $this -> db -> set_charset('utf8');
  }
 }

 public function add_records($range)
 {
  // PHP_EOL for CLI or <br> for browser
  echo debug::get_memory_usage().'<br>';
  $range = explode('-', $range);
  $range[0] = (int)$range[0];
  $range[1] = (int)$range[1];
  $stmt = $this -> db -> prepare('INSERT INTO players (account_id) VALUES (?)');
  $this -> db -> autocommit(false);

  while($range[0] >= $range[1])
  {
   // Fill the table
   $stmt -> bind_param('i', $range[0]);
   $stmt -> execute();
   --$range[0];
  }

  if($this -> db -> commit() === false)
  {
   $this -> db -> rollback();
  }

  $this -> db -> autocommit(true);
  echo debug::get_memory_usage().'<br>';
 }

 public function create_random_holes()
 {
  // May take a while
  $stmt = $this -> db -> prepare('DELETE FROM players ORDER BY RAND() LIMIT 10000');
  $stmt -> execute();
 }

 public function some_operation($range)
 {
  // Uwaga syf  
  echo debug::get_memory_usage().'<br>';
  $range = explode('-', $range);
  $range[0] = (int)$range[0];
  $range[1] = (int)$range[1];
  $stmt = $this -> db -> prepare('SELECT account_id FROM players WHERE account_id BETWEEN ? AND ? ORDER BY account_id DESC');
  $stmt -> bind_param('ii', $range[1], $range[0]);
  $stmt -> execute();
  $result = $stmt -> get_result();
  $stmt -> free_result();
  // $stmt -> close();
  // $stmt -> store_result();
  // $stmt -> bind_result($account_id);
  // $stmt -> fetch();
  
  while ($obj = $result->fetch_object())
  {
   // echo $obj -> account_id.'<br>';
  }
  
  echo debug::get_memory_usage().'<br>';
  // var_dump($result);
  exit;
  // $result = $stmt->get_result();
  // $cached = new CachingIterator($result, CachingIterator::FULL_CACHE);
  
  while($range[0] >= $range[1])
  {
   if($range[0] === $account_id)
   {
    $stmt -> fetch();
   }
   else
   {
    // Adding missing player
    // $this -> add_player($range[0]);
   }

   --$range[0];
  }

  echo debug::get_memory_usage().'<br>';
 }
 
 private function add_player($account_id)
 {
  $stmt1 = $this -> db -> prepare('INSERT INTO players (account_id) VALUES (?)');
  $stmt1 -> bind_param('i', $account_id);
  $stmt1 -> execute();  
  
  return $stmt -> affected_rows === 1;
 }
}
?>

Struktura tabeli

CREATE TABLE IF NOT EXISTS `players` (`account_id` bigint(1) NOT NULL) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin;
ALTER TABLE `players` ADD PRIMARY KEY (`account_id`);

PS
Widzialem kilka tematow na polskich forach programistycznych (w tym takze na tym) dotyczacych tego problemu jednak rozwiazania, ktore padly nie satysfakcjonuja mnie, bo to nie ta skala.

0

Pytanie jest, czy NA PEWNO chcesz odnaleźć wszystkie braki na raz? Po co ci to? Chyba wystarczy ci jeden - pierwszy. A w miarę optymalnie możesz to zrobić tak:

SELECT t1.id+1 FROM tabela t1 LEFT JOIN tabela t2 ON t1.id=t2.id+1 WHERE t2.id IS NULL
0

Ciezko mi sobie to wyobrazic. Przy zalozeniu minimum 25 procesow i ciupaniu minimum jednego rekordu na sekunde co daje minimum 25 zapytan na sekunde [w rzeczywistosci troche (wiecej?) mniej bo cos kolo 0,6]. Jedyne nad czym pomyslalem to pobierac sektorami/zakresami. Czyli po np. tysiac brakow. Wiesz docelowo baza bedzie zawierac cos kolo 150m rekordow wiec nie jestem pewien czy takie zapytania co chwile dadza rade. Wole miec gotowa liste i po prostu w petli dodawac. Zaraz przetestuje pod obciazeniem, zobaczymy jak to sie zachowa.

Chodzi o to aby takie zapytanie co sekunde nie spowalnialo znaczaco procesu.

Aha jeszcze myslalem nad jednym rozwiazaniem tj. spakowaniem tej listy tylko czy proces odczytu bedzie wystarczajaco szybki. Z tego co pamietam mozna by bylo zredukowac to z 50MB do mniej niz 10MB.

2

po co takie sztuczki? Z doświadczenia wiem, że szukanie dziur w UNIKALNYM ID i wstawianie rekordów w luki wiąże się z błędem na poziomie założeń projektu. Piszesz, że ma to robić ok 25 wątków jednocześnie. Następnie, że wolisz pobrać na raz tablicę wolnych ID. A jak to się ma do zapełniania tych dziur przez 25 wątków jednocześnie? Wg mnie najszybszą metodą będzie osobna tabela z wolnymi ID, które będą usuwane na bieżąco (także na bieżąco wstawiane przy zwolnieniu ID). Możesz to wszystko zrobić po stronie bazy używając triggerów, łącznie z pobraniem ID do wstawienia

0

Wiedzialem, ze ktos sie o to przygrzmoci :D Po prostu wiedzialem i dlatego sie zalozylem ze znajomym o flache :D Dzieki wygrales dla mnie zaklad. Moze jakbym robil w tym rok albo dwa i nie mial doswiadczenia to mozna byloby cos takiego zalozyc (blad w zalozeniach projektu) ale nie... troszke juz w tym siedze. Ciekawe co Ty na to Panie. Powiedzialem, ze bedzie nie mniej niz 25 procesow. W rzeczywistosci bedzie ich o wiele wiecej. Jestem w trakcie tworzenia "sporego" serwisu, ktory bedzie mial hm... nie mniej niz 4 uslugi, ktore mozna zaliczyc do osobnych (serwisow) ale baza (jako podstawa) musi byc.

Target ma 5 glownych regionow (zwanych dalej klastrami). Kazdy z nich zaczyna ID od okreslonej "stalej", ktora sobie tam wydumali programisci korpo tj. kolejno 0, 500000000, 1000000000, 2000000000, 3000000000. W sumie genialna sprawa szczegolnie, ze jeden klaster nigdy nie przekroczy limitu pomiedzy zakresem jednego i drugiego, bo za wolno sie rozrasta (za wolno buduje baza graczy i klanow), na ktorej gra bazuje. Pewnie marketing i za malo reklam w TV to powoduje, a moze... a moze to nie jest celem tematu.

Wyobraz sobie, ze nie tylko te procesy operuja na tej tabeli lecz takze inne, ktore takze dodaja gdy brakuje wiersza w tabeli. W zwiazku z tym tworza sie "extra" dziury. Te procesy dzialaly sobie skutecznie przez bodajze 21 dni lecz wymuszony zostal reboot i niestety nie przewidzialem zapisania aktualnego offsetu przy kazdym watku. Dane sa ciagniete przez API/nieoficjalne kanaly. Optymalnym parametrem dla requestu jest od 30 do 50 kont jednym zapytaniem. Przy wiekszej ilosci sa po prostu timeoutykody bledow bo API (czyt. ich serwer) nie wyrabia. Ponadto serwer limituje requesty dla API w granicach ~10/sekunda (czasami 20 czasami 25 - zalezy od obciazenia) dlatego lecimy przez nieoficjalne odkryte kanaly pozyskiwania informacji jak i uzywamy wiecej niz jednej maszyny aby przyspieszyc proces. Ponadto kazdy klaster jest polozony w innym miejscu. W zwiazku z tym wykupienie maszyn blisko serwerowni targetu jest kluczowe aby zmniejszyc opoznienia. No sory, nie bede walil wszystkich zapytan z Europy, szczegolnie, ze jeden klaster to rosyjski, a drugi azjatycki, a trzeci koreanski :D Podane wyzej stale sa takze auto_increment dlatego pewna metoda wiemy do ktorego miejsca ripowac dane.

Piszesz, że ma to robić ok 25 wątków jednocześnie. Następnie, że wolisz pobrać na raz tablicę wolnych ID. A jak to się ma do zapełniania tych dziur przez 25 wątków jednocześnie?

Jakbys uwaznie czytal Panie to bys wiedzial (lub tez mogl sie domyslic), ze robie to zakresami czyli np. jeden proces bierze 501000000-500000000, drugi 502000000-501000000 (-1) i tak dalej. Kazdy proces dziala niezaleznie i dobija dane do bazy. Jezeli wpadlbys na pomysl sugestii, ze to moze byc jeden proces z uzyciem watkow to niestety zmartwie Ciebie ale poza tym co tutaj napisalem jest jeszcze wiecej obliczen/operacji, ktorych nie bede zdradzal.

I nadal uwazasz, ze stworzenie osobnej tabeli z lukami to dobry pomysl przy targecie +150m? Tak? Pobieramy dla zakresu, dodajemy tam, usuwamy tu, etc.? Albo... Pobierzmy dla zakresu, jak proces walnie w kalendarz to update dla "tymczasowej" tabeli :D Nie zamierzam marnowac miejsca na maszynie na taka tabele.

4

-1. pisząc w taki sposób ośmieszasz tylko siebie, nie mnie.
0. było już wielu takich, co to bazy programowali jeszcze na kartach perforowanych a błędy robili jak dzieci z przedszkola

  1. czy masz możliwość ingerencji w bazę czy jedynie pobierać dane?
  2. czy brak dziur to wymóg konieczny czy może być tak, że w ramach "klastra" dziury mogą być?
  3. jeśli 2 jest true to może po prostu zrobić tak http://www.percona.com/blog/2008/04/02/stored-function-to-generate-sequences/ czyli osobna "sekwencja" dla każdego klastra

Widzisz tyle "mondrych" ludzi nad tym systemem siedzi a ty szukasz pomocy na forum wśród idiotów...

0

Ad. 1
Gdybym mial mozliwosc ingerencji w baze danych (fizyczny dostep) to bym sie nie bawil w sciaganie danych via API/nieoficjalne kanaly komunikacji. To chyba logiczne i wynika z poprzednich postow. W koncu mozna po prostu zrobic replike na zywca.

Ad. 2
Brak dziur to wymog konieczny, bo w rzeczywistosci one nie wystepuja (patrz wyzej, bo byla mowa auto_increment) czyli gdy usluga na dany region zostala uruchomiona to lecialo od podanych wyzej stalych. Wykonujac okreslone nazwijmy to zapytanie wiem, ze ostatni dodany np. account_id wynosi tyle i tyle. Gdy baza zostanie skompletowana dla danego klastra to dane beda "dobijane" cyklicznie co np. tydzien. Przypominam, ze rekordy powyzej "zadanego punktu" takze moga sie pojawic, ze wzgledu na dzialajace inne procesy. Czyli np. w naszej bazie jest ostatni zadany rekord o ID 525666666 i baze mamy w pelni uzupelniana, odpalamy zapytanie (zewnetrzne do serwera) sprawdzajace aktualnie ostatni account_id to wybieramy "gapy" miedzy tym zakresem (pobrany ID i ostatni zadany rekord) i uzupelniamy braki (minus te, ktore powstaly w wyniku osobnych procesow) aby baza byla aktualna.

Aby zobrazowac sytuacje na szybko posluze sie grafika (ktora, mocno nie odbiega od sytuacji biezacej) z natrafionego bloga. Zielone linie pokazuja, w ktorych miejscach sa "gapy". Oczywiscie ma to odniesienie do danego zakresu czyli np. 501000000-500000000.
user image

Moze Ty sobie wyobrazasz dziury w bazie danych przy generowaniu statystyk dla calego klastra ja jednak nie - stad taki a nie inny wymog wobec kompletnego uzupelnienia. Dodatkowo jezeli ktos wysle request, ze chce zobaczyc dane tego i tego gracza, a nie ma go w bazie danych to trzeba dodac do kolejki aby worker sciagna dane. Oczywiscie to z automatu generuje problem, bo jezeli za duzo osob na raz rzuci sie na ID, ktorego nie ma to bedzie to za dlugo zajmowac (przypominam o limitach na requesty per IP). Dlatego wlasnie... baze trzeba uzupelniac praktycznie w czasie rzeczywistym o ile pozwala na to sytuacja. Oczywiscie wyzej stwierdzony "tydzien" jest tylko przykladem na potrzeby wytlumaczenia.

Wracajac do watku statystyk. Jezeli wystepowalyby dziury to w przypadku generowania statystyk dla calego klastra wartosci zostalyby zmanipulowane i latwo mozna byloby zostac osadzonym o klamstwo. Chyba nie na tym rzecz polega? A budowanie w tym wypadku statystyk na bazie niekompletnych danych mija sie z celem.

Ad. 3
W zwiazku z powyzszym i innymi powodami podany przez Ciebie przyklad odpada. Zdarzylem na niego wpasc duzo wczesniej przed pisaniem postow, przegladajac kilkaset stron/blogow/serwisow ala stackoverflow/vortali tematycznych.

Reszty rzeczy nie komentuje, bo szkoda mi klawiatury.

3

ja dalej nie kumam co kto gdzie i po co. W pierwszym poście dałeś jakieś SQLe, potem pisałeś, że dane wyciągane są różnymi kanałami (API, nieoficjalne), teraz, że do bazy nie masz w ogóle dostępu. Jak to w końcu jest. Co z tą bazą, po co te ID? Ja wiem jak wyglądają dziury w numeracji ale wiem też, że ID jest po to aby rekord identyfikować a nie po to aby ładnie wyglądać. Piszesz

CapaciousCore napisał(a):

Wracajac do watku statystyk. Jezeli wystepowalyby dziury to w przypadku generowania statystyk dla calego klastra wartosci zostalyby zmanipulowane i latwo mozna byloby zostac osadzonym o klamstwo. Chyba nie na tym rzecz polega? A budowanie w tym wypadku statystyk na bazie niekompletnych danych mija sie z celem.

A ja nie potrafię zrozumieć jaki wpływ na statystyki, poprawność, prawdziwość danych ma fakt, że w numeracji są dziury.

Piszesz dużo, udowadniając co to nie jest za projekt i jakich rozmiarów on nie ma, traktując innych z góry i uważając ich za idiotów zamiast napisać raz, krótko i na temat.

Jeśli musisz pobrać ID "dziur" to jedyne co możesz zrobić to pobrać id wszystkich istniejących i na tej podstawie znaleźć "dziury". Niestety MySQL jest na tyle ubogi, że nie potrafi wygenerować sekwencji liczb od X do Y bez użycia dodatkowych tabel albo UNION.

Jak cię to po oczach nie razi to możesz zapytać o puste ID w ten sposób

SELECT x.id FROM
  (select (th*1000+h*100+t*10+u+1) id from
    (select 0 th union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) A,
    (select 0 h union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) B,
    (select 0 t union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) C,
    (select 0 u union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) D
  order by x) x
left join twoaja_tabela t on t.id = x.id
where
  t.id is null

To akurat sprawdza pierwsze 10000 rekordów ale myślę, że ideę załapiesz

2

@abrakadaber moja szklana kula mówi, że kolega bawi się w (nielegalne tak btw) crawlowanie informacji z jakiejś onlinowej gry. Stąd też ma swoją bazę do której wrzuca crawlowane dane. Problem w tym że dane mają dziury, tzn niektóre ID nie są jeszcze wykorzystane, ale nie masz tam ładnej kolejności tylko z pewnych względów dziury w numeracji.
Kolega więc iteruje sobie po wszystkich ID i ciągnie dane. Niemniej w efekcie u siebie w bazie też ma dziury, dla tych ID które w grze były jeszcze nieprzypisane. Chciałby teraz niewielkim kosztem "dociągać" te brakujące informacje w miarę jak się będą pojawiać, ale do tego potrzeba mu niby efektywnej metody wybrania brakujących ID.

Co mnie generalnie dziwi, to po co właściwie tyle zachodu o "szybkie" wybranie pustych ID? Przecież crawlowanie będzie wymagało komunikacji sieciowej i w efekcie będzie nieporównywalnie wolniejsze od pobierania listy brakujących ID. Zresztą w ogóle nie rozumiem za bardzo jaki sens bawić się tu w angażowanie bazy danych. Wystarczy przecież raz wyciągnąć i zapisać w jakiejś kolejce z której potem wątki będą ściągać i crawlować. Jak danych nadal nie ma to ID leci na koniec kolejki i tyle.

0

Dobra po kolei. @Shalom niestety rozczaruje Ciebie gdyz wszystko jest zgodne z EULA wiec o zadnym nielegalnym bawieniu sie w crawlowanie nie ma mowy. Gdyby tak nie bylo to kilka serwisow (notujacych minimum 1m uu dziennie) o podobnych funkcjonalnosciach nie istnialyby. Zgadza sie, mamy swoja baze danych, ktora systematycznie uzupelniamy. Dlatego wlasnie mowilem, o procesie, ktory ripowal 21 dni i niestety zaliczyl nieoczekiwanego "zgona" za sprawa reboota. Stad caly ten problem, ktory jest opisany w tym watku. Dokladnie rzecz ujmujac jednym zapytaniem via "kanal" (API/nieoficjalne) pobieram 30 segmentow danych (ktore musze przeparsowac) na temat kont.

Glownymi celemi sa po pierwsze obnizenie zurzycia pamieci, a po drugie wyszukanie "gapow", ktore sluza za liste, w trakcie budowy requestu a nastepnie dodanie tego do bazy danych.

A ja nie potrafię zrozumieć jaki wpływ na statystyki, poprawność, prawdziwość danych ma fakt, że w numeracji są dziury.

Ano ma taki wplyw, ze wraz z requestem i informacja na temat konta dostaje mase informacji, ktore obrabiam i ktore sa potrzebne ;) Jezeli robisz hm np. statystyki dla klastra i robisz wykres, w ktorym przedstawiasz np. sredni czas aktywnosci to mowimy o calosci, a nie o danych czastkowych. Chyba mnie rozumiesz i nie trzeba tego watku ciagnac. Statystyka jest tylko jednym z przykladow dlaczego potrzebne mi sa kompletne dane.

No wlasnie to jest zabawne w MySQL, ze nie ma takiej mozliwosci, z reszta nie nie tylko tej ale... to temat jak rzeka.

Tak jak powiedzialem na poczatku dla mnie liczy sie efekt koncowy o ktorym mowa w drugim akapicie.

[edit]
Przetestowalem rozwiazanie @abrakadaber i jest dla mnie w miare zadawalajace. Podziekowal. Temat uwazam, za rozwiazany.

1 użytkowników online, w tym zalogowanych: 0, gości: 1